Picture of a black hole

Strathclyde Open Access research that creates ripples...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of research papers by University of Strathclyde researchers, including by Strathclyde physicists involved in observing gravitational waves and black hole mergers as part of the Laser Interferometer Gravitational-Wave Observatory (LIGO) - but also other internationally significant research from the Department of Physics. Discover why Strathclyde's physics research is making ripples...

Strathprints also exposes world leading research from the Faculties of Science, Engineering, Humanities & Social Sciences, and from the Strathclyde Business School.

Discover more...

Abstraction-based action ordering in planning

Fox, M. and Long, D. and Porteous, J. (2005) Abstraction-based action ordering in planning. In: Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI-05). IJCAI.

[img]
Preview
PDF (strathprints002711.pdf)
strathprints002711.pdf

Download (133kB) | Preview

Abstract

Many planning problems contain collections of symmetric objects, actions and structures which render them difficult to solve efficiently. It has been shown that the detection and exploitation of symmetric structure in planning problems can dramatically reduce the size of the search space and the time taken to find a solution. We present the idea of using an abstraction of the problem domain to reveal symmetric structure and guide the navigation of the search space. We show that this is effective even in domains in which there is little accessible symmetric structure available for pruning. Proactive exploitation represents a flexible and powerfulalternative to the symmetry-breaking strategies exploited in earlier work in planning and CSPs. The notion of almost symmetry is defined and results are presented showing that proactive exploitation of almost symmetry can improve the performance of a heuristic forward search planner.