Ανοχή Βυζαντινών Σφαλμάτων σε Προβλήματα Διαφυγής Αυτόνομων Ρομπότ

Abstract

Σε αυτή τη διατριβή, μελετάμε προβλήματα αναζήτησης (search) και διαφυγής (evacuation) αυτόνομων ρομπότ δηλαδή καταστάσεις όπου μια ομάδα ρομπότ πρέπει να βρει έναν ή περισσότερους στόχους που βρίσκονται σε άγνωστα σημεία μιας περιοχής. Στην περίπτωση που μας ενδιαφέρει, ο στόχος είναι μια έξοδος και ο στόχος των ρομπότ είναι είτε να να εντοπίσουν την έξοδο (πρόβλημα αναζήτησης) ή να εγκαταλείψουν την περιοχή (πρόβλημα διαφυγής) όσο το δυνατόν γρηγορότερα. Στην μελέτη αυτή, εξετάζουμε την (n,f)-αναζήτηση και την (n,f)-διαφυγή από έναν κύκλο, όπου n ρομπότ συνεργάζονται για να να εντοπίσουν την έξοδο ή να διαφύγουν μέσω της εξόδου και f από αυτά μπορεί να εμφανίσουν σφάλματα. Για την ανάλυση της χειρότερης περίπτωσης των αλγορίθμων μας, θεωρούμε έναν αντίπαλο που επιλέγει τη θέση της εξόδου και τη συμπεριφορά των εσφαλμένων ρομπότ (τις τροχιές τους καθώς και τα μηνύματα που θα μεταδώσουν)με στόχο την μεγιστοποίηση του χρόνου αναζήτησης και ολοκλήρωσης της διαφυγής. Ο αντίπαλος επιλέγει επίσης ποια ρομπότ θα εμφανίσουν σφάλματα. Διερευνώνται δύο διαφορετικά μοντέλα επικοινωνίας για τη διευκόλυνση των αλληλεπιδράσεων μεταξύ των ρομπότ: το ασύρματο μοντέλο όπου τα ρομπότ μπορούν να επικοινωνούν άμεσα ανεξαρτήτως απόστασης και το μοντέλο Face-to-Face που απαιτεί από τα ρομπότ να συναντηθούν ταυτόχρονα στην ίδια τοποθεσία προκειμένου να ανταλλάξουν πληροφορίες. Παρέχουμε βέλτιστους αλγορίθμους για την (n,f)-αναζήτηση σε έναν κύκλο αντιμετωπίζοντας σενάρια που περιλαμβάνουν f σφάλματα συντριβής (crash faults) ή ένα Βυζαντινό σφάλμα. Επεκτείνουμε τη συζήτηση στην διαφυγή από κύκλο υπό ένα και δύο Βυζαντινά σφάλματα και υπό f Βυζαντινά σφάλματα παρουσιάζοντας λεπτομερείς αλγορίθμους και πραγματοποιώντας μια εις βάθος ανάλυση των χρονικών τους απαιτήσεων.