---
title: "Best-First Utility-Guided Search"
authors:
  - "Wheeler Ruml"
  - "Minh Binh Do"
doi: ""
url: "https://ijcai.org/proceedings/2007/383"
pdf: "https://ijcai.org/proceedings/2007/0383.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "2378-2383"
track: ""
keywords:
---

# Best-First Utility-Guided Search

Wheeler Ruml, Minh Binh Do

*Proceedings of the Twentieth International Joint Conference on Artificial Intelligence*, pages 2378-2383.

## Abstract

In many shortest-path problems of practical interest, insufficient time is available to find a provably optimal solution. One can only hope to achieve a balance between search time and solution cost that respects the user's preferences, expressed as a utility function over time and cost. Current state-of-the-art approaches to this problem rely on anytime algorithms such as Anytime A* or ARA*. These algorithms require the use of extensive training data to compute a termination policy that respects the user's utility function. We propose a more direct approach, called Bugsy, that incorporates the utility function directly into the search, obviating the need for a separate termination policy. Experiments in several challenging problem domains, including sequence alignment and temporal planning, demonstrate that this direct approach can surpass anytime algorithms without requiring expensive performance profiling.