The detection and exploitation of symmetry in planning problems

M. Fox, D. Long

Research output: Contribution to conferencePaperpeer-review

84 Citations (Scopus)

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.
Original languageEnglish
Pages956-961
Number of pages5
Publication statusPublished - Jul 1999
EventProceedings of IJCAI'99 - Stockholm, Sweden
Duration: 31 Jul 19996 Aug 1999

Conference

ConferenceProceedings of IJCAI'99
CityStockholm, Sweden
Period31/07/996/08/99

Keywords

  • planning technology
  • symmetry
  • STAN
  • graphplan
  • state analysis techniques

Fingerprint

Dive into the research topics of 'The detection and exploitation of symmetry in planning problems'. Together they form a unique fingerprint.

Cite this