Fast Elimination Method for Pruning in POMDPs

Date

2016-09-30

Author

Ozgen, Selim
Demirekler, Mübeccel

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

159
views

0
downloads

This paper aims to speed up the pruning procedure that is encountered in the exact value iteration in POMDPs. The value function in POMDPs can be represented by a finite set of vectors over the state space. In each step of the exact value iteration algorithm, the number of possible vectors increases linearly with the cardinality of the action set and exponentially with the cardinality of the observation set. This set of vectors should be pruned to a minimal subset retaining the same value function over the state space. Therefore, pruning procedure in general is the bottleneck of finding the optimal policy for POMDPs. This paper analyses two different linear programming methods, the classical Lark's algorithm and the recently proposed Skyline algorithm for detecting these useless vectors. We claim that using the information about the support region of the vectors that have already been processed, both algorithms can be drastically improved. We present comparative experiments on both randomly generated problems and POMDP benchmarks.

Subject Keywords

Linear programming, POMDP, Pruning

URI

https://hdl.handle.net/11511/56790

DOI

https://doi.org/10.1007/978-3-319-46073-4_5

Collections

Graduate School of Natural and Applied Sciences, Conference / Seminar

Suggestions

OpenMETU
Core

A visual interactive approach for scenario-based stochastic multi-objective problems and an application Balibek, E.; Köksalan, Mustafa Murat (2012-12-01) In many practical applications of stochastic programming, discretization of continuous random variables in the form of a scenario tree is required. In this paper, we deal with the randomness in scenario generation and present a visual interactive method for scenario-based stochastic multi-objective problems. The method relies on multi-variate statistical analysis of solutions obtained from a multi-objective stochastic problem to construct joint confidence regions for the objective function values. The decis...
Efficient Three-Layer Iterative Solutions of Electromagnetic Problems Using the Multilevel Fast Multipole Algorithm Onol, Can; Ucuncu, Arif; Ergül, Özgür Salih (2017-05-19) We present a three-layer iterative algorithm for fast and efficient solutions of electromagnetic problems formulated with surface integral equations. The strategy is based on nested iterative solutions employing the multilevel fast multipole algorithm and its approximate forms. We show that the three-layer mechanism significantly reduces solution times, while it requires no additional memory as opposed to algebraic preconditioners. Numerical examples involving three-dimensional scattering problems are prese...
Improved state estimation for jump Markov linear systems Orguner, Umut; Demirekler, Mübeccel; Department of Electrical and Electronics Engineering (2005) This thesis presents a comprehensive example framework on how current multiple model state estimation algorithms for jump Markov linear systems can be improved. The possible improvements are categorized as: -Design of multiple model state estimation algorithms using new criteria. -Improvements obtained using existing multiple model state estimation algorithms. In the first category, risk-sensitive estimation is proposed for jump Markov linear systems. Two types of cost functions namely, the instantaneous an...
On plateaued functions, linear structures and permutation polynomials Mesnager, Sihem; Kaytancı, Kübra; Özbudak, Ferruh (2019-01-01) We obtain concrete upper bounds on the algebraic immunity of a class of highly nonlinear plateaued functions without linear structures than the one was given recently in 2017, Cusick. Moreover, we extend Cusick’s class to a much bigger explicit class and we show that our class has better algebraic immunity by an explicit example. We also give a new notion of linear translator, which includes the Frobenius linear translator given in 2018, Cepak, Pasalic and Muratović-Ribić as a special case. We find some app...
Automated composition of web services with the abductive event calculus Ozorhan, Esra Kirci; Kuban, Esat Kaan; Çiçekli, Fehime Nihan (2010-10-01) This paper proposes the application of the abductive event calculus to the web service composition and execution problem. There are different approaches to web service composition, which are suitable for different application scenarios. In this paper, we are concerned with the formalization of both the interleaved and template-based approaches using the event calculus framework. First, in the interleaved approach, it is shown that given a set of OWL-S web service descriptions in a service repository and a s...

Citation Formats

S. Ozgen and M. Demirekler, “Fast Elimination Method for Pruning in POMDPs,” 2016, vol. 9904, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/56790.