[ CogSci Summaries home | UP | email ]
P. Haddawy (1996). Focussing Attention in Anytime Decision-Theoretic Planning, SIGART Bulletin, Vol. 7, No. 2.
author = "P. Haddaway",
title = "Focussing Attention in Anytime Decision-Theoretic Planning",
journal = "SIGART Bulletin,
year = "1996",
volume = "7",
OPTnumber = "2",
Author of the summary: Samuel R. Collins, 1999, firstname.lastname@example.org
The actual paper
is online at http://www.jimdavies.org/summaries/haddawy.ps
Cite this paper for:
- Anytime algorithm for decision-theoretic planning
- Automatically generating abstractions
- SYSTEM: DRIPS : Decision-theoretic refinement planning system
- Chronicle is a complete specification of the world throughout time
- Interaction abstractions
- Sequential abstractions
- Abstraction hierarchy
- rational refinement property: focus on most important parts
before worrying about the details
- Design of anytime algorithm for decision-theoretic planning
"... uses abstraction to focus attention first to those aspects of a
planning problem that have the highest impact on expected utility."
The Planning Algorithm
- An anytime decision theoretic planning algorithm is one that can return some plan or set of candidate plans anytime during its execution.
- An optimal anytime decision-theoretic planning algorithm is one for which the plan or set of candidate plans converges to the optimal plan or set of plans.
- Consider the most important aspects of the planning problem before moving to the details
- Planner should focus on the attribute description rather than states
- Focus on the attributes which have a high impact on expected utility in order to eliminate highly sub-optimal plans
- DRIPS find the optimal by building abstract plans, comparing them, and refining only those that might yield the optimal plan.
- The planner can be stopped at any time to yield the set of abstract plans which have not yet been shown to be suboptimal.
- World Model - The world is described in terms of chronicles where a chronicle is a complete specification of the world through time.
- Action model - Actions are both conditional and probabilistic
- Drips planner primarily uses two types of abstraction
- Interaction - action abstraction is to group together a set
of analogous actions. Purpose: You can choose a group early on
without choosing which individual action in the group. That is a
- Sequential abstraction specifies the end effects of a sequence
of actions and initial conditions. Like composition in ACT-R. At
the high level of abstraction it treats a sequence like one
- Implemented tools to partially automate the process of creating abstract action
The DRIPS Planner
- DRIPS finds the optimal plan by building abstract plans, comparing them, and refining only those that might yield the optimal plan
- If run to completion DRIPS explores the entire space of possible solutions
Automatically Generating Abstractions
- User provide BNF grammar
- Task is to find useful abstraction hierarchies for the sets of alternative actions
- Focus on estimating the effect of the Expected Utility
Summary author's notes:
Back to the Cognitive Science Summaries homepage
JimDavies ( email@example.com )
Cognitive Science Summaries Webmaster:
Last modified: Mon Apr 26 08:34:05 EDT 1999