Hierarchical landmarks - a means to reduce search effort in hybrid planning
FacultiesFakultät für Ingenieurwissenschaften und Informatik
LicenseStandard (Fassung vom 01.10.2008)
Artificial Intelligence planning is a key problem solving technology currently being used in a variety of applications including military campaigns, robot navigation, airplane scheduling, and human computer interaction. The generation of plans - courses of actions to achieve desired goals or perform specific tasks - is a costly process, however. Developing methods to systematically reduce the search effort and increase the performance of planning systems is thus a central concern. We have developed a novel pre-processing technique to extract knowledge from a hierarchically structured planning domain and a current problem description which is used to significantly improve planning performance. This specific landmark-technique firstly enables to prune parts of the search space by identifying tasks that are not achievable from a certain initial situation. Secondly, it is used to guide hierarchical planning processes more efficiently towards a solution of a given planning problem. Finally, the technique serves to decompose the original planning problem into a set of sub-problems each of which can then be solved separately using a multi-agent based planning approach. In this talk, we will present the hierarchical landmark technique and its exploitation. Furthermore, we will show the results of the empirical evaluation of our approach, which provides evidence of the significant performance increase gained this way.
Subject HeadingsKünstliche Intelligenz [GND]
Artificial intelligence. Planning [LCSH]