Exploring the boundaries of decidable verification of non-terminating Golog programs

Abstract

The action programming language GOLOG has been found useful for the control of autonomous agents such as mobile robots. In scenarios like these, tasks are often open-ended so that the respective control programs are non-terminating. Before deploying such programs on a robot, it is often desirable to verify that they meet cer-tain requirements. For this purpose, Claßen and Lake-meyer recently introduced algorithms for the verifica-tion of temporal properties of GOLOG programs. How-ever, given the expressiveness of GOLOG, their verifi-cation procedures are not guaranteed to terminate. In this paper, we show how decidability can be obtained by suitably restricting the underlying base logic, the ef-fect axioms for primitive actions, and the use of actions within GOLOG programs. Moreover, we show that drop-ping any of these restrictions immediately leads to un-decidability of the verification problem.