A Reasoning Module for Long-Lived Cognitive Agents (Ph.D.-2009)

A Reasoning Module for Long-Lived Cognitive Agents, Stavros Vassos, Ph.D. Thesis, Department of Computer Science, University of Toronto, 2009.
[pdf | citeulike]

This thesis was completed under the supervision of Hector J. Levesque. The other two members of my internal committee were Sheila McIlraith and Yves Lesperance. My external examiner was Michael Thielscher.

In this thesis we study a reasoning module for agents that have cognitive abilities, such as memory, perception, action, and are expected to function autonomously for long periods of time. The module provides the ability to reason about action and change using the language of the situation calculus and variants of the basic action theories. The main focus of this thesis is on the logical problem of progressing an action theory.

First, we investigate the conjecture by Lin and Reiter that a practical first-order
definition of progression is not appropriate for the general case. We show that Lin and Reiter were indeed correct in their intuitions by providing a proof for the conjecture, thus resolving the open question about the first-order definability of progression and justifying the need for a second-order definition.

Then we proceed to identify three cases where it is possible to obtain a first-order progression with the desired properties: i) we extend earlier work by Lin and Reiter and present a case where we restrict our attention to a practical class of queries that may only quantify over situations in a limited way; ii) we revisit the local-effect assumption of Liu and Levesque that requires that the effects of an action are fixed by the arguments of the action and show that in this case a first-order progression is suitable; iii) we investigate a way that the local-effect assumption can be relaxed and show that when the initial knowledge base is a database of possible closures and the effects of the actions are range-restricted then a first-order progression is also suitable under a just-in-time assumption.

Finally, we examine a special case of the action theories with range-restricted effects and present an algorithm for computing a finite progression. We prove the correctness and the complexity of the algorithm, and show its application in a simple example that is inspired by video games.


address = {Toronto, Canada},
author = {Vassos, Stavros},
school = {University of Toronto},
title = {A Reasoning Module for Long-Lived Cognitive Agents},
year = {2009}


  • Page 38,  point 5, last equation:  ”s less-than do(a,s’)” should be  ”s less-or-equal-than do(a,s’)”.
  • Page 175, second paragraph, last sentence:  ”Unfortunately we can no longer then assume that D_una” should be “Unfortunately we can no longer then assume that D_alpha”.