改进A*的多机器人双层路径规划算法

doi:10.3778/j.issn.1002-8331.2203-0197

摘要/Abstract

摘要： 为了得到多机器人的高质量无碰撞路径，提出一种基于改进A*算法和冲突协调策略的多机器人双层规划算法。在算法的第一层，通过引入结合路径信息的动态权重因子改进传统A*算法的启发函数，避免其盲目搜索，从而加快搜索速度；通过筛选机制和Bezier曲线，减少机器人实际转弯次数并平滑路径，进而得到单机器人的初始路径。在算法的第二层，在二维路径基础上引入时间维度，建立机器人路径时间图，从而预测机器人之间的冲突。通过冲突协调策略对机器人与机器人之间、机器人与动态障碍物之间产生的冲突进行协调。实验结果表明，双层规划算法能够有效地减少路径搜索时间和转弯次数，得到各机器人平滑无碰撞的导航路径。

关键词: 多机器人, 路径规划, 改进A*算法, 冲突协调策略

Abstract: In order to obtain the high-quality collision free path of multi-robots, a multi-robot bilevel programming algorithm based on improved A* algorithm and conflict coordination strategy is proposed. Firstly, in the first layer of the algorithm, the heuristic function of the traditional A* algorithm is improved by introducing the dynamic weight factor combined with planned path information to avoid its blind search, so as to speed up the search speed. Through the screening mechanism and Bezier curve, the actual turning times of the robot are reduced and planned path is smoothed, and then the initial path of a single robot is obtained. Secondly, in the second layer of the algorithm, the time dimension is introduced based on the two-dimensional path to establish the robot path time map, so as to predict the conflict between robots. Finally, the conflict coordination strategy is used to coordinate the conflicts between robots and between robots and dynamic obstacles. The experimental results show that the bilevel programming algorithm can effectively reduce planned path search time and the number of turns, and obtain the smooth and collision free navigation path of each robot.

Key words: multi-robot, path planning, improved A* algorithm, conflict coordination strategy

陈光友, 余粟. 改进A*的多机器人双层路径规划算法[J]. 计算机工程与应用, 2023, 59(11): 312-319.

CHEN Guangyou, YU Su. Improved A* Multi-Robot Bilevel Path Planning Algorithm[J]. Computer Engineering and Applications, 2023, 59(11): 312-319.

参考文献

[1] WANG X D，ZHANG H W，LIU S，et al.Path planning of scenic spots based on improved A* algorithm[J].Scientific Reports，2022，12（1）：1320.
[2] LI Y，LIU F.Path planning algorithm for mobile robot based on improved ant colony algorithm[J].Journal of Physics：Conference Series，2021，2083（4）：042033.
[3] 黄书召，田军委，乔路，等.基于改进遗传算法的无人机路径规划[J].计算机应用，2021，41（2）：390-397.
HUANG S Z，TIAN J W，QIAO L，et al.Unmanned aerial vehicle path planning based on improved genetic algorithm[J].Journal of Computer Applications，2021，41（2）：390-397.
[4] 张中伟，张博晖，代争争，等.基于动态优先级策略的多AGV无冲突路径规划[J].计算机应用研究，2021，38（7）：2108-2111.
ZHANG Z W，ZHANG B H，DAI Z Z，et al.Multi-AGV conflict-free path planning based on dynamic priority strategy[J].Application Research of Computers，2021，38（7）：2108-2111.
[5] 琚泽立，杨博，孙浩飞，等.面向电力智能巡检的多机器人系统协同路径规划算法[J].智慧电力，2020，48（6）：92-97.
JU Z L，YANG B，SUN H F，et al.Cooperative path planning of multi-robot system for power grid intelligent inspection[J].Smart Power，2020，48（6）：92-97.
[6] 赵萍，雷新宇，陈波芝，等.基于TI-A*的多机器人动态规划协调方法研究[J].系统仿真学报，2019，31（5）：925-935.
ZHAO P，LEI X Y，CHEN B Z，et al.TI-A* based multi-robot dynamic planning and coordination method[J].Journal of System Simulation，2019，31（5）：925-935.
[7] SHI J，SU Y，BU C，et al.A mobile robot path planning algorithm based on improved A[J].Journal of Physics：Conference Series，2020，1486（3）：032018.
[8] 张超超，房建东.基于定向加权A*算法的自主移动机器人路径规划[J].计算机应用，2017，37（S2）：77-81.
ZHANG C C，FANG J D.Path planning of autonomous mobile robot based on directional weighted A* algorithmm[J].Journal of Computer Applications，2017，37（S2）：77-81.
[9] ZHANG L，LI Y.Mobile robot path planning algorithm based on improved A star[J].Journal of Physics：Conference Series，2021，1848（1）：012013.
[10] 曹如月，张振乾，李世超，等.基于改进A*算法和Bezier曲线的多机协同全局路径规划[J].农业机械学报，2021，52（S1）：548-554.
CAO R Y，ZHANG Z Q，LI S C，et al.Multi-machine cooeration global path planning based on A-star algorithm and Bezier curve[J].Transactions of the Chinese Society of Agricultural Machinery，2021，52（S1）：548-554.
[11] 杨世团，于宝成，吴云韬.动态仓储环境下的多机器人路径规划方法[J].计算机应用与软件，2022，39（3）：56-62.
YANG S T，YU B C，WU Y T.Multi-robot path planning method in dynamic storage environment[J].Computer Applications and Software，2022，39（3）：56-62.
[12] 夏清松，唐秋华，张利平.多仓储机器人协同路径规划与作业避碰[J].信息与控制，2019，48（1）：22-28.
XIA Q S，TANG Q H，ZHANG L P.Cooperative path planning and operation collision avoidance for multiple storage robots[J].Information and Control，2019，48（1）：22-28.
[13] DAS P K，BEHERA H S，JENA P K，et al.An intelligent multi-robot path planning in a dynamic environment using improved gravitational search algorithm[J].International Journal of Automation and Computing，2021，18（6）：1032-1044.
[14] 晁永生，孙文磊.动态修改路径的多机器人路径规划[J].机械科学与技术，2018，37（10）：1483-1488.
CHAO Y S，SUN W L.Dynamic path modification for multi-robot path planning[J].Mechanical Science and Technology for Aerospace Engineering，2018，37（10）：1483-1488.
[15] PU Y，SHI Y，LIN X，et al.C2-continuous orientation planning for robot end-effector with b-spline curve based on logarithmic quaternion[J].Mathematical Problems in Engineering，2020，2020：2543824.
[16] SONG B，WANG Z，ZOU L.An improved PSO algorithm for smooth path planning of mobile robots using continuous high-degree Bezier curve[J].Applied Soft Computing，2021，100：106960.
[17] ZHANG J H，FENG Q，ZHAO A D，et al.Local path planning of mobile robot based on self-adaptive dynamic window approach[J].Journal of Physics：Conference Series，2021，1905（1）：012019.