Until this book, possibly the only comprehensive treatment of planning has been a paper collection: Readings in Planning (Morgan Kaufmann Series in Representation and Reasoning). What these authors have done is phenominal - they've marshalled a bibliography of 565 publications into a comprehensive treatment from a common point of view. That makes it much easier to analyze different approaches to planning, as well as to see how various application domains have applied these approaches to solve real problems.
The first 448 pages of the book discusses various planning approaches, from classical state-space planning including recent improvements in the STRIPS model (GraphPlan), to dealing with temporal operations and resource scheduling. They then use the readers understanding of these deterministic approaches to bridge to planning under uncertainty, which is where planning meets the "real world" of imperfect knowledge, observability or even actions having unintended effects. The next roughly 100 pages goes into application domains discussing how space applications, robotics, manufacturing, emergency evacuation and even the game of bridge has used these planning methods to give the reader better intuitions on their own domain.
Finally some minority approaches such as case-based planning and plan related areas such as plan recognition are introduced briefly, leading to tutorial appendices on search (and complexity), first order logic, and model checking.
I have been working on the periphery of planning research for over 25 years, including (currently) directing advanced research in adversarial planning (a topic not addressed by this book, but that's hardly surprising given the novelty of the approach ;-). This is the best overview and reference I've seen to date for this very important area.
Author(s): Malik Ghallab, Dana Nau, Paolo Traverso
Series: The Morgan Kaufmann Series in Artificial Intelligence
Edition: 1
Publisher: Morgan Kaufmann
Year: 2004
Language: English
Pages: 638
1558608567......Page 1
Copyright......Page 2
About the Authors......Page 3
Table of Contents......Page 4
Foreword......Page 18
Preface......Page 19
Web Site......Page 20
Acknowledgments......Page 22
Table of Notation......Page 23
1.1 First Intuitions on Planning......Page 25
1.2 Forms of Planning......Page 26
1.3 Domain-Independent Planning......Page 27
1.4 Conceptual Model for Planning......Page 29
1.5 Restricted Model......Page 33
1.6 Extended Models......Page 35
1.7 A Running Example: Dock-Worker Robots......Page 37
Part I: Classical Planning......Page 41
2.1 Introduction......Page 43
2.2.1 Planning Domains, Problems, and Solutions......Page 44
2.2.2 State Reachability......Page 46
2.2.3 Stating a Planning Problem......Page 47
2.2.4 Properties of the Set-Theoretic Representation......Page 48
2.3.1 States......Page 51
2.3.2 Operators and Actions......Page 52
2.3.3 Plans, Problems, and Solutions......Page 55
2.3.4 Semantics of Classical Representations......Page 57
2.4.2 Conditional Planning Operators......Page 58
2.4.3 Quantified Expressions......Page 60
2.4.4 Disjunctive Preconditions......Page 61
2.4.5 Axiomatic Inference......Page 62
2.4.8 Extended Goals......Page 63
2.5.1 State Variables......Page 65
2.5.2 Operators and Actions......Page 67
2.5.3 Domains and Problems......Page 68
2.5.4 Properties......Page 70
2.6 Comparisons......Page 71
2.7 Discussion and Historical Remarks......Page 73
2.8 Exercises......Page 74
3.1 Introduction......Page 78
3.2 Preliminaries......Page 79
3.3 Decidability and Undecidability Results......Page 80
3.4 Complexity Results......Page 82
3.4.1 Binary Counters......Page 83
3.4.2 Unrestricted Classical Planning......Page 84
3.4.3 Other Results......Page 86
3.5 Limitations......Page 88
3.7 Exercises......Page 89
4.2 Forward Search......Page 91
4.2.1 Formal Properties......Page 92
4.2.2 Deterministic Implementations......Page 94
4.3 Backward Search......Page 95
4.4 The STRIPS Algorithm......Page 98
4.5.1 The Container-Stacking Domain......Page 100
4.5.2 Planning Algorithm......Page 101
4.7 Exercises......Page 103
5.1 Introduction......Page 106
5.2 The Search Space of Partial Plans......Page 107
5.3 Solution Plans......Page 112
5.4.1 The PSP Procedure......Page 115
5.4.2 The PoP Procedure......Page 120
5.5 Extensions......Page 121
5.6 Plan-Space versus State-Space Planning......Page 122
5.7 Discussion and Historical Remarks......Page 124
5.8 Exercises......Page 126
Part II: Neoclassical Planning......Page 131
6.1 Introduction......Page 133
6.2.1 Reachability Trees......Page 134
6.2.2 Reachability with Planning Graphs......Page 137
6.2.3 Independent Actions and Layered Plans......Page 139
6.2.4 Mutual Exclusion Relations......Page 140
6.3.1 Expanding the Planning Graph......Page 143
6.3.2 Searching the Planning Graph......Page 145
6.3.3 Analysis of Graphplan......Page 149
6.4.1 Extending the Language......Page 151
6.4.2 Improving the Planner......Page 153
6.4.3 Extending the Independence Relation......Page 154
6.5 Discussion and Historical Remarks......Page 157
6.6 Exercises......Page 159
7.1 Introduction......Page 162
7.2.1 States as Propositional Formulas......Page 163
7.2.2 State Transitions as Propositional Formulas......Page 164
7.2.3 Planning Problems as Propositional Formulas......Page 166
7.3 Planning by Satisfiability......Page 170
7.3.1 Davis-Putnam Procedure......Page 171
7.3.2 Stochastic Procedures......Page 175
7.4 Different Encodings......Page 179
7.4.1 Action Representation......Page 180
7.4.2 Frame Axioms......Page 181
7.5 Discussion and Historical Remarks......Page 183
7.6 Exercises......Page 184
8.1 Introduction......Page 186
8.2 Constraint Satisfaction Problems......Page 187
8.3 Planning Problems as CSPs......Page 191
8.3.1 Encoding a Planning Problem into a CSP......Page 193
8.3.2 Analysis of the CSP Encoding......Page 196
8.4.1 Search Algorithms for CSPs......Page 197
8.4.2 Filtering Techniques......Page 199
8.4.3 Local Search Techniques and Hybrid Approaches......Page 203
8.5.1 Active CSPs......Page 204
8.6.1 CSPs in Plan-Space Search......Page 206
8.6.2 CSPs for Planning-Graph Techniques......Page 207
8.7 Discussion and Historical Remarks......Page 208
8.8 Exercises......Page 209
Part III: Heuristics and Control Strategies......Page 211
9.2 Design Principle for Heuristics: Relaxation......Page 216
9.3.1 State Reachability Relaxation......Page 218
9.3.2 Heuristically Guided Backward Search......Page 221
9.3.3 Admissible State-Space Heuristics......Page 222
9.3.4 6raphpian as a Heuristic Search Planner......Page 224
9.4.1 Flaw-Selection Heuristics......Page 225
9.4.2 Resolver-Selection Heuristics......Page 229
9.5 Discussion and Historical Remarks......Page 230
9.6 Exercises......Page 231
10.1 Introduction......Page 233
10.2 Simple Temporal Logic......Page 234
10.3 Progression......Page 236
10.4 Planning Procedure......Page 238
10.5 Extensions......Page 239
10.6 Extended Goals......Page 240
10.7 Discussion and Historical Remarks......Page 242
10.8 Exercises......Page 243
11.1 Introduction......Page 245
11.2.1 Tasks and Methods......Page 247
11.2.2 Problems and Solutions......Page 251
11.3 Total-Order STN Planning......Page 254
11.4 Partial-Order STN Planning......Page 256
11.5.1 Task Networks......Page 260
11.5.2 HTN Methods......Page 261
11.5.3 HTN Problems and Solutions......Page 263
11.5.4 Planning Procedures......Page 264
11.6.1 HTN Planning versus STN Planning......Page 266
11.6.2 HTN Methods versus Control Rules......Page 267
11.7.1 Extensions from Chapter 2......Page 268
11.7.2 Additional Extensions......Page 271
11.8 Extended Goals......Page 272
11.9 Discussion and Historical Remarks......Page 273
11.10 Exercises......Page 275
12.1 Introduction......Page 278
12.2.1 Situations......Page 279
12.2.2 Actions......Page 280
12.2.3 Planning Domains, Problems, and Solutions......Page 282
12.2. 4 Plans as Programs in Situation Calculus......Page 284
12. 3 Dynamic Logic......Page 285
12.3.1 The Language of the Logic......Page 286
12.3.2 The Semantics......Page 287
12.3.4 Planning Domains, Problems, and Solutions......Page 288
12.3.5 Extensions......Page 289
12.3.6 User-Defined Control Strategies as Tactics......Page 290
12.4 Discussion and Historical Remarks......Page 291
12. 5 Exercises......Page 293
Part IV: Planning with Time and Resources......Page 295
13.2 Temporal References and Relations......Page 299
13.3.1 Point Algebra......Page 304
13.3.2 Interval Algebra......Page 307
13.3.3 A Geometric Interpretation of Interval Algebra......Page 313
13.3.4 Interval Algebra versus Point Algebra......Page 315
13.4 Quantitative Temporal Constraints......Page 316
13.4.1 Simple Temporal Constraints......Page 317
13.4.2 Temporal Constraint Networks......Page 319
13.5 Discussion and Historical Remarks......Page 320
13.6 Exercises......Page 321
14 .1 Introduction......Page 323
14.2.1 Temporal Expressions and Temporal Databases......Page 324
14.2.2 Temporal Planning Operators......Page 328
14.2.3 Domain Axioms......Page 331
14.2.4 Temporal Planning Domains, Problems, and Plans......Page 334
14.2.5 Concurrent Actions with Interfering Effects......Page 335
14.2.6 A Temporal Planning Procedure......Page 337
14.3 Planning with Chronicles......Page 340
14.3.1 State Variables, Timelines, and Chronicles......Page 341
14.3.2 Chronicles as Planning Operators......Page 348
14.3.3 Chronicle Planning Procedures......Page 350
14.3.4 Constraint Management in CP......Page 353
14.3.5 Search Control in CP......Page 355
14.4 Discussion and Historical Remarks......Page 357
14.5 Exercises......Page 359
15.1 Introduction......Page 362
15.2 Elements of Scheduling Problems......Page 364
15.2.2 Resources......Page 365
15.2. 3 Constraints and Cost Functions......Page 367
15.3.1 Classes of Machine Scheduling Problems......Page 369
15.3.2 Complexity of Machine Scheduling......Page 371
15.3.4 Planning and Machine Scheduling......Page 373
15.4.1 Representation......Page 375
15.4.2 Detecting Resource Conflicts......Page 380
15.4.3 Managing Resource Conflict Flaws......Page 383
15.5 Discussion and Historical Remarks......Page 385
15.6 Exercises......Page 386
Part V: Planning under Uncertainty......Page 388
16.1 Introduction......Page 392
16.2.1 Domains, Plans, and Planning Problems......Page 393
16.2.2 Planning Algorithms......Page 399
16.3.1 Domains, Plans, and Planning Problems......Page 405
16.3.2 Planning Algorithms......Page 409
16.4 Reachability and Extended Goals......Page 410
16.5 Discussion and Historical Remarks......Page 411
16.6 Exercises......Page 413
17.1 Introduction......Page 415
17.2 Planning for Reachability Goals......Page 416
17.2.1 Domains, Plans, and Planning Problems......Page 417
17.2.2 Planning Algorithms......Page 420
17.3.1 Domains, Plans, and Planning Problems......Page 426
17.3.2 Planning Algorithms......Page 430
17.3.3 Beyond Temporal Logic......Page 433
17.4.1 Domains, Plans, and Planning Problems......Page 437
17.4.2 Planning Algorithms......Page 441
17.6 Discussion and Historical Remarks......Page 444
17.7 Exercises......Page 446
18.2 Planning as Satisfiability......Page 448
18.2.1 Planning Problems......Page 449
18.2.2 Planning Problems as Propositional Formulas......Page 450
18.2.4 QBF Planning......Page 453
18.3 Planning Graphs......Page 454
18.4 Discussion and Historical Remarks......Page 457
18.5 Exercises......Page 458
Part VI: Case Studies and Applications......Page 459
19.3 The Autonomous Remote Agent......Page 461
19.4 The Remote Agent Architecture......Page 463
19.5 The Planner Architecture......Page 467
19.6 The Deep Space 1 Experiment......Page 471
19.6.1 Validation Objectives......Page 472
19.6.2 Scenarios......Page 473
19.6.3 Experiment Results......Page 474
19.7 Discussion and Historical Remarks......Page 476
20.1 Introduction......Page 478
20.2 Path and Motion Planning......Page 480
20.3 Planning for the Design of a Robust Controller......Page 486
20.3.1 Sensory-Motor Functions......Page 487
20.3.2 Modalities......Page 489
20.3.3 The Controller......Page 492
20.4 Dock-Worker Robots......Page 496
20.5 Discussion and Historical Remarks......Page 499
21.2 Machined Parts......Page 501
21.3 Feature Extraction......Page 503
21.4 Generating Abstract Plans......Page 505
21.6 Additional Steps......Page 507
21.8 Efficiency Considerations......Page 510
21.9 Concluding Remarks......Page 511
22.1 Introduction......Page 512
22.2 Evacuation Operations......Page 513
22.3.1 HTNs......Page 514
22.4 Hierarchical Task Editor......Page 515
22.5.1 How SiN Works......Page 516
22.5.3 Imperfect World Information......Page 518
22.6 Example......Page 519
22.7 Summary......Page 520
22.8 Discussion and Historical Remarks......Page 522
23.2 Overview of Bridge......Page 524
23.3 Game-Tree Search in Bridge......Page 526
23.4 Adapting HTN Planning for Bridge......Page 528
23.5 Implementation and Results......Page 531
Part VII: Conclusion......Page 532
24.1 Case-Based Planning......Page 534
24.2 Linear and Integer Programming......Page 536
24.3 Multiagent Planning......Page 537
24.4 Plan Merging and Plan Rewriting......Page 538
24.5 Abstraction Hierarchies......Page 539
24.6 Domain Analysis......Page 541
24.7 Planning and Learning......Page 542
24.8 Planning and Acting, Situated Planning, and Dynamic Planning......Page 543
24.9 Plan Recognition......Page 544
24.10 Suggestions for Future Work......Page 547
A.1 Nondeterministic Problem Solving......Page 548
A.2 State-Space Search......Page 549
A.3 Problem-Reduction Search......Page 553
A.4 Computational Complexity of Procedures......Page 555
A.5 Computational Complexity of Problems......Page 556
A.6 Planning Domains as Language-Recognition Problems......Page 557
A.7 Discussion and Historical Remarks......Page 558
B.2 Propositional Logic......Page 559
B.3 First-Order Logic......Page 561
C.2 Intuitions......Page 565
C.3 The Model Checking Problem......Page 567
C.4 Model Checking Algorithms......Page 569
C.5 Symbolic Model Checking......Page 571
C.6 BDD-Based Symbolic Model Checking......Page 574
Bibliography......Page 577
Index......Page 612
