Lamprou, I 
ORCID: 0000-0001-5337-7336
(2018)
Mobility Problems in Distributed Search and Combinatorial Games.
PhD thesis, University of Liverpool.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
201146565_Nov2018.pdf - Unspecified Download (1MB) |
Abstract
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 |
| Supervisors: |
|
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3028459 |
Dimensions
Dimensions
