Vein-Based Coalitions for Multi-Agent Pattern Formation Tasks
Zhehong Zhang, Songhao Piao · IEEE Robotics and Automation Letters · 2022
This letter explores the vein trait of the structural formation task and extracts four typical parallel-straight vein structures for generating coalitions. Then, the Vein-Based Multi-Agent Pattern Formation (VB-MAPF) method is proposed to resolve task and path planning on coalitions. Besides, the presented rectifying operation guarantees the optimal coalition structure, and the vein-based pruned conflict-based search reduces the searching space for collision-free path planning. Compared with typical solvers, the inter-performance and the intra-performance orders show the efficiency and scalability of the VB-MAPF method in terms ofmakespan,average distance, andmaximum distanceon dozens of coalitions and thousands of agents.