University of Twente Student Theses
On a framework for domain independent heuristics in graph transformation planning
Elsinga, J.W. (2016) On a framework for domain independent heuristics in graph transformation planning.
|
PDF
2MB |
| Abstract: | Planning is the task of finding a sequence of actions which, for an initial state, reach a predefined goal. A technique to model planning problems is graph transition systems. Graph transition system are an extension of a transition system in which states are associated with a unique graph and transitions are expressed by graph transformations and graph morphisms. A technique to solve planning problems is forward state space exploration. However, for large problem instances a state space may become unbearably large and uninformed state space exploration is no longer feasible. It becomes necessary to have some functionality which guides the exploration. For with we use a heuristic, which is a function which estimates the distance of a state to the goal. In this work we developed and present two distinct domain independent heuristic approaches which are based on the underlying graph transformation planning problem modeling paradigm. The first of these is the \textsc{NENTuple} approach which is based on the comparison of graph abstractions. The second approach is linearization abstraction which is based on calculating distance metrics from linearized abstracted state spaces. We have furthermore designed and implemented a framework in GROOVE for heuristics functions. In this framework we have implemented he rustics functions based on the above mentioned approaches. To evaluate the effectiveness of the heuristic approaches developed in the thesis we had run experiments using three planning problems. From the results we found that our heuristics provide a significant improvement over uninformed exploration and furthermore perform equal or better than heuristics presented in related work. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 54 computer science |
| Programme: | Computer Science MSc (60300) |
| Link to this item: | https://purl.utwente.nl/essays/70937 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page