Point Based Value Iteration with Optimal Belief Compression for Dec-POMDPsPoint Based Value Iteration with Optimal Belief Compression for Dec-POMDPsMacDermed, Liam and Isbell, Charles L.2013
Paper summarynipsreviewsThis paper proposes a new method for Dec-POMDP planning that is built out of several components. The first is a new way of solving cooperative Bayesian games using an integer linear program. The second is the transformation of the Dec-POMDP to a belief POMDP in which a "centralized mediator" must select at each timestep the best action for each agent-belief pair. The third is to automate the discovery of optimal belief compression by dividing each timestep into two parts, the first corresponding to the original Dec-POMDP and the second giving each agent a chance to select how its beliefs in that timestep are mapped to a bounded set and thus compressed. The fourth assembles these components together into a point-based value iteration method that solves the resulting belief POMDP using a varient of PERSEUS in which the CBG solver is used to compute maximizations.
Three contributions are made:
* An approach to convert DEC-POMDPs to bounded belief DEC-POMDPs
* An approach to convert bounded belief DEC-POMDPs to POMDPs with exponentially many actions
* An integer linear program to optimize one-step look-ahead policies in POMDPs with exponentially many actions
This paper proposes a new method for Dec-POMDP planning that is built out of several components. The first is a new way of solving cooperative Bayesian games using an integer linear program. The second is the transformation of the Dec-POMDP to a belief POMDP in which a "centralized mediator" must select at each timestep the best action for each agent-belief pair. The third is to automate the discovery of optimal belief compression by dividing each timestep into two parts, the first corresponding to the original Dec-POMDP and the second giving each agent a chance to select how its beliefs in that timestep are mapped to a bounded set and thus compressed. The fourth assembles these components together into a point-based value iteration method that solves the resulting belief POMDP using a varient of PERSEUS in which the CBG solver is used to compute maximizations.
Three contributions are made:
* An approach to convert DEC-POMDPs to bounded belief DEC-POMDPs
* An approach to convert bounded belief DEC-POMDPs to POMDPs with exponentially many actions
* An integer linear program to optimize one-step look-ahead policies in POMDPs with exponentially many actions