A Uniform Abstraction Framework for Generalized Planning

A Uniform Abstraction Framework for Generalized Planning

Zhenhe Cui, Yongmei Liu, Kailun Luo

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 1837-1844. https://doi.org/10.24963/ijcai.2021/253

Generalized planning aims at finding a general solution for a set of similar planning problems. Abstractions are widely used to solve such problems. However, the connections among these abstraction works remain vague. Thus, to facilitate a deep understanding and further exploration of abstraction approaches for generalized planning, it is important to develop a uniform abstraction framework for generalized planning. Recently, Banihashemi et al. proposed an agent abstraction framework based on the situation calculus. However, expressiveness of such an abstraction framework is limited. In this paper, by extending their abstraction framework, we propose a uniform abstraction framework for generalized planning. We formalize a generalized planning problem as a triple of a basic action theory, a trajectory constraint, and a goal. Then we define the concepts of sound abstractions of a generalized planning problem. We show that solutions to a generalized planning problem are nicely related to those of its sound abstractions. We also define and analyze the dual notion of complete abstractions. Finally, we review some important abstraction works for generalized planning and show that they can be formalized in our framework.
Keywords:
Knowledge Representation and Reasoning: Action, Change and Causality