Bounds on the cleaning times of robot vacuums

Abstract

We show a robot vacuum using a protocol that next cleans the “dirtiest” incident edge may take exponential time to clean a network. This disproves a conjecture of Messinger and Nowakowski. We also present two simple variants of this protocol that are polynomial in time.

Introduction

Messinger and Nowakowski [1] examine the behaviour of the following deterministic walk $W$ in an undirected graph $G=(V,E)$: When the walk reaches vertex $v$, the next edge traversed is the edge incident to $v$ that was last traversed the furthest back in time. The motivation behind their work is a cleaning process where a robot has to clean the edges and/or vertices of a network. For example, the robot may clean a set of rooms, a set of algae infested pipelines, etc. A simple protocol for the robot would be to clean the most contaminated (that is, dirtiest) incident edge. Thus, we may view each edge as having a weight or timestamp $w_e$ recording the time it was last cleaned (in either direction). The robot begins at a starting vertex $s$ at time $T_0=1+{max}_{e\in E}{w}_e$. Then, at time $T$, the robot traverses the incident edge of minimum weight and sets the weight of that edge to $T$.

The cover time, $c\left(G\right)$, of a connected graph $G$ is the maximum number of steps, over all initial edge weightings $w$ and all possible starting vertices $s$, until each edge has been visited. We define, $C_m$ to be the worst-case cover time over all graphs containing exactly $m$ edges.

In [1], it is shown that the cover time $C_m$ is at most exponential in $m$, and the authors conjecture that it is, in fact, polynomial in $m$. Our main result, given in Section 2.1, is an example network whose cover time is exponential. Specifically, we present a graph on which the walk mimics a ternary counter. The counter is slightly strange and is not the standard ternary counter, but it still has the property that it takes exponential time before the walk activates the $n$th bit — this will give our result.

Finally, in Section 3, we present two simple modifications to this walk protocol that both lead to polynomial time cover times. The first is to make the protocol asymmetric: the walk chooses the incident edge that was last traversed in the same direction the furthest back in time. The second modification is to incorporate a simple counter: the walk takes the incident edge that has been cleaned the fewest number of times.