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

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 leader’s path by maximizing the spatial separation of inter-group and minimizing spatiotemporal overlap. The agents within each group, referred to as followers, 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.