The robot cleaning problem: A graphical representation

Abstract

Suppose there is a building with many different hallways and a robot vacuum that cleans the building. Each hallway has a time stamp with the last time the hallway was cleaned. The robot cleans the hallways using a greedy algorithm: at each step, the robot looks at the neighbouring hallways and traverses the dirtiest (i.e. the one that hasn't been cleaned in the longest time). We will find the bounds for the minimum number of steps, s(G), the robot takes to clean every edge of a graph G such as: bipartite, tripartite, and multipartite graphs. We will define what it means for a graph to be weakly self-stabilizing, and show that by connecting two weakly/self-stabilizing graphs may result in a weakly self-stabilizing graph. Lastly, we will introduce throttling: the trade-off in cost between adding more robots to a graph and reducing the number of steps to clean the graph.