Back to search

National Technical University of Athens (NTUA)

Byzantine fault tolerance in autonomous robots evacuation problems

Abstract

dc:description

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.

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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/56796

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Papaioannou, Ioannis; Παπαϊωάννου, Ιωάννης. Byzantine fault tolerance in autonomous robots evacuation problems. National Technical University of Athens (NTUA), 2024. http://hdl.handle.net/10442/hedi/56796