Please wait a minute...
浙江大学学报(工学版)
J4  2012, Vol. 46 Issue (8): 1546-1552    DOI: 10.3785/j.issn.1008-973X.2012.08.029
    
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
Download:   PDF(0KB) HTML
Export: BibTeX | EndNote (RIS)      

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.

Published: 23 September 2012
CLC:  TP 242.6  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

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.

URL:

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


基于运动约束的泛化Field D*路径规划

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

［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] CHEN Ming-ya, XIANG Zhi-yu, LIU Ji-lin. Assistance localization method for mobile robot based on
monocular natural visual landmarks[J]. J4, 2014, 48(2): 285-291.
[2] LIN Ying, GONG Xiao-jin, LIU Ji-lin. Calibration of fisheye cameras based on the viewing sphere[J]. J4, 2013, 47(8): 1500-1507.
[3] WANG Hui-fang, ZHU Shi-qiang, WU Wen-xiang. Improved adaptive robust control of servo system with harmonic drive[J]. J4, 2012, 46(10): 1757-1763.
[4] OUYANG Liu, XU Jin, GONG Xiao-jin, LIU Ji-lin. Optimization of visual odometry based on uncertainty analysis[J]. J4, 2012, 46(9): 1572-1579.
[5] XU Jin, SHEN Min-yi, YANG Li, WANG Wei-qiang, LIU Ji-lin. Binocular bundle adjustment based localization
and terrain stitching for robot[J]. J4, 2011, 45(7): 1141-1146.
[6] CHEN Jia-qian, LIUYu-tian, HE Yan, JIANG Jing-ping. Novel dynamic mapping method based on occupancy grid
model and sample sets[J]. J4, 2011, 45(5): 794-798.
[7] CHEN Jia-Gan, HE Yan, JIANG Jing-Ping. Improved FastSLAM algorithm based on importance weight smoothing[J]. J4, 2010, 44(8): 1454-1459.
[8] XU Sheng-Lin, LIU Yan-Na. Modeling of biped robot by SimMechanics[J]. J4, 2010, 44(7): 1361-1367.
[9] MEI Gong, ZHANG Zhi-Feng, LAI Huan-Huan. Continuoustime based optimized scheduling of production process[J]. J4, 2010, 44(7): 1423-1427.
[10] BO Hua-Dong, WANG Ji-Cong, XIE Bin, HU Shi-Fang, LIU Ji-Lin. Data processing method of time-of-flight 3D imaging camera[J]. J4, 2010, 44(6): 1049-1056.
[11] WANG Li, XIONG Rong, CHU Jian, et al. Fuzzy evaluation based exploring planning for map building in unknown environment[J]. J4, 2010, 44(2): 253-258.
[12] CHEN Shao-Bin, JIANG Jing-Ping. Optimal state feedback control for trajectory tracking of four-wheel mobile robot[J]. J4, 2009, 43(12): 2186-2190.