From State Spaces to Semigroups: Leveraging Algebraic Formalism for Automated Planning


This paper introduces an algebraic formalism linking transformation semigroups and the state transition systems induced by classical planning problems. We investigate some basic planning problems with interesting properties and establish fundamental characteristics of the corresponding semigroups, such as their ideals and Green’s relations. Furthermore, we leverage semigroup theory to propose new approaches to existing concepts in automated planning, including the identification of landmark actions and the study of dead ends. We demonstrate that algebraic results can be applied to facilitate an understanding of a planning problem’s state space and explore its solutions, thus verifying the relevance and effectiveness of such formal modeling.

Workshop on Heuristics and Search for Domain-independent Planning