Hierarchical scheduling based multi-robot path planning for pass terrain

被引：0

作者：

Zhang K. ^{[1
]}

Mao J. ^{[2
]}

Xuan Z. ^{[2
]}

Xiang F. ^{[2
]}

Fu L. ^{[2
]}

机构：

[1] Faculty of Mechanical and Electrical Engineering, Kunming University of Science and Technology, Kunming

[2] Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming

来源：

Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS | 2024年 / 30卷 / 01期

基金：

中国国家自然科学基金;

关键词：

genetic algorithms; multi-robot; pass terrain; path planning; scheduling order;

D O I：

10.13196/j.cims.2021.0648

中图分类号：

学科分类号：

摘要：

Aiming at the high coupling of multi-robot paths in pass terrain, a hierarchical multi-robot path planning and optimization algorithm was constructed by introducing the idea of scheduling order optimization. In the optimization layer, the genetic algorithm was responsible for generating the scheduling order of each robot, and evolving the scheduling order according to the fitness. Then, in the planning layer, the Improved Hierarchical Cooperative A∗ (IHCA∗ ) algorithm was used to find paths according to the scheduling order from the optimization layer, and the solutions was returned to the optimization layer to update the fitness of the scheduling order. Accordingly, by the cooperation between the upper and lower layers, the success rate of problem solving was improved and the path costs were reduced. In addition, a search fuse mechanism was proposed to avoid the repeated invalid search of original HCA∗ algorithm in the pass terrain, which could further improve the solving efficiency. The results showed that the proposed algorithm had performance of higher success rate and less solution costs in high coupling pass terrain. © 2024 CIMS. All rights reserved.

引用

页码：172 / 183

页数：11

共 33 条

[1]

SHI Wei, FENG Yanghe, CHENG Guangquan, Et al., Research on multi-aircratt cooperative air combat method based on deep reinforcement learning, Acta Automata Sinica, 47, 7, pp. 1610-1623, (2021)

[2]

LI J Y, SURYNEK P, FELNER A, Et al., MuM-agent path tïnding for large agents, Proceedmgs of the AAAI Conference on Artificial Intelligence, 1, pp. 7627-7676, (2019)

[3]

YU J, LAVALLE S., Optmal muMrobot path pmrmi g on graphs: compete aggorithms and effective heuristïcs, IEEE Transactions on Robots, 32, 5, pp. 1163-1177, (2016)

[4]

LI J, RAN M, XIE L., Efficient trajectory pknnmg for muh-ple non-holonomïc moble robots va a prioritized trajectory opt-mization, IEEE Robots and Automation Letters, 6, 2, pp. 4055-412, (2020)

[5]

MORRIS R, PASAREANU C, LUCKOW K, Et al., Planning, schedutng and monitoring for arport surface operatoins, Proceedïngs of the AAAI Conference on Arml Inteltgence (AAAI), (2016)

[6]

MA H, HONIG W, COHEN L, Et al., Overvïew: A herar-chïcal framework for pLm generation and executïon tn multi-robot systems [J], IEEE Intelhgent Systems, 32, 6, pp. 6-12, (2017)

[7]

MA H., Target asrgnment and path planmng for navigation tasks with teams of agents, (2020)

[8]

YU J, LAV ALLE S., Planmng optimal paths for muMp! robots on graphs, Proceedmgs of 2013 IEEE International Conference on Robotïcs and Automaton (ICRA), pp. 3612-3617, (2013)

[9]

SURYNEK P., Tïme-expanded graph-based propositional en-codïngs for makespan-optïmal solvïng of cooperatïve path find-ïng probeems[J], Annals of Mathematics and Artiricial Intel-gence, 81, 3, pp. 329-3755, (2017)

[10]

HART P, NILSSON N, RAPHAEL B., A formal bas! for the heuristic determïnatïon of minimum cost paths, IEEE Transactïons on Systems Stence and Cybernetics, 19, pp. 100-107

← 1 2 3 4 →