Byzantine fault tolerance in autonomous robots evacuation problems

Abstract

In this thesis, we study search and evacuation problems of autonomous robots i.e. situations where a group of robots needs to find one or more targets that are located in unknown points of a territory. In our case of interest, the target is an exit and the goal of the robots is either to locate the exit (search problem) or to leave the territory (evacuation problem), as fast as possible. In our work, we consider (n,f)-search and (n,f)-evacuation from a circle, where n robots cooperate to find or evacuate from the exit and f of them may be faulty. For the worst-case analysis of our algorithms, we consider an adversary who selects the location of the exit and the behaviour of the malicious robots (its trajectories as well as the messages they will broadcast) to maximize the resulting search and evacuation completion time. The adversary also chooses which robots are faulty, adding to the challenge. Two distinct communication models are explored to facilitate interactions among the robots: the Wireless model where robots can communicate instantly regardless of distance and the Face-to-Face model that requires robots to physically gather in the same location simultaneously in order to exchange information. We provide optimal algorithms for the (n,f)-search on a circle addressing scenarios that involve f crash faults or one Byzantine fault. We extend the discussion to circle evacuation under one and two Byzantine faults and under f Byzantine faults presenting detailedalgorithms and conducting an in-depth analysis of their time requirements.

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