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

Η παρούσα διατριβή ασχολείται με το πρόβλημα της πλοήγησης ομάδων ρομπότ σε άγνωστα ή μερικώς γνωστά περιβάλλοντα, έτσι ώστε να καλυφθούν οι στόχοι της εκάστοτε αποστολής. Η δομή της διατριβής χωρίζεται σε δυο κύριους πυλώνες. Ο πρώτος πυλώνας αφορά τον σχεδιασμό τροχών 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) αλγορίθμων, (δ) είναι ανεκτική στον θόρυβο, (ε) μπορεί να χειριστεί επαρκώς προβλήματα πλοήγησης πολλαπλών ρομπότ, όπου οι στόχοι αλλάζουν κατά τη διάρκεια της αποστολής, και (στ) μπορεί να υλοποιηθεί σε ενσωματωμένα συστήματα με περιορισμένες ενεργειακές δυνατότητες. Ο προτεινόμενος αλγόριθμος δοκιμάστηκε σε τέσσερα διαφορετικά προβλήματα που αφορούν την πλοήγηση ρομπότ, με αρκετά διαφορετικά σενάρια, συγκρινόμενος με γενικού σκοπού αλγορίθμους αλλά και μεθοδολογίες ειδικά κατασκευασμένες για το εκάστοτε πρόβλημα.