Optimisation and relaxation for multiagent planning in the situation calculus

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 precondition relaxations, based on Lagrangian relaxation. We show how this facilitates optimisation of a restricted class of Golog programs for which plan existence (under a cost budget) is decidable. It allows for tractably computing relaxations to the planning problem and leads to a general, blackbox, approach to optimally solving multi-agent planning problems without explicit reference to the semantics of interleaved concurrency.