Relaxing regression for a heuristic GOLOG

Abstract

GOLOG is an agent programming language designed to represent complex actions and procedures in the situation calculus. In this paper we apply relaxation-based heuristics - often used in classical planning - to find (near) optimal executions of a GOLOG program. In doing so we present and utilise a theory of relaxed regression for the approximate interpretation of a GOLOG program. This relaxed interpreter is used to heuristically evaluate the available choices in the search for a program execution. We compare the performance of our heuristic interpreter (in terms of the quality of executions found) with a traditional depth-first search interpreter and one guided by a greedy heuristic without a..