Reasoning About Large Taxonomies of Actions

Abstract

We design a representation based on the situation calculus to facilitate development, maintenance and elaboration of very large taxonomies of actions. This representation leads to more compact and modular basic action theories (BATs) for reasoning about actions than currently possible. We compare our representation with Reiter’s BATs and prove that our rep-resentation inherits all useful properties of his BATs. More-over, we show that our axioms can be more succinct, but ex-tended Reiter’s regression can still be used to solve the projec-tion problem (this is the problem of whether a given logical expression will hold after executing a sequence of actions). We also show that our representation has significant compu-tational advantages. For taxonomies of actions that can be represented as finitely branching trees, the regression oper-ator can work exponentially faster with our theories than it works with Reiter’s BATs. Finally, we propose general guide-lines on how a taxonomy of actions can be constructed from the given set of effect axioms in a domain.