Mobility Problems in Distributed Search and Combinatorial Games

Lamprou, I ORCID: 0000-0001-5337-7336
(2018) Mobility Problems in Distributed Search and Combinatorial Games. PhD thesis, University of Liverpool.

[thumbnail of 201146565_Nov2018.pdf] Text
201146565_Nov2018.pdf - Unspecified

Download (1MB)


This thesis examines a collection of topics under the general notion of mobility of agents. We examine problems where a set of entities, perceived as robots or tokens, navigate in some given (discrete or continuous) environment to accomplish a goal. The problems we consider fall under two main research fields. First, Distributed Search where the agents cooperate to explore their environment or search for a specific target location within it. Second, Combinatorial Games, in the spirit of Pursuit-Evasion, where the agents are now divided into two groups with complementary objectives competing against each other. More specifically, we consider three distinct problems: disk evacuation, exploration of dynamic graphs and eternal domination. In Disk Evacuation, two robots with different speeds aim to discover an unknown exit lying on the boundary of a unit disk. For a wide range of speeds, we provide matching upper and lower bounds. In Dynamic Graph Exploration, we analyze the exploration time for a randomly-walking agent wishing to visit all the vertices of a stochastically-evolving graph. In Eternal Domination, we consider rectangular grid graphs and upper bound the amount of guard agents needed to perpetually defend the vertices against an attacker.

Item Type: Thesis (PhD)
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 30 Nov 2018 11:39
Last Modified: 19 Jan 2023 01:13
DOI: 10.17638/03028459