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.
Proposed Adaptive Schedulers
The authors propose two adaptive meta-algorithms to replace the round-robin scheduler:
- 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.
- 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).
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