基于TI-A~*的多机器人动态规划协调方法研究
|
摘要
多机器人在动态环境下路径规划问题是集群机器人群体感知与协调的重要基础问题之一。通过引入时间代价函数,提出结合时间代价的A~*算法(Time Integrated A~*Algorithm,TI-A~*),将规划问题分解成路径规划和冲突协调两个模块。利用变速运动来协调避免死锁和碰撞。通过调整协调阶段介入的时间,可得出改变运动速率和改变规划路径等两种不同TI-A~*协调方法。比较两种算法,归纳各自适用环境。仿真结果验证了移动机器人能够在复杂环境下进行动态路径规划,表明两种算法均基本解决了现有A~*算法存在的问题。
Multiple robots path planning problem in dynamic environment is one of the significant and basic problems of cluster robot perception and coordination. The planning problem is decomposed into two modules: the path planning and the conflict coordination. By introducing time-cost function, the Time Integrated A~* algorithm(TI-A~*) is introduced. Variable speed is employed simultaneously to coordinate the motion and hereby to avoid the deadlock and conflict. By adjusting the timing when the coordination phase is involved, two different coordination TI-A~* algorithms are presented, including the speed-changing algorithm and path-changing algorithm. The two algorithms are compared and the respective environments are summarized. The simulation results verify that the mobile robot can apply the dynamic path planning in the complex environment so that the algorithm proposed in this paper can solve the existing problems of the existing A * algorithm.
Multiple robots path planning problem in dynamic environment is one of the significant and basic problems of cluster robot perception and coordination. The planning problem is decomposed into two modules: the path planning and the conflict coordination. By introducing time-cost function, the Time Integrated A~* algorithm(TI-A~*) is introduced. Variable speed is employed simultaneously to coordinate the motion and hereby to avoid the deadlock and conflict. By adjusting the timing when the coordination phase is involved, two different coordination TI-A~* algorithms are presented, including the speed-changing algorithm and path-changing algorithm. The two algorithms are compared and the respective environments are summarized. The simulation results verify that the mobile robot can apply the dynamic path planning in the complex environment so that the algorithm proposed in this paper can solve the existing problems of the existing A * algorithm.
引文
[1]蒋新松.机器人学导论[M].沈阳:辽宁科学技术出版社,1994:1-50.Jiang Xinsong.Robotics Introduction[M].Shenyang:Liaoning Science and Technology Publishing House,1994:1-50.
[2]Hopcroft J E,Schwartz J T,Sharir M.On the Complexity of Motion Planning for Multiple Independent Objects;PSPACE-Hardness of the"Warehouseman's Problem"[J].International Journal of Robotics Research(S0278-3649),1984,3(3):76-88.
[3]Arora S,Barak B.Computational complexity:a modern approach[M].UK:Cambridge University Press,2005:38-94.
[4]Wang F,Sarkar N.Supervisory controller design for a robot-assisted reach-to-grasp rehabilitation task[C]//IEEE Engineering in Medicine and Biology Society.USA:IEEE,2008:4258-4261.
[5]苏霞,李伟光.FMS中自动导引车路径规划[J].机械设计与制造,2015,1(1):201-203.Su Xia,Li Weiguang.Path Planning of Automated Guided Vehicles In FMS[J].Machinery Design&Manufacture,2015,1(1):201-203.
[6]Shen X,Chong Z J,Pendleton S,et al.Multi-vehicle motion coordination using V2V communication[C]//IEEE Intelligent Vehicles Symposium.USA:IEEE,2015:1334-1341.
[7]Huang J,Zhong X,Peng X.Velocity variation space based multiple agents motion planning for mobile robot[C]//Proceedings of the 31st Chinese Control Conference.USA:IEEE,2012:4820-4824.
[8]Silveira L,Maffei R Q,Almeida F,et al.Using Space D*for Crowded Real Robots Environments[C]//Brazilian Robotics Symposium and Latin American Robotics Symposium.Germany:Springer-Verlag,2012:273-278.
[9]Gürel U,Adar N,Parlaktuna O.Priority-based task allocation in auction-based applications[C]//IEEEInternational Symposium on Innovations in Intelligent Systems and Applications.USA:IEEE,2013:1-5.
[10]González D,Pérez J,Milanés V,et al.A Review of Motion Planning Techniques for Automated Vehicles[J].IEEE Transactions on Intelligent Transportation Systems,2016,17(4):1135-1145.
[11]刘磊,高岩,吴越鹏.刚体轮式机器人高速避障的生存控制方法[J].系统仿真学报,2016,28(12):3001-3009.Liu Lei,Gao Yan,Wu Yuepeng.Viability Control of Rigid Body Wheeled Robots for High Speed Obstacle Avoidance[J].Journal of System Simulation,2016,28(12):3001-3009.
[2]Hopcroft J E,Schwartz J T,Sharir M.On the Complexity of Motion Planning for Multiple Independent Objects;PSPACE-Hardness of the"Warehouseman's Problem"[J].International Journal of Robotics Research(S0278-3649),1984,3(3):76-88.
[3]Arora S,Barak B.Computational complexity:a modern approach[M].UK:Cambridge University Press,2005:38-94.
[4]Wang F,Sarkar N.Supervisory controller design for a robot-assisted reach-to-grasp rehabilitation task[C]//IEEE Engineering in Medicine and Biology Society.USA:IEEE,2008:4258-4261.
[5]苏霞,李伟光.FMS中自动导引车路径规划[J].机械设计与制造,2015,1(1):201-203.Su Xia,Li Weiguang.Path Planning of Automated Guided Vehicles In FMS[J].Machinery Design&Manufacture,2015,1(1):201-203.
[6]Shen X,Chong Z J,Pendleton S,et al.Multi-vehicle motion coordination using V2V communication[C]//IEEE Intelligent Vehicles Symposium.USA:IEEE,2015:1334-1341.
[7]Huang J,Zhong X,Peng X.Velocity variation space based multiple agents motion planning for mobile robot[C]//Proceedings of the 31st Chinese Control Conference.USA:IEEE,2012:4820-4824.
[8]Silveira L,Maffei R Q,Almeida F,et al.Using Space D*for Crowded Real Robots Environments[C]//Brazilian Robotics Symposium and Latin American Robotics Symposium.Germany:Springer-Verlag,2012:273-278.
[9]Gürel U,Adar N,Parlaktuna O.Priority-based task allocation in auction-based applications[C]//IEEEInternational Symposium on Innovations in Intelligent Systems and Applications.USA:IEEE,2013:1-5.
[10]González D,Pérez J,Milanés V,et al.A Review of Motion Planning Techniques for Automated Vehicles[J].IEEE Transactions on Intelligent Transportation Systems,2016,17(4):1135-1145.
[11]刘磊,高岩,吴越鹏.刚体轮式机器人高速避障的生存控制方法[J].系统仿真学报,2016,28(12):3001-3009.Liu Lei,Gao Yan,Wu Yuepeng.Viability Control of Rigid Body Wheeled Robots for High Speed Obstacle Avoidance[J].Journal of System Simulation,2016,28(12):3001-3009.