Carleton University - School of Computer Science Honours Project
Summer 2020
Automatons in Action – Exploring a Solution to Nest Building
SCS Honours Project Image
ABSTRACT
The work presented in Building a Nest by an Automaton (J. Czyzowicz, D. Dereniowski and A. Pelc, "arXiv | Building a Nest by an Automaton," 24 April 2019. [Online]. Available: https://arxiv.org/abs/1904.10850.), will present the basis for this report. The intent is to recreate the algorithm discussed in the paper. The algorithm focuses on a robot building the smallest possible nest in optimal time. The robot is presented with an infinite two-dimensional environment, where each point represents a box either containing a brick or being empty. The chance of a box containing a brick in the initial state is unknown to the robot. The robot will start on a box that contains a brick. The robot can move in any of the polar directions. At any time, the robot may choose to pick up a brick from its current position, assuming the robot is not already carrying a brick and the box it is on has a brick. Upon the robot collecting a brick, the box will change to an empty state. The robot may continue to carry the brick traveling any distance, inevitably releasing the brick on an empty box. The goal of the robot is to construct a connected brick structure with the smallest Manhattan distances between the structure’s two furthest bricks.