Mutex Graphs and Multicliques: Reducing Grounding Size for Planning

Mutual exclusion (mutex) can be traced back to concurrency control, which refers to the condition that prevents simultaneous accesses to a shared resource. In knowledge representation, they specify the constraints that some properties cannot hold at the same time. For example, an object cannot be at different locations at the same time. These constraints frequently occur in applications from model-checking problems in computer-aided verification [2], computer vision [12, 17], graph algorithms [11], and AI planning [14]. The goal of this paper is to develop a graph-theoretic technique for compactly encoding large sets of mutex constraints and apply it to planning in ASP . We do his by focusing on domain-independent AI planning as started out by SA TPlan [10]. That is, we will first obtain an ASP planner by a straightforward translation from SA TPlan and then study how to encode mutex constraints compactly for the planner. In SA T/ASP planning, mutex constraints are specified by formulas/rules that, for any state (which involves a time step, also called a layer in this paper), the actions with conflicting preconditions or effects, and the fluents that are inferred to be conflicting, are mutually exclusive. A naive encoding of these constraints can certainly generate enough rules to overwhelm the underlying solver for large planning instances.