Proceedings

The Detection and Exploitation of Symmetry in Planning Problems

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Planning and Scheduling. Pages 956-960.

© 1999 International Joint Conferences on Artificial Intelligence

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.

  1. [Blum and Furst, 1997] A. Blum and M. Furst. Fast planning through planning graph analysis. AIJ, 90(1- 2):279-298, 1997. IJCAI
  2. [Fikes and Nilsson, 1971] R.E. Fikes and N.J. Nilsson . STRIPS: A New Approach to the Application of Theorem-Proving to Problem-Solving. Artificial In- telligence, 2(3), 1971. IJCAI
  3. [Fox and Long, 1998] M. Fox and D. Long. The auto- matic inference of state invariants in TIM . JAIR, 9, 1998.
  4. [Long and Fox, 1999] D. Long and M. Fox. The efficient implementation of the plan-graph in STAN. To appear in JAIR, 10, 1999.
  5. [Nebel et al., 1997] B. Nebel, Y. Dimopoulos, and J. Koehler. Ignoring irrelevant facts and operators in plan generation. In ECP-97, pages 338-350, 1997.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards