Hierarchical landmarks - a means to reduce search effort in hybrid planning [Elektronische Ressource] / Mohamed Mohamed Nabil Mohamed Shams Eldeen Elkawkagy

Sujets

• Informatik

Informations

• Publié par: universitat_ulm
• Publié le: 01 janvier 2011
• Nombre de lectures: 38
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Hierarchical Landmarks
A Means to Reduce Search Effort in Hybrid Planning
Dissertation zur Erlangung des Doktorgrades
Doktor der Naturwissenschaften (Dr. rer. nat.)
der Fakultat¨ fur¨ Ingenieurwissenschaften und Informatik
der Universitat¨ Ulm
vorgelegt von
Mohamed Mohamed Nabil Mohamed Shams Eldeen Elkawkagy
¨aus Menoufyia, Agypten
Institut fur¨ Kunstliche¨ Intelligenz
¨ ¨Fakultat fur Ingenieurwissenschaften und Informatik
Universitat¨ Ulm
Institutsleitung
Prof. Dr. Susanne Biundo-Stephan
Ulm, Deutschland
July 2011Amtierender Dekan der Fakultat¨ fur¨ Ingenieurwissenschaften und Informatik:
Prof. Dr.-Ing. Klaus Dietmayer
Vorsitzender des Promotionsausschusses:
Prof. Dr. Uwe Schoning¨
Mitglieder des
Prof. Dr. Heiko Neumann
Prof. Dr. Helmuth A. Partsch
Die Gutachter der Dissertation:
Prof. Dr. Susanne Biundo-Stephan
Prof. Dr. Gunther¨ Palm
Tag der Promotion: 13 July 2011Hierarchical Landmarks
A Means to Reduce Search Effort in Hybrid Planning
A PhD thesis submitted to the Faculty of
Engineering and Computer Science, Ulm University
in fulfillment of the requirements for the degree of
Doktor rerum naturarum (Dr. rer. nat.)
by
Mohamed Mohamed Nabil Mohamed Shams Eldeen Elkawkagy
from Menoufyia, Egypt
Institute of Artificial Intelligence
Faculty of Engineering and Computer Science
Ulm University
Advisor
Prof. Dr. Susanne Biundo-Stephan
Ulm, Germany
July 2011Dean of the Faculty of Engineering and Computer Science:
Prof. Dr.-Ing. Klaus Dietmayer
Chairman of the doctoral committee:
Prof. Dr. Uwe Schoning¨
Members of the doctoral committee:
Prof. Dr. Heiko Neumann
Prof. Dr. Helmuth A. Partsch
Reviewers of the dissertation:
Prof. Dr. Susanne Biundo-Stephan
Prof. Dr. Gunther¨ Palm
Day of Conferral of Doctorate: 13 July 2011ABSTRACT
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 re-
duce the search effort and increase (the) performance of planning systems is thus a central concern.
In recent years, a number of approaches have been proposed to run a preliminary analysis of the ar-
tificial intelligence planning domain. They aim to extract and exploit knowledge from the domain
model and problem description in order to reduce the planning effort. In general, pre-processing
approaches can be done either ”off-line” - analyzing the domain model before having access to a
problem- or ”on-line” - analyzing the domain model and planning problem description together.
We have developed a novel pre-processing technique to extract knowledge from a hierarchically
structured planning domain and a current planning problem description which is used to signifi-
cantly improve planning performance. This pre-processing technique enables pruning all branches
which can be proven to never lead to a solution by identifying tasks that are not achievable from a
certain initial situation.
The efficiency of planning systems depends on the kind of planning search strategy which the
planner uses. We developed novel domain independent strategies relying on the knowledge that is
generated by pre-processing in order to guide the hierarchical planning processes more effectively
towards a solution of a given planning problem.
The complexity in real-world applications has led artificial intelligence planning researchers to de-
velop algorithms and systems that more closely match realistic planning environments, in which
planning activity is often distributed, and plan generation can happen concurrently with plan ex-
ecution. Finally, our pre-processing technique in the context of hierarchical planning approach is
integrated with a multi-agent based planning approach to decompose the original planning prob-
lem into a set of sub-problems each of which can then be solved separately. Our integration ap-
proach presents two different techniques to split the planning problem into a set of sub-problems:
Dependent which constructs a set of dependent sub-problems andIndependent which pro-
duces a set of independent sub-problems.
Our empirical evaluation shows that the pre-processing technique improves performance because
the dead ends can be detected much earlier than without pruning and that our search strategies
outperform many other possible strategies. In addition, the integration between the pre-processing
technique and a multi-agent based planning approach dramatically reduce computation effort. In
general, our empirical evaluation proves that our approach improves the efficiency of planning
systems on the tested domains.ACKNOWLEDGMENTS
Foremost, I would like to express my deep and sincere gratitude to my advisor Prof. Dr. Su-
sanne Biundo-Stephan, the director of the Institute of Artificial Intelligence, University of Ulm,
accepting me as a doctoral student at her institute, for the continuous support of my Ph.D study
and research, for her patience, motivation, enthusiasm, and immense knowledge. Her guidance
helped me in all the time of research and writing of this thesis. I could not have imagined having a
better advisor and mentor for my Ph.D study. I have enjoyed working with her.
Besides my supervisor, I would like to thank the rest of my defense committee for their guidance.
My sincere thanks also go to Dr. Bernd Schattenberg for his valuable advice and friendly help. His
extensive discussions around my work and he always had an answer when had a question.
During this work I have collaborated with my colleagues Dr. Julien Bidot and Pascal Bercher for
whom I have great regard, and I wish to extend my warmest thanks to all those who have helped
me with my work in the Institute of Artificial Intelligence.
Last but not least, I owe my loving thanks to my wife Heba Elbeh, my son Yousuf and my daughter
Salma. They have lost a lot due to my research abroad. Without their encouragement and under-
standing it would have been impossible for me to finish this work. My special gratitude is due
to my parents, brothers, my sister and their families for their loving support. They let me own a
happy family in Egypt.
Ulm, Germany, 2011
Mohamed ElkawkagyDEDICATION
To my parents and my wife for their support and encouragement