A point-based POMDP planner for target tracking

Target tracking has two variants that are often studied independently with different approaches: target searching requires a robot to find a target initially not visible, and target following requires a robot to maintain visibility on a target initially visible. In this work, we use a partially observable Markov decision process (POMDP) to build a single model that unifies target searching and target following. The POMDP solution exhibits interesting tracking behaviors, such as anticipatory moves that exploit target dynamics, informationgathering moves that reduce target position uncertainty, and energy-conserving actions that allow the target to get out of sight, but do not compromise long-term tracking performance. To overcome the high computational complexity of solving POMDPs, we have developed SARSOP, a new point-based POMDP algorithm based on successively approximating the space reachable under optimal policies. Experimental results show that SARSOP is competitive with the fastest existing pointbased algorithm on many standard test problems and faster by many times on some.

Authors

• David Hsu
• Wee Sun Lee
• Nan Rong

Keywords

• Target tracking
• Robot sensing systems
• Orbital robotics
• Uncertainty
• USA Councils
• Computer science
• Computational complexity
• Robotics and automation
• Sun
• Testing
• Target Location
• Reachable
• Optimal Policy
• Tracking Performance
• High Computational Complexity
• Target Search
• Behavioral Tracking
• Time Step
• Value Function
• Autonomic System
• Sequence Of Actions
• Current Position
• Probability Function
• Dynamic Programming
• Simulation Run
• Robot Control
• Tracking Problem
• Position Of The Robot
• Successive Approximation
• Value Function Approximation
• Robot Sensors
• Optimal Value Function
• Target Path
• Current Beliefs
• Target Trajectory
• Robotic Tasks