Table Of Links
VI. RESULTS OF DECOMPOSITION’S APPLICATION
VII. CONCLUSION, ACKNOWLEDGMENTS AND REFERENCES
VI. RESULTS OF DECOMPOSITION’S APPLICATION
In this section, we evaluate the influence of decomposing MAPF instances on various MAPF methods, including EECBS, PBS, LNS, HCA∗ (serial MAPF method), and Push and Swap, PIBT+, LaCAM (parallel MAPF method). We refer to the methods with decomposition of MAPF instances as the ”layered” versions of the raw MAPF methods. To maintain consistency, we utilize the same MAPF instances as in Section V to analyze how decomposition affects their application. We assess decomposition’s impact in terms of time cost, memory usage, success rate, sum of cost, and makespan. The default configurations of these MAPF methods are used in our experiments.
As a common rule in solving MAPF instances, we set an upper bound on the time cost (30 seconds). Methods that are complete but fail to find a solution within the limited time are considered as failed. Additionally, methods that run out of memory space are also considered as failed.
A. Explicit Estimation CBS
Explicit Estimation CBS (EECBS) [4] stands out as one of the state-of-the-art CBS-based MAPF methods, characterized by its completeness and bounded suboptimality. Beyond its explicit estimation in high-level search, EECBS also incorporates conflict resolution techniques such as bypassing conflicts, prioritizing conflicts, symmetry reasoning, and weighted dependency graphs to reduce the time cost of CBS. Further details can be found in Section II. EECBS’s code 3 operates by
searching each agent’s path separately and provides interfaces to avoid conflicts with external paths, rendering it a serial MAPF method. In its layered version, which we refer to as ”layered EECBS,” previous subproblems’ paths and subsequent subproblems’ starts are set as constraints.
As illustrated in Fig. 5, on average, layered EECBS exhibits lower time costs (1.0 × 104 ms < 1.5 × 104 ms), leading to a higher success rate (0.77 > 0.64). The time cost of decomposition is relatively small compared to the time cost of solving the MAPF instance. Regarding memory usage, layered EECBS consumes less memory space compared to raw EECBS (12 MB < 24 MB). Decomposition of the MAPF instance significantly reduces the growth of the conflict tree’s size by decreasing the number of agents solved simultaneously.
In terms of path quality, layered EECBS yields a larger makespan (layered EECBS: 2.5×102 , raw EECBS: 2.0×102 ), resulting in a larger sum of costs (layered EECBS: 5.0 × 104 , raw EECBS: 3.4 × 104 ). In maps where both raw EECBS and layered EECBS achieve a success rate close to 1 (e.g., map 1, 8, 10, 19, 21 and 22), both methods exhibit similar makespan and sum of costs. However, in maps where raw EECBS has a lower success rate compared to layered EECBS (e.g., map 4, 16, 17 and 24), layered EECBS demonstrates a larger makespan and sum of costs, as depicted in Fig. 6.
This phenomenon can be attributed to two factors: Firstly, solving all agents together provides more opportunities to find shorter solutions than solving them separately. Secondly, raw EECBS struggles to find longer solutions, particularly in maps where its success rate is lower. In summary, layered EECBS boasts explicit advantages in terms of time cost, memory usage, and success rate compared to raw EECBS. Additionally, in maps where both methods achieve a high success rate, their solutions tend to be similar. However, layered EECBS outperforms raw EECBS in finding longer solutions when the latter fails to do so.
B. Priority Based Search
Priority Based Search (PBS) [11] is an incomplete, suboptimal, and priority-based MAPF method. Conceptually, when faced with a collision, PBS greedily chooses which agent should be given higher priority. It backtracks efficiently and explores other branches only if there is no solution in the current branch. PBS searches each agent’s path separately and it’s code4 provides interfaces to avoid conflicts with external paths, making it a serial MAPF method. In its layered version, which we refer to as ”layered PBS,” we set previous subproblems’ paths and subsequent subproblems’ starts as constraints.
As shown in Fig. 5, on average, layered PBS has a lower time cost (1.2 × 104 ms < 2.0 × 104 ms) and thus a higher success rate (0.75 > 0.42). The time cost of decomposition is relatively small compared to the time cost of solving the MAPF instance. In terms of memory usage, layered PBS has lower memory usage compared to raw PBS (1.0 MB < 3.9 MB) because decomposition of the MAPF instance reduces the complexity of the priority tree significantly.
When it comes to path quality, layered PBS has a larger makespan (2.5 × 102 > 1.3 × 102 ) and thus a larger SOC (5.5 × 104 > 1.7 × 104 ). Similar to EECBS, raw PBS finds it difficult to find longer solutions and can only finds shorter solutions, resulting in lower success rates for maps where raw PBS struggles (e.g., map 4, 6, 16 and 17). For maps where both methods have high success rates (e.g., map 1, 9 and 10), they have similar makespan and SOC, as shown in Fig. 6.
In summary, layered PBS has explicit advantages in time cost, memory usage, and success rate compared to raw PBS. Additionally, layered PBS produces solutions similar to raw PBS’s solutions on maps where both methods have success rates close to 1. Furthermore, layered PBS achieves a higher success rate in finding long solutions when raw PBS fails.
C. Large Neighborhood Search 2
Large Neighborhood Search 2 (LNS2) [7] is a complete and suboptimal MAPF method that starts from a set of paths with collisions and repeatedly replans subsets of paths to reduce the overall number of collisions until the paths become collision-free. LNS2 updates each agent’s path separately, and its code5 provides interfaces to avoid conflicts with external paths, making it a serial MAPF method.
As shown in Fig. 5, on average, layered LNS2 has a lower time cost (1.0 × 104 ms < 1.4 × 104 ms) and thus a higher success rate (0.76 > 0.55). In terms of memory usage, layered LNS2 has lower memory usage compared to raw LNS2 (2.4 MB < 32 MB). Due to the decomposition of the MAPF instance, other agents’ paths are considered as dynamic obstacles and do not join conflict resolve, resulting in layered LNS2 requiring fewer repair actions to fix conflicts between agents’ paths.
Regarding path quality, layered LNS2 has a larger makespan (2.5 × 102 > 2.1 × 102 ) and SOC (5.1 × 104 > 3.4 × 104 ). Similar to EECBS and PBS, raw LNS2 struggles to find longer solutions and can only discovers shorter solutions, particularly in maps where raw LNS2 has a lower success rate (e.g., map 12 and 16). For maps where both methods have similar success rates (e.g., map 1, 2, 8, 21 and 22), raw LNS2 and layered LNS2 have similar makespan and SOC, as shown in Fig. 6.
In summary, layered LNS2 exhibits explicit advantages in time cost, memory usage, and success rate compared to raw LNS2. Additionally, layered LNS2 produces solutions similar to raw LNS2’s solutions in maps where both methods have success rates close to 1. Furthermore, layered LNS2 achieves a higher success rate in finding long solutions when raw LNS2 cannot.
D. Push and Swap
Push and Swap (PAS) [10] is a suboptimal and complete rule-based MAPF method. The algorithm employs two primitives: a “push” operation where agents move towards their goals until no progress can be made, and a “swap” operation that allows two agents to exchange positions without affecting other agents’ configurations.
For each agent in the MAPF instance, the algorithm uses “push” to move the agent toward its goal along the shortest path until encountering another agent. Then, it employs “swap” to exchange their positions without altering other agents’ positions. If a “swap” fails, the problem is deemed unsolvable. The algorithm alternates between ”push” and “swap” operations until all agents reach their targets.
Push and Swap updates agents’ paths simultaneously (via an action called “MULTIPUSH”, which moves a set of adjacent agents simultaneously), and its code6 provides no interfaces to avoid conflicts with external paths and ensures that the same state of agents does not occur twice in the solution, making it a parallel MAPF method. In its layered version, referred to as ”layered Push and Swap” or ”layered PAS,” we set previous subproblems’ targets and subsequent subproblems’ starts as static obstacles. Subsequently, we merge subproblems’ solutions by adding wait actions after solving all subproblems.
As shown in Fig. 5, on average, layered PAS consumes less time (4.6 × 103 ms < 8.8 × 103 ms) and memory space (6.2 MB < 70 MB) than raw PAS, resulting in a higher success rate (0.95 > 0.82). Decomposing the MAPF instance enables layered Push and Swap to solve subproblems separately, requiring fewer “push” and “swap” actions. However, the number of “push” and “swap” actions grows exponentially as the number of agents increases. Regarding path quality, as PAS is a parallel MAPF method, the addition of wait actions to merge subproblems’ solutions, layered PAS has a larger makespan (1.0 × 104 > 6.1 × 103 ) and SOC (3.6 × 106 > 2.4 × 106 ) compared to raw PAS.
In summary, layered Push and Swap consume less time and memory space than raw Push and Swap, resulting in a higher success rate. However, the introduction of wait actions to merge subproblems’ solutions leads to a larger makespan and SOC compared to raw Push and Swap.
E. Hierarchical Cooperative A∗
Hierarchical Cooperative A* (HCA*) [17] is a suboptimal and incomplete prioritized MAPF algorithm that decouples into a series of single-agent searches. The individual searches are performed in three-dimensional space-time, taking into account the planned routes of other agents. Essentially, HCA* decomposes the MAPF instance into subproblems that involve only one agent. HCA* also calculates a distance table for each agent to determine their priority.
HCA* searches each agent’s path separately, making it a serial MAPF method. But the code7 for HCA* provides no interfaces to set external paths as dynamic obstacles to avoid. We updated its code to enable it to set external paths as dynamic obstacles. On average, layered HCA* has a slightly higher time cost than raw HCA* (1.3 × 104 ms > 1.1 × 104 ms) and a similar success rate (layered HCA*: 0.68, raw HCA*: 0.64) as HCA* solves each agent separately, and decomposition does not improve the efficiency of HCA*. However, layered HCA* requires less memory space than raw HCA* (2.9×102 MB < 5.4×102 MB), as layered HCA* only stores the distance table of the current subproblem’s agents, while raw HCA* needs to store the distance table of all agents.
Regarding path quality, layered HCA* has a slightly larger makespan (2.4 × 102 > 2.1 × 102 ) and SOC (4.6 × 104 > 3.8×104 ). Because HCA* solves agents in order of decreasing distance to the target, raw HCA* solves agents with longer paths first, limiting the makespan of these agents’ solutions, while layered HCA* breaks this order as agents with long paths may not be in the same subproblem and may not be solved first.
In summary, layered HCA* shows little improvement compared to raw HCA* and has slightly worse solutions because HCA* has a fixed priority and solves each agent separately. However, layered HCA* has an advantage in memory usage, as it only needs to store the distance table of the current subproblem’s agents rather than all agents.
F. Priority Inheritance with Backtracking+
Priority Inheritance with Backtracking+ (PIBT+) [15] is an incomplete and suboptimal MAPF algorithm. Its high level assigns a unique priority to each agent at every timestep, while its low level moves each agent one step at every timestep. Consequently, all intermediate states are saved until all agents reach their targets. PIBT+ avoids the occurrence of the same state of agents twice in the solution. And the code8 for PIBT+ provides no interfaces to avoid conflicts with external paths, making it a parallel MAPF method.
In general, layered PIBT+ takes more time than raw PIBT+ (2.0 × 103 ms > 6.9 × 102 ms). As mentioned in Section V, the decomposition of MAPF instances with 800 to 1000 agents may cost 1s to 3s, and these instances play a major role in contributing to the mean time cost of the MAPF method. Although decomposition reduces the time cost of PIBT+, the time cost of decomposition offsets the reduced time cost and thus increases the overall time cost.
Layered PIBT+ has a similar success rate compared to raw PIBT+ (layered PIBT+: 0.99, raw PIBT+: 0.99), as both layered PIBT+ and raw PIBT+ typically take less than 30s in most cases. In terms of memory usage, layered PIBT+ requires less memory space than raw PIBT+ (6.8 MB < 18 MB), as decomposition reduces the number of intermediate states by reducing the number of agents solved simultaneously.
Regarding solution quality, as PIBT+ is a parallel MAPF method, layered PIBT+ introduces extra wait actions, resulting in solutions with higher makespan (9.5 × 103 > 4.3 × 102 ) and SOC (3.1 × 106 > 1.2 × 105 ) compared to raw PIBT+’s solutions. In summary, layered PIBT+ shows little improvement compared to raw PIBT+ and has worse solutions due to the introduction of wait actions when merging solutions. However, layered PIBT+ has an advantage in memory usage, as it reduces the number of intermediate states by reducing the number of agents solved simultaneously.
G. Lazy Constraints Addition for MAPF
Lazy Constraints Addition for MAPF (LaCAM) [13] is a complete and suboptimal method. More details about LaCAM can be found in Section II. LaCAM avoids the occurrence of the same state of agents twice in the solution. The code9 for LaCAM provides no interfaces to avoid conflicts with external paths, making it a parallel MAPF method.
In general, layered LaCAM has slightly lower time cost than raw LaCAM (3.6 × 103 ms < 3.8 × 102 ms). Similar to PIBT+, the decomposition of MAPF instances with 800 to 1000 agents may cost 1s to 3s, and these instances play a major role in determining the time cost of the MAPF method. Although decomposition reduces the time cost of LaCAM, the time cost of decomposition offsets the reduced time cost, resulting in no significant difference in the overall time cost.
Layered LaCAM has a slightly better success rate compared to raw LaCAM (layered LaCAM: 0.93, raw LaCAM: 0.88), as both layered LaCAM and raw LaCAM typically take less than 30s in most cases. In terms of memory usage, layered LaCAM requires less memory space than raw LaCAM (12 MB < 18 MB), as decomposition reduces the number of intermediate states by reducing the number of agents solved simultaneously.
Regarding solution quality, layered LaCAM introduces extra wait actions, resulting in solutions with higher makespan (9.3 × 103 > 3.2 × 102 ) and SOC (3.1 × 106 > 8.6 × 104 ) compared to raw LaCAM’s solutions.
In summary, layered LaCAM shows little improvement compared to raw LaCAM and has worse solutions due to the introduction of wait actions when merging solutions. However, layered LaCAM has an advantage in memory usage, as it reduces the number of intermediate states by reducing the number of agents solved simultaneously.
H. Summary
On average, decomposition of MAPF instances significantly reduces the memory usage of all seven methods and also decreases the time cost for EECBS, PBS, LNS2, Push and Swap. Layered MAPF methods exhibit higher success rates compared to raw MAPF methods, particularly for serial MAPF methods, with the exception of HCA*, an incomplete prioritized method that solves agents one-by-one.
Regarding solution quality, the layered version of serial MAPF methods generally exhibits similar quality compared to the raw version. However, the layered version of parallel MAPF methods tends to produce worse solutions due to the insertion of numerous wait actions during solution merging. This disparity arises from the fact that serial MAPF methods treat external paths as dynamic obstacles to avoid, while parallel MAPF methods do not.
In conclusion, decomposition of MAPF instances is most advantageous for serial MAPF methods, resulting in reduced time cost and memory usage without significantly sacrificing solution quality. For parallel MAPF methods, decomposition reduce memory usage significantly but often leads to worsened solutions without notable improvements in time cost. Moreover, serial MAPF methods (e.g., EECBS, LNS2) generally demand more time compared to parallel MAPF methods (e.g., LaCAM and PIBT+), yet they yield higherquality solutions.. Notably, serial MAPF methods frequently fail due to time constraints, while parallel MAPF methods tend to fail due to memory limitations.
The observed discrepancy can be attributed to the differing search algorithms utilized: serial methods repeatedly search for complete paths. However, they employ memory-efficient data structures such as priority trees or conflict trees to store knowledge about resolving conflicts. In contrast, parallel methods store previous conflict-solving knowledge as intermediate states to avoid searching for the complete path of agents repeatedly. However, they may exhaust memory resources under complex MAPF instances.
Authors:
- Zhuo Yao
- Wei Wang
This paper is