A Path Planning and Following Algorithm Based on Twofold Interpolations
LIANG Zhiwei1, MA Xudong2, FANG Fang2, ZHU Songhao1
1. College of Automation, Nanjing University of Posts and Telecommunications, Nanjing 210046, China; 2. Key Lab of MCCSE, Ministry of Education, Southeast University, Nanjing 210096, China
Abstract：Aiming at the deficiencies of traditional path planning algorithms based on grid maps,a twofold-interpolation-based path planning algorithm called T* is presented.First,using FMM(fast marching method) interpolation,a goal-wave map is obtained,on which wave is supposed to start at the goal node and propagate radiantly through four adjacent nodes, assigning monotonically increasing values to nodes.Based on the goal-wave map,a linear interpolation is used to search a smooth path starring from the robot's current position to the target point along the reverse direction of the wave.At last, an improved VVM(virtual vehicle method) is applied to tracking this generated path by a nonholonomic mobile robot.The experiment results demonstrate the effectiveness of the approach.
[1] Bhattacharya P,Gavrilova M L.Roadmap-based path planning-Using the Voronoi diagram for a clearance-based shortestpath[J].IEEE Robotics and Automation Magazine,2008,15(2):58-66.
[2] 孟庆浩,彭商贤,刘大维.基于Q-M图启发式搜索的移动机器人全局路径规划[J].机器人,1998,20(4):273-279.Meng Qinghao,Peng Shangxian,Liu Dawei.Mobile robot global path planning using heuristic search on the Q-M graph[J].Robot,1998,20(4):273-279.
[3] Dijkstra E.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1:269-271.
[4] Koenig S,Likhachev M.Incremental A*[M]//Advances in Neural Information Processing Systems.Cambridge,MA,USA:MIT Press,2001.
[5] Likhachev M,Ferguson D,Gordon G,et al.Anytime dynamic A*:An anytime,replanning algorithm[C]//International Conference on Automated Planning and Scheduling.California,USA:2005:262-271.
[6] Koenig S,Likhachev M.D* lite[C]//National Conference on Artificial Intelligence.Cambridge,MA,USA:MIT Press,2002:476-483.
[7] Stentz A.The focused D* algorithm for real-time replanning[C]//International Joint Conference on Artificial Intelligence.1995:1652-1659.
[8] Konolige K.A gradient method for realtime robot control[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ,USA:IEEE,2000:639-646.
[9] Philippsen R.Motion planning and obstacle avoidance for mobile robots in highly cluttered dynamic environments[D].Switzerland:Ecole Polytechnique Fédérale de Lausanne,2004.
[10] Philippsen R,Jesnen B,Siegwart R.Toward online probabilistic path replanning in dynamic environments[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway,NJ,USA:IEEE,2006:2876-2881.
[11] Latombe J C.Robot motion planning[M].Holand:Kluwer Aca-demic Publisher,1991.
[12] Lengyel J,Reichert M,Donald B R,et al.Real-time robot motion planning using rasterizing computer graphics hardware[J].Computer Graphics,1990,24(4):327-335.
[13] Szczerba R J,Chen D Z,Uhran J.A grid-based approach for finding conditional shortest paths in an unknown environment[EB/OL].[2010-01-15].www.cse.nd.edu/Reports/1994/tr-94-34.ps.
[14] Andrews J,Sethian J A.Fast marching methods for the continuous traveling salesman problems[J].PNAS,2007,104(4):1118-1123.
[15] Ferguson D,Stentz A.Using interpolation to improve path planning:The field D* algorithm[J].Journal of Field Robotics,2006,23(2):79-101.
[16] Lee T-C,Song K-T,Lee,C-H,et al.Tracking control of mobile robots using saturation feedback controiler[C]//IEEE International Conference on Robotics and Automation.Piscataway,NJ,USA:IEEE,1999:2639-2644.
[17] Soueres P,Balluchi A,Bicchi A.Optimal feedback control for route tracking with a bounded-curvature vehicle[C]//IEEE International Conference on Robotics and Automation.Piscataway,NJ,USA:IEEE,2000:2473-2478.
[18] Egerstedt M,Hu X,Stotsky A.Control of mobile platforms using a virtual vehicle approach[J].IEEE Transactions on Automatic Control,2001,46(11):1777-1782.
[19] Macek K,Petrovic I,Siegwart R.A control method for stable and smooth path following of mobile robots[C]//European Conference on Mobile Robots.2005:128-133.
[20] Sethian J A,Smereka P.Level set methods for fluid interfaces[J].Annual Review of Fluid Mechanics,2003,35:341-372.
[21] 梁志伟,马旭东,戴先中.分布式感知协作的扩展Monte Carlo定位算法[J].机器人,2008,30(3):210-216.Liang Zhiwei,Ma Xudong,Dai Xianzhong.An extended Monte Carlo localization approach based on collaborative distributed perception[J].Robot,2008,30(3):210-216.
[22] Liang Z W,Ma X D,Dai X Z.Compliant navigation mechanisms utilizing probabilistic motion patterns of humans in a camera network[J].Advanced Robotics,2008,22(9):929-948.
