---
title: "Speedy versus Greedy Search"
authors:
  - "Christopher Makoto Wilt"
  - "Wheeler Ruml"
doi: ""
url: "https://ijcai.org/proceedings/2015/616"
pdf: "https://ijcai.org/proceedings/2015/0616.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "4331-4337"
track: "Best Papers from Sister Conferences Track"
keywords:
---

# Speedy versus Greedy Search

Christopher Makoto Wilt, Wheeler Ruml

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

## Abstract

When an optimal solution is not required, satisficing search methods such as greedy best-first search are often used to find solutions quickly. In work on satisficing search, there has been substantial attention devoted to how to solve problems associated with local minima or plateaus in the heuristic function. One technique that has been shown to be quite promising is using an alternative heuristic function that does not estimate cost-to-go, but rather estimates distance-to-go. There is currently little beyond intuition to explain its superiority. We begin by empirically showing that the success of the distance-to-go heuristic appears related to its having smaller local minima. We then discuss a reasonable theoretical model of heuristics and show that, under this model, the expected size of local minima is higher for a cost-to-go heuristic than a distance-to-go heuristic, offering a possible explanation as to why distance-to-go heuristics tend to outperform cost-to-go heuristics.