The Detection and Exploitation of Symmetry in Planning Problems

Abstract

Many planning problems exhibit a high degree of symmetr y that cannot yet be exploited successfully by mod ern planning technology. For example , problems in the Gripper domain , in which a r obot with two grippers must transfer balls from one room to another, are trivial to the human problem-solver because the high degree of symmetry in the domain means that the order in which pairs of balls are transported is irrelevant to the leng th of the shortest transportat ion plan . However, planners typically search all possible orderings giving rise to an exponential explosion of the search space. This paper describes a way of detecting and exploiting symmetry in the solution of problems that demonstrate these characteristics. We have implemented our techniqu es in STAN, a Graphp lan-based planner that uses state analysis techniqu es in a number of ways to exploit the underlying structures of domains. We have achieved a dramatic improve ment in performance in solving problems exhibiting symmetry. We pr ese nt a range of r es ults and indicate the further developments we are now pursuing.