Towards a fully autonomous and cooperative deployment of multi-robot teams for exploration and coverage in unknown or partially known environments

Abstract

In this thesis we deal with the problem of navigating a team of robots in both known and unknown environments, so as the mission's objectives to be fulfilled. The structure of this thesis is divided into two main pillars. In the first pillar we deal with the problem of determining an optimal path involving all points of a given area of interest (offline), while avoiding sub-areas with specific characteristics (e.g. obstacles, no-fly zones, etc.). This problem, which is usually referred as multi-robot coverage path planning (mCPP), has been proven to be NP-hard. Currently, existing approaches produce polynomial algorithms that are able to only approximate the minimum covering time. In chapter 3, a novel methodology is proposed, capable of producing such optimal paths in approximately polynomial time. In the heart of the proposed approach lies the DARP algorithm, which divides the terrain into a number of equal areas each corresponding to a specific robot, in such a way to guarantee: complete coverage, non-backtracking solution, minimum coverage path, while at the same time does not need any preparatory stage. In the second pillar of this thesis, we design algorithms capable of navigating team of robots without any prior knowledge. More specifically, we deal with problems where the objectives of the multi-robot system can be transformed to the optimization of a specifically defined cost-function. Due to the unknown environment, unknown robots' dynamics, sensor nonlinearities, etc., the analytic form of the cost-function is not available a priori. Therefore, standard gradient descent-like algorithms are not applicable to these problems. In chapter 4, we first show that optimal one-step-ahead exploration schemes that are based on a transformed optimization criterion can lead to highly efficient solutions to the multi-robot exploration. As, however, optimal one-step-ahead solutions to the transformed optimization criterion cannot be practically obtained using conventional optimization schemes, the second step in our approach is to combine the use of the transformed optimization criterion with the Cognitive Adaptive Optimization (CAO): CAO is a practicably feasible computational methodology which adaptively provides an accurate approximation of the optimal one-step-ahead solutions. This combination results in a multi-robot exploration scheme which is both practically implementable and provides with quite efficient solutions as it is shown both by theoretical analysis and, most importantly, by extensive simulation experiments and real-life underwater sea-floor mapping experiments in the Leixoes port, Portugal. Finally, in chapter 5, we propose a distributed algorithm applicable to a quite large class of practical multi-robot applications. In such multi-robot applications, the user-defined objectives of the mission can be casted as a general optimization problem, without explicit guidelines of the sub-tasks per different robot. A novel distributed methodology is proposed, based on the CAO algorithm (as proposed on the previous chapter) that carefully designs a cost-function for each operational robot, where the joined optimization of which can accomplish the overall team objectives. The latter can be achieved by online learning (on each robot), only the problem-specific characteristics that affect the accomplishment of the overall mission objectives. The overall, low-complexity algorithm, can straightforwardly incorporate any kind of operational constraint, is fault tolerant and can appropriately tackle time-varying cost-functions. A cornerstone of this approach is that it shares the same convergence characteristics as those of block coordinate descent algorithms. The proposed algorithm is evaluated in four heterogeneous simulation set-ups under multiple scenarios, against both general purpose (centralized) and specifically-tailored to the problem in hand, algorithms.

Η παρούσα διατριβή ασχολείται με το πρόβλημα της πλοήγησης ομάδων ρομπότ σε άγνωστα ή μερικώς γνωστά περιβάλλοντα, έτσι ώστε να καλυφθούν οι στόχοι της εκάστοτε αποστολής. Η δομή της διατριβής χωρίζεται σε δυο κύριους πυλώνες. Ο πρώτος πυλώνας αφορά τον σχεδιασμό τροχών offline για περιπτώσεις στις οποίες υπάρχει πληροφορία σχετικά με το περιβάλλον που χρειάζεται να καλύψει η ομάδα από ρομπότ. Για την περίπτωση του ενός ρομπότ, όπου το πρόβλημα είναι γνωστό και ως Σχεδιασμός Τροχιάς για Κάλυψη (Coverage Path Planning, CPP), μια βέλτιστη Ο(n) μεθοδολογία έχει προταθεί, όπου n είναι το μέγεθος του πλέγματος που πρέπει να καλυφθεί. Δυστυχώς, όταν εμπλέκονται παραπάνω από ένα ρομπότ το πρόβλημα γίνεται NP-hard και μόνο προσεγγιστικές μεθοδολογίες έχουν προταθεί. Στο 3ο κεφάλαιο της παρούσας διατριβής, προτείνουμε έναν αλγόριθμο που χωρίζει τη διαθέσιμη περιοχή σε χωρικά-συμπαγείς υποπεριοχές, μία για κάθε ρομπότ. Αξίζει να σημειωθεί ότι οι αρχικές θέσεις των ρομπότ είναι μέρος της εξίσωσης και άρα δεν απαιτείται ξεχωριστός χρόνος έτσι ώστε να μεταφερθεί το κάθε ρομπότ στη δικιά του υποπεριοχή. Μετά από τη χάραξη αυτών των υποπεριοχών, εφαρμόζουμε κατανεμημένα τον βέλτιστο αλγόριθμο (STC), που έχει προταθεί για την περίπτωση του ενός ρομπότ, σε κάθε μια από αυτές τις περιοχές. Συνολικά, η μεθοδολογία πλοήγησης πετυχαίνει: 1) να διασχίσει όλη τη διαθέσιμη περιοχή (complete coverage), 2)περνώντας μόνο μια φορά από κάθε σημείο της περιοχής (without backtracking), 3) πραγματοποιώντας ελάχιστα ίδια μονοπάτια για κάθε διαθέσιμο ρομπότ (minimum coverage path per robot), 4) και τέλος τα ρομπότ μπορούν να ξεκινούν από τις αρχικές τους θέσεις (initial positions constraint).Μελετώντας τη σχετική βιβλιογραφία (κεφάλαιο 2), προκύπτει ότι καμία άλλη μέθοδος δεν πετυχαίνει όλα τα προηγούμενα χαρακτηριστικά στην παραγόμενη λύση της. Ο δεύτερος άξονας αφορά την ανάπτυξη μια ομάδας από ρομπότ σε ένα τελείως άγνωστο περιβάλλον, έτσι ώστε να επιτευχθούν οι στόχοι της αποστολής. Στο δεύτερο άξονα οι αποφάσεις για την πλοήγηση των αυτόνομων οχημάτων λαμβάνονται σε πραγματικό χρόνο αξιοποιώντας τη γνώση (από τις μετρήσεις) που έχουν λάβει μέχρι το εκάστοτε βήμα. Η πλειονότητα των συγκεκριμένων προβλημάτων έχει αποδειχθεί αρκετά δύσκολη να επιλυθεί αποδοτικά. Στη βιβλιογραφία το παραπάνω πρόβλημα έχει αντιμετωπιστεί με τις ακόλουθες κλάσεις προσεγγίσεων: 1) Βέλτιστος έλεγχος ή τεχνικές δυναμικού προγραμματισμού, 2) Άπληστοι αλγόριθμοι, 3) Εκμάθηση παραμέτρων ελέγχου μέσω εκτεταμένων προσομοιώσεων (simulation-based). Στο 2ο κεφάλαιο παρουσιάζουμε συνοπτικά τις βασικές αρχές που διέπουν τη λειτουργία τους αλλά και τα επιτεύγματα και τις αδυναμίες που παρουσιάζουν η κάθε μια από αυτές. Στο 4ο κεφάλαιο προτείνουμε μια μεθοδολογία που είναι σε θέση να σχεδιάζει τις τροχιές των ρομπότ αυτόματα σε πραγματικό χρόνο, έτσι ώστε να κατασκευάζεται ο χάρτης της περιοχής στον μικρότερο δυνατό χρόνο. Το συγκεκριμένο πρόβλημα έχει αποδειχθεί ότι είναι NP-complete, έτσι δεν μπορεί να λυθεί με βέλτιστο τρόπο. Στο ίδιο κεφάλαιο δείχνουμε ότι το συνολικό πρόβλημα μπορεί να αντιμετωπιστεί επαρκώς, εάν σχεδιαστεί μια συνάρτηση κόστους (κριτήριο απόδοσης) που περιλαμβάνει όρους που αφορούν συγκεκριμένες παραμέτρους και μετρικές του προβλήματος της χαρτογράφησης. Παρόλα αυτά, οι άπληστες μεθοδολογίες δεν μπορούν να εφαρμοστούν στον πραγματικό κόσμο αφού θα απαιτούσαν από την ομάδα των ρομπότ να κάνει ένα (μεγάλο) σύνολο από κινήσεις και ύστερα να αποφασίσει ποια είναι η αποδοτικότερη για να ακολουθήσει. Για να αντιμετωπίσουμε το συγκεκριμένο πρόβλημα προτείνουμε μια μεθοδολογία πλοήγησης που θα μπορεί να υλοποιηθεί σε ρομποτικά αυτόνομα οχήματα πραγματικού κόσμου. Η μεθοδολογία αυτή βασίζεται στον Γνωσιακό Προσαρμοστικό αλγόριθμο Βελτιστοποίησης (Cognitive-based Adaptive Optimization, CAO) και είναι σε θέση να προσεγγίζει τις λύσεις από τους άπληστους αλγορίθμους μέσω ενός πρακτικά υλοποιήσιμου συστήματος αποφάσεων, αφαιρώντας τη μη ρεαλιστική απαίτηση για πραγματοποίηση ενός συνόλου από εντολές ελέγχου πριν τη λήψη της απόφασης. Ο προτεινόμενος αλγόριθμος ξεπέρασε την υπάρχουσα στρατηγική χαρτογράφησης σε μια σειρά από εκτεταμένες προσομοιώσεις, αλλά και όταν εφαρμόστηκε σε πραγματικά μη επανδρωμένα υποβρύχια οχήματα που βρίσκονταν στο λιμάνι Leixoes του Πόρτο. Στο 5ο κεφάλαιο προτείνουμε έναν κατανεμημένο αλγόριθμο γενικού σκοπού, που είναι σε θέση να πλοηγεί ομάδες από ρομπότ με σκοπό την επίτευξη των αυθαίρετα ορισμένων στόχων της αποστολής. Η συγκεκριμένη μεθοδολογία επεκτείνει τον αλγόριθμο που προτάθηκε στο προηγούμενο κεφάλαιο, για αυτό το λόγο παρουσιάζουμε και μια λεπτομερή σύγκριση της απόδοσης των δυο αλγορίθμων. Το κύριο χαρακτηριστικό που διαφοροποιεί τον παρόντα αλγόριθμο - εκτός από την κατανεμημένη φύση του - σε σχέση με αυτόν που προτάθηκε στο 4ο κεφάλαιο, είναι η ικανότητά του να χρησιμοποιεί αποδοτικά πληροφορία από προηγμένες αποφάσεις, με σκοπό την προσέγγιση της παραγώγου της συνάρτησης κόστους που πρέπει να βελτιστοποιηθεί σε κάθε αποστολή. Συνολικά, η προτεινόμενη μεθοδολογία έχει τα ακόλουθα πλεονεκτήματα: (α) δεν απαιτεί γνώση από τις δυναμικές του συστήματος που καλείται να βελτιστοποιήσει, (β) μπορεί να ενσωματώσει οποιουδήποτε είδους λειτουργικούς ή φυσικούς περιορισμούς, (γ) έχει τα ίδια χαρακτηριστικά σύγκλισης με την οικογένεια των block coordinate descent (BCD) αλγορίθμων, (δ) είναι ανεκτική στον θόρυβο, (ε) μπορεί να χειριστεί επαρκώς προβλήματα πλοήγησης πολλαπλών ρομπότ, όπου οι στόχοι αλλάζουν κατά τη διάρκεια της αποστολής, και (στ) μπορεί να υλοποιηθεί σε ενσωματωμένα συστήματα με περιορισμένες ενεργειακές δυνατότητες. Ο προτεινόμενος αλγόριθμος δοκιμάστηκε σε τέσσερα διαφορετικά προβλήματα που αφορούν την πλοήγηση ρομπότ, με αρκετά διαφορετικά σενάρια, συγκρινόμενος με γενικού σκοπού αλγορίθμους αλλά και μεθοδολογίες ειδικά κατασκευασμένες για το εκάστοτε πρόβλημα.