Task planning and control synthesis for multi-agent systems

Abstract

One of the major areas of research interest in the field of robotics has been the operation of autonomous multi-agent systems in order to perform complicated tasks in dynamical environments. Additionally, the combination of task planning with supervisory control for autonomous multi-agent systems is very challenging and it has been a topic of increasing interest in the last decade, since it can provide a robust framework for autonomous multi-agent task planning and execution. While task planning considers the determination of discrete sequences of actions that are appropriately executed ensuring that the system reaches given objectives, the supervisory control considers the orchestration of the control actions across multiple systems to achieve a given set of high-level specifications. A key requirement for the automatic task planning is in determining the appropriate abstraction models. A state-of-the-art problem is to determine the appropriate formalism to encode high-level specifications of tasks and the consequent methodologies of converting those into low-level action descriptions. Applications of formal methods to optimization problems provide abstractions for modeling the continuous agents’ actions in an appropriate discrete domain. Task planning problems have a wide variety of applications, such as robotics, logistics, healthcare, traffic control, autonomous vehicles etc.. This dissertation introduces a novel methodology for automatic task planning of (possibly) heterogeneous multi-agent systems utilizing concepts from automata theory in an appropriate form for the proposed methodology. The modeling of system's capabilities, constraints and failure modes is presented. The resulting solution is guaranteed to be complete and optimal, while a heuristic approach is proposed for size reduction of the discrete domain of the system. This dissertation includes a formal analysis leveraging the power and effectiveness of discrete abstractions models in solving complex task planning problems. This dissertation provides industrial applications leveraging the proposed methodology to expound the modeling power of the proposed framework, while demonstrating its potential applications in providing solutions for the industry. This dissertation introduces a new supervisory control framework for heterogeneous multi-agent control synthesis with reactive failure-mode based reconfiguration. Using concepts from automata theory in an appropriate form for the proposed methodology, this framework synthesizes the appropriate control actions for the multi-agent system to fulfill the given task specification with the capability of on-the-fly optimal reconfiguration of the task plan in case of failure occurrence.

Ένας από τους κυριότερους τομείς ερευνητικού ενδιαφέροντος στον τομέα της ρομποτικής είναι η λειτουργία αυτόνομων συστημάτων πολλαπλών πρακτόρων για την εκτέλεση περίπλοκων εργασιών σε δυναμικά περιβάλλοντα. Επιπλέον, ο συνδυασμός σχεδιασμού διαδικασιών με εποπτικό έλεγχο για αυτόνομα συστήματα πολλαπλών πρακτόρων είναι πολύ απαιτητικός και δύσκολος, για αυτό και αποτελεί ένα θέμα αυξανόμενου ενδιαφέροντος την τελευταία δεκαετία, καθώς μπορεί να παρέχει ένα ισχυρό πλαίσιο για αυτόνομο σχεδιασμό και εκτέλεση διαδικασιών πολλαπλών πρακτόρων. Ενώ ο σχεδιασμός διαδικασιών λαμβάνει υπόψιν τον προσδιορισμό των διακριτών ενεργειών που εκτελούνται σε ακολουθία, διασφαλίζοντας με αυτό τον τρόπο ότι το σύστημα επιτυγχάνει τους στόχους που έχουν τεθεί, ο εποπτικός έλεγχος εξετάζει την ενορχήστρωση των ενεργειών ελέγχου σε πολλαπλά συστήματα για την επίτευξη ενός συνόλου διαδικασιών υψηλού επιπέδου. Μια βασική απαίτηση για τον αυτόματο σχεδιασμό διαδικασιών είναι ο καθορισμός των κατάλληλων διακριτών μοντέλων αφαίρεσης. Ένα από τα κύρια προβλήματα της σύγχρονης τεχνολογίας είναι ο προσδιορισμός του κατάλληλου φορμαλισμού για την κωδικοποίηση των προδιαγραφών και των διαδικασιών σε υψηλό επίπεδο, αλλά και η μελέτη της μεθοδολογίας για την μετατροπή αυτών σε περιγραφές χαμηλού επιπέδου. Οι εφαρμογές τυπικών μεθόδων για διακριτά προβλήματα βελτιστοποίησης παρέχουν διακριτά μοντέλα αφαίρεσης, μοντελοποιώντας έτσι τις διαδικασίες των συνεχών πρακτόρων σε έναν διακριτό χώρο. Προβλήματα σχεδιασμού διαδικασιών συναντούμε για παράδειγμα στην ρομποτική, στην εφοδιαστική αλυσίδα, στην υγειονομική περίθαλψη, στον έλεγχο κυκλοφορίας οχημάτων, στα αυτόνομα οχήματα κ.α.. Αυτή η διατριβή εισάγει μια νέα μεθοδολογία για τον αυτόματο σχεδιασμό διαδικασιών συστημάτων πολλαπλών (πιθανώς) ετερογενών πρακτόρων, που χρησιμοποιούν έννοιες από τη θεωρία των αυτόματων, κατάλληλα διαμορφωμένες για την προτεινόμενη μεθοδολογία. Παρουσιάζεται η μοντελοποίηση των δυνατοτήτων, των περιορισμών και των τρόπων αποτυχίας του συστήματος. Η λύση που προκύπτει είναι εγγυημένα πλήρης και βέλτιστη, ενώ προτείνεται μια ευρετική προσέγγιση για τη μείωση του μεγέθους του διακριτού χώρου του συστήματος. Στην παρούσα διατριβή παρουσιάζεται μια επίσημη ανάλυση που αξιοποιεί τη δύναμη και την αποτελεσματικότητα των διακριτών μοντέλων αφαίρεσης για την επίλυση σύνθετων προβλημάτων για τον αυτόματο σχεδιασμό διαδικασιών. Ακόμη, η διατριβή αυτή παρέχει την περιγραφή μερικών βιομηχανικών εφαρμογών, αξιοποιώντας την προτεινόμενη μεθοδολογία, με σκοπό να παρουσιάσει τη δύναμη της μοντελοποίησης της προτεινόμενης μεθοδολογίας, ενώ καταδεικνύει τις πιθανές εφαρμογές αυτής στην παροχή λύσεων για αυτόματα συστήματα στον κλάδο της βιομηχανίας. Τέλος, στην διατριβή αυτή εισάγεται ένα νέο πλαίσιο ελέγχου εποπτείας για την σύνθεση ελέγχου συστημάτων πολλαπλών ετερογενών παραγόντων με δυνατότητα επαναδιαμόρφωσης σε περιπτώσεις αποτυχίας του ελεγχόμενου συστήματος. Χρησιμοποιώντας έννοιες από τη θεωρία των αυτομάτων, κατάλληλα διαμορφωμένες για την προτεινόμενη μεθοδολογία, αυτό το πλαίσιο συνθέτει τις κατάλληλες διαδικασίες ελέγχου για το σύστημα πολλαπλών ετερογενών πρακτόρων για την εκπλήρωση των στόχων που έχουν τεθεί με τη δυνατότητα της βέλτιστης αναδιαμόρφωσης του σχεδίου διαδικασιών σε περιπτώσεις αποτυχίας των ελεγχόμενων πρακτόρων.