General Reversibility of Deterministic ...

Automated planning, understood as “reasoning about acting'' is one of the oldest problems studied in Artificial Intelligence and has been successfully applied in many practical domains. Environments are described from the point of view of an agent, and its dynamics are captured by actions (under the control of the agent) and events (not under its control). Besides plan generation, formal symbolic specification of planning tasks is important for investigating their structure. Action reversibility, which is the concern of this project, refers to the possibility to revert effects of an action by (other) actions. In other words, after execution of a reversible action, there exists a sequence of actions that reverts the state of the environment to exactly the state before the reversible action was executed. The problem of determining reversibility of actions has been identified and tackled in a few previous works, but the existing approaches rely on either very general or quite restrictive frameworks. In the proposed project we propose to explore more of the middle ground, in particular domains represented using lifted representation and Fully Observable Non-deterministic (FOND) domains. By leveraging Answer Set Programming techniques, we believe that we will be able to construct a framework that will provide a good tradeoff between being general and efficient. There are several indications that ASP is particularly well-suited for determining reversible actions and events in lifted and FOND domains, which we intend to substantiate in the project. The contributions of the project will therefore be both theoretical and practical in nature, in the form of novel definitions of reversibility, a formal study of their computational properties, new algorithms, their implementation, and an experimental evaluation.