file.pdf (816.94 kB)
Fast Planning for Dynamic Preferences
journal contribution
posted on 2008-01-01, 00:00 authored by Brian D. Ziebart, Anind K. Dey, J. Andrew BagnellWe 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 parameters. 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.