Changes of problem representation: Theory and experiments
Eugene Fink
Springer-Verlag, Berlin, Germany, 2003. ISBN 3-7908-1523-3.Available for purchase through Springer-Verlag and Amazon.Com.
|
|
Changes of problem representation: Theory and experimentsEugene FinkSpringer-Verlag, Berlin, Germany, 2003. ISBN 3-7908-1523-3.Available for purchase through Springer-Verlag and Amazon.Com. |
| Part I. Introduction
. 1. Motivation . 1.1 Representations in problem solving . 1.1.1 Informal examples . 1.1.2 Alternative definitions of representation . 1.1.3 Representations in the SHAPER system . 1.1.4 The role of representation . 1.2 Examples of representation changes . 1.2.1 Tower-of-Hanoi Domain . 1.2.2 Constructing an abstraction hierarchy . 1.2.3 Selecting primary effects . 1.2.4 Partially instantiating operators . 1.2.5 Choosing a problem solver . 1.3 Related work . 1.3.1 Psychological evidence . 1.3.2 Automatic representation changes . 1.3.3 Integrated systems . 1.3.4 Theoretical results . 1.4 Overview of the approach . 1.4.1 Architecture of the system . 1.4.2 Specifications of description changers . 1.4.3 Search in the space of representations . 1.5 Extended abstract . 2. PRODIGY search . 2.1 PRODIGY system . 2.1.1 History . 2.1.2 Advantages and drawbacks . 2.2 Search engine . 2.2.1 Encoding of problems . 2.2.2 Incomplete solutions . 2.2.3 Simulating execution . 2.2.4 Backward chaining . 2.2.5 Main versions . 2.3 Extended domain language . 2.3.1 Extended operators . 2.3.2 Inference rules . 2.3.3 Complex types . 2.4 Search control . 2.4.1 Avoiding redundant search . 2.4.2 Knob values . 2.4.3 Control rules . 2.5 Completeness . 2.5.1 Limitation of means-ends analysis . 2.5.2 Clobbers among if-effects . 2.5.3 Other violations of completeness . 2.5.4 Completeness proof . 2.5.5 Performance of the extended solver . 2.5.6 Summary of completeness results . . Part II. Description changers . 3. Primary effects . 3.1 Search with primary effects . 3.1.1 Motivating examples . 3.1.2 Main definitions . 3.1.3 Search algorithm . 3.2 Completeness of primary effects . 3.2.1 Completeness and solution costs . 3.2.2 Condition for completeness . 3.3 Analysis of search reduction . 3.4 Automatically selecting primary effects . 3.4.1 Selection heuristics . 3.4.2 Instantiating the operators . 3.5 Learning additional primary effects . 3.5.1 Inductive learning algorithm . 3.5.2 Selection heuristics . 3.5.3 Sample complexity . 3.6 ABTWEAK experiments . 3.6.1 Controlled experiments . 3.6.2 Robot world and machine shop . 3.7 PRODIGY experiments . 3.7.1 Domains from ABTWEAK . 3.7.2 Sokoban puzzle and STRIPS world . 3.7.3 Summary of experimental results . 4 Abstraction . 4.1 Abstraction in problem solving . 4.1.1 History of abstraction . 4.1.2 Hierarchical problem solving . 4.1.3 Efficiency and possible problems . 4.1.4 Avoiding the problems . 4.1.5 Ordered monotonicity . 4.2 Hierarchies for the PRODIGY domain language . 4.2.1 Additional constraints . 4.2.2 Abstraction graph . 4.3 Partial instantiation of predicates . 4.3.1 Improving the granularity . 4.3.2 Instantiation graph . 4.3.3 Basic operations . 4.3.4 Construction of a hierarchy . 4.3.5 Level of a given literal . 4.4 Performance of the abstraction search . 5. Summary and extensions . 5.1 Abstracting the effects of operators . 5.2 Identifying the relevant literals . 5.3 Summary of work on description changers . 5.3.1 Library of description changers . 5.3.2 Unexplored description changes . 5.3.3 Toward a theory of description changes . . Part III. Top-level control . 6. Multiple representations . 6.1 Solvers and changers . 6.1.1 Domain descriptions . 6.1.2 Problem solvers . 6.1.3 Description changers . 6.1.4 Representations . 6.2 Description and representation spaces . 6.2.1 Descriptions, solvers, and changers . 6.2.2 Description space . 6.2.3 Representation space . 6.3 Utility functions . 6.3.1 Gain function . 6.3.2 Additional constraints . 6.3.3 Representation quality . 6.3.4 Use of multiple representations . 6.3.5 Summing gains . 6.4 Simplifying assumptions . 7. Statistical selection . 7.1 Selection task . 7.1.1 Previous and new results . 7.1.2 Example and general problem . 7.2 Statistical foundations . 7.3 Computations of the gain estimates . 7.4 Selection of a representation and time bound . 7.4.1 Candidate bounds . 7.4.2 Setting a time bound . 7.4.3 Selecting a representation . 7.4.4 Selection without past data . 7.5 Empirical examples . 7.5.1 Extended transportation domain . 7.5.2 Phone-call domain . 7.6 Artificial tests 8. Statistical extensions
|
1
. 3
4 4 6 8 12 14 14 16 19 21 21 23 24 25 26 27 28 29 30 32 34 . 39 40 40 41 43 43 44 46 47 49 53 53 55 58 61 61 64 65 66 67 70 73 75 77 78 . . 79 . 81 82 82 83 86 88 89 90 92 95 96 99 107 108 111 111 115 115 118 120 120 122 131 . 133 133 133 135 135 138 140 141 142 144 149 149 151 154 157 160 160 . 167 167 175 182 182 184 190 . . 191 . 193 193 193 194 195 195 195 195 197 197 199 199 200 201 202 203 204 . 205 205 205 206 208 211 214 216 216 218 220 222 222 223 225 . 231 231 233 233 235 237 239 239 242 243 . 245 245 245 246 249 250 250 . . 255 . 259 259 267 274 . 279 279 287 293 . 299 299 309 315 . 321 321 328 334 . 339 . 343 |