---
title: "Efficient Search with an Ensemble of Heuristics"
authors:
  - "Mike Phillips"
  - "Venkatraman Narayanan"
  - "Sandip Aine"
  - "Maxim Likhachev"
doi: ""
url: "https://ijcai.org/proceedings/2015/116"
pdf: "https://ijcai.org/proceedings/2015/0116.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "784-790"
track: "Main Track"
keywords:
---

# Efficient Search with an Ensemble of Heuristics

Mike Phillips, Venkatraman Narayanan, Sandip Aine, Maxim Likhachev

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 784-790.

## Abstract

Recently, a number of papers have shown that for many domains, using multiple heuristics in independent searches performs better than combining them into a single heuristic. Furthermore, using a large number of “weak” heuristics could potentially eliminate the need for the careful design of a few. The standard approach to distribute computation in these multi-heuristic searches is to rotate through the heuristics in a round-robin fashion. However, this strategy can be inefficient especially in the case when only a few of the heuristics are leading to progress. In this paper, we present two principled methods to adaptively distribute computation time among the different searches of the Multi- Heuristic A* algorithm. The first method, Meta-A*, constructs and searches a meta-graph, which represents the problem of finding the best heuristic as the problem of minimizing the total number of expansions. The second treats the scheduling of searches with different heuristics as a multi-armed bandit problem. It applies Dynamic Thompson Sampling (DTS) to keep track of what searches are making progress the most and continuously re-computes the schedule of searches based on this information. We provide a theoretical analysis and compare our new strategies with the round-robin method on a 12-DOF full-body motion planning problem and on sliding tile puzzle problems. In these experiments, we used up to 20 heuristics and observed a several times speedup without loss in solution quality.