Picture of Open Access badges

Discover Open Access research at Strathprints

It's International Open Access Week, 24-30 October 2016. This year's theme is "Open in Action" and is all about taking meaningful steps towards opening up research and scholarship. The Strathprints institutional repository is a digital archive of University of Strathclyde research outputs. Explore recent world leading Open Access research content by University of Strathclyde researchers and see how Strathclyde researchers are committing to putting "Open in Action".


Image: h_pampel, CC-BY

The detection and exploitation of symmetry in planning problems

Fox, M. and Long, D. (1999) The detection and exploitation of symmetry in planning problems. In: Proceedings of IJCAI'99, 1999-07-31 - 1999-08-06.

Full text not available in this repository. (Request a copy from the Strathclyde author)


Many planning problems exhibit a high degree of symmetry that cannot yet be exploited successfully by modern planning technology. For example, problems in the Gripper domain, in which a robot 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 length of the shortest transportation 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 techniques in STAN, a Graphplanbased planner that uses state analysis techniques in a number of ways to exploit the underlying structures of domains. We have achieved a dramatic improvement in performance in solving problems exhibiting symmetry. We present a range of results and indicate the further developments we are now pursuing.