Reformulating Theories Of Action For Efficient Planning

D. Benjamin

Domain theories are used in a wide variety of fields of computer science as a means of representing properties of the domain under consideration. These fields include artificial intelligence, software engineering, VLSI design, cryptography, and distributed computing. In each ease, the advantages of using theories include the precision of task specification and the ability to verify results. A great deal of effort has gone into the development of tools to make the use of theories easier. This effort has met with some success. However, a fundamental problem remains: the choice of symbolic formulation for a theory, including both the choice of features for describing the environment and the design of abstractions that encode the actions. This paper describes fundamental research on the algebraic structure of the representations of domain theories. The perspective of this work is to view a problem’s state space as though it were physical space, and the actions in the state space as though they were physical motions. A domain theory should then state the laws of motion within the space. Following the analogy with physics, a representation is a coordinate system, and theories are transformed by changing coordinates. This permits symbolic computational techniques to be used to transform theories and find useful decompositions. A system has been implemented using Mathematiea and GAP that performs these computations. The mathematical basis for this approach is given, and the computations are illustrated by examples.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.