Fast Planning for Dynamic Preferences

International Conference on Automated Planning and Scheduling (ICAPS 2008).
[pdf]

Abstract: We present an algorithm that quickly finds optimal plans for unforeseen agent preferences within graph-based planning domains where actions have deterministic outcomes and action costs are linearly parameterized by preference parame- ters. We focus on vehicle route planning for drivers with personal trade-offs for different types of roads, and specifically on settings where these preferences are not known until planning time. We employ novel bounds (based on the triangle inequality and on the the concavity of the optimal plan cost in the space of preferences) to enable the reuse of previously computed optimal plans that are similar to the new plan preferences. The resulting lower bounds are employed to guide the search for the optimal plan up to 60 times more efficiently than previous methods.

Related Research Areas: Fast planning, A* search, heuristic functions

Bibtex:

@inproceedings{bziebart-maxentirl,
   author = {Brian D. Ziebart and J. Andrew Bagnell and Anind K. Dey},
   title = {Fast Planning for Dynamic Preferences},
   year = {2008},
   booktitle = {Proc. ICAPS},
   pages = {412--419}
}