In this project the optimization of transport planning has been studied. The approach was that smaller transport companies do not have the capability to fully optimize their transports. Their transport optimization is performed at a company level, meaning that the end result might be optimal for their company, but that potential for further optimization exists. The idea was to build a collaboration of transport companies, and then to optimize the transports globally within the collaboration. The intent was for the collaboration to perform the same driving assignments but at a lower cost, by using fewer vehicles and drivers, or travel shorter distance, or both combined. This should be achieved by planning the assignments in a smarter way, for example using a company's empty return journey to perform an assignment for another company. Due to the complexity of these types of problems, called Vehicle Routing Problem (VRP), shown to be NP-complete, search methods are often used. In this project the method of choice was a PDDL-based planner called LPG-td. It uses enforced hill-climbing together with a best-first search to find feasible solutions. The method was tested for scaling, performance versus another method and against time, as well as together with a real-life based problem. The results showed that LPG-td might not be a suitable candidate to solve the problem considered in this project. The solutions found for the collaboration were worse than for the sum of individual solutions, and used more computational time. Since the solution for the collaboration at most should be equal to the sum of individual solutions, in theory, this meant that the planner failed.

Seit langem ist die Intelligenz des Menschen für viele Forscher und Philosophen ein faszinierendes Forschungsobjekt. Mit dem Aufkommen der Computertechnik erscheint nun zum ersten mal der Traum, einige dieser typisch menschlichen Fähigkeiten nicht nur zu verstehen, sondern nachbauen oder in Teilgebieten gar übertreffen zu können, als realistisch. Ein wichtiger Teil dieses mit "Künstliche Intelligenz" überschriebenen Forschungsgebietes ist das Schließen über Aktionen und Veränderung. Hier wird versucht, die menschliche Fähigkeit, die Effekte seiner Aktionen vorauszusehen und Pläne zum Erreichen von Zielen zu schmieden, nachzubilden. Ein aktives Forschungsgebiet in diesem Rahmen ist der Fluentkalkül, ein Formalismus zur Modellierung von Aktionen und Veränderung. Er stellt Mittel bereit, in der ein automatischer Agent seine Umgebung und die Effekte seiner Aktionen im Rahmen der mathematischen Logik darstellen kann, um mit Hilfe von logischem Schließen sein Verhalten zu planen. Obwohl zum Fluentkalkül viele Arbeiten existieren, die dessen Anwendungsbereiche und Semantik erweitern, gibt es doch noch relativ wenige Arbeiten zum effizienten Schlussfolgern. Dies ist ein Hauptaugenmerk der vorliegenden Arbeit. Es wird ein Algorithmus geschaffen, der Erkenntnisse aus effizienten Verfahren zum Modelchecking mit Binären Entscheidungsdiagrammen (BDDs) sinngemäß überträgt und für ein Fragment des Fluentkalkül erweitert. Damit können nun auch Planungsprobleme von Fluentkalkül-Planern gelöst werden, die der realisierten symbolischen Breitensuche besser zugänglich sind, als der bisher aussschliesslich verwendeten heuristischen Tiefensuche. Um eine leichtere Vergleichbarkeit Fluentkalkül-basierter Planungsverfahren mit anderen Planungsalgorithmen zu ermöglichen, wurde eine Übersetzung des ADL-Fragments der Planungsdomänenbeschreibungssprache PDDL in den Fluentkalkül geschaffen. Damit können zahlreiche Planungsprobleme aus der Literatur und Planungsdomänenbibliotheken auch mit Fluentkalkül-Planern bearbeitet werden. Die Übersetzung kann zugleich als formale Semantik des nur informal spezifizierten PDDL dienen.

Die vorliegende Arbeit beschäftigt sich mit zwei Problembereichen. Zum einen wird untersucht, auf welche Weise Präferenzen über Zielen geeignet ausgedrückt werden können. Weiterhin wird ein Ansatz zur Lösung partieller Erfüllbarkeitsprobleme vorgestellt. Die Arbeit beginnt mit einer Einführung grundlegender Begriffe aus dem Bereich des automatischen Planens. Dies beinhaltet eine Definition bzw. Erläuterung partieller Erfüllbarkeitsprobleme und der gängigen Repräsentationssprachen für Planungsprobleme. Weiterhin werden aktuelle, der Literatur entnommene, Lösungsansätze für partielle Erfüllbarkeitsprobleme vorgestellt und wesentliche Unterscheidungsmerkmale zu dem Ansatz dieser Arbeit herausgearbeitet. Die Effektivität des vorgestellten Ansatzes zur Lösung partieller Erfüllbarkeitsprobleme beruht wesentlich auf der Linearisierung der Präferenzrelation. Die dafür notwendigen Betrachtungen erfolgen im weiteren Verlauf der Arbeit. Es wird schließlich eine lineare, numerische Beschreibungssprache als Erweiterung der Repräsentationssprache PDDL 2.1 vorgeschlagen. Weiterhin wird explizit aufgezeigt, wie sich der vorgestellte Lösungsalgorithmus mithilfe herkömmlicher Planungssysteme umsetzen läßt. Die Implementation des Algorithmus als C-Programm bzw. Perl-Skript liegt der gedruckten Ausgabe bei.

O grande avanço das técnicas de Planejamento em Inteligência Artificial fez com que a Engenharia de Requisitos e a Engenharia do Conhecimento ganhassem extrema importância entre as disciplinas relacionadas a projeto de engenharia (Engineering Design). A especificação, modelagem e análise dos domínios de planejamento automático se tornam etapas fundamentais para melhor entender e classificar os domínios de planejamento, servindo também de guia na busca de soluções. Neste trabalho, é apresentada uma proposta de um ambiente integrado de modelagem e análise de domínios de planejamento, que leva em consideração o ciclo de vida de projeto, representado por uma ferramenta gráfica de modelagem que utiliza diferentes representações: a UML para modelar e analisar as características estáticas dos domínios; XML para armazenar, integrar, e exportar informação para outras linguagens (ex.: PDDL); as Redes de Petri para fazer a análise dinâmica; e a PDDL para testes com planejadores. / The great development in Artificial Intelligence Planning has emphasized the role of Requirements Engineering and Knowledge Engineering among the disciplines that contributes to Engineering Design. The modeling and specification of automated planning domains turn out to be fundamental tasks in order to understand and classify planning domains and guide the application of problem solving techniques. In this work, it is presented the proposed integrated environment for modeling and analyzing automated planning domains, which considered the life cycle of a project, represented by a tool that uses several language representations: UML to model and perform static analyses of planning environments; XML to hold, integrate, share and export information to other language representations (e.g. PDDL); Petri Nets, where dynamic analyses are made; and PDDL for testing models with planners.

O grande avanço das técnicas de Planejamento em Inteligência Artificial fez com que a Engenharia de Requisitos e a Engenharia do Conhecimento ganhassem extrema importância entre as disciplinas relacionadas a projeto de engenharia (Engineering Design). A especificação, modelagem e análise dos domínios de planejamento automático se tornam etapas fundamentais para melhor entender e classificar os domínios de planejamento, servindo também de guia na busca de soluções. Neste trabalho, é apresentada uma proposta de um ambiente integrado de modelagem e análise de domínios de planejamento, que leva em consideração o ciclo de vida de projeto, representado por uma ferramenta gráfica de modelagem que utiliza diferentes representações: a UML para modelar e analisar as características estáticas dos domínios; XML para armazenar, integrar, e exportar informação para outras linguagens (ex.: PDDL); as Redes de Petri para fazer a análise dinâmica; e a PDDL para testes com planejadores. / The great development in Artificial Intelligence Planning has emphasized the role of Requirements Engineering and Knowledge Engineering among the disciplines that contributes to Engineering Design. The modeling and specification of automated planning domains turn out to be fundamental tasks in order to understand and classify planning domains and guide the application of problem solving techniques. In this work, it is presented the proposed integrated environment for modeling and analyzing automated planning domains, which considered the life cycle of a project, represented by a tool that uses several language representations: UML to model and perform static analyses of planning environments; XML to hold, integrate, share and export information to other language representations (e.g. PDDL); Petri Nets, where dynamic analyses are made; and PDDL for testing models with planners.

This work describes graphplan, satplan and real-time adaptive A* planning algorithms. Through implementation of these algorithms, functionality and assumed attributes (real-time calculation, parallelism) are tested. These tests take place in nontrivial domains. Graphplan and satplan algorithms were tested in block-world, tire-world and bulldozer domains. Results of these tests were compared and displayed in graphs. Real-time adaptive A* algorithm was tested in tire-world domain. Results of these tests were compared with classic A* algorithm. Advantages and disadvantages of these algorithms are also described in this work.

Seit langem ist die Intelligenz des Menschen für viele Forscher und Philosophen ein faszinierendes Forschungsobjekt. Mit dem Aufkommen der Computertechnik erscheint nun zum ersten mal der Traum, einige dieser typisch menschlichen Fähigkeiten nicht nur zu verstehen, sondern nachbauen oder in Teilgebieten gar übertreffen zu können, als realistisch. Ein wichtiger Teil dieses mit "Künstliche Intelligenz" überschriebenen Forschungsgebietes ist das Schließen über Aktionen und Veränderung. Hier wird versucht, die menschliche Fähigkeit, die Effekte seiner Aktionen vorauszusehen und Pläne zum Erreichen von Zielen zu schmieden, nachzubilden. Ein aktives Forschungsgebiet in diesem Rahmen ist der Fluentkalkül, ein Formalismus zur Modellierung von Aktionen und Veränderung. Er stellt Mittel bereit, in der ein automatischer Agent seine Umgebung und die Effekte seiner Aktionen im Rahmen der mathematischen Logik darstellen kann, um mit Hilfe von logischem Schließen sein Verhalten zu planen. Obwohl zum Fluentkalkül viele Arbeiten existieren, die dessen Anwendungsbereiche und Semantik erweitern, gibt es doch noch relativ wenige Arbeiten zum effizienten Schlussfolgern. Dies ist ein Hauptaugenmerk der vorliegenden Arbeit. Es wird ein Algorithmus geschaffen, der Erkenntnisse aus effizienten Verfahren zum Modelchecking mit Binären Entscheidungsdiagrammen (BDDs) sinngemäß überträgt und für ein Fragment des Fluentkalkül erweitert. Damit können nun auch Planungsprobleme von Fluentkalkül-Planern gelöst werden, die der realisierten symbolischen Breitensuche besser zugänglich sind, als der bisher aussschliesslich verwendeten heuristischen Tiefensuche. Um eine leichtere Vergleichbarkeit Fluentkalkül-basierter Planungsverfahren mit anderen Planungsalgorithmen zu ermöglichen, wurde eine Übersetzung des ADL-Fragments der Planungsdomänenbeschreibungssprache PDDL in den Fluentkalkül geschaffen. Damit können zahlreiche Planungsprobleme aus der Literatur und Planungsdomänenbibliotheken auch mit Fluentkalkül-Planern bearbeitet werden. Die Übersetzung kann zugleich als formale Semantik des nur informal spezifizierten PDDL dienen.