Understanding Planning Tasks: Domain Complexity and Heuristic Decomposition Book

Part I Planning Benchmarks

1 The Role of Benchmarks 3

1.1 Evaluating Planner Performance 3

1.1.1 Worst-Case Evaluation 4

1.1.2 Average-Case Evaluation 5

1.2 Planning Benchmarks Are Important 7

1.3 Theoretical Analyses of Planning Benchmarks 8

1.3.1 Why Theoretical Analyses Are Useful 8

1.3.2 Published Results on Benchmark Complexity 9

1.4 Standard Benchmarks 9

1.5 Summary and Overview 11

2 Defining Planning Domains 13

2.1 Optimization Problems 13

2.1.1 Minimization Problems 14

2.1.2 Approximation Algorithms 15

2.1.3 Approximation Classes 16

2.1.4 Reductions 18

2.2 Formalizing Planning Domains 21

2.3 General Results and Reductions 24

2.3.1 Upper Bounds 24

2.3.2 Shortest Plan Length 25

2.3.3 Approximation Classes of Limited Interest 26

2.3.4 Relating Planning and (Bounded) Plan Existence 28

2.3.5 Generalization and Specialization 29

3 The Benchmark Suite 31

3.1 Defining the Competition Domains 31

3.2 The Benchmark Suite 32

3.2.1 IPC1 Domains 32

3.2.2 IPC2 Domains 34

3.2.3 IPC3 Domains 34

3.2.4 IPC4 Domains 35

3.3 Domains and Domain Families 36

4 Transportation and Route Planning 39

4.1 Transport and Route 39

4.1.1 The Transport Domain 41

4.1.2 The Route Domain 43

4.1.3 Special Cases and Hierarchy 44

4.2 General Results 46

4.3 Plan Existence 52

4.4 Hardness of Optimization 54

4.5 Constant Factor Approximation 59

4.6 Hardness of Constant Factor Approximation 62

4.7 Summary 68

4.8 Beyond Transport and Route 71

5 IPC Domains: Transportation and Route Planning 75

5.1 Gripper 75

5.2 Mystery and Mystery Prime 76

5.3 Logistics 78

5.4 Zenotravel 83

5.5 Depots 85

5.6 Miconic-10 88

5.7 Rovers93

5.8 Grid 98

5.9 Driverlog 103

5.10 Airport 108

5.11 Summary 111

6 IPC Domains: Others 113

6.1 Assembly 113

6.2 Blocksworld 117

6.3 Freecell 117

6.4 Movie 126

6.5 Pipesworld 127

6.6 Promela 132

6.7 PSR 138

6.8 Satellite 142

6.9 Schedule 145

6.10 Summary 149

7 Conclusions 151

7.1 Ten Conclusions 151

7.2 Going Further 154

Part II Fast Downward

8 Solving Planning Tasks Hierarchically 157

8.1 Introduction 157

8.2 Related Work 163

8.2.1 Causal Graphs and Abstraction 164

8.2.2 Causal Graphs and Unary STRIPS Operators 165

8.2.3 Multi-Valued Planning Tasks 167

8.3 Architecture and Overview 168

9 Translation 171

9.1 PDDL and Multi-valued Planning Tasks 171

9.2 Translation Overview 175

9.3 Normalization 176

9.3.1 Compiling Away Types 177

9.3.2 Simplifying Conditions 177

9.3.3 Simplifying Effects 179

9.3.4 Normalization Result 179

9.4 Invariant Synthesis 180

9.4.1 Initial Candidates 182

9.4.2 Proving Invariance 183

9.4.3 Refining Failed Candidates 186

9.4.4 Examples 188

9.4.5 Related Work 188

9.5 Grounding 190

9.5.1 Overview of Horn Exploration 191

9.5.2 Generating the Logic Program 191

9.5.3 Translating the Logic Program to Normal Form 193

9.5.4 Computing the Canonical Model 195

9.5.5 Axiom and Operator Instantiation 197

9.6 Multi-valued Planning Task Generation 197

9.6.1 Variable Selection 198

9.6.2 Converting the Initial State 199

9.6.3 Converting Operator Effects 200

9.6.4 Converting Conditions 201

9.6.5 Computing Axiom Layers 202

9.6.6 Generating the Output 202

9.7 Performance Notes 203

9.7.1 Relative Performance Compared to MIPS Translator 203

9.7.2 Absolute Performance 205

10 Knowledge Compilation 207

10.1 Overview 207

10.2 Domain Transition Graphs 208

10.3 Causal Graphs 213

10.3.1 Acyclic Causal Graphs 214

10.3.2 Generating and Pruning Causal Graphs 215

10.3.3 Causal Graph Examples 217

10.4 Successor Generators and Axiom Evaluators 220

10.4.1 Successor Generators 220

10.4.2 Axiom Evaluators 221

11 Search 223

11.1 Overview 223

11.2 The Causal Graph Heuristic 224

11.2.1 Conceptual View of the Causal Graph Heurstic 225

11.2.2 Computation of the Causal Graph Heuristic 226

11.2.3 States with Infinite Heuristic Value 228

11.2.4 Helpful Transitions 229

11.3 The FF Heuristic 230

11.4 Greedy Best-First Search in Fast Downward 231

11.4.1 Preferred Operators 231

11.4.2 Deferred Heuristic Evaluation 232

11.5 Multi-heuristic Best-First Search 233

11.6 Focused Iterative-Broadening Search 234

12 Experiments 239

12.1 Experiment Design 239

12.1.1 Benchmark Set 240

12.1.2 Experiment Setup 242

12.1.3 Translation and Knowledge Compilation vs. Search 243

12.2 Strips Domains from IPC1-3 243

12.3 ADL Domains from IPC1-3 246

12.4 Domains from IPC4 248

12.5 Conclusions from the Experiment 251

13 Discussion 253

13.1 Summary 253

13.2 Major Contributors 254

13.2.1 Multi-valued Representations 254

13.2.2 Task Decomposition Heuristics 256

13.3 Minor Contributions 257

13.4 Going Further 258

References 259

Index 267