基于TI-A*的多机器人动态规划协调方法研究

doi:10.16182/j.issn1004731x.joss.17-0280

系统仿真学报 ›› 2019, Vol. 31 ›› Issue (5): 925-935.doi: 10.16182/j.issn1004731x.joss.17-0280

基于TI-A*的多机器人动态规划协调方法研究

赵萍¹, 雷新宇¹, 陈波芝¹, 杨矫云²

1.合肥工业大学机械工程学院,安徽合肥 230009;
2.合肥工业大学计算机与信息学院,安徽合肥 230009

收稿日期:2017-06-12 修回日期:2017-08-01 出版日期:2019-05-08 发布日期:2019-11-20
作者简介:赵萍(1987-), 女, 山东烟台, 博士, 副教授, 研究方向为机器人学; 雷新宇(1992-), 男, 湖北武汉, 硕士, 研究方向为多移动机器人路径规划; 陈波芝(1992-), 女, 新疆伊犁, 硕士, 研究方向为串联机器人运动规划。
基金资助:
国家自然科学基金(61502135)

TI-A* Based Multi-robot Dynamic Planning and Coordination Method

Zhao Ping¹, Lei Xinyu¹, Chen Bozhi¹, Yang Jiaoyun²

1.School of Mechanical Engineering, Hefei University of Technology, Hefei 230009, China;
2.School of Computer and Information, Hefei University of Technology, Hefei 230009, China

Received:2017-06-12 Revised:2017-08-01 Online:2019-05-08 Published:2019-11-20

摘要/Abstract

摘要： 多机器人在动态环境下路径规划问题是集群机器人群体感知与协调的重要基础问题之一。通过引入时间代价函数,提出结合时间代价的A*算法(Time Integrated A* Algorithm,TI-A*),将规划问题分解成路径规划和冲突协调两个模块。利用变速运动来协调避免死锁和碰撞。通过调整协调阶段介入的时间,可得出改变运动速率和改变规划路径等两种不同TI-A*协调方法。比较两种算法,归纳各自适用环境。仿真结果验证了移动机器人能够在复杂环境下进行动态路径规划,表明两种算法均基本解决了现有A*算法存在的问题。

关键词: 多移动机器人, Time Integrated A*算法, 路径规划, 动态避障, 冲突协调

Abstract: 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.

Key words: multiple mobile robot, Time Integrated A* algorithm, path planning, collision avoidance dynamically, conflict coordination

中图分类号:

TP242

赵萍, 雷新宇, 陈波芝, 杨矫云. 基于TI-A*的多机器人动态规划协调方法研究[J]. 系统仿真学报, 2019, 31(5): 925-935.

Zhao Ping, Lei Xinyu, Chen Bozhi, Yang Jiaoyun. TI-A* Based Multi-robot Dynamic Planning and Coordination Method[J]. Journal of System Simulation, 2019, 31(5): 925-935.

参考文献

[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]// IEEE International 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.

[1]	陆淼嘉, 黄承媛, 滕靖. 基于多智能体的网购生鲜无人车配送调度仿真[J]. 系统仿真学报, 2022, 34(6): 1185-1195.
[2]	张森, 张孟炎, 邵敬平, 普杰信. 基于随机策略搜索的多机三维路径规划方法[J]. 系统仿真学报, 2022, 34(6): 1286-1295.
[3]	蒙盾, 胡卓, 张华军. 基于改进A^*算法的多层邮轮疏散系统仿真[J]. 系统仿真学报, 2022, 34(6): 1375-1382.
[4]	梁江涛, 王慧琴. 基于改进蚁群算法的建筑火灾疏散路径规划研究[J]. 系统仿真学报, 2022, 34(5): 1044-1053.
[5]	邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
[6]	李兆强, 张时雨. 基于快速RRT算法的三维路径规划算法研究[J]. 系统仿真学报, 2022, 34(3): 503-511.
[7]	王启明, 宗高强, 胥津铭. 多段式自动泊车最优路径规划与仿真分析[J]. 系统仿真学报, 2022, 34(2): 385-395.
[8]	陈志梅, 李敏, 邵雪卷, 赵志诚. 基于改进RRT算法的桥式起重机避障路径规划[J]. 系统仿真学报, 2021, 33(8): 1832-1838.
[9]	李颀, 汪伟. 多全向轮协同分拣平台的路径规划[J]. 系统仿真学报, 2021, 33(3): 698-709.
[10]	黄晓冬, 苑海涛, 毕敬, 刘涛. 基于DQN的海战场舰船路径规划及仿真[J]. 系统仿真学报, 2021, 33(10): 2440-2448.
[11]	林彬, 韩光辉, 宋晨晨, 张雅静. 基于辐射扫描算法的机器人路径规划与仿真[J]. 系统仿真学报, 2021, 33(1): 84-90.
[12]	朱大奇, 朱婷婷, 颜明重. 基于改进神经网络的多AUV全覆盖路径规划[J]. 系统仿真学报, 2020, 32(8): 1505-1514.
[13]	张倩, 熊英, 何明珂, 张浩. 不确定需求生鲜电商配送路径规划多目标模型[J]. 系统仿真学报, 2019, 31(8): 1582-1590.
[14]	石敏, 魏育坤, 金相臣, 王素琴, 毛天露. 可支持跃层寻径的虚拟场景漫游方法[J]. 系统仿真学报, 2019, 31(7): 1358-1366.
[15]	吉珊珊. 基于增强蚁群算法的传感网移动sink路径规划[J]. 系统仿真学报, 2019, 31(11): 2543-2552.

基于TI-A*的多机器人动态规划协调方法研究

TI-A* Based Multi-robot Dynamic Planning and Coordination Method

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价