Chopra_Nisha.pdf (865.55 kB)
Download file

Scatter Search on a Disk

Download (865.55 kB)
thesis
posted on 23.05.2021, 15:07 by Nisha Chopra
Consider a unit disk with two objects at unidentified locations. We examine the problem of two or more robots in search of both objects in the wireless communication model. We begin with two robots and both are needed to carry an object. Subsequently, we design several algorithms that describe robots trajectories in search of the objects. We were able to achieve a minimum worst-case search time of 6.7518 and a lower bound of 3 + π 2 . Additionally, we define two general cases and bound the worst-case search time for both. The first of the cases is for n ≥ 3 robots and an object can be moved by one robot. The second case is where we have n ≥ 3 robots and two robots are needed to carry an object. We achieve an upper bound of 1 + 2π n + sin (⌊n 2 ⌋ π n ) for the first case and an upper bound of 3 + 2π n + sin π n for the second case, with lower bounds of 2 + π n and 3 + π n respectively.

History

Language

eng

Degree

Master of Science

Program

Applied Mathematics

Granting Institution

Ryerson University

LAC Thesis Type

Thesis

Usage metrics

Keywords

Exports