Carleton University - School of Computer Science Honours Project
Summer 2020
Automatons in Action – Exploring a Solution to Nest Building
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.