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 
摘要：

为了解决基于栅格的路径规划算法因环境描述的离散化导致规划结果不能满足机器人运动约束,以及单一路径代价的局限致使算法无法适用于复杂环境的问题,提出一种基于运动约束的泛化Field D*算法.该算法的代价函数可同时考虑路程、行驶安全以及行驶时间等一个或多个行驶代价.根据机器人运动模型的特性,在路径点提取过程中结合机器人的最小转弯半径,进行满足运动约束的路径平滑.该算法在多组模拟的复杂环境栅格地图中进行测试,实验结果表明,算法对复杂环境有很好的适应性,同时有效提高路径的可执行性.
关键词：  ;  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.
Key words: Field D*    path planning    generalized cost function    minimum turning radius
出版日期: 2012-09-03
:  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/xueshu/eng/CN/10.3785/j.issn.1008-973X.2012.08.029    或    http://www.zjujournals.com/xueshu/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]. 浙江大学学报(工学版), 2017, 51(6): 1153-1162.
[2] 任迪, 万健, 殷昱煜, 周丽, 高敏. 基于贝叶斯分类的Web服务质量预测方法研究[J]. 浙江大学学报(工学版), 2017, 51(6): 1242-1251.
[3] 宋瑞祥, 张庆国, 于海敬, 徐丽, 施悯悯. 遥感数据的城市不透水面估算及增温效应[J]. 浙江大学学报(工学版), 2017, 51(5): 1051-1056.
[4] 李静, 王哲. 似平面应力条件下混凝土的变形特性[J]. 浙江大学学报(工学版), 2017, 51(4): 745-751.
[5] 蒋鑫龙, 陈益强, 刘军发, 忽丽莎, 沈建飞. 面向自闭症患者社交距离认知的可穿戴系统[J]. 浙江大学学报(工学版), 2017, 51(4): 637-647.
[6] 高德东, 李强, 雷勇, 徐飞, 白辉全. 基于几何逼近法的斜尖柔性穿刺针运动学研究[J]. 浙江大学学报(工学版), 2017, 51(4): 706-713.
[7] 李明, 刘扬, 唐雪松. 疲劳裂纹的跨尺度分析[J]. 浙江大学学报(工学版), 2017, 51(3): 524-531.
[8] 张捷, 肖新标, 王瑞乾, 金学松. 高速列车铝型材声振特性测试及等效建模[J]. 浙江大学学报(工学版), 2017, 51(3): 545-553.
[9] 李晓东, 祝跃飞, 刘胜利, 肖睿卿. 基于权限的Android应用程序安全审计方法[J]. 浙江大学学报(工学版), 2017, 51(3): 590-597.
[10] 苏星, 王慧泉, 金仲和. 实时高可靠综合电子系统的逻辑架构设计[J]. 浙江大学学报(工学版), 2017, 51(3): 628-636.
[11] 潜龙昊, 胡士强, 杨永胜. 多节双八面体变几何桁架臂逆运动学解析算法[J]. 浙江大学学报(工学版), 2017, 51(1): 75-81.
[12] 张伟, 胡友德, 郑立荣. 基于频率可调驻波振荡器的芯片时钟系统设计[J]. 浙江大学学报(工学版), 2017, 51(1): 168-176.
[13] 谢罗峰, 徐慧宁, 黄沁元, 赵越, 殷国富. 应用双树复小波包和NCA-LSSVM检测磁瓦内部缺陷[J]. 浙江大学学报(工学版), 2017, 51(1): 184-191.
[14] 刘海宾, 王勇, 马鹏磊, 谢玉东. 基于平行式振荡翼系统参数耦合分析[J]. 浙江大学学报(工学版), 2017, 51(1): 153-159.
[15] 厉文榜,方梦祥,岑建孟,肖平,时正海,山石泉,王勤辉,骆仲泱. K-Fe复合催化剂对煤半焦气化速率与产物的影响[J]. 浙江大学学报(工学版), 2016, 50(9): 1746-1751.