The problem is MAPF on a graph with multiple labeled agents, each having a start and a goal location. At every time step, an agent may move to a neighboring vertex or wait, but no vertex may contain more than one agent at the same time. Two agents also may not traverse the same connecting edge in opposite directions simultaneously, although following another agent through successive edges is allowed. The objective is to find a minimum-cost joint sequence of move and wait actions that places every agent at its goal. Ordinary moves and waits cost one, while waiting at an agent's goal costs zero; if the agent later leaves that goal, the accumulated goal-waiting time contributes to the cost of the subsequent move.
The first contribution is a detailed application of enhanced partial expansion A* (EPEA*) to MAPF. EPEA* uses domain-specific knowledge to avoid generating surplus nodes whose evaluation exceeds the cost of an optimal solution. The paper generalizes its application so that pattern databases can be used on top of EPEA*, and the authors describe this as the first reported application of pattern databases to MAPF in the literature at that time. A further contribution is a new optimal MAPF A* variant that combines Standley's operator decomposition with basic partial expansion, called BPEODA* in the supplied evidence. Together, these contributions examine how different ways of controlling successor generation affect optimal MAPF search.
The method distinguishes a node's ordinary evaluation, based on path cost plus heuristic value, from the value currently stored for that node in the open list. When a node is expanded, EPEA* does not generate every joint action and then discard high-valued successors; instead, it generates successors in the relevant increasing-cost categories and keeps only those matching the currently required stored value. For composite agents, the possible evaluation increases of individual operators are combined, and a recursive procedure enumerates combinations that meet the required total increase. Pattern databases are built for agent groups expected to participate in many conflicts, but such groups are not known in advance. The paper therefore uses the independence detection framework: when independence detection joins agents into a group, the method builds pairwise pattern databases for later stages. Basic partial expansion is also applied over operator decomposition: standard nodes use the normal partial-expansion condition, while an intermediate node is retained only when its value equals the stored value of the relevant standard predecessor.
The reported experiment uses a four-connected, obstacle-free 8 by 8 grid with varying numbers of agents. It compares ordinary A*, operator-decomposition A* (ODA*), basic partial-expansion A* (BPEA*), the operator-decomposition/basic-partial-expansion hybrid BPEODA*, EPEA*, and EPEA* augmented with pattern databases. The evaluation considers whether instances can be solved under the resource limit, together with runtime, search-node behavior, and the cost of constructing instance-specific pattern databases. The supplied excerpt says that each instance had a two-minute and two-gigabyte limit, but it does not provide the full instance set, exact timings, exact node counts, or complete implementation details. It also does not establish results on other maps, obstacle configurations, agent distributions, or objective functions.
The reported results say that, except for the most trivial instances, A* and BPEA* could not solve the tested problems within the allocated two minutes and two gigabytes per instance. ODA* was faster than A*, and BPEA* was also faster than A*, but BPEA* incurred overhead by generating surplus nodes and pruning them afterward. BPEODA* significantly outperformed A* and ODA* because it maintained a much smaller open list, making open-list operations cheaper. EPEA* was faster than all of these variants under the reported setting. For hard instances, adding pattern databases produced a significant improvement on top of EPEA*, reported as up to three times on average. The trade-off is that the databases are instance-dependent and their construction time cannot be amortized across all instances; on easier instances, EPEA* with pattern databases was best by node count but not by runtime. These observations support selective use of stronger, more expensive heuristics rather than assuming that preprocessing always improves elapsed time.
Optimal MAPF has attracted substantial attention because interactions among agents make the joint search space much larger than a single-agent pathfinding space. Earlier work introduced operator decomposition, partial-expansion techniques, and other search variants intended to reduce the cost of exploring that space. This paper focuses specifically on A*-based approaches and on using problem structure to avoid unnecessary successor generation. Its perspective is complementary to methods that change the high-level search organization: it improves the behavior of the underlying optimal A* exploration.
The formal input is a graph and a set of labeled agents, each with a start and goal vertex. Agents may move or wait, subject to vertex conflicts and opposite-direction edge conflicts. Both actions normally cost one, except that a wait at an agent's goal costs zero; leaving after goal waiting incorporates the accumulated wait into the move cost. The required output is a minimum-cost joint plan that reaches all goals. The supplied excerpt does not establish any variant beyond this collision model and cost definition.
EPEA* separates the static evaluation of a node from its current open-list value, allowing successor generation to be restricted to the value level that can still matter for an optimal solution. Joint operator choices are handled through their individual evaluation increases, with recursive enumeration of combinations that meet a required sum. Pattern databases are selected dynamically through independence detection rather than by assuming in advance which agents will conflict most. BPEODA* applies basic partial-expansion filtering to the intermediate nodes created by operator decomposition, retaining nodes consistent with the stored value of their standard predecessor.
The explicit test environment is an obstacle-free four-connected 8 by 8 grid, with the number of agents varied. The compared methods are A*, ODA*, BPEA*, BPEODA*, EPEA*, and EPEA* with pattern databases. A resource limit of two minutes and two gigabytes per instance is reported. The supplied evidence does not give the complete benchmark suite, repetitions, hardware details, exact preprocessing accounting, or results for other map families.
A* and BPEA* failed to solve all but the most trivial cases within the stated resource limit. ODA* was faster than A*, while BPEODA* substantially outperformed A* and ODA* by keeping the open list much smaller. EPEA* was faster than the other compared variants in the reported experiment. On hard instances, pattern databases improved EPEA* by up to about three times on average; on easier instances, the EPEA* plus PDB combination used the fewest nodes but was not best in elapsed time because of database construction.
The study argues that avoiding the generation of unnecessary nodes is central to efficient optimal MAPF search. Under the supplied experimental setting, EPEA* outperformed the other compared A* variants. Pattern databases can provide a substantial additional benefit on hard instances, but their instance-specific construction cost can dominate on easy ones. The authors also indicate that a fuller version would present further insights about the earlier techniques, so the excerpt does not establish the scope of those additional conclusions.
The middle portion of the paper is explicitly omitted from the supplied evidence, so the complete EPEA* data structure, successor-generation procedure, and implementation treatment of conflicts are not established here. The experimental summary covers one obstacle-free grid family and does not provide the full benchmark distribution, exact timings, exact node counts, or detailed parameter settings. Pattern-database usefulness depends on identifying groups that participate in many conflicts, while those groups are not known a priori and must be inferred through independence detection. Consequently, the excerpt alone cannot show that the reported ranking or speedups generalize to arbitrary maps, obstacle densities, agent placements, cost models, or MAPF objectives.
The paper is important for showing that optimal MAPF performance depends not only on heuristic values but also on controlling which successors are generated at all. Its combination of EPEA*, pattern databases, independence detection, and operator decomposition provides a concrete design pattern for reducing node generation and open-list overhead. The contrast between node-count improvements and runtime improvements also gives a practical warning: a stronger heuristic can reduce search effort while still being disadvantageous when its construction cost is included.
This paper is useful for researchers studying optimal MAPF, A* variants, partial expansion, operator decomposition, and pattern-database heuristics. It is especially suitable for understanding how low-level successor-generation choices affect open-list size and runtime. Researchers focused on large-scale deployment, bounded-suboptimal MAPF, stochastic environments, or alternative cost models should treat the supplied evidence as insufficient and seek the full paper and broader evaluations.