TaskSimLF: Efficient Leader-Follower Multi-Agent Path Finding With Clustered Pickup and Delivery

Abstract

Multi-Agent Path Finding (MAPF) aims at finding a set of conflict-free and cost-optimal paths for agents from pickup to delivery locations. Most existing MAPF research focus on exhaustively search for path set for the agents with conflict-free paths, which often results in high computational costs. In this letter, we aim to accelerate the path-finding process by considering the distribution of pickup-delivery pairs and leveraging task similarity. We propose TaskSimLF, a task-similarity based leader-follower path finding method. Specifically, the algorithm first employs an adaptive clustering of tasks to group them based on spatial similarity. For each group, we generate the representative <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">leader</i>’s path by maximizing the spatial separation of inter-group and minimizing spatiotemporal overlap. The agents within each group, referred to as <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">followers</i>, find their paths by following the leader's trajectory, using topological features of the leader's path to reduce intra-group conflicts. Experimental results demonstrate that our proposed algorithm shows superior performance while significantly improves runtime efficiency with fewer node expansion in different map scenarios.