Haddaway 1996: Focussing Attention in Anytime Decision-Theoretic Planning

[ CogSci Summaries home | UP | email ]
http://www.jimdavies.org/summaries/

P. Haddawy (1996). Focussing Attention in Anytime Decision-Theoretic Planning, SIGART Bulletin, Vol. 7, No. 2.

@Article{haddaway1996,
  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, scollins@cc.gatech.edu

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.

Representation

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

Abstract Actions

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 later specification.

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 action.

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:

none

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:

JimDavies ( jim@jimdavies.org )

Last modified: Mon Apr 26 08:34:05 EDT 1999