Improving AI planning and search with automatic abstraction.

摘要

Planning is ubiquitous in real life. AI planning and single-agent heuristic search, two major areas of artificial intelligence research, focus on machine-generated solutions to a great range of real-life planning applications. To successfully tackle large planning problems, significant advances in technology are necessary.; This research focuses on speeding up planning and single-agent search. Abstraction, a central idea of this work, is explored in three major application domains, each assuming a different level of application-specific knowledge available beforehand.; The first framework is fully automated AI planning, with no application-specific knowledge provided. The contributions include a family of adaptive techniques that automatically infer new information about a domain. Macro-actions are extracted from previously acquired information. Algorithms for ranking, filtering, and using macros at runtime are introduced. Experiments show an improvement of orders of magnitude, as compared to a state-of-the-art planner such as FF, in domains where structural information can automatically be inferred. Macro-FF, an adaptive planner that implements these ideas, successfully participated in the International Planning Competition IPC-4, taking the first place in 3 out of 7 domains where it competed.; As a second domain, abstraction for path-finding on grid maps is explored. Partial application-specific knowledge is assumed, since path-finding usually takes place in a space with topological structure. The main contribution is Hierarchical Path-Finding A*, an approach shown to achieve up to a 10-fold speed-up in exchange for a 1% degradation in path duality, as compared to a highly optimized implementation of A*.; The third research domain provides a rich application-specific context: the puzzle of Sokoban. The main contribution is a novel solving approach that combines planning with abstraction. A maze is partitioned into rooms and tunnels, allowing the decomposition of a hard initial problem into several much simpler sub-problems. Experiments show that a prototype implementation of these ideas is competitive with a state-of-the-art specialized solver, on a subset of problems.