Please wait a minute...
浙江大学学报(工学版)
J4  2012, Vol. 46 Issue (8): 1546-1552    DOI: 10.3785/j.issn.1008-973X.2012.08.029
光学工程、电信技术     
基于运动约束的泛化Field D*路径规划
马丽莎1, 周文晖2, 龚小谨1, 刘济林1
1. 浙江大学 信息与电子工程学系,浙江 杭州310027；2. 杭州电子科技大学 计算机学院,浙江 杭州310018
Motion constrained generalized Field D* path planning
MA Li-sha1, ZHOU Wen-hui2, GONG Xiao-jin1, LIU Ji-lin1
1. Department of Information Science and Electronic Engineering, Zhejiang University,Hangzhou 310027, China；
2. Department of Computer Science, Hangzhou Dianzi University, Hangzhou 310018, China
 全文: PDF  HTML
摘要：

为了解决基于栅格的路径规划算法因环境描述的离散化导致规划结果不能满足机器人运动约束,以及单一路径代价的局限致使算法无法适用于复杂环境的问题,提出一种基于运动约束的泛化Field D*算法.该算法的代价函数可同时考虑路程、行驶安全以及行驶时间等一个或多个行驶代价.根据机器人运动模型的特性,在路径点提取过程中结合机器人的最小转弯半径,进行满足运动约束的路径平滑.该算法在多组模拟的复杂环境栅格地图中进行测试,实验结果表明,算法对复杂环境有很好的适应性,同时有效提高路径的可执行性.
Abstract:

Grid-based path planning method can’t meet the motion constraints due to discretization, and its cost function only considers an aspect of navigation costs, which limits it to relative simple environments. To solve these two problems, a motion constrained generalized Field D* algorithm is proposed. In this algorithm, the cost function was designed to involve one or several navigation costs, including distance, safety and time cost. Moreover, according to motion model of robot, the planned path was further smoothed regarding to the constraint of minimum turning radius. A group of simulated grid maps describing complicated environments had been tested. Experiments show that the proposed algorithm not only fits complicated environments but also improves performability of the results.
出版日期: 2012-09-23
:  TP 242.6  
基金资助:

国家自然科学基金重大资助项目（NSFC 6053407）;国家自然科学基金资助项目（60902077）.
通讯作者: 龚小谨，女，讲师.     E-mail: gongxj@zju.edu.cn
作者简介: 马丽莎（1986—），女，硕士生，从事计算机视觉、机器人导航研究. E-mail: lisha_ma@yahoo.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

马丽莎, 周文晖, 龚小谨, 刘济林. 基于运动约束的泛化Field D*路径规划[J]. J4, 2012, 46(8): 1546-1552.

MA Li-sha, ZHOU Wen-hui, GONG Xiao-jin, LIU Ji-lin. Motion constrained generalized Field D* path planning. J4, 2012, 46(8): 1546-1552.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2012.08.029    或    http://www.zjujournals.com/eng/CN/Y2012/V46/I8/1546

［1］ STENTZ A. Optimal and efficient path planning for partiallyknown enviroments \
[C\] ∥ Proceedings of the International Conference on Robotics and Automation. San Diego: IEEE,1994: 3310-3317.
［2］ STENTZ A. The Focussed D* algorithm for realtime replanning［C］∥Proceedings of the International Joint Conference on Artificial Intelligence. Montréal: ［s. n.］, 1995: 1652-1659.
［3］ KOENIG S, LIKHACHEV M.D* lite ［C］∥Proceedings of the National Conference on Artificial Intelligence. Edmonton: ［s. n.］, 2002: 476-483.
［4］ LUIS H, OLIVERIA R, LUIZ C. A survey and classification of A* based bestfirst heuristic search algorithms ［M］. London: Springer, 2011: 253-262.
［5］ DAVE F, ANTHONY S. Using interpolation to improve path planning: The Field D* algorithm ［J］. Field Robot, 2006, 23（2）: 79-101.
［6］ THOMAS C. Fast optimal kinodynamic path planning in dynamic environments ［R］. MIT6.887 Cambrige, MA, USA: MIT Robotics Science & Systems, 2006.
［7］ LING X, ANTHONY S. Blended local planning for generating safe and feasible paths ［C］∥Proceedings of International Conference on Intelligent Robots and Systems. Nice: IEEE, 2008: 709-716.
［8］ KAO T H, JING S L, YAU Z C. A comparative study of smooth path planning for a mobile robot by evolutionary multiobjective optimization ［C］∥Proceedings of International Symposium on Computational Intelligence in Robotics and Automation. Jacksonville: IEEE, 2007: 254-259.
［9］ LIN H Y, TAUR J S, CHEN W Z. Pathplanning using the behavior cost and the path length with a multiresolution scheme ［C］∥ Proceedings of IEEE International Conference on Systems Man and Cybernetics (SMC). Istanbul: IEEE, 2010: 35-42.
［10］ MARIJA S, IVAN P. Integration of Focused D* and Witkowski’s algorithm for path planning and replanning ［C］∥Proceedings of 4th European Conference on Mobile Robots. Mlini/Dubrovnik: Mobile Robots, 2009: 99-104.
［11］ 叶玮琼,余永权.未知环境下基于可拓策略的路径规划［J］.计算机工程与应用,2010,46(19): 10-17.
YE Weiqiong, YU Yongquan. Path planning based on extension strategy in unknown environment［J］. Computer Engineering and Applications. 2010, 46(19): 10-17.
［12］ ANNETT C, HEIKO H. Stereo camera based navigation of mobile robots on rough terrain ［C］∥Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. St. Louis: IEEE, 2009: 4571-4576.
［13］ PIERRE L, SASCHA K, ROLAND S. The SmartTera vehicle for fully autonomous navigation and mapping in outdoor environments ［C］∥Proceedings of Climbing and Walking Robots. Brussels: ［s. n.］, 2006.
［14］ SOUERES P, BOISSONNAT J D. Optimal trajectories for nonholonomic mobile robots ［J］. Lecture Notes in Control and Information Science, 1998, 229: 93-170.
［15］ CHEN X, LI Y M. Smooth path planning of a mobile robot using stochastic particle swarm optimization ［C］∥Proceedings of International Conference on Mechatronics and Automation. Zhenzhou: IEEE, 2006: 25-28.
［16］ SERVIA A, ROMBANT M, Pmciado, A. Comparative study of the different methods of path generation for a mobile robot in a free environment ［C］∥Proceedings of the IEEE 5th International Conference on Advanced Robotics. New Jersey: IEEE, 1991: 1667-1670.
［17］ YOSSAWEE W, TSUBOUCHI T, SERATA S. Path generation for articulated steering type vehicle using symmetrical clothoid ［C］∥Proceedings of the IEEE International Conference on Industrial Technology. New York: IEEE, 2002: 187-192.
［18］ SIMON T, SATOSHI K. Smooth trajectory planning with obstacle avoidance for carlike mobile robots ［C］∥Proceedings of the 23rd Annual Conference of the Robotics Society of Japan. Yokohama: ［s. n.］, 2005: 1E/18-1E22.
［19］ KYUNG I L, JAE H K, CHUNG K K. The unmanned ground vehicle’s local path plan algorithm that adapted weight according to obstacles in local area ［C］∥Proceedings of International Conference on Control, Automation and Systems. Gyeonggido Korea: ［s. n.］, 2010: 1097-1100.
［20］ 孟偲,王田苗.一种移动机器人全局最优路径规划算法［J］.机器人,2008,20(3): 217-222.
MENG Cai, WANG Tianmiao. A global optimal path planning algorithm for mobile robot ［J］. Robot. 2008, 20(3): 217-222.
[1] 陈明芽, 项志宇, 刘济林. 单目视觉自然路标辅助的移动机器人定位方法[J]. J4, 2014, 48(2): 285-291.
[2] 林颖, 龚小谨, 刘济林. 基于单位视球的鱼眼相机标定方法[J]. J4, 2013, 47(8): 1500-1507.
[3] 王会方, 朱世强, 吴文祥. 谐波驱动伺服系统的改进自适应鲁棒控制[J]. J4, 2012, 46(10): 1757-1763.
[4] 欧阳柳,徐进,龚小谨,刘济林. 基于不确定性分析的视觉里程计优化[J]. J4, 2012, 46(9): 1572-1579.
[5] 徐进,沈敏一,杨力,王炜强,刘济林. 基于双目光束法平差的机器人定位与地形拼接[J]. J4, 2011, 45(7): 1141-1146.
[6] 陈家乾,柳玉甜,何衍,蒋静坪. 基于栅格模型和样本集合的动态环境地图创建[J]. J4, 2011, 45(5): 794-798.
[7] 陈家乾, 何衍, 蒋静坪. 基于权值平滑的改良FastSLAM算法[J]. J4, 2010, 44(8): 1454-1459.
[8] 徐生林, 刘艳娜. 两足机器人的SimMechanics建模[J]. J4, 2010, 44(7): 1361-1367.
[9] 梅红, 张智丰, 赖欢欢. 基于连续时间的生产过程优化调度[J]. J4, 2010, 44(7): 1423-1427.
[10] 潘华东, 王其聪, 谢斌, 许世芳, 刘济林. 飞行时间法三维成像摄像机数据处理方法研究[J]. J4, 2010, 44(6): 1049-1056.
[11] 王立, 熊蓉, 褚健, 等. 基于模糊评价的未知环境地图构建探测规划[J]. J4, 2010, 44(2): 253-258.
[12] 陈少斌, 蒋静坪. 四轮移动机器人轨迹跟踪的最优状态反馈控制[J]. J4, 2009, 43(12): 2186-2190.