Identifying Undoable Actions and Events...

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). One issue that has received less attention than it deserves is that of plan safety, and in particular the question of which actions or events are irreversible or lead to dead ends. In this project, we will focus on the characterization and identification of actions and events that are not undoable, and thus unsafe in a specific sense. While there has been some earlier work on this topic, the existing approaches rely on either very general or quite restrictive frameworks. In the proposed project we propose to cover the middle ground and propose to do so using a specific instrument, Answer Set Programming (ASP, a logic programming framework that is theoretically well-studied and also has efficient practical system support). There are several indications that ASP is particularly well-suited for determining undoable actions and events, 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 undoability, a formal study of their computational properties, new algorithms, their implementation, and an experimental evaluation.