Paper Info
Title
Three New Algorithms to Solve N-POMDPs.
Abstract
In many fields in computational sustainability, applications of POMDPs are inhibited by the complexity of the optimal solution. One way of delivering simple solutions is to represent the policy with a small number of alpha-vectors. We would like to find the best possible policy that can be expressed using a fixed number N of alpha-vectors. We call this the N-POMDP problem. The existing solver alpha-min approximately solves finite-horizon POMDPs with a controllable number of alpha-vectors. However alpha-min is a greedy algorithm without performance guarantees, and it is rather slow. This paper proposes three new algorithms, based on a general approach that we call alpha-min-2. These three algorithms are able to approximately solve N-POMDPs. alpha-min-2-fast (heuristic) and alpha-min-2-p (with performance guarantees) are designed to complement an existing POMDP solver, while alpha-min-2-solve (heuristic) is a solver itself. Complexity results are provided for each of the algorithms, and they are tested on well-known benchmarks. These new algorithms will help users to interpret solutions to POMDP problems in computational sustain ability.
Year
Venue
Field
2017
THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE
Computer science,Artificial intelligence,Machine learning,Randomized algorithms as zero-sum games
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
7
3
Name
Order
Citations
PageRank
Yann Dujardin100.68
Thomas G. Dietterich293361722.57
Iadine Chades3366.00