The paper studies optimal state-space search guided by an admissible heuristic, with particular attention to domains in which a node has many applicable operators. Standard A* generates the children of an expanded node and adds frontier candidates to OPEN, so children that are not immediately needed for an optimal solution may still consume time and memory. The paper calls nodes whose cost exceeds the optimal-solution cost surplus nodes. Partial Expansion A* avoids retaining surplus nodes in OPEN, but it still generates all children before deciding which ones are needed. EPEA* addresses that remaining generation cost by selecting appropriate operators before their children are generated.
The main contribution is a refinement of Partial Expansion A* that moves partial expansion from post-generation filtering to pre-generation operator selection. EPEA* uses prior knowledge about a domain and its heuristic in an Operator Selection Function, or OSF, to identify operators producing children with the evaluation value currently required by the search. The paper studies full-checking, direct-computation, and hybrid OSFs, and develops OSFs based on pattern databases and additive pattern databases. It also extends the principle to iterative-deepening A*, producing Enhanced Partial Expansion IDA*, and provides theoretical analyses intended to explain when the additional computation is worthwhile.
When EPEA* expands a node, it does not immediately turn every applicable operator into a child node. Its OSF first identifies the operators whose children have the evaluation value currently required by the search. Only those children are generated and inserted into OPEN; the parent is reinserted with the next relevant value so that later children can be produced in the same search order without materializing surplus children. A full-checking OSF examines candidate operators, a direct-computation OSF derives the needed operators from domain-specific structure, and a hybrid OSF combines the two strategies. For additive pattern databases, the OSF combines contributions from several abstractions, and needed entries can be computed lazily when a node is first expanded. EPEIDA* applies analogous threshold-based selection within IDA* iterations.
The reported evaluation covers standard benchmark domains including the 15-puzzle, pancake puzzle, Rubik’s cube, single-agent pathfinding, and multi-agent pathfinding. The comparisons include A*, IDA*, PEA*, EPEA*, and variants using different heuristics or OSFs, although the supplied excerpt does not establish every comparison condition or every dataset detail. In the MAPF study, 1,000 instances place agents on an obstacle-free, four-connected 8-by-8 grid; all variants run in an iterative-deepening framework and receive a limit of two minutes and two gigabytes of memory per instance. Results are grouped by the number of agents, and the reported measures include node performance, runtime, and memory performance. The MAPF comparison specifically includes EPEA* with the SIC heuristic and EPEA* with an additive-pattern-database-based OSF.
The reported results show substantial runtime and memory improvements for EPEA* and EPEIDA* on several standard benchmark applications, and the conclusion describes their runtime performance as state of the art on the reported domains. For difficult MAPF instances, EPEA* with the additive-pattern-database OSF is described as the clear winner and runs up to three times faster than EPEA* using the SIC heuristic. The advantage is not unconditional: partial expansion does not always make OPEN smaller, and a particular MAPF construction can cause PEA* and EPEA* to maintain a much larger OPEN than A*. Performance depends on average branching factor, implementation costs of ordinary A* and IDA*, OSF cost, and domain- and heuristic-dependent parameters. EPEA* is therefore a specialized optimization whose benefit depends on whether selecting operators costs less than generating and managing surplus children.
A* selects frontier nodes using an evaluation formed from the cost already incurred and a heuristic estimate. With an admissible, non-overestimating heuristic, it is guaranteed to find an optimal solution; IDA* and RBFS are related state-space search methods. Partial Expansion A* saves memory by placing only children with the currently needed evaluation value into OPEN and reinserting the parent with the best discarded value. This leaves the cost of generating and inspecting all children, which is the time overhead that motivates EPEA*.
The central problem is the surplus-node effect. A node with a large branching factor can produce many children whose evaluation values exceed the cost of an optimal solution, so they are not immediately useful to an optimal best-first search. Standard A* may nevertheless generate them and add them to OPEN, causing runtime and memory growth. PEA* removes much of the storage burden but still pays for generating every child. The challenge is to preserve the search order and optimality of partial expansion while identifying useful operators without first constructing every child.
EPEA* uses an OSF to select, before child creation, the applicable operators that produce the required evaluation increment. Full-checking OSFs inspect candidate operators, direct-computation OSFs derive the needed candidates from domain-specific knowledge, and hybrid OSFs combine the approaches. Pattern databases represent abstractions that retain only selected state variables, while additive pattern databases combine contributions from multiple abstractions. In the MAPF additive-PDB OSF, needed difference-PDB entries are computed lazily at a node’s first expansion if they are not already available.
The paper reports OSF studies that begin with comparatively simple domains and progress to pattern-database and additive-pattern-database constructions. The domains named in the supplied material include the 15-puzzle with the Manhattan-distance heuristic, the pancake puzzle with a GAP heuristic, Rubik’s cube, single-agent pathfinding, and MAPF. For MAPF, six A*-variants are compared in terms of nodes and time, with two EPEA* configurations: one using SIC and one using an additive-PDB OSF. The MAPF instances use an obstacle-free four-connected 8-by-8 grid, total 1,000 instances, per-instance limits of two minutes and two gigabytes, and grouping by agent count. The excerpt does not provide complete tables, exact averages, all baseline configurations, or hardware details for every experiment.
The abstract states that the experiments show significant runtime and memory improvements on several standard benchmark applications. The conclusion describes EPEA* and EPEIDA* as achieving state-of-the-art runtime performance across the reported domains. In MAPF, the additive-PDB-based EPEA* is reported to be up to three times faster than the SIC-based EPEA* on hard instances. The supplied material also says that EPEA* was not observed to be slower than A* in the reported experiments except for an unshown SAPF experiment where it was slightly slower. It does not establish exact node counts, absolute runtimes, averages, variance, statistical significance, or a universal ranking across all domains.
EPEA* advances partial expansion by using prior domain and heuristic knowledge to avoid generating surplus nodes rather than merely avoiding their storage. Its OSF mechanism can be adapted to simple local heuristics, pattern databases, additive pattern databases, and, with a related threshold interpretation, IDA*. The experiments and theoretical discussion support strong benefits when branching is large and the OSF can be computed efficiently. They also show that memory behavior, runtime, and applicability depend on structural and implementation factors. The paper therefore presents EPEA* as a domain-sensitive complement to A*, PEA*, and IDA*, not as an unconditional replacement.
EPEA* requires sufficiently detailed domain- and heuristic-specific knowledge, and the abstract explicitly notes that it is not always applicable or practical. Constructing or evaluating an OSF can itself be expensive, especially when the branching factor is not large enough to justify that cost. Partial expansion can sometimes increase rather than decrease the size of OPEN, as illustrated by a MAPF case in the supplied material. The analysis depends on branching behavior, implementation costs, OSF cost, and EPEA*-specific parameters, but the excerpt does not provide a generally reliable way to estimate all of them. The paper also identifies an unresolved trade-off between EPEA* and exploiting the full power of value propagation with inconsistent heuristics; an experimental study of that trade-off is left for future work. Exact limitations of the reported benchmarks cannot be fully assessed because many numerical details are omitted from the supplied excerpts.
The paper’s importance is conceptual as well as 提案手順c. It treats unnecessary child generation as a distinct source of search cost and shows how heuristic structure can be used before state generation, rather than only after states have been created. For MAPF and other combinatorial planning problems, this provides a way to connect strong abstraction-based heuristics with selective successor generation. It also gives researchers a framework for analyzing whether a specialized operator selector will repay its computation through fewer generated nodes, lower memory pressure, or faster search.
This paper is recommended for researchers in MAPF, optimal pathfinding, heuristic search, pattern databases, and implementations of A* or IDA*. It is particularly useful for readers studying surplus-node suppression, successor-generation cost, and the trade-off between OPEN size and runtime. The distinction between full-checking and direct-computation OSFs also makes it useful as a design reference for domain-specific search accelerators. Readers who need reproducible numerical comparisons should consult the complete paper, since the supplied evidence does not establish all experimental conditions or detailed measurements.