Reversing Action Effects: Theory and Practice

Some actions just cannot be reversed, a lesson we often learn early on in life. In an old TV commercial for an insurance company, one saw a flowerpot shattering on the ground - the reel was then played backwards to suggest that everything can be fixed. In reality, not all actions can of course be reversed, and even more so when only our own actions can be used for reversal. Clearly, the non-reversible actions are critical, and we tend to them only if necessary. In this project the question of reversibility of actions is studied in the context of artificial agents. It is assumed that they have a (limited) set of actions, the behaviour of which is represented in a specific language. Representations like this are often used in Artificial Intelligence, usually to find plans that allow the agent to reach a specific goal. We instead intend to devise methods that detect which actions are reversible. While some progress has been made on this topic in the past, in this project we follow several novel strands: action representations that allow multiple (nondeterministic) possible outcomes, reversibility under specific circumstances, use cases for reversibility, with a particular focus on cybersecurity. The project will combine theoretical analysis with practical evaluation. Properties will be formally stated and proved, using methods from theoretical computer science. Algorithms will be implemented and experimentally evaluated. The use cases will also be evaluated formally (proving correctness and completeness) and experimentally (in terms of resource consumption). On the Austrian side the project will be led by Wolfgang Faber and Michael Morak of the University of Klagenfurt, on the Czech side the project will be guided by Lukš Chrpa and Jakub Med of the Czech Technical University in Prague.