Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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, Stockholm, Sweden.

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

Abstract

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.

Item type: Conference or Workshop Item (Paper)
ID code: 1944
Keywords: planning technology, symmetry, STAN, graphplan, state analysis techniques, Electronic computers. Computer science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Related URLs:
Depositing user: Professor Maria Fox
Date Deposited: 02 Nov 2006
Last modified: 04 Oct 2012 16:59
URI: http://strathprints.strath.ac.uk/id/eprint/1944

Actions (login required)

View Item