## An Ant System for Plan Merging

##### Rene Michel, Institut für Angewandte Informatik und Formale Beschreibungsverfahren, University of Karlsruhe, Germany

M. Middendorf, Institut für Angewandte Informatik und Formale Beschreibungsverfahren, University of Karlsruhe, Germany

Email: middendorf@aifb.uni-karlsruhe.de

We describe an Ant System AS-PM for solving the Plan Merging problem (PM).
This problem is to find a cheap execution sequence for the
operations of a plan (i.e. a directed acyclic graph where each vertex
represents an operation and the arcs define a precedence relation between
the vertices) by exploiting the property that it is cheap to execute
operations of the same type together. PM has applications in production
planning and mechanical engineering.

In AS-PM the ants are guided by the values of parameters (trail information)
that are assigned to the operations of the plan when applying a fast
constructive heuristic to build up an execution sequence. We compare
AS-PM with a genetic algorithm and heuristics for PM on several test
instances.

Our tests show that it is advantageous when the ants use a lookahead
function when they make their decisions. Thus the decisions about
which operations to be scheduled next depend on the quality of the
resulting state which is measured as the amount of trail information
on the operations that can possibly be scheduled afterwards. For an
important subproblem of PM where the connected components of the plan
are paths with similar sequences of operations the tests show good
results when working with two different poulations of ants that exchange
trace information - ants of the ``forward population'' move along the
direction of the arcs through the plan whereas the ``backward ants''
take the opposite direction.