Mixed-integer linear programming applied to temporal planning of concurrent actions

Abstract

Auf Grund ihrer vielfältigen Anwendungsmöglichkeiten gewinnen autonome Systeme zunehmend an Bedeutung. Entsprechend besteht großes Interesse an effizienten Verfahren für das automatische Planen. Das Planen mit STRIPS-ähnlichen Operatoren ist ein kombinatorisches Problem. Die gemischt-ganzzahlige Optimierung kann effektiv zur Lösung von Problemen dieser Art eingesetzt werden. In dieser Arbeit werden allgemeine, vom konkreten Anwendungsfall unabhängige Formulierungen gemischt-ganzzahliger linearer Programme für das temporale Planen nebenläufiger Aktionen und eine Verallgemeinerung des in Graphplan verwendeten Planungsgraphen vorgestellt. Gemeinsam werden sie zur Bestimmung von Plänen minimaler Dauer angewendet. Dabei darf die Dauer von Aktionen reellwertig sein. Ein Vergleich mit Temporal Graphplan basierend auf experimentell ermittelten Perfomanzdaten liefert erfolgversprechende Resultate.

Due to the wide range of applications, the relevance of autonomous systems is growing. Hence, there is great interest in efficient automated planning methods. Planning of STRIPSlike operators is a combinatorial problem. Mixed-Integer Programming is a powerful tool for modeling and solving problems of this type. In this thesis domain-independent Mixed-Integer Linear Programming formulations for temporal planning of concurrent actions and a generalization of Graphplan's planning graph are presented. In combination they are applied to compute plans, that are optimal with respect to their duration. The method can handle actions of real-valued duration. A comparison with Temporal Graphplan based on experimental performance data yields promising results.