Time-Extended Multi-Robot Task Allocation - A Reoptimization Framework with Provable Performance

Die Kombination der Stärken von Mensch und Automation in interaktiven Multi-Robot-Task-Allocation (MRTA) Optimierungssystemen zur Koordination von Multi-Roboter Systemen ist empfehlenswert, um deren volles Potential auszuschöpfen. Zur Realisierung solcher interaktiven MRTA Optimierungssysteme sind Reoptimierungsansätze vielversprechend. Diese fehlen jedoch bislang für MRTA Probleme, insbesondere solche mit Qualitätsgarantien. Daher fokussiert sich diese Dissertation auf Reoptimierungsansätze für heterogene, zeitlich ausgedehnte MRTA Probleme mit Vorgänger- und Synchronisierungsbedingungen. ... mehrFür zehn relevante Problemmodifikationen werden Reoptimierungsheuristiken vorgestellt, deren generierte Lösungen garantiert zulässig sind. Zudem werden für die Modifikationen des Hinzufügens und Löschens einer Aufgabe Garantien zur Lösungsgüte in Form von oberen Schranken des resultierenden Approximationsverhältnisses gegeben. Zur weiteren Exploration des Lösungsraums wird ein metaheuristisches Reoptimierungs-Framework vorgestellt, das die Reoptimierungsheuristiken mit einer beliebigen, für heterogene, zeitlich ausgedehnte MRTA Probleme mit Vorgänger- und Synchronisierungsbedingungen geeigneten Metaheuristik kombiniert. Die vorgestellte konkrete Realisierung dieses Frameworks, welche auf einem Genetischen Algorithmus basiert, erhält die zuvor gegebenen Qualitätsgarantien. Abschließend wird eine umfangreiche Auswertung der vorgestellten Reoptimierungsansätze durchgeführt, welche diese mit zwei Optimierungsansätzen vergleicht. Die Ergebnisse der Untersuchung zeigen deutlich, dass die Reoptimierungsansätze den Optimierungsansätzen überlegen sind hinsichtlich der für die Anwendung in interaktiven MRTA Optimierungssystemen relevanten Kombination von Lösungsgüte, Lösungsstabilität und Reaktionsfähigkeit.

Combining the strength of the human and the automation in interactive multi-robot task allocation (MRTA) optimization systems is a promising approach to the coordination of multi-robot systems to fully exploit their potential. To enable interactive MRTA optimization systems, reoptimization approaches are very auspicious. However, so far no reoptimization approaches with performance guarantees have been proposed for MRTA problems. To close this gap, this thesis focuses on reoptimization approaches for heterogeneous, time-extended MRTA problems with precedence and synchronization constraints. ... mehrReoptimization heuristics are introduced for ten relevant problem modifications which are all guaranteed to yield feasible solutions. Furthermore, guarantees on the solution quality in the form of upper bounds on the resulting approximation ratios are given for the modifications of inserting a task to and deleting a task from a problem instance. A metaheuristic reoptimization framework that combines the proposed reoptimization heuristics with any metaheuristic suitable for heterogeneous, time-extended MRTA problems with precedence and synchronization constraints is proposed to further exploit the solution space. Moreover, a specific implementation of the framework is presented. It is based on a genetic algorithm and preserves the afore given performance guarantees. Finally, an extensive evaluation of the proposed reoptimization approaches comparing them to two optimization approaches is conducted. The evaluation results clearly indicate the reoptimization approaches to be superior to the optimization approaches w.r.t. the combination of solution quality, responsiveness and solution stability, all of which are characteristics relevant for the application of solution approaches in interactive MRTA optimization systems.