Description

The assignment is to implement state-of-the art planning algorithms (based on heuristic search, also called best-first to distinguish it from depth-first and breadth-first) in the graph transformation tool GROOVE, improve the algorithms based on the specific properties of graphs, and compare the resulting performance with existing planning tools.

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 is 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.

Tasks

• Gain an understanding of (i) automated planning and (ii) graph transformation
• Investigate the state of the art in planning algorithms (best-first/heuristic search)
• Develop specific distance measures and abstractions based on graphs
• Implement the (existing and) improved algorithms in GROOVE
• Experiment and compare the GROOVE-based implementation with existing planning tools

References

1. GROOVE (Digital version available here)

Additional Resources

1. The paper