Multi mobile robot task allocation using multi-objective optimization techniques

Abstract

This thesis explores multi-objective optimization for multi-robot task allocation. The goal was to develop a generalized system for task allocation, that would be able to support tasks belonging to different domains, optimizing the allocation with regards to various objectives. Improvements/additions to the initial system were also developed: first, a method to combine knowledge of different robots to better estimate the required resources for each task; then, an adaptive multi-objective routing system, that enables the robotic agents to select a route using different profiles, that allocate different levels of importance to the objectives they pursue. At the same time, they adapt to changes in the environment.The scope of this work is the task allocation problem itself; not task detection, neither task decomposition. The collaborative knowledge usage of knowledge, as well as the routing method proposed, enhance the task allocation system, however they are developed in such a way, that they can be used independently. To solve the individual problems, software was developed, using the Java programming language. Simulators were used like Player/Stage, to test the quality of the solution, or NetLogo, to acquire traffic data. In some parts, like the collaborative learning method, the solution was tested on additional domains, to examine its broadness of application. Other parts (like the task allocation system itself) were developed in such a way, that their application domain is the broadest possible. The results have revealed that the solutions proposed have a significant effect on the efficiency. In the task allocation system, up to 15% of the time, as well as up to 35% of the energy was saved, compared to the other methods examined. The collaborative learning method has shown to reduce the resource prediction error by more than 40% in the presence of limited available data, The routing methods compared to the one proposed, required from 40 to 105% more time to reach their target. Traffic congestion doubled their time required, while the increase for the method proposed was in the range of 10%. Different route profiles, produced different results. Therefore, the methods proposed in this work can bring a big improvement in the allocation of tasks in multi-robot systems, something important during our times with the constant increase of robots in our everyday life. The collaborative learning method - even though it uses already existing approaches - can bring a significant improvement in the absence of sufficient data, and the routing method proposed, has the potential to evolve into a complete urban traffic management system.

Σκοπός της διδακτορικής αυτής διατριβής είναι η κατανομή σε πραγματικό χρόνο εργασιών διαφορετικών τύπων, σε έξυπνους πράκτορες διαφορετικού τύπου. Απώτερος σκοπός είναι η βέλτιστη κατανομή των εργασιών στους καταλληλότερους πράκτορες, ικανοποιώντας στο μέγιστο δυνατό βαθμό τους ορισθέντες στόχους, οι οποίοι είναι περισσότεροι του ενός. Ταυτόχρονα, επιχειρείται η εισαγωγή ενός μηχανισμού ο οποίος θα βελτιώσει τον τρόπο με τον οποίο οι πράκτορες κινούνται προς την θέση στην οποία πρέπει να εκτελεστεί η κάθε εργασία, σύμφωνα με επίσης πολλαπλά κριτήρια.