Heuristic Search for Large Problems with Real Costs

Matthew HatemAAAI 2013 · DOI

Introduction

Heuristic search algorithms, most notably A, are fundamental to artificial intelligence, providing the backbone for applications ranging from pathfinding to complex planning. However, the utility of A is fundamentally constrained by its memory requirements: the algorithm must store every visited state in RAM to ensure optimality and avoid redundant work. For large-scale, real-world problems, memory capacity is typically exhausted long before the processor can reach a solution.

This research addresses the "memory wall" by modernizing external memory search—utilizing hard disks as an extension of RAM—while overcoming two critical hurdles: the inefficiency of real-valued edge costs and the explosive memory demands of high branching factors.

While external memory search algorithms exist, they historically struggle with two specific types of problem domains:

  1. Real-Valued Costs: Traditional external search relies on "layering" nodes based on their cost. If edge costs are small integers, many nodes share the same cost, allowing for large, efficient batches of data to be written to disk. However, in domains with real-valued costs (e.g., 1.234), almost every node resides in its own unique layer. This causes the system to perform frequent, small random disk accesses, leading to massive I/O overhead and crippling performance.
  2. High Branching Factors: In domains like Multiple Sequence Alignment (MSA) in bioinformatics, a single state can have thousands of potential successors. Generating all these successors simultaneously can cause a system crash or memory overflow before the data can even be processed or moved to disk.

To address these limitations, a four-part framework was developed to enable efficient, large-scale heuristic search on modern hardware.

PEDAL: Handling Real-Valued Costs

Parallel External search with Dynamic A* Layering (PEDAL) is designed specifically for domains where costs are not discrete. Instead of rigid layers, PEDAL dynamically groups nodes into larger buckets. This strategy ensures that the algorithm accesses the disk sequentially rather than randomly. By prioritizing sequential throughput over random access latency, PEDAL exploits the high bandwidth of modern storage devices.

PE2A*: Managing High Branching Factors

Parallel External PEA (PE2A) combines two powerful techniques: Partial Expansion A (PEA) and Delayed Duplicate Detection (DDD). PEA* mitigates the branching factor problem by only generating the most promising successor nodes initially, saving space. DDD then manages the search frontier by sorting data on the disk to identify and remove duplicate states, ensuring the search remains efficient without requiring a massive hash table in RAM.

Bounded Suboptimality and Distributed Computing

Recognizing that a "perfect" solution is often less valuable than a "fast" one, the framework incorporates Weighted-A (wA). This allows researchers to trade a controlled amount of solution quality for significant gains in search speed. Furthermore, the research extends these concepts into a distributed framework, pooling the RAM and disk resources of multiple machines in a computing cluster to solve problems that exceed the capacity of any single node.

Experimental Validation: Multiple Sequence Alignment

The primary benchmark for this research was BAliBASE, a standard in bioinformatics for Multiple Sequence Alignment. Using Reference Set 1, the PE2A* algorithm was tested against biologically accurate, real-valued cost functions.

The results demonstrated a significant breakthrough: PE2A* became the first algorithm capable of solving the entire BAliBASE Reference Set 1 using these precise cost functions. This indicates that external best-first search can now compete with, and often outperform, the uninformed search methods traditionally used in biological research.

Conclusion and Future Directions

This research demonstrates that with the right data structures and access patterns, external memory can effectively scale heuristic search to massive problems. PEDAL and PE2A* prove that the limitations of real-valued costs and high branching factors are surmountable.

Future work remains in fully integrating the distributed framework and optimizing these sequential-access patterns for the unique performance characteristics of Solid State Drives (SSDs) and NVMe storage, which differ significantly from the hard disks originally targeted. Additionally, the ongoing integration of PEDAL’s real-valued handling with PE2A*’s branching management promises even greater capabilities for complex bioinformatics applications.

Summary updated

BibTeX
@inproceedings{hatem2013heuristic,
  author = {Matthew Hatem},
  title = {{Heuristic Search for Large Problems with Real Costs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8492},
}
Figure