Reasoning about Large Taxonomies of Actions

Yilan Gu, Mikhail Soutchanski

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 representation inherits all useful properties of his BATs. Moreover, we show that our axioms can be more succinct, but extended Reiter's regression can still be used to solve the projection 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 computational advantages. For taxonomies of actions that can be represented as finitely branching trees, the regression operator can work exponentially faster with our theories than it works with Reiter's BATs. Finally, we propose general guidelines on how a taxonomy of actions can be constructed from the given set of effect axioms in a domain.

Subjects: 11. Knowledge Representation; 5. Common Sense Reasoning

Submitted: Apr 14, 2008


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.