Practical Planning (eBook)

Extending the Classical AI Planning Paradigm

David E. Wilkins (Autor)

eBook Download: PDF

2014 | 1. Auflage
205 Seiten
Elsevier Science (Verlag)
978-0-08-051447-5 (ISBN)

Infos

Planning, or reasoning about actions, is a fundamental element of intelligent behavior--and one that artificial intelligence has found very difficult to implement. The most well-understood approach to building planning systems has been under refinement since the late 1960s and has now reached a level of maturity where there are good prospects for building working planners. Practical Planning is an in-depth examination of this classical planning paradigm through an intensive case study of SIPE, a significantly implemented planning system. The author, the developer of SIPE, defines the planning problem in general, explains why reasoning about actions is so complex, and describes all parts of the SIPE system and the algorithms needed to achieve efficiency. Details are discussed in the context of problems and important issues in building a practical planner; discussions of how other systems address these issues are also included. Assuming only a basic background in AI, Practical Planning will be of great interest to professionals interested in incorporating planning capabilities into AI systems.

Inhalt

Front Cover 1
Practical Planning: Extending the Classical AI Planning Paradigm 4
Copyright Page 5
Table of Contents 8
Acknowledgments 6
List of Figures 12
List of Tables 14
CHAPTER 1. Reasoning about Actions and Planning 16
1.1 Philosophical and Practical Importance 16
1.2 The Classical AI Planning Problem 18
1.3 Reactive Planning 20
1.4 The Essence of Planning 21
1.5 Capabilities of a Planning System 23
1.6 How Hard is Planning? 26
1.7 Classical AI Planning Systems 27
1.8 SIPE 31
CHAPTER 2. Basic Assumptions and Limitations 34
2.1 Important Features 36
2.2 Limitations 39
CHAPTER 3. SIPE and Its Representations 42
3.1 Representation of Domain Objects and Relationships 46
3.2 Operator Description Language 48
3.3 Plan Rationale 53
3.4 Plans 54
CHAPTER 4. Hierarchical Planning at Differing Abstraction Levels 60
4.1 The Many Guises of Hierarchical Planning 61
4.2 A Problem with Current Planners 63
4.3 Solutions 66
CHAPTER 5. Constraints 74
5.1 SIPE's Constraint Language 75
5.2 Use of Constraints 78
5.3 Unification 80
CHAPTER 6. The Truth Criterion 82
6.1 The Formula Truth Criterion 84
6.2 The PTC for Ground, Linear Plans 86
6.3 Introducing Variables 86
6.4 Introducing Existential Quantifiers 89
6.5 Introducing Universal Quantifiers 93
6.6 Introducing Nonlinearity 95
6.7 Summary 98
CHAPTER 7. Deductive Causal Theories 100
7.1 A Motivating Example 101
7.2 Domain Rules 103
7.3 Problems with Domain Rules 105
7.4 Heuristic Adequacy and Expressive Power 107
CHAPTER 8. Plan Critics 110
8.1 Solving the Constraint Network 111
8.2 Parallel Interactions 112
8.3 Goal Phantomization 114
8.4 Solving Harmful Interactions 118
8.5 Adding Ordering Constraints 120
8.6 Examples 121
CHAPTER 9. Resources: Reusable, Consumable, Temporal 128
9.1 Reusable Resources 129
9.2 Representation of Numerical Quantities 133
9.3 Consumable Resources 136
9.4 Temporal Reasoning 142
9.5 Manipulating Numerical Quantities 144
9.6 Summary 146
CHAPTER 10. Search 148
10.1 Automatic Search 149
10.2 Intermingling Planning and Execution 153
10.3 Interactive Control 154
10.4 Domain-Dependent Search Control 154
10.5 Other Search Strategies 155
CHAPTER 11. Replanning During Execution 160
11.1 Overview of SIPE's Execution-Monitoring System 162
11.2 Unknowns 163
11.3 Interpreting the Input 164
11.4 The Problem Recognizer 165
11.5 Replanning Actions 168
11.6 The General Replanner 174
11.7 Examples 176
11.8 Searching the Space of Modified Plans 178
11.9 Summary 180
CHAPTER 12. Planning and Reactivity 184
12.1 Level of the Interface 187
12.2 Who Is in Control? 188
CHAPTER 13. Achieving Heuristic Adequacy 192
13.1 Summary of Heuristics 193
13.2 Subsumption of Pred Constraints 197
13.3 Encoding Domains in SIPE 199
CHAPTER 14. Comparison with Other Systems 202
14.1 Nonclassical Planning Systems 203
14.2 Previous Classical Planners 204
14.3 Constraints 205
14.4 Critics 206
14.5 Replanning 207
14.6 Heuristic Adequacy 209
Bibliography 212
Index 216

Produkt-Details

• Erscheint lt. Verlag: 28.6.2014
• Sprache: englisch
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• Themenwelt: Sozialwissenschaften ► Kommunikation / Medien ► Buchhandel / Bibliothekswesen
• ISBN-10: 0-08-051447-2 / 0080514472
• ISBN-13: 978-0-08-051447-5 / 9780080514475