Multi-agent Path Planning with Obstacle Penalty Factor

Authors

Xingyu Yan, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, ChinaFollow
Dayan Li, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, ChinaFollow
Niya Wang, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
Kaixiang Zhang, Faculty of Mechanical and Electrical Engineering, Kunming University of Science and Technology, Kunming 650500, China
Jianlin Mao, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China

Abstract

Abstract: In light load environments, complex obstacle areas will exacerbate local conflicts between agents, leading to a decrease in path solving efficiency. This paper proposes a multi-agent path planning (MAPF) method with obstacle penalty factors in light load environments. First, in the low-level single machine planning process based on the conflict-based search (CBS) algorithm framework, by judging the distribution type of surrounding obstacles that are about to expand the agent's position, corresponding obstacle penalty factors are assigned to them; then, the penalty factors in the path planning process are accumulated and used as the heuristic value of single machine planning to select the path; finally, combined with the upper-level conflict resolution strategy of the CBS algorithm framework, MAPF and conflict coordination are performed. The results show that in a light load environment with a 10% obstacle distribution, the proposed algorithm has a solving time of about 81.38%~83.67% of that of the CBS algorithm, and the expansion amount of the constraint tree (CT) is 60.14%~71.66% of that of the CBS algorithm. Simulation in Gazebo has shown that this method can reduce the number of passes through complex obstacle areas.

Recommended Citation

Yan, Xingyu; Li, Dayan; Wang, Niya; Zhang, Kaixiang; and Mao, Jianlin (2024) "Multi-agent Path Planning with Obstacle Penalty Factor," Journal of System Simulation: Vol. 36: Iss. 3, Article 12.
DOI: 10.16182/j.issn1004731x.joss.23-0397
Available at: https://dc-china-simulation.researchcommons.org/journal/vol36/iss3/12

First Page

673

Last Page

685

CLC

TP242; TP18

Recommended Citation

Yan Xingyu, Li Dayan, Wang Niya, et al. Multi-agent Path Planning with Obstacle Penalty Factor[J]. Journal of System Simulation, 2024, 36(3): 673-685.

Corresponding Author

Li Dayan

DOI

10.16182/j.issn1004731x.joss.23-0397