Learning Appropriate Abstractions for Planning in Formation Problems

Abstract

Abstraction is a powerful technique that reduces the size of large search spaces encountered during problem solving. Recently, techniques for automatically generating appropriate abstractions have been developed. Current techniques create abstractions by introducing approximations that eliminate details by ignoring conditions or constraints in the domain. In this article we argue that approximation is best suited to derivation problems such as those in the blocks world and robot planning domains. We propose a new technique for introducing appropriate abstractions for solving formation problems that arise in domains such as mechanical design and chess. This technique introduces abstractions by changing the gain size of both the objects in the domain, through aggregation of the existing objects, and the goals in the domain, through the refinement of existing goals. We sketch a hierarchical planner that exploits these abstractions to effectively solve formation problems. We illustrate our approach in the domain of chess.