Carnegie Mellon University,

We present a novel heuristic search framework, called Multi-Heuristic A * (MHA*), that simultaneously uses multiple, arbitrarily inadmissible heuristic functions and one consistent heuristic to search for complete and bounded suboptimal solutions. This simplifies the design of heuristics and enables the search to effectively com-bine the guiding powers of different heuristic functions. We support these claims with experimental results on full-body manipulation for PR2 robots. The performance of heuristic search based planners de-pends heavily on the accuracy of the heuristic function and can degrade severely in the presence of heuristic depression regions, i.e., regions in the search space where the heuris-tic values do not correlate well with the actual cost-to-goal