Searching for Good Solutions in Goal-Dense Search Spaces

Research output: Chapter in Book/Report/Conference proceedingConference paper

2 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationProceedings of the Twenty Third International Conference on Automated Planning and Scheduling (ICAPS 2013)
EditorsDaniel Borrajo, Subbarao Kambhampati, Angela Oddi, Simone Fratini
PublisherAAAI Press
Number of pages9
ISBN (Print)9781577356097
Publication statusPublished - Aug 2013


  • planning
  • preferences
  • heuristics
  • search


Dive into the research topics of 'Searching for Good Solutions in Goal-Dense Search Spaces'. Together they form a unique fingerprint.

Cite this