Hybrid Planning with Preferences Using a Heuristic for Partially Ordered Plans

Hybrid Planning with Preferences Using a Heuristic for Partially Ordered Plans. Bercher, P. & Biundo, S. In 26th PuK Workshop "Planen, Scheduling und Konfigurieren, Entwerfen" (PuK 2011), 2011.

Paper

Slides abstract bibtex

This paper is concerned with the problem of finding preferred plans in a hybrid planning setting, which is the fusion of classical and hierarchical planning. Here, we define preferences as weighted soft goals – facts one would like to see satisfied in a goal state, but which do not have to hold necessarily. We present a branch-and-bound algorithm that allows a broad variety of search strategies, as opposed to the majority of existing planning systems which usually perform progression. The algorithm prunes task networks from the search space which will never lead to a better solution than the best solution found so far. To this end, we developed an admissible heuristic, based on a combination of the h^2 heuristic and delete relaxation, which takes as input a task network and estimates the best quality of any solution that can be developed from it.

@inproceedings{Bercher2011Preferences,
  author     = {Pascal Bercher and Susanne Biundo},
  title      = {Hybrid Planning with Preferences Using a Heuristic for Partially Ordered Plans},
  booktitle  = {26th {PuK} Workshop "Planen, Scheduling und Konfigurieren, Entwerfen" ({PuK} 2011)},
  year       = {2011},
  abstract   = {This paper is concerned with the problem of finding preferred plans in a hybrid planning setting, which is the fusion of classical and hierarchical planning. Here, we define preferences as weighted soft goals -- facts one would like to see satisfied in a goal state, but which do not have to hold necessarily. We present a branch-and-bound algorithm that allows a broad variety of search strategies, as opposed to the majority of existing planning systems which usually perform progression. The algorithm prunes task networks from the search space which will never lead to a better solution than the best solution found so far. To this end, we developed an admissible heuristic, based on a combination of the h^2 heuristic and delete relaxation, which takes as input a task network and estimates the best quality of any solution that can be developed from it.},
  url_Paper  = {https://bercher.net/publications/2011/Bercher2011Preferences.pdf},
  url_Slides = {https://bercher.net/publications/2011/Bercher2011PreferencesSlides.pdf},
  keywords   = {workshop}
}

Downloads: 0