Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed and can handle up to thousands of agents, they usually rely on the assumption that each action of the agent takes a time unit, and the actions of all agents are synchronized in a sense that the actions of agents start at the same discrete time step. This assumption in MAPF planners may limit their use in practice, especially when the agent speeds are different or an agent has to vary its speed when going through different edges. To get rid of this assumption, we consider the MAPF with asynchronous actions (MAPF-AA), where different agents may have different duration when going through the same edge, or an agent may take different amount of time when going through diffferent edges.
Loosely Synchronized Search (LSS)
We begin by extending A*-based MAPF planners to handle asynchronous actions. A*-based planners have been extensively investigated. These planners provide guarantees on solution completeness and optimality, and outperforms other types of MAPF planners in certain scenarios. However, existing A*-based methods rely on the assumption of synchronous actions to easily identify “planning steps” for all agents and run A*-like search. For MAPF-AA problem, a naive application of conventional A*-based planners may require too fine a discretization of the time dimension so that a common unit time can be found for planners to identify planning steps. We seek to overcome this challenge by proposing a method called Loosely Synchronized Search (LSS). In this approach, we introduce a new state space which combines the spatial and temporal information of agents for the purpose of describing asynchronous actions. The standard state expansion used in A*-based planners is then generalized to also account for the temporal information. Finally, we use dominance principles from the multi-objective optimization to compare and prune states that cannot lead to an optimal solution. We implement this approach based on both A* and M*, and the resulting LS-A* and LS-M* are complete and can find an optimal solution for MAPF-AA. More on LSS can be found in our paper [1].
Loosely Synchronized Rule-Based Planning (LSRP)
A limitation on LSS is its limited scalability as the number of agents grows. Till now, only a few algorithms were developed to address asynchronous actions in MAPF. Most of these algorithms (including LSS) lie on one end of the spectrum, finding optimal or bounded sub-optimal solutions at the cost of limited scalability as the number of agents grows. We therefore seek to solve MAPF-AA for a large number of agents (e.g. 1000 agents) at the cost of finding unbounded sub-optimal solution paths.
When all agents’ actions are synchronous, the existing MAPF algorithms, such as rule-based planning, they can readily scale up to thousands of agents by finding an unbounded sub-optimal solution. However, extending them to handle asynchronous actions introduce additional challenges: Rule-based planning usually relies on the notion of time step where all agents take actions and plans forward in a step-by-step fashion. When the actions of agents are of various duration, there is no notion of planning steps, and one may have to plan multiple actions for a fast moving agent and only one action for a slow agent. In other words, an action with long duration of an agent may affect multiple subsequent actions of another agent, which thus complicates the interaction among the agents.
To handle the challenges, we leverage both the idea in our prior work LSS in handling asynchronous actions and rule-based planning methods (PIBT) for MAPF to develop a new algorithm Loosely Synchronized Rule-based Planning (LSRP) [2], trading off solution quality for scalability, by finding an unbounded suboptimal solution for many agents. We analyze the theoretic properties of LSRP and show that LSRP guarantees reachability in graphs when the graph satisfies certain conditions. For the experiments, we compare LSRP against several baselines including Continuous-Time Conflict-Based Search and prioritized planning in various maps from a MAPF benchmark, and the results show that LSRP can solve up to an order of magnitude more agents than existing methods with low runtime, despite about 25% longer makespan. Additionally, our asynchronous planning method produces better solutions, whose makespan ranges from 55% to 90% of those planned by ignoring the asynchronous actions. More details can be found in our paper [2].
