Fast Planning for Dynamic Preferences

Brian D. Ziebart, Anind Dey, and J. Andrew (Drew) Bagnell
ICAPS: International Conference on Automated Planning and Scheduling, October, 2008.


Download
  • Adobe portable document format (pdf) (832KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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 weights. We focus on vehicle route planning for drivers with personal trade-offs for different road types, and specifically on settings where these preferences are not known until planning time. We employ novel bounds (based on the triangle inequality and the concavity of the the optimal plan costs 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.

Keywords
Inverse Optimal Control, Probabilistic Reasoning, Navigation, Machine Learning

Notes
Sponsor: NSF
Associated Center(s) / Consortia: Vision and Autonomous Systems Center and Quality of Life Technology Center
Associated Lab(s) / Group(s): Human-Robot Interaction Group
Associated Project(s): Quality of Life Technology

Text Reference
Brian D. Ziebart, Anind Dey, and J. Andrew (Drew) Bagnell, "Fast Planning for Dynamic Preferences," ICAPS: International Conference on Automated Planning and Scheduling, October, 2008.

BibTeX Reference
@inproceedings{Ziebart_2008_6202,
   author = "Brian D. Ziebart and Anind Dey and J. Andrew (Drew) Bagnell",
   title = "Fast Planning for Dynamic Preferences",
   booktitle = "ICAPS: International Conference on Automated Planning and Scheduling",
   month = "October",
   year = "2008",
}