中国邮电高校学报(英文版) ›› 2021, Vol. 28 ›› Issue (3): 49-62.doi: 10.19682/j.cnki.1005-8885.2021.0017

• Artificial Intelligence • 上一篇    下一篇

Partition sampling strategy for robot motion planning under uncertainty

曹启贺1,李庆华2,邱书波3,韩丰键1,冯超1   

  1. 1. 齐鲁工业大学(山东省科学院)
    2. 齐鲁工业大学(山东省科学院);济南市人机智能协同工程实验室
    3.
  • 收稿日期:2020-07-27 修回日期:2020-11-23 出版日期:2021-06-30 发布日期:2021-06-22
  • 通讯作者: 冯超 E-mail:cfeng@qlu.edu.cn
  • 基金资助:
    国家自然科学基金;齐鲁工业大学(山东省科学院)青年博士合作基金

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 E-mail:cfeng@qlu.edu.cn
  • 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.


关键词:

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

Abstract:

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

中图分类号: