| Planning Benchmarks | |
| The Role of Benchmarks | p. 3 |
| Evaluating Planner Performance | p. 3 |
| Worst-Case Evaluation | p. 4 |
| Average-Case Evaluation | p. 5 |
| Planning Benchmarks Are Important | p. 7 |
| Theoretical Analyses of Planning Benchmarks | p. 8 |
| Why Theoretical Analyses Are Useful | p. 8 |
| Published Results on Benchmark Complexity | p. 9 |
| Standard Benchmarks | p. 9 |
| Summary and Overview | p. 11 |
| Defining Planning Domains | p. 13 |
| Optimization Problems | p. 13 |
| Minimization Problems | p. 14 |
| Approximation Algorithms | p. 15 |
| Approximation Classes | p. 16 |
| Reductions | p. 18 |
| Formalizing Planning Domains | p. 21 |
| General Results and Reductions | p. 24 |
| Upper Bounds | p. 24 |
| Shortest Plan Length | p. 25 |
| Approximation Classes of Limited Interest | p. 26 |
| Relating Planning and (Bounded) Plan Existence | p. 28 |
| Generalization and Specialization | p. 29 |
| The Benchmark Suite | p. 31 |
| Defining the Competition Domains | p. 31 |
| The Benchmark Suite | p. 32 |
| IPC1 Domains | p. 32 |
| IPC2 Domains | p. 34 |
| IPC3 Domains | p. 34 |
| IPC4 Domains | p. 35 |
| Domains and Domain Families | p. 36 |
| Transportation and Route Planning | p. 39 |
| Transport and Route | p. 39 |
| The Transport Domain | p. 41 |
| The Route Domain | p. 43 |
| Special Cases and Hierarchy | p. 44 |
| General Results | p. 46 |
| Plan Existence | p. 52 |
| Hardness of Optimization | p. 54 |
| Constant Factor Approximation | p. 59 |
| Hardness of Constant Factor Approximation | p. 62 |
| Summary | p. 68 |
| Beyond Transport and Route | p. 71 |
| IPC Domains: Transportation and Route Planning | p. 75 |
| Gripper | p. 75 |
| Mystery and Mystery Prime | p. 76 |
| Logistics | p. 78 |
| Zenotravel | p. 83 |
| Depots | p. 85 |
| Miconic-10 | p. 88 |
| Rovers | p. 93 |
| Grid | p. 98 |
| Driverlog | p. 103 |
| Airport | p. 108 |
| Summary | p. 111 |
| IPC Domains: Others | p. 113 |
| Assembly | p. 113 |
| Blocksworld | p. 117 |
| Freecell | p. 117 |
| Movie | p. 126 |
| Pipesworld | p. 127 |
| Promela | p. 132 |
| PSR | p. 138 |
| Satellite | p. 142 |
| Schedule | p. 145 |
| Summary | p. 149 |
| Conclusions | p. 151 |
| Ten Conclusions | p. 151 |
| Going Further | p. 154 |
| Fast Downward | |
| Solving Planning Tasks Hierarchically | p. 157 |
| Introduction | p. 157 |
| Related Work | p. 163 |
| Causal Graphs and Abstraction | p. 164 |
| Causal Graphs and Unary STRIPS Operators | p. 165 |
| Multi-Valued Planning Tasks | p. 167 |
| Architecture and Overview | p. 168 |
| Translation | p. 171 |
| PDDL and Multi-valued Planning Tasks | p. 171 |
| Translation Overview | p. 175 |
| Normalization | p. 176 |
| Compiling Away Types | p. 177 |
| Simplifying Conditions | p. 177 |
| Simplifying Effects | p. 179 |
| Normalization Result | p. 179 |
| Invariant Synthesis | p. 180 |
| Initial Candidates | p. 182 |
| Proving Invariance | p. 183 |
| Refining Failed Candidates | p. 186 |
| Examples | p. 188 |
| Related Work | p. 188 |
| Grounding | p. 190 |
| Overview of Horn Exploration | p. 191 |
| Generating the Logic Program | p. 191 |
| Translating the Logic Program to Normal Form | p. 193 |
| Computing the Canonical Model | p. 195 |
| Axiom and Operator Instantiation | p. 197 |
| Multi-valued Planning Task Generation | p. 197 |
| Variable Selection | p. 198 |
| Converting the Initial State | p. 199 |
| Converting Operator Effects | p. 200 |
| Converting Conditions | p. 201 |
| Computing Axiom Layers | p. 202 |
| Generating the Output | p. 202 |
| Performance Notes | p. 203 |
| Relative Performance Compared to MIPS Translator | p. 203 |
| Absolute Performance | p. 205 |
| Knowledge Compilation | p. 207 |
| Overview | p. 207 |
| Domain Transition Graphs | p. 208 |
| Causal Graphs | p. 213 |
| Acyclic Causal Graphs | p. 214 |
| Generating and Pruning Causal Graphs | p. 215 |
| Causal Graph Examples | p. 217 |
| Successor Generators and Axiom Evaluators | p. 220 |
| Successor Generators | p. 220 |
| Axiom Evaluators | p. 221 |
| Search | p. 223 |
| Overview | p. 223 |
| The Causal Graph Heuristic | p. 224 |
| Conceptual View of the Causal Graph Heurstic | p. 225 |
| Computation of the Causal Graph Heuristic | p. 226 |
| States with Infinite Heuristic Value | p. 228 |
| Helpful Transitions | p. 229 |
| The FF Heuristic | p. 230 |
| Greedy Best-First Search in Fast Downward | p. 231 |
| Preferred Operators | p. 231 |
| Deferred Heuristic Evaluation | p. 232 |
| Multi-heuristic Best-First Search | p. 233 |
| Focused Iterative-Broadening Search | p. 234 |
| Experiments | p. 239 |
| Experiment Design | p. 239 |
| Benchmark Set | p. 240 |
| Experiment Setup | p. 242 |
| Translation and Knowledge Compilation vs. Search | p. 243 |
| Strips Domains from IPC1-3 | p. 243 |
| ADL Domains from IPC1-3 | p. 246 |
| Domains from IPC4 | p. 248 |
| Conclusions from the Experiment | p. 251 |
| Discussion | p. 253 |
| Summary | p. 253 |
| Major Contributors | p. 254 |
| Multi-valued Representations | p. 254 |
| Task Decomposition Heuristics | p. 256 |
| Minor Contributions | p. 257 |
| Going Further | p. 258 |
| References | p. 259 |
| Index | p. 267 |
| Table of Contents provided by Ingram. All Rights Reserved. |
