Improved Multi-Heuristic A * for Searching with Uncalibrated Heuristics

Recently, several researchers have brought forth the bene-fits of searching with multiple (and possibly inadmissible) heuristics, arguing how different heuristics could be inde-pendently useful in different parts of the state space. How-ever, algorithms that use inadmissible heuristics in the tradi-tional best-first sense, such as the recently developed Multi-Heuristic A * (MHA*), are subject to a crippling calibration problem: they prioritize nodes for expansion by additively combining the cost-to-come and the inadmissible heuristics even if those heuristics have no connection with the cost-to-go (e.g., the heuristics are uncalibrated). For instance, if the inadmissible heuristic were an order of magnitude greater than the perfect heuristic, an algorithm like MHA * would simply reduce to a weighted A * search with one consis-tent heuristic. In this work, we introduce a general multi-heuristic search framework that solves the calibration prob-lem and as a result a) facilitates the effective use of multi-ple uncalibrated inadmissible heuristics, and b) provides sig-nificantly better performance than MHA * whenever tighter sub-optimality bounds on solution quality are desired. Exper-imental evaluations on a complex full-body robotics motion planning problem and large sliding tile puzzles demonstrate the benefits of our framework