Utilizing Problem Structure in Planning: A Local Search Approach (Lecture Notes in Computer Science)

Planning is a crucial skill for any autonomous agent, be it a physically embedded agent, such as a robot, or a purely simulated software agent. For this reason, planning, as a central research area of artificial intelligence from its beginnings, has gained even more attention and importance recently. After giving a general introduction to AI planning, the book describes and carefully evaluates the algorithmic techniques used in fast-forward planning systems (FF), demonstrating their excellent performance in many wellknown benchmark domains. In advance, an original and detailed investigation identifies the main patterns of structure which cause the performance of FF, categorizing planning domains in a taxonomy of different classes with respect to their aptitude for being solved by heuristic approaches, such as FF. As shown, the majority of the planning benchmark domains lie in classes which are easy to solve.

Planning is a crucial skill for any autonomous agent, be it a physically embedded agent, such as a robot, or a purely simulated software agent. For this reason, planning, as a central research area of artificial intelligence from its beginnings, has gained even more attention and importance recently.

After giving a general introduction to AI planning, the book describes and carefully evaluates the algorithmic techniques used in fast-forward planning systems (FF), demonstrating their excellent performance in many wellknown benchmark domains. In advance, an original and detailed investigation identifies the main patterns of structure which cause the performance of FF, categorizing planning domains in a taxonomy of different classes with respect to their aptitude for being solved by heuristic approaches, such as FF. As shown, the majority of the planning benchmark domains lie in classes which are easy to solve.

Front Matter....Pages - Front Matter....Pages 1-1 Chapter 1: Introduction....Pages 3-10 Chapter 2: Planning....Pages 11-31 Front Matter....Pages 33-33 Chapter 3: Base Architecture....Pages 35-73 Chapter 4: Dead Ends....Pages 75-88 Chapter 5: Goal Orderings....Pages 89-105 Chapter 6: The AIPS-2000 Competition....Pages 107-112 Front Matter....Pages 113-113 Chapter 7: Gathering Insights....Pages 115-134 Chapter 8: Verifying the h + Hypotheses....Pages 135-180 Chapter 9: Supporting the h FF Hypotheses....Pages 181-197 Chapter 10: Discussion....Pages 199-202 Appendix A: Formalized Benchmark Domains....Pages 203-233 Appendix B: Automated Instance Generation....Pages 235-241 Back Matter....Pages - One of the distinguishing qualities of humans is their pronounced ability to anticipate the effects of their actions, and form plans to achieve their goals.