Research on Incremental Heuristic Path Planner with Variable Dimensional State Space
-
摘要: 在移动机器人路径规划中需要考虑运动几何约束,同时,由于它经常工作于动态、时变的环 境中,因此,还必须保证路径规划算法的效率.本文提出了一种基于变维度状态空间的增量启发式路径规划 方法,该方法既能满足移动机器人的运动几何约束,又能保证规划算法的效率.首先,设计了变维度状态空间, 在机器人周围的局部区域考虑运动几何约束组织高维状态空间,其他区域组织低维状态空间;然后,基于变维 度状态空间,提出了一种增量启发式路径规划方法,该方法在新的规划进程中可以使用以前的规划结果,仅对 机器人周围的局部区域进行重搜索,从而能保证算法的增量性及实时性;最后,通过仿真计算和机器人实验验 证了算法的有效性.Abstract: Path planning with kinodynamic constraints is often required for mobile robots. Meanwhile, the robot often operates in dynamic and time-varying environments, so the effectiveness of the planner should be guaranteed. In this paper we present an incremental heuristic path planner based on variable dimensional state space. The proposed planner not only considers the robot's kinodynamic constraints into planning, but also guarantees the effectiveness. First, the variable dimensional state space is designed. The high-dimensional state space is organized around the robot and the low-dimensional state space elsewhere. Then, an incremental heuristic path planner is proposed based on the variable dimensional state space. The incremental and anytime properties of the planner are guaranteed by reusing previous computation. Finally, the effectiveness of the planner is confirmed by simulation and robot experiments.
-
[1] Likhachev M, Gorden G J, Thrun S. ARA*: anytime A* with provable bounds on sub-optimality. In: Proceedings of the 17th Annual Conference on Neural Information Proceeding Systems. New York, USA: IEEE, 2003 [2] Bekris K E, Kavraki L E. Greedy but safe replanning under kinodynamic constraints. In: Proceedings of the 2007 IEEE International Conference on Robotics and Automation. New York, USA: IEEE, 2007. 704-710 [3] Petti S, Fraichard T. Safe motion planning in dynamic environments. In: Proceedings of the 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. New York, USA: IEEE, 2005. 2210-2215 [4] Likhachev M, Ferguson D. Planning long dynamically feasible maneuvers for autonomous vehicles. International Journal of Robotics Research, 2009, 28(8): 933-945 [5] Brock O, Khatib O. High-speed navigation using the global dynamic window approach. In: Proceedings of the 1999 IEEE International Conference on Robotics and Automation. New York, USA: IEEE, 1999. 341-346 [6] Kelly A J. An Intelligent, Predictive Control Approach to the High-speed Cross-country Autonomous Navigation Problem, Technical Report, CMU-RI-TR-95-33, Robotics Institute, Carnegie Mellon University, 1995 [7] Philippsen R, Siegwart R. Smooth and efficient obstacle avoidance for a tour guide robot. In: Proceedings of the 2003 IEEE International Conference on Robotics and Automation. New York, USA: IEEE, 2003. 446-451 [8] Mills-Tettey G A, Stentz A, Bernardine Dias M. DD* lite: efficient incremental search with state dominance. In: Proceedings of the 21st National Conference on Artificial Intelligence. Palo Alto, USA: AAAI, 2006. 1032-1038 [9] Zhang H J, Chen H Y, Jiang Y, Gong J W, Xiong G M. Variable dimensional state space based global path planning for mobile robot. Journal of Beijing Institute of Technology, 2012, 21(3): 328-335 [10] Zhang H J, Butzke J, Likhachev M. Combining global and local planning with guarantees on completeness. In: Proceedings of the 2012 IEEE International Conference on Robotics and Automation. New York, USA: IEEE, 2012. 4500-4506 [11] Howard T M, Kelly A. Optimal rough terrain trajectory generation for wheeled mobile robots. International Journal of Robotics Research, 2007, 26(2): 141-166 [12] Pitvoraiko M, Knepper R A, Kelly A. Differentially constrained mobile robot motion planning in state lattices. Journal of Field Robotics, 2009, 26(3): 308-333 [13] Likhachev M, Ferguson D I, Gordon G J, Stentz A, Thrun S. Anytime dynamic A*: an anytime, replanning algorithm. In: Proceedings of the 2005 International Conference on Automated Planning and Scheduling. California, USA: IEEE, 2005. 262-271
点击查看大图
计量
- 文章访问数: 1900
- HTML全文浏览量: 100
- PDF下载量: 2111
- 被引次数: 0