The Journal of China Universities of Posts and Telecommunications ›› 2021, Vol. 28 ›› Issue (3): 49-62.doi: 10.19682/j.cnki.1005-8885.2021.0017

Previous Articles     Next Articles

Partition sampling strategy for robot motion planning under uncertainty


  • Received:2020-07-27 Revised:2020-11-23 Online:2021-06-30 Published:2021-06-22
  • Contact: Chao FENG
  • Supported by:
    National Natural Science Foundation of China;Young Doctor Cooperation Foundation of Qilu University of Technology (Shandong Academy of Sciences)


In order to solve the sensing and motion uncertainty problem of motion planning in narrow passage environment, a partition sampling strategy based on partially observable Markov decision process (POMDP) was proposed. The method combines partition sampling strategy and can improve the success rate of the robot motion planning in the narrow passage. Firstly, the environment is divided into open area and narrow area by using a partition sampling strategy, and generates the initial trajectory of the robot with fewer sampling points. Secondly, the method can calculate a local optimal solution of the initial nominal trajectory by solving POMDP problem, and iterates an overall optimal trajectory of robot motion. The proposed method follows the general POMDP solution framework, in which the belief dynamics is approximated by an extended Kalman filter (EKF), and the value function is represented by an effective quadratic function in the belief space near the nominal trajectory. Using a belief space variant of iterative linear quadratic Gaussian (iLQG) to perform the value iteration, which results in a linear control policy over the belief space that is locally optimal around the nominal trajectory. A new nominal trajectory is generated by executing the control strategy iteration, and the process is repeated until it converges to a locally optimal solution. Finally, the robot gets the optimal trajectory to safely pass through a narrow passage. The experimental results show that the proposed method can efficiently improves the performance of motion planning under uncertainty.

Key words:

motion planning, narrow passage, partition sampling, partially observable Markov decision process (POMDP), uncertainty

CLC Number: