Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions

Multi-agent path finding (MAPF) determines an ensemble of collision-free paths for multiple agents between their respective start and goal locations. Among the available MAPF planners for workspace modeled as a graph, A*-based approaches have been widely investigated due to their guarantees on completeness and solution optimality, and have demonstrated their efficiency in many scenarios. However, almost all of these A*-based methods assume that each agent executes an action concurrently in that all agents start and stop together. This article presents a natural generalization of MAPF with asynchronous actions (MAPF-AA) where agents do not necessarily start and stop concurrently. The main contribution of the work is a proposed approach called Loosely Synchronized Search (LSS) that extends A*-based MAPF planners to handle asynchronous actions. We show LSS is complete and finds an optimal solution if one exists. We also combine LSS with other existing MAPF methods that aims to trade-off optimality for computational efficiency. Numerical results are presented to corroborate the performance of LSS and the applicability of the proposed method is verified in the Robotarium, a remotely accessible swarm robotics research platform.

I. Introduction

Multi-agent path finding (MAPF), as its name suggests, computes a set of collision-free paths for multiple agents from their respective starts to goal locations. Most MAPF methods [20] describe the workspace as a graph, where vertices represent possible locations of agents and edges are actions that move agents between locations. Conventional MAPF planners [5], [20], including our own [22], typically consider the case where each agent executes an action concurrently in that all agents start and stop together. The requirement of such synchronized actions among agents limits the application of MAPF planners to scenarios where agents move with different speeds. This paper considers a natural generalization of the MAPF with the agents’ actions running asynchronously, meaning they do not necessarily start and stop concurrently. We refer to this generalization as MAPF with asynchronous actions (MAPF-AA). In MAPF-AA, different actions by agents may require different time durations to complete. See Fig. 1 for a toy example.