An online algorithm for constrained POMDPs

This work seeks to address the problem of planning in the presence of uncertainty and constraints. Such problems arise in many situations, including the basis of this work, which involves planning for a team of first responders (both humans and robots) operating in an urban environment. The problem is framed as a Partially-Observable Markov Decision Process (POMDP) with constraints, and it is shown that even in a relatively simple planning problem, modeling constraints as large penalties does not lead to good solutions. The main contribution of the work is a new online algorithm that explicitly ensures constraint feasibility while remaining computationally tractable. Its performance is demonstrated on an example problem and it is demonstrated that our online algorithm generates policies comparable to an offline constrained POMDP algorithm.

Authors

• Aditya Undurti
• Jonathan P. How

Keywords

• Humans
• Vehicle dynamics
• Process planning
• Chemicals
• Explosives
• Robotics and automation
• USA Councils
• Uncertainty
• Urban planning
• Robots
• Online Algorithm
• Partially Observable Markov Decision Process
• Markov Decision Process
• Presence Of Uncertainty
• Presence Of Constraints
• Large Penalty
• Feasibility Constraints
• Value Function
• Approximate Solution
• Optimal Policy
• Leaf Node
• Reward Function
• High Reward
• Mixed Integer Linear Programming
• Constraint Violation
• Hard Constraints
• Value Iteration
• Current Node
• Current Beliefs
• Planning Horizon
• Constraint Value
• Danger Zone
• Forward Search
• Successive Nodes
• Negative Reward
• Belief State
• Violation Probability
• Autonomous Vehicles
• Large Reward
• Risk Of Violation