Description

Automated Planning is a research field in which the aim is to find a plan, this being a sequence of steps that wil bring a system from a predefined initial state into a desired final state. Most puzzles fall into this category: for instance, an initial state could be a mixed-up Rubik's cube, the desired final state is the solved cube, and the plan is the sequence of turns needed to achieve the solution.

Graph Transformation involves the stepwise modification of graphs according to predefined transformation rules. One of the possible applications of where the graphs represent states of some system, and the rules correspond to computational steps of the system, which modify those states. If one graph is the initial state and another the desired final state, then our graph transformation system is actually a planning problem.

In previous (Bachelor) assignments, concrete instances of planning problems were successfully implemented in GROOVE, and a general translator was built from PDDL, the input language for many planning tools, to GROOVE rules. The latter now enables the direct experimental comparison of GROOVE to existing planners.

This assignment is to set up and systematically carry out experiments showing the performance of GROOVE with respect to existing, state-of-the-art planners. It is expected that these experiments will show GROOVE to be substantially slower, but it is not clear by how much, and the experiments will show where performance gains can be made, thus leading to potential future tool improvements.

Additional Resources

1. The paper