Improved Multi-Heuristic A* for Searching with Uncalibrated Heuristics

June 2015

Improved Multi-Heuristic A* for Searching with Uncalibrated Heuristics

Authors:

Venkatraman Narayanan, Sandip Aine, and Maxim Likhachev

Abstract:

Recently, several researchers have brought forth the benefits of searching with multiple (and possibly inadmissible) heuristics, arguing how different heuristics could be independently useful in different parts of the state space. However, algorithms that use inadmissible heuristics in the traditional best-first sense, such as the recently developed MultiHeuristic 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 consistent heuristic. In this work, we introduce a general multiheuristic search framework that solves the calibration problem and as a result a) facilitates the effective use of multiple uncalibrated inadmissible heuristics, and b) provides significantly better performance than MHA* whenever tighter sub-optimality bounds on solution quality are desired. Experimental evaluations on a complex full-body robotics motion planning problem and large sliding tile puzzles demonstrate the benefits of our framework.
@conference{Narayanan-2015-5971,
author = {Venkatraman Narayanan And Sandip Aine And Maxim Likhachev},
title = {Improved Multi-Heuristic A* for Searching with Uncalibrated Heuristics},
booktitle = {Proceedings of 8th International Symposium on Combinatorial Search (SoCS '15)},
year = {2015},
month = {June},
pages = {78 - 86},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.