Path Planning Algorithm based on Partially POMDP Model

다국어 초록 (Multilingual Abstract)

To address the problem that reactive navigation is prone to local optimality under uncertain and complex environments, a POMDP-based global path planning algorithm is proposed for mobile robots. A 6-tuple model is constructed for path planning under complex dynamic environments, and the global optimality is realizes by maximizing the accumulative reward function. State transition function and observation function are used to handle unknown obstacles and noisy perception by modeling the error probability. Belief state space is introduced, and a value iteration algorithm using point-based policy treepruning is developed to solve for real time planning policy, which effectively reduces the computational complexity. Simulation results show that using this algorithm the robot can automatically adapt to different probing granularities, avoid obstacles under complex uncertain environments, and achieve the optimal paths.

목차 (Table of Contents)

• Abstract
• 1. Introduction
• 2. Path Planning Model of MDP
• 2.1. Path Planning Model of POMDP
• 2.2. Modeling of State Transition Function
• 2.3. Modeling of Observation Function
• 2.4. Modeling of Reward Function
• 3. Solution Algorithm Based on Point Pruning Policy Tree
• 3.1. Analysis for Algorithm Complexity
• 3.2. Value Iteration Solution Algorithm based on Point Pruning Policy Tree
• 4. Simulation and Result Analysis
• 4.1. Simulation Environment and Parameter Settin
• 4.2. Environment Simulation of U-Shaped Obstacles
• 4.3. Environment Simulation of Random Obstacles
• 5. Conclusion
• Referencea