Searching for Good Solutions in Goal-Dense Search Spaces

Book One

Volume

Proceedings of the International Conference on Automated Planning and Scheduling, 23

Full Technical Papers

In this paper we explore the challenges surrounding searching effectively in problems with preferences.  These problems are characterized by a relative abundance of goal states: at one extreme, if every goal is soft, every state is a goal state.  We present techniques for planning in such search spaces, managing the sometimes-conflicting aims of intensifying search around states on the open list that are heuristically close to new, better goal states; and ensuring search is sufficiently diverse to find new low-cost areas of the search space, avoiding local minima.  Our approach uses a novel cost-bound-sensitive heuristic, based on finding several heuristic distance-to-go estimates in each state, each satisfying a different subset of preferences.  We present results comparing our new techniques to the current state-of-the-art and demonstrating their effectiveness on a wide range of problems from recent International Planning Competitions.

10.1609/icaps.v23i1.13541