Efficient Search with an Ensemble of Heuristics

Mike Phillips, Venkatraman Narayanan, Sandip Aine, Maxim LikhachevIJCAI 2015

Overview

This research introduces two principled methods for managing ensembles of "weak" heuristics in search algorithms like Multi-Heuristic A (MHA). By adaptively scheduling which heuristic to prioritize—using either a meta-graph search (Meta-A) or a multi-armed bandit approach (Dynamic Thompson Sampling*)—the authors achieve up to a 4.5x speedup over standard round-robin methods without sacrificing solution quality.

The Challenge: The "Blind" Round-Robin

Heuristic search algorithms rely on a "hint" function (the heuristic) to guide them toward a goal. In complex domains like high-dimensional robotics, designing one perfect heuristic is nearly impossible. A common workaround is to use an ensemble of many "weak" heuristics, each capturing a different aspect of the problem.

The state-of-the-art framework for this is Multi-Heuristic A (MHA), which typically rotates through these heuristics in a round-robin fashion. However, round-robin is "blind" — it gives equal time to every heuristic, even if most are currently stuck in local minima. This leads to a linear slowdown as you add more heuristics, defeating the purpose of using a large ensemble to simplify engineering.

The MHA* framework maintains multiple search queues, one for each heuristic in the ensemble.

Proposed Adaptive Schedulers

The authors propose two adaptive meta-algorithms to replace the round-robin scheduler:

  1. Meta-A*: This approach treats heuristic selection as a search problem itself. It constructs a "meta-graph" where each node represents the state of an underlying search queue. By running A* on this meta-graph, the algorithm prioritizes the search queue expected to reach the goal with the fewest total expansions.
  2. Dynamic Thompson Sampling (DTS): This treats heuristic selection as a Multi-Armed Bandit (MAB) problem. Each heuristic is an "arm." If an expansion using a specific heuristic lowers the best-seen heuristic value, it receives a reward. DTS uses a "dynamic" window to discard old history, allowing the agent to quickly pivot when a previously successful heuristic hits a wall.

Experimental Results

The methods were evaluated on 12-DOF full-body motion planning for a PR2 robot in a cluttered kitchen and large-scale sliding tile puzzles.

Key Performance Gains

In the robotics domain, both Meta-A and DTS achieved an average 4.5x speedup over the round-robin baseline. Compared to sampling-based planners like RRT-Connect, the MHA variants had significantly higher success rates in cluttered environments and produced much higher-quality paths (e.g., arm motions were 3x shorter).

Planning time comparison between the Round-Robin (RR) baseline and Dynamic Thompson Sampling (DTS). Points above the y=x line represent instances where DTS outperformed RR.

Scalability

In sliding tile puzzles, the adaptive methods showed much better resilience to the overhead of adding more heuristics. While round-robin performance often degraded when moving from 5 to 17 heuristics due to wasted expansions, DTS and Meta-A* continued to improve or stayed stable.

Conclusion

The core insight of this work is viewing search as a resource allocation problem. By intelligently "betting" on the most promising heuristics in real-time, Meta-A* and DTS overcome the limitations of blind scheduling, enabling the use of large heuristic ensembles for complex planning tasks.

Summary updated

BibTeX
@inproceedings{phillips2015efficient,
  author = {Mike Phillips and Venkatraman Narayanan and Sandip Aine and Maxim Likhachev},
  title = {{Efficient Search with an Ensemble of Heuristics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure