Optimisation and Relaxation for Multiagent Planning in the Situation Calculus

Abstract

The situation calculus can express rich agent behaviours and goals and facilitates the reduction of complex planning problems to theorem proving. However, in many planning problems, solution quality is critically important, and the achievable quality is not necessarily known in advance. Existing Golog implementations merely search for a Legal plan, typically relying on depth-first search to find an execution. We illustrate where existing strategies will not terminate when quality is considered, and to overcome this limitation we formally introduce the notion of cost to simplify the search for a solution. The main contribution is a new class of relaxations of the planning problem, termed prec..