A* with Bounded Costs

Brian Logan, Natasha Alechina

A key assumption of all problem-solving approaches based on utility theory, including heuristic search, is that we can as-sign a utility or cost to each state. This in turn requires that all criteria of interest can be reduced to a common ratio scale. However, many real-world problems are difficult or impossible to formulate in terms of minimising a single criterion, and it is often more natural to express problem requirements in terms of a set of constraints which a solution should satisfy. In this paper, we present a generalisation of the A- search algorithm, A- with bounded costs ( ABC ), which searches for a solution which best satisfies a set of prioritised soft constraints, and show that, given certain reasonable assumptions about the constraints, the algorithm is both complete and optimal. We briefly describe a route planner based on ABC and illustrate the advantages of our approach in a simple route planning problem.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.