Transcript CIS 730 (Introduction to Artificial Intelligence)

Lecture 23 of 41
Planning and Reaction
Friday, 15 October 2004
William H. Hsu
Department of Computing and Information Sciences, KSU
http://www.kddresearch.org
http://www.cis.ksu.edu/~bhsu
Reading:
Chapter 12, Russell and Norvig
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Lecture Outline
•
Today’s Reading
– Chapter 13, Russell and Norvig
– References: Readings in Planning – Allen, Hendler, and Tate
•
Next Week: Review Chapter 14, Russell and Norvig (Basic Probability)
•
Previously: Classical and Abstract Planning
•
Today, Monday: More Practical Planning
– Conditional planning, concluded
– Monitoring
•
Next Wednesday: Introduction to Uncertain Reasoning
– Uncertainty in AI
• Need for uncertain representation
• Soft computing: probabilistic, neural, fuzzy, other representations
– Probabilistic knowledge representation
• Views of probability
• Justification
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Review:
Hierarchical Abstraction Planning
•
Need for Abstraction
– Question: What is wrong with uniform granularity?
– Answers (among many)
• Representational problems
• Inferential problems: inefficient plan synthesis
•
Family of Solutions: Abstract Planning
– But what to abstract in “problem environment”, “representation”?
• Objects, obstacles (quantification: later)
• Assumptions (closed world)
• Other entities
• Operators
• Situations
– Hierarchical abstraction
• See: Sections 12.2 – 12.3 R&N, pp. 371 – 380
• Figure 12.1, 12.6 (examples), 12.2 (algorithm), 12.3-5 (properties)
Adapted from Russell and Norvig
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Review:
How Things Go Wrong in Planning
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Review:
Practical Planning Solutions
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Conditional Planning
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Conditional Planning Example
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Monitoring and Replanning
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Preconditions for Remaining Plan
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Replanning
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Summary Points
•
Two Weeks Ago: Introduction to Classical Planning
– Search vs. planning
– STRIPS axioms
•
Last Week: More Classical Planning
– Partial-order planning (NOAH, etc.)”
– Limitations of POP
– Abstraction in planning
– Producing practical planners
•
Today: More Practical Planning
– Conditional planning, concluded
– Monitoring and replanning
– Relation to reactive and universal planning
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Terminology
•
Classical Planning Framework
– Planning versus search
– Representation: initial state, goal state / test, operators
– STRIPS operators
– Partial versus total-order: property of plans
– Interleaved vs. noninterleaved: property of planners
•
Last Week
– Hierarchical abstraction planning: ABSTRIPS
– Conditional plans
•
This Week
– Monitoring and replanning
– Reactive plans and policies
•
Later
– Decision theory
– Markov decision processes
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences