Multi-Agent Collaborative Path Planning Algorithm with Multiple Meeting Points

• Published in: Electronics (Basel) 2024-08, Vol.13 (16), p.3347
• Main Authors: Mao, Jianlin, He, Zhigang, Li, Dayan, Li, Ruiqi, Zhang, Shufan, Wang, Niya
• Format: Article
• Language: English
• Subjects: Algorithms; Autonomous underwater vehicles; Collaboration; Cooperation; Efficiency; Energy consumption; Multiagent systems; Path planning; Planning; Strategy; Switching; Unmanned aerial vehicles
• ISSN: 2079-9292; 2079-9292
• DOI: 10.3390/electronics13163347

Traditional multi-agent path planning algorithms often lead to path overlap and excessive energy consumption when dealing with cooperative tasks due to the single-agent-single-task configuration. For this reason, the “many-to-one” cooperative planning method has been proposed, which, although improved, still faces challenges in the vast search space for meeting points and unreasonable task handover locations. This paper proposes the Cooperative Dynamic Priority Safe Interval Path Planning with a multi-meeting-point and single-meeting-point solving mode switching (Co-DPSIPPms) algorithm to achieve multi-agent path planning with task handovers at multiple or single meeting points. First, the initial priority is set based on the positional relationships among agents within the cooperative group, and the improved Fermat point method is used to locate multiple meeting points quickly. Second, considering that agents must pick up sub-tasks or conduct task handovers midway, a segmented path planning strategy is proposed to ensure that cooperative agents can efficiently and accurately complete task handovers. Finally, an automatic switching strategy between multi-meeting-point and single-meeting-point solving modes is designed to ensure the algorithm’s success rate. Tests show that Co-DPSIPPms outperforms existing algorithms in 1-to-1 and m-to-1 cooperative tasks, demonstrating its efficiency and practicality.