第1页 / 共638页
第2页 / 共638页
第3页 / 共638页
第4页 / 共638页
第5页 / 共638页
第6页 / 共638页
第7页 / 共638页
第8页 / 共638页
Automated planning: Theory and practics.pdf
1558608567
Copyright
About the Authors
Table of Contents
Foreword
Preface
Using This Book
Web Site
Acknowledgments
Table of Notation
1. Introduction and Overview
1.1 First Intuitions on Planning
1.2 Forms of Planning
1.3 Domain-Independent Planning
1.4 Conceptual Model for Planning
1.5 Restricted Model
1.6 Extended Models
1.7 A Running Example: Dock-Worker Robots
Part I: Classical Planning
2. Representations for Classical Planning
2.1 Introduction
2.2 Set-Theoretic Representation
2.2.1 Planning Domains, Problems, and Solutions
2.2.2 State Reachability
2.2.3 Stating a Planning Problem
2.2.4 Properties of the Set-Theoretic Representation
2.3 Classical Representation
2.3.1 States
2.3.2 Operators and Actions
2.3.3 Plans, Problems, and Solutions
2.3.4 Semantics of Classical Representations
2.4 Extending the Classical Representation
2.4.1 Simple Syntactical Extensions
2.4.2 Conditional Planning Operators
2.4.3 Quantified Expressions
2.4.4 Disjunctive Preconditions
2.4.5 Axiomatic Inference
2.4.6 Function Symbols
2.4.7 Attached Procedures
2.4.8 Extended Goals
2.5 State-Variable Representation
2.5.1 State Variables
2.5.2 Operators and Actions
2.5.3 Domains and Problems
2.5.4 Properties
2.6 Comparisons
2.7 Discussion and Historical Remarks
2.8 Exercises
3. Complexity of Classical Planning
3.1 Introduction
3.2 Preliminaries
3.3 Decidability and Undecidability Results
3.4 Complexity Results
3.4.1 Binary Counters
3.4.2 Unrestricted Classical Planning
3.4.3 Other Results
3.5 Limitations
3.6 Discussion and Historical Remarks
3.7 Exercises
4. State-Space Planning
4.1 Introduction
4.2 Forward Search
4.2.1 Formal Properties
4.2.2 Deterministic Implementations
4.3 Backward Search
4.4 The STRIPS Algorithm
4.5 Domain-Specific State-Space Planning
4.5.1 The Container-Stacking Domain
4.5.2 Planning Algorithm
4.6 Discussion and Historical Remarks
4.7 Exercises
5. Plan-Space Planning
5.1 Introduction
5.2 The Search Space of Partial Plans
5.3 Solution Plans
5.4 Algorithms for Plan-Space Planning
5.4.1 The PSP Procedure
5.4.2 The PoP Procedure
5.5 Extensions
5.6 Plan-Space versus State-Space Planning
5.7 Discussion and Historical Remarks
5.8 Exercises
Part II: Neoclassical Planning
6. Planning-Graph Techniques
6.1 Introduction
6.2 Planning Graphs
6.2.1 Reachability Trees
6.2.2 Reachability with Planning Graphs
6.2.3 Independent Actions and Layered Plans
6.2.4 Mutual Exclusion Relations
6.3 The Graphplan Planner
6.3.1 Expanding the Planning Graph
6.3.2 Searching the Planning Graph
6.3.3 Analysis of Graphplan
6.4 Extensions and Improvements of Graphplan
6.4.1 Extending the Language
6.4.2 Improving the Planner
6.4.3 Extending the Independence Relation
6.5 Discussion and Historical Remarks
6.6 Exercises
7. Propositional Satisfiability Techniques
7.1 Introduction
7.2 Planning Problems as Satisfiability Problems
7.2.1 States as Propositional Formulas
7.2.2 State Transitions as Propositional Formulas
7.2.3 Planning Problems as Propositional Formulas
7.3 Planning by Satisfiability
7.3.1 Davis-Putnam Procedure
7.3.2 Stochastic Procedures
7.4 Different Encodings
7.4.1 Action Representation
7.4.2 Frame Axioms
7.5 Discussion and Historical Remarks
7.6 Exercises
8. Constraint Satisfaction Techniques
8.1 Introduction
8.2 Constraint Satisfaction Problems
8.3 Planning Problems as CSPs
8.3.1 Encoding a Planning Problem into a CSP
8.3.2 Analysis of the CSP Encoding
8.4 CSP Techniques and Algorithms
8.4.1 Search Algorithms for CSPs
8.4.2 Filtering Techniques
8.4.3 Local Search Techniques and Hybrid Approaches
8.5 Extended CSP Models
8.5.1 Active CSPs
8.6 CSP Techniques in Planning
8.6.1 CSPs in Plan-Space Search
8.6.2 CSPs for Planning-Graph Techniques
8.7 Discussion and Historical Remarks
8.8 Exercises
Part III: Heuristics and Control Strategies
9. Heuristics in Planning
9.1 Introduction
9.2 Design Principle for Heuristics: Relaxation
9.3 Heuristics for State-Space Planning
9.3.1 State Reachability Relaxation
9.3.2 Heuristically Guided Backward Search
9.3.3 Admissible State-Space Heuristics
9.3.4 6raphpian as a Heuristic Search Planner
9.4 Heuristics for Plan-Space Planning
9.4.1 Flaw-Selection Heuristics
9.4.2 Resolver-Selection Heuristics
9.5 Discussion and Historical Remarks
9.6 Exercises
10. Control Rules in Planning
10.1 Introduction
10.2 Simple Temporal Logic
10.3 Progression
10.4 Planning Procedure
10.5 Extensions
10.6 Extended Goals
10.7 Discussion and Historical Remarks
10.8 Exercises
11. Hierarchical Task Network Planning
11.1 Introduction
11.2 STN Planning
11.2.1 Tasks and Methods
11.2.2 Problems and Solutions
11.3 Total-Order STN Planning
11.4 Partial-Order STN Planning
11. 5 HTN Planning
11.5.1 Task Networks
11.5.2 HTN Methods
11.5.3 HTN Problems and Solutions
11.5.4 Planning Procedures
11.6 Comparisons
11.6.1 HTN Planning versus STN Planning
11.6.2 HTN Methods versus Control Rules
11.7 Extensions
11.7.1 Extensions from Chapter 2
11.7.2 Additional Extensions
11.8 Extended Goals
11.9 Discussion and Historical Remarks
11.10 Exercises
12. Control Strategies in Deductive Planning
12.1 Introduction
12.2 Situation Calculus
12.2.1 Situations
12.2.2 Actions
12.2.3 Planning Domains, Problems, and Solutions
12.2. 4 Plans as Programs in Situation Calculus
12. 3 Dynamic Logic
12.3.1 The Language of the Logic
12.3.2 The Semantics
12.3.3 The Deductive Machinery
12.3.4 Planning Domains, Problems, and Solutions
12.3.5 Extensions
12.3.6 User-Defined Control Strategies as Tactics
12.4 Discussion and Historical Remarks
12. 5 Exercises
Part IV: Planning with Time and Resources
13. Time for Planning
13.1 Introduction
13.2 Temporal References and Relations
13.3 Qualitative Temporal Relations
13.3.1 Point Algebra
13.3.2 Interval Algebra
13.3.3 A Geometric Interpretation of Interval Algebra
13.3.4 Interval Algebra versus Point Algebra
13.4 Quantitative Temporal Constraints
13.4.1 Simple Temporal Constraints
13.4.2 Temporal Constraint Networks
13.5 Discussion and Historical Remarks
13.6 Exercises
14. Temporal Planning
14 .1 Introduction
14.2 Planning with Temporal Operators
14.2.1 Temporal Expressions and Temporal Databases
14.2.2 Temporal Planning Operators
14.2.3 Domain Axioms
14.2.4 Temporal Planning Domains, Problems, and Plans
14.2.5 Concurrent Actions with Interfering Effects
14.2.6 A Temporal Planning Procedure
14.3 Planning with Chronicles
14.3.1 State Variables, Timelines, and Chronicles
14.3.2 Chronicles as Planning Operators
14.3.3 Chronicle Planning Procedures
14.3.4 Constraint Management in CP
14.3.5 Search Control in CP
14.4 Discussion and Historical Remarks
14.5 Exercises
15. Planning and Resource Scheduling
15.1 Introduction
15.2 Elements of Scheduling Problems
15.2.1 Actions
15.2.2 Resources
15.2. 3 Constraints and Cost Functions
15.3 Machine Scheduling Problems
15.3.1 Classes of Machine Scheduling Problems
15.3.2 Complexity of Machine Scheduling
15.3.3 Solving Machine Scheduling Problems
15.3.4 Planning and Machine Scheduling
15.4 Integrating Planning and Scheduling
15.4.1 Representation
15.4.2 Detecting Resource Conflicts
15.4.3 Managing Resource Conflict Flaws
15.5 Discussion and Historical Remarks
15.6 Exercises
Part V: Planning under Uncertainty
16. Planning Based on Markov Decision Processes
16.1 Introduction
16.2 Planning in Fully Observable Domains
16.2.1 Domains, Plans, and Planning Problems
16.2.2 Planning Algorithms
16.3 Planning under Partial Observability
16.3.1 Domains, Plans, and Planning Problems
16.3.2 Planning Algorithms
16.4 Reachability and Extended Goals
16.5 Discussion and Historical Remarks
16.6 Exercises
17. Planning Based on Model Checking
17.1 Introduction
17.2 Planning for Reachability Goals
17.2.1 Domains, Plans, and Planning Problems
17.2.2 Planning Algorithms
17.3 Planning for Extended Goals
17.3.1 Domains, Plans, and Planning Problems
17.3.2 Planning Algorithms
17.3.3 Beyond Temporal Logic
17.4 Planning under Partial Observability
17.4.1 Domains, Plans, and Planning Problems
17.4.2 Planning Algorithms
17.5 Planning as Model Checking versus MDPs
17.6 Discussion and Historical Remarks
17.7 Exercises
18. Uncertainty with Neoclassical Techniques
18.1 Introduction
18.2 Planning as Satisfiability
18.2.1 Planning Problems
18.2.2 Planning Problems as Propositional Formulas
18.2. 3 Planning by Satisfiability
18.2.4 QBF Planning
18.3 Planning Graphs
18.4 Discussion and Historical Remarks
18.5 Exercises
Part VI: Case Studies and Applications
19. Space Applications
19.1 Introduction
19.2 Deep Space 1
19.3 The Autonomous Remote Agent
19.4 The Remote Agent Architecture
19.5 The Planner Architecture
19.6 The Deep Space 1 Experiment
19.6.1 Validation Objectives
19.6.2 Scenarios
19.6.3 Experiment Results
19.6.4 Lessons Learned
19.7 Discussion and Historical Remarks
20.Planning in Robotics
20.1 Introduction
20.2 Path and Motion Planning
20.3 Planning for the Design of a Robust Controller
20.3.1 Sensory-Motor Functions
20.3.2 Modalities
20.3.3 The Controller
20.3.4 Analysis of the Approach
20.4 Dock-Worker Robots
20.5 Discussion and Historical Remarks
21. Planning for Manufacturability Analysis
21.1 Introduction
21.2 Machined Parts
21.3 Feature Extraction
21.4 Generating Abstract Plans
21.5 Resolving Goal Interactions
21.6 Additional Steps
21.7 Operation Plan Evaluation
21.8 Efficiency Considerations
21.9 Concluding Remarks
22. Emergency Evacuation Planning
22.1 Introduction
22.2 Evacuation Operations
22.3 Knowledge Representation
22.3.1 HTNs
22.3.2 Cases
22.4 Hierarchical Task Editor
22.5 SiN
22.5.1 How SiN Works
22.5.2 Correctness of SiN
22.5.3 Imperfect World Information
22.6 Example
22.7 Summary
22.8 Discussion and Historical Remarks
23. Planning in the Game of Bridge
23.1 Introduction
23.2 Overview of Bridge
23.3 Game-Tree Search in Bridge
23.4 Adapting HTN Planning for Bridge
23.5 Implementation and Results
Part VII: Conclusion
24. Other Approaches to Planning
24.1 Case-Based Planning
24.2 Linear and Integer Programming
24.3 Multiagent Planning
24.4 Plan Merging and Plan Rewriting
24.5 Abstraction Hierarchies
24.6 Domain Analysis
24.7 Planning and Learning
24.8 Planning and Acting, Situated Planning, and Dynamic Planning
24.9 Plan Recognition
24.10 Suggestions for Future Work
Appendix A: Search Procedures and Computational Complexity
A.1 Nondeterministic Problem Solving
A.2 State-Space Search
A.3 Problem-Reduction Search
A.4 Computational Complexity of Procedures
A.5 Computational Complexity of Problems
A.6 Planning Domains as Language-Recognition Problems
A.7 Discussion and Historical Remarks
Appendix B: First-Order Logic
B.1 Introduction
B.2 Propositional Logic
B.3 First-Order Logic
Appendix C: Model Checking
C.1 Introduction
C.2 Intuitions
C.3 The Model Checking Problem
C.4 Model Checking Algorithms
C.5 Symbolic Model Checking
C.6 BDD-Based Symbolic Model Checking
Bibliography
Index
A
b
o
u
t
t
h
e
A
u
t
h
o
r
s
M
a
l
i
k
G
h
a
l
l
a
b
i
s
D
i
r
e
c
t
e
u
r
d
e
R
e
c
h
e
r
c
h
e
a
t
C
N
R
S
,
t
h
e
F
r
e
n
c
h
n
a
t
i
o
n
a
l
o
r
g
a
n
i
z
a
-
t
i
o
n
f
o
r
s
c
i
e
n
t
i
f
i
c
r
e
s
e
a
r
c
h
.
H
i
s
m
a
i
n
i
n
t
e
r
e
s
t
s
l
a
y
a
t
t
h
e
i
n
t
e
r
s
e
c
t
i
o
n
o
f
r
o
b
o
t
i
c
s
a
n
d
A
I
,
i
n
t
h
e
r
o
b
u
s
t
i
n
t
e
g
r
a
t
i
o
n
o
f
p
e
r
c
e
p
t
i
o
n
,
a
c
t
i
o
n
,
a
n
d
r
e
a
s
o
n
i
n
g
c
a
p
a
b
i
l
i
-
t
i
e
s
w
i
t
h
i
n
a
u
t
o
n
o
m
o
u
s
r
o
b
o
t
s
.
H
e
c
o
n
t
r
i
b
u
t
e
d
t
o
t
o
p
i
c
s
s
u
c
h
a
s
o
b
j
e
c
t
r
e
c
o
g
n
i
t
i
o
n
,
s
c
e
n
e
i
n
t
e
r
p
r
e
t
a
t
i
o
n
,
h
e
u
r
i
s
t
i
c
s
s
e
a
r
c
h
,
p
a
t
t
e
r
n
m
a
t
c
h
i
n
g
a
n
d
u
n
i
f
i
c
a
t
i
o
n
a
l
g
o
r
i
t
h
m
s
,
k
n
o
w
l
e
d
g
e
c
o
m
p
i
l
i
n
g
f
o
r
r
e
a
l
-
t
i
m
e
s
y
n
c
h
r
o
n
o
u
s
s
y
s
t
e
m
s
,
t
e
m
p
o
r
a
l
p
l
a
n
n
i
n
g
,
a
n
d
s
u
p
e
r
v
i
s
i
o
n
s
y
s
t
e
m
s
.
H
i
s
w
o
r
k
o
n
t
h
e
l
a
t
t
e
r
t
o
p
i
c
h
a
s
b
e
e
n
f
o
c
u
s
e
d
o
n
t
h
e
d
e
v
e
l
o
p
-
m
e
n
t
o
f
t
h
e
I
x
T
e
T
s
y
s
t
e
m
f
o
r
p
l
a
n
n
i
n
g
a
n
d
c
h
r
o
n
i
c
l
e
r
e
c
o
g
n
i
t
i
o
n
.
I
x
T
e
T
h
a
s
b
e
e
n
a
p
p
l
i
e
d
t
o
r
o
b
o
t
i
c
s
a
s
w
e
l
l
a
s
t
o
o
t
h
e
r
d
o
m
a
i
n
s
,
e
x
a
m
p
l
e
,
s
c
h
e
d
u
l
i
n
g
a
n
d
p
r
o
c
e
s
s
s
u
p
e
r
v
i
s
i
o
n
.
M
a
l
i
k
G
h
a
l
l
a
b
i
s
h
e
a
d
o
f
t
h
e
F
r
e
n
c
h
n
a
t
i
o
n
a
l
r
o
b
o
t
i
c
s
p
r
o
g
r
a
m
R
o
b
e
a
a
n
d
d
i
r
e
c
t
o
r
o
f
t
h
e
L
A
A
S
-
C
N
R
S
i
n
s
t
i
t
u
t
e
i
n
T
o
u
l
o
u
s
e
.
D
a
n
a
N
a
u
i
s
a
p
r
o
f
e
s
s
o
r
a
t
t
h
e
U
n
i
v
e
r
s
i
t
y
o
f
M
a
r
y
l
a
n
d
i
n
t
h
e
D
e
p
a
r
t
m
e
n
t
o
f
C
o
m
p
u
t
e
r
S
c
i
e
n
c
e
a
n
d
t
h
e
I
n
s
t
i
t
u
t
e
f
o
r
S
y
s
t
e
m
s
R
e
s
e
a
r
c
h
.
H
i
s
r
e
s
e
a
r
c
h
i
n
t
e
r
-
e
s
t
s
i
n
c
l
u
d
e
A
I
p
l
a
n
n
i
n
g
a
n
d
s
e
a
r
c
h
i
n
g
a
s
w
e
l
l
a
s
c
o
m
p
u
t
e
r
-
i
n
t
e
g
r
a
t
e
d
d
e
s
i
g
n
a
n
d
m
a
n
u
f
a
c
t
u
r
i
n
g
.
H
e
r
e
c
e
i
v
e
d
h
i
s
P
h
.
D
.
f
r
o
m
D
u
k
e
U
n
i
v
e
r
s
i
t
y
i
n
1
9
7
9
,
w
h
e
r
e
h
e
w
a
s
a
N
a
t
i
o
n
a
l
S
c
i
e
n
c
e
F
o
u
n
d
a
t
i
o
n
(
N
S
F
)
g
r
a
d
u
a
t
e
f
e
l
l
o
w
.
H
e
h
a
s
m
o
r
e
t
h
a
n
2
5
0
t
e
c
h
-
n
i
c
a
l
p
u
b
l
i
c
a
t
i
o
n
s
.
H
e
h
a
s
r
e
c
e
i
v
e
d
a
n
N
S
F
P
r
e
s
i
d
e
n
t
i
a
l
Y
o
u
n
g
I
n
v
e
s
t
i
g
a
t
o
r
a
w
a
r
d
,
a
n
O
u
t
s
t
a
n
d
i
n
g
F
a
c
u
l
t
y
a
w
a
r
d
,
s
e
v
e
r
a
l
"
b
e
s
t
p
a
p
e
r
"
a
w
a
r
d
s
,
a
n
d
s
e
v
e
r
a
l
p
r
i
z
e
s
f
o
r
c
o
m
p
e
t
i
t
i
o
n
-
l
e
v
e
l
p
e
r
f
o
r
m
a
n
c
e
o
f
h
i
s
A
I
p
l
a
n
n
i
n
g
a
n
d
g
a
m
e
-
p
l
a
y
i
n
g
p
r
o
g
r
a
m
s
.
H
e
i
s
a
F
e
l
l
o
w
o
f
t
h
e
A
m
e
r
i
c
a
n
A
s
s
o
c
i
a
t
i
o
n
f
o
r
A
r
t
i
f
i
c
i
a
l
I
n
t
e
l
l
i
g
e
n
c
e
(
A
A
A
I
)
.
P
a
o
l
o
T
r
a
v
e
r
s
o
i
s
H
e
a
d
o
f
D
i
v
i
s
i
o
n
a
t
I
T
C
-
I
R
S
T
i
n
T
r
e
n
t
o
,
I
t
a
l
y
.
T
h
e
D
i
v
i
s
i
o
n
i
s
a
c
t
i
v
e
i
n
t
h
e
f
i
e
l
d
s
o
f
a
u
t
o
m
a
t
e
d
p
l
a
n
n
i
n
g
,
m
o
d
e
l
c
h
e
c
k
i
n
g
,
c
a
s
e
-
b
a
s
e
d
r
e
a
s
o
n
i
n
g
a
n
d
m
a
c
h
i
n
e
l
e
a
r
n
i
n
g
,
d
i
s
t
r
i
b
u
t
e
d
s
y
s
t
e
m
s
,
a
n
d
a
g
e
n
t
s
.
H
i
s
m
a
i
n
r
e
s
e
a
r
c
h
i
n
t
e
r
-
e
s
t
s
i
n
c
l
u
d
e
a
u
t
o
m
a
t
e
d
r
e
a
s
o
n
i
n
g
,
p
l
a
n
n
i
n
g
u
n
d
e
r
u
n
c
e
r
t
a
i
n
t
y
,
a
n
d
t
h
e
s
y
n
t
h
e
s
i
s
o
f
c
o
n
t
r
o
l
l
e
r
s
.
H
e
h
a
s
c
o
n
t
r
i
b
u
t
e
d
t
o
r
e
s
e
a
r
c
h
o
n
m
e
c
h
a
n
i
z
e
d
m
e
t
a
t
h
e
o
r
i
e
s
,
f
o
r
m
a
l
v
e
r
i
f
i
c
a
t
i
o
n
,
k
n
o
w
l
e
d
g
e
m
a
n
a
g
e
m
e
n
t
,
e
m
b
e
d
d
e
d
s
y
s
t
e
m
s
,
a
n
d
l
o
g
i
c
s
f
o
r
t
h
e
i
n
t
e
-
g
r
a
t
i
o
n
o
f
p
l
a
n
n
i
n
g
,
a
c
t
i
n
g
,
a
n
d
s
e
n
s
i
n
g
,
f
o
r
a
l
i
s
t
o
f
r
e
c
e
n
t
p
u
b
l
i
c
a
t
i
o
n
s
.
H
e
i
s
a
m
e
m
b
e
r
o
f
t
h
e
E
d
i
t
o
r
i
a
l
B
o
a
r
d
o
f
t
h
e
J
o
u
r
n
a
l
o
f
A
r
t
i
f
i
c
i
a
l
I
n
t
e
l
l
i
g
e
n
c
e
R
e
s
e
a
r
c
h
,
a
m
e
m
b
e
r
o
f
t
h
e
E
x
e
c
u
t
i
v
e
C
o
u
n
c
i
l
o
f
t
h
e
I
n
t
e
r
n
a
t
i
o
n
a
l
C
o
n
f
e
r
e
n
c
e
o
n
A
u
t
o
m
a
t
e
d
P
l
a
n
n
i
n
g
a
n
d
S
c
h
e
d
u
l
i
n
g
,
a
n
d
a
m
e
m
b
e
r
o
f
t
h
e
B
o
a
r
d
o
f
D
i
r
e
c
t
o
r
s
o
f
t
h
e
I
t
a
l
i
a
n
A
s
s
o
c
i
a
t
i
o
n
f
o
r
A
r
t
i
f
i
c
i
a
l
I
n
t
e
l
l
i
g
e
n
c
e
.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
