Generating Effective Admissible Heuristics by Abstraction and Reconstitution

Armand Prieditis, Bhaskar JanakiramanAAAI 1993

Abstract: This paper introduces "reconstitution," a novel paradigm for generating effective admissible search heuristics. While traditional heuristics often rely on problem abstraction—ignoring constraints to simplify computation—this approach selectively reintroduces ignored details to tighten lower-bound estimates. Applied to project scheduling, the resulting Reconstituted Critical Path (RCP) heuristic demonstrates significant pruning power, reducing search states and computation time by orders of magnitude compared to standard critical path methods.

Introduction

In pathfinding and optimization, an admissible heuristic serves as a lower-bound estimate of the remaining cost to reach a goal. If the heuristic never overestimates this cost, algorithms like A are guaranteed to find optimal solutions. Historically, these heuristics are generated through abstraction*: removing constraints to make a problem easier to solve (e.g., ignoring tile collisions in the 8-puzzle to calculate Manhattan Distance).

The primary challenge lies in the "accuracy vs. efficiency" trade-off. High-level abstractions are fast to compute but provide loose bounds, leading to an exponential explosion of states to explore. Conversely, low-level abstractions are more accurate but can be as computationally expensive as the original problem. This research proposes a middle ground: starting with a high-level abstraction and strategically adding back just enough detail to tighten the bound without sacrificing computational speed.

The Reconstitution Paradigm

The core innovation is a three-step process: Abstract → Solve → Reconstitute. Instead of attempting to solve a complex problem in its entirety, the system solves a simplified version and then "patches" the solution by identifying which original constraints were violated.

Conceptual framework of the reconstitution paradigm, mapping between the original, abstracted, and reconstituted problem spaces.

As shown in Figure 1, the process maps the original problem state ($s$) to an abstracted state ($s'$). After finding a path in the abstracted space, the algorithm reconstitutes specific details ($s'_r$) to create a more accurate estimate for the original goal ($g$). This allows for a "selective detail" approach where only the most impactful constraints are reintroduced.

Application: Project Scheduling

The authors demonstrate this paradigm using Project Scheduling, an NP-hard problem involving jobs with specific durations, precedence requirements (Job A must finish before B), and mutual exclusion constraints (Job C and D cannot overlap due to shared resources).

  1. The Base (Abstraction): The process starts with the Critical Path (CP) heuristic. This ignores all resource/mutual exclusion constraints and only considers precedence. While fast ($O(n)$), it frequently underestimates project duration.
  2. The Innovation (RCP): The Reconstituted Critical Path (RCP) heuristic first calculates the standard CP. It then traverses that path backward to identify "unsatisfied" mutual exclusion constraints. If a job not on the critical path must be delayed due to a resource conflict with a job on the critical path, the algorithm calculates the minimum necessary overlap and adds it to the total duration estimate.

This keeps the heuristic computation efficient ($O(n^2)$) while providing a much tighter bound by focusing only on constraints that directly impact the current critical path.

Experimental Results

The heuristics were evaluated using IDA* on sets of randomly generated project scheduling problems with varying numbers of jobs (30 to 40) and mutual exclusion constraints (0 to 40).

Performance comparison between the standard Critical Path (CP) heuristic and the Reconstituted Critical Path (RCP) heuristic across varying problem complexities.

The results in Figure 4 highlight a dramatic performance gap as problem complexity increases:

  • Pruning Power: In a 30-job problem with 25 mutual exclusions, the standard CP heuristic required expanding 6,242 states, whereas the RCP heuristic required only 54 states.
  • Computational Efficiency: For the same problem, CP took 1,651.53 seconds to find a solution, while RCP achieved the same result in just 30.67 seconds—a roughly 50x speedup.
  • Scalability: As constraints increased, CP's performance degraded exponentially. In contrast, RCP remained relatively stable, proving that reconstitution effectively manages search space complexity.

Conclusion and Future Work

The reconstitution paradigm offers a powerful method for generating heuristics that are both accurate and efficient. By selectively adding detail to an abstracted solution, the RCP heuristic prevents the exploration of millions of redundant states.

Future research aims to extend this model to handle complex resource pools (beyond simple mutual exclusion) and temporal constraints like deadlines. A significant long-term goal is the automation of the reconstitution logic, allowing systems to independently discover which details are most critical to reintroduce for any given problem domain.

Summary updated

BibTeX
@inproceedings{prieditis1993generating,
  author = {Armand Prieditis and Bhaskar Janakiraman},
  title = {{Generating Effective Admissible Heuristics by Abstraction and Reconstitution}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure