Optimizing projection in the situation calculus

Abstract

Among the most frequent reasoning tasks in the situation calculus are projection queries that query the truth of conditions in a future state of affairs. However, in long running action sequences involving thousands or millions of independent actions, solving the projection problem is complex. Existing approaches require either syntactically rewriting queries through each action that has occurred via a mechanism called regression or producing and maintaining an updated representation of the knowledge base via progression. This latter approach is often infeasible, as updating a knowledge base without loss of relevant information is not possible for many domains.

This thesis introduces a new technique which allows the length of the action sequences to be reduced by reordering independent actions and removing dominated actions; maintaining semantic equivalence with respect to the original action theory. This transformation allows for the removal of actions that are problematic with respect to progression, allowing for periodic update of the action theory to reflect the current state of affairs. We provide the logical framework for the general case and give specific methods for important classes of action theories. We also show how more expressive cases may be handled, such as the reordering of sensing actions in order to delay progression. We investigate mechanisms for deciding which actions should be removed or reordered to improve the efficiency via a guided search and introduce appropriate heuristics.

The end result is a method that allows long-running situation calculus based agents to reason more efficiently about their current and future situations.