National Technical University of Athens (NTUA)
Byzantine fault tolerance in autonomous robots evacuation problems
Abstract
dc:descriptionIn 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.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Papaioannou, Ioannis
- Παπαϊωάννου, Ιωάννης
Subjects
dc:subject × 17- Ανοχή σε σφάλματα
- Αυτόνομα ρομπότ
- Βυζαντινά σφάλματα
- Fault tolerance
- Crash faults
- Byzantine faults
- Search
- Evacuation
- Autonomous robots
- Wireless communication
- Face-to-Face communication
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Επιστήμη ηλεκτρονικών υπολογιστών
- Computer and Information Sciences
- Natural Sciences
- Computer Science
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/56796