My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
Papers

Daphne Koller Publications

Generalizing Plans to New Environments in Relational MDPs (2003)

by C. Guestrin, D. Koller, C. Gearhart, and N. Kanodia


Abstract: A longstanding goal in planning research is the ability to generalize plans developed for some set of environments to a new but similar environment, with minimal or no replanning. Such generalization can both reduce planning time and allow us to tackle larger domains than the ones tractable for direct planning. In this paper, we present an approach to the generalization problem based on a new framework of relational Markov Decision Processes (RMDPs). An RMDP can model a set of similar environments by representing objects as instances of different classes. In order to generalize plans to multiple environments, we define an approximate value function specified in terms of classes of objects and, in a multiagent setting, by classes of agents. This class-based approximate value function is optimized relative to a sampled subset of environments, and computed using an efficient linear programming method. We prove that a polynomial number of sampled environments suffices to achieve performance close to the performance achievable when optimizing over the entire space. Our experimental results show that our method generalizes plans successfully to new, significantly larger, environments, with minimal loss of performance relative to environment-specific planning. We demonstrate our approach on a real strategic computer war game.

Download Information

C. Guestrin, D. Koller, C. Gearhart, and N. Kanodia (2003). "Generalizing Plans to New Environments in Relational MDPs." Eighteenth International Joint Conference on Artificial Intelligence (IJCAI). pdf ps.gz html

Bibtex citation

@inproceedings{Guestrin+al:IJCAI03,
  title = {Generalizing Plans to New Environments in Relational MDPs},
  author = {C. Guestrin and D. Koller and C. Gearhart and N. Kanodia},
  booktitle = {Eighteenth International Joint Conference on Artificial Intelligence (IJCAI)},
  month = {August},
  year = 2003, 
  address = {Acapulco, Mexico},
}

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal