Symmetry, Near Symmetry and its Exploitation in Planning and Search

Introduction

Symmetry plays an important role in search. In particular, where a search space is generated by a significant number of symmetric choices, the symmetries create redundancy in the search space. This can lead to several effects:

• symmetries can multiply the number of uninterestingly different solutions
• symmetries can multiply entire parts of the search space in which no solutions exist
• symmetries can affect the relative density of solutions in the search space, which can impact on local search techniques

Symmetry in Planning

In our earlier work on symmetry, we explored these phenomena in the context of planning search spaces. In planning some special issues arise that distinguish the behaviour of symmetry in these problems from that in other search problems: planning problems are naturally dynamic (that is, the choices lead to state changes over time) and this dynamism can mean that objects make transitions between symmetric and non-symmetric states at various stages of execution of the plan. As a consequence, sometimes the choices that must be made between alternative objects are symmetric choices and sometimes they are not. Tracking this changing status is an important problem in handling symmetry in planning and doing so efficiently is a particularly hard challenge.

Symmetry impacts on planning in multiple ways (SymCon'03):

• Object symmetries: a collection of objects in a planning problem can be interchangeable. This symmetry arises because of naming of otherwise identical objects (IJCAI'99 and ICAPS'02).
• Configuration symmetries: multiple collections of objects form symmetric configurations. That is, the relationships that hold between one collection of objects are isomorphic to the relationships that hold between another collection of objects. These collections of objects are then interchangeable in solutions. Object symmetries are a special case of configuration symmetries, but also easier to handle than the general case.
• Plan permutation symmetries (PlanSIG'03): often the ordering of some sequence of actions can be permuted without changing the final state that the sequence generates. This can lead to sigificant inefficiency in planners that consider alternative orderings of actions as part of their search. For example, a forward state space planner such as FF will, when crossing plateaux in the search space, consider alternative orderings of actions that ultimately converge on the same final state.

We have examined the exploitation of near symmetry in planning problems and identified a positive role it can play in helping to guide a planner to choose actions that are nearly symmetric to those that it has already used that appear to be promoting the solution (PlanSIG'04 and IJCAI'05).

Beyond Planning

Our investigations of the importance of near symmetry in planning led us to begin to explore near symmetry in a more abstract form. This has become a key focus of more recent research on symmetry. In particular, we have begun to explore the concept of near symmetries in graphs (SymNet'05 and AAAI'07). The idea behind this work is that a graph can be used as a very general representation of relational structures, including planning problems, CSPs, SAT problems and other search-related structures, molecules, engineering designs, dependency structures and so on. Near symmetries can often represent important and relevant structures, yet the standard techniques for identifying symmetry in graphs are unable to identify them at all.

Software

We have produced various software tools as part of the project. These will eventually be added here.

Spectral Graph Layout

One software tool that was developed by Stephen Seggie as part of his undergraduate degree is a spectral graph layout tool. This is a very useful way to visualise the relationship between symmetries and graph spectra and their eigenvectors. It accepts data in a limited "dot" format. The graphs must appear as:

graph NAME {
e1 -- e2
e3 -- e4 
...
}

The software is available as a jar file here. The following pictures give some idea of the visual appeal of these layouts.

Mysterious Symmetry

A layout using eigenvectors for widely spaced eigenvalues

Close up

Highlighting a symmetry