A Point-based POMDP Algorithm for Robot Planning

We present an approximate POMDP solution method for robot planning in partially observable environments. Our algorithm belongs to the family of point-based value iteration solution techniques for POMDP, in which planning is performed only on a sampled set of reachable belief points. We describe a simple, randomized procedure that performs value update steps that strictly improve the value of all belief points in each step. We demonstrate our algorithm on a robotic delivery task in an office environment and on several benchmark problems, for which we compute solutions that are very competitive to those of state-of-the-art methods in terms of speed and solution quality.

Authors

• Matthijs T. J. Spaan
• Nikos Vlassis

Keywords

• Robot sensing systems
• Orbital robotics
• Motion planning
• Uncertainty
• Sensor systems
• Informatics
• Robot motion
• Working environment noise
• Navigation
• Postal services
• Planning Of Robots
• Technical Solutions
• Solution Quality
• Update Step
• Updated Values
• Value Iteration
• Benchmark Problems
• Points In Step
• Discretion
• Value Function
• Number Of Observations
• K-means
• State Space
• Estimation Algorithm
• Finite Set
• Markov Decision Process
• Observation Space
• Sensor Readings
• Belief State
• Value Function Approximation
• Large State Space
• Sensor Observations
• Simulated Robot