AAAI Publications, Twenty-Third International Conference on Automated Planning and Scheduling

Font Size: 
Searching for Good Solutions in Goal-Dense Search Spaces
Amanda Jane Coles, Andrew Ian Coles

Last modified: 2013-06-02

Abstract


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.

Full Text: PDF