Research output: Thesis › Doctoral Thesis

Published

Lancaster University, 2023. 327 p.

Research output: Thesis › Doctoral Thesis

Passos, YT 2023, 'Congestion control of robotic swarms in the common target problem: Theory and algorithms', PhD, Lancaster University. https://doi.org/10.17635/lancaster/thesis/2184

Passos, Y. T. (2023). *Congestion control of robotic swarms in the common target problem: Theory and algorithms*. [Doctoral Thesis, Lancaster University]. Lancaster University. https://doi.org/10.17635/lancaster/thesis/2184

Passos YT. Congestion control of robotic swarms in the common target problem: Theory and algorithms. Lancaster University, 2023. 327 p. doi: 10.17635/lancaster/thesis/2184

@phdthesis{694c49b4bbe8437d82402a5ff9470d30,

title = "Congestion control of robotic swarms in the common target problem: Theory and algorithms",

abstract = "The common target problem in robotic swarms occurs when every robot must visit the same target region. This may happen when a swarm of robots has to collect a leaked toxic substance, for instance. To minimise congestion in such a situation, coordination algorithms for traffic control are required. This thesis presents a mathematical study about measures for evaluating the access efficiency of a common target area as the number of robots in the swarm rises: the target area throughput and the asymptotic throughput. Based on them, two algorithms were developed: the Single Queue Former (SQF) and the Touch and Run Vector Fields (TRVF). I also present approaches for ad hoc robots (i.e., those unaware of the coordination algorithm used by others) without having to learn about them: the Ad Hoc Follower (AHF) and the Mixed Teams (MT). Surprisingly, between the proposed approaches, simply executing an alternative algorithm is better than following another robot perceived by local sensors. In the tests performed in the Stage simulator, the other robots can use SQF or TRVF. These algorithms are tested as alternative algorithms in addition to no coordination (NC), where the robots only go directly to the target and avoid bumping each other. SQF significantly outperforms all algorithms for a higher number of robots or when the circular target region radius is small. Estimations of the expected task completion time for the presented algorithms are also studied. These estimations consider not only the number of robots as input but also environmental and algorithmic global variables, such as the common target area size, the average speed and the average distance between the robots. This work is a fundamental first step to start a discussion on how better approximations can be achieved and which mathematical theories about local-to-global analysis are better suited to this problem.",

author = "Passos, {Yuri Tavares}",

year = "2023",

doi = "10.17635/lancaster/thesis/2184",

language = "English",

publisher = "Lancaster University",

school = "Lancaster University",

}

TY - BOOK

T1 - Congestion control of robotic swarms in the common target problem

T2 - Theory and algorithms

AU - Passos, Yuri Tavares

PY - 2023

Y1 - 2023

N2 - The common target problem in robotic swarms occurs when every robot must visit the same target region. This may happen when a swarm of robots has to collect a leaked toxic substance, for instance. To minimise congestion in such a situation, coordination algorithms for traffic control are required. This thesis presents a mathematical study about measures for evaluating the access efficiency of a common target area as the number of robots in the swarm rises: the target area throughput and the asymptotic throughput. Based on them, two algorithms were developed: the Single Queue Former (SQF) and the Touch and Run Vector Fields (TRVF). I also present approaches for ad hoc robots (i.e., those unaware of the coordination algorithm used by others) without having to learn about them: the Ad Hoc Follower (AHF) and the Mixed Teams (MT). Surprisingly, between the proposed approaches, simply executing an alternative algorithm is better than following another robot perceived by local sensors. In the tests performed in the Stage simulator, the other robots can use SQF or TRVF. These algorithms are tested as alternative algorithms in addition to no coordination (NC), where the robots only go directly to the target and avoid bumping each other. SQF significantly outperforms all algorithms for a higher number of robots or when the circular target region radius is small. Estimations of the expected task completion time for the presented algorithms are also studied. These estimations consider not only the number of robots as input but also environmental and algorithmic global variables, such as the common target area size, the average speed and the average distance between the robots. This work is a fundamental first step to start a discussion on how better approximations can be achieved and which mathematical theories about local-to-global analysis are better suited to this problem.

AB - The common target problem in robotic swarms occurs when every robot must visit the same target region. This may happen when a swarm of robots has to collect a leaked toxic substance, for instance. To minimise congestion in such a situation, coordination algorithms for traffic control are required. This thesis presents a mathematical study about measures for evaluating the access efficiency of a common target area as the number of robots in the swarm rises: the target area throughput and the asymptotic throughput. Based on them, two algorithms were developed: the Single Queue Former (SQF) and the Touch and Run Vector Fields (TRVF). I also present approaches for ad hoc robots (i.e., those unaware of the coordination algorithm used by others) without having to learn about them: the Ad Hoc Follower (AHF) and the Mixed Teams (MT). Surprisingly, between the proposed approaches, simply executing an alternative algorithm is better than following another robot perceived by local sensors. In the tests performed in the Stage simulator, the other robots can use SQF or TRVF. These algorithms are tested as alternative algorithms in addition to no coordination (NC), where the robots only go directly to the target and avoid bumping each other. SQF significantly outperforms all algorithms for a higher number of robots or when the circular target region radius is small. Estimations of the expected task completion time for the presented algorithms are also studied. These estimations consider not only the number of robots as input but also environmental and algorithmic global variables, such as the common target area size, the average speed and the average distance between the robots. This work is a fundamental first step to start a discussion on how better approximations can be achieved and which mathematical theories about local-to-global analysis are better suited to this problem.

U2 - 10.17635/lancaster/thesis/2184

DO - 10.17635/lancaster/thesis/2184

M3 - Doctoral Thesis

PB - Lancaster University

ER -