Carleton University - School of Computer Science Honours Project
Winter 2019
Robot Evacuation in a Disk with Arbitrary Starting Positions
Nicolas Perez
SCS Honours Project Image
ABSTRACT
Imagine a scenario in which there are 2 robots which can move at most 1 unit speed are placed inside of a room (AKA a disk) whose perimeter is in the shape of a perfect circle of 1 unit radius. The 2 robots must find the exit along the perimeter and leave the room in the shortest amount of time. In this project, I will examine this problem from a mathematical perspective, considering a 'perfect' model for simplicity and considering various sub-scenarios which determine where they are initially placed inside of the disk and how much information they know about their initial placements. The robots can only find the exit once they come into contact with it, and both robots can communicate anything they know or have learnt about their environment to the other robots. This includes but is not limited to their trajectory, their GPS coordinates, the location of the perimeter of the disk (if it is known) and the exit to the disk (again, if it is known). Using knowledge from various pieces of work on similar variations of this problem as well as some of my own original work, I will show algorithms for multiple variations of the problem which are all proven to be at-most 1 unit of time off from optimal solutions. I will also discuss a modified model for the problem as well as demonstrate methods for getting the expected run time of evacuation algorithm which both might be useful for future work on the evacuation problem.