Bounds on the cleaning times of robot vacuums
Introduction
Messinger and Nowakowski [1] examine the behaviour of the following deterministic walk in an undirected graph : When the walk reaches vertex , the next edge traversed is the edge incident to 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 recording the time it was last cleaned (in either direction). The robot begins at a starting vertex at time . Then, at time , the robot traverses the incident edge of minimum weight and sets the weight of that edge to .
The cover time, , of a connected graph is the maximum number of steps, over all initial edge weightings and all possible starting vertices , until each edge has been visited. We define, to be the worst-case cover time over all graphs containing exactly edges.
In [1], it is shown that the cover time is at most exponential in , and the authors conjecture that it is, in fact, polynomial in . 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 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.
Section snippets
Exponential bounds on the cover time
Here we present exponential bounds on the cover time.
Polynomial time protocols
In this section we present two simple deterministic walks that do lead to polynomial cover times.
Acknowledgements
The authors were partly supported by NSERC.
We thank the referee for the many helpful suggestions and improvements.
References (2)
- et al.
The robot cleans up
- et al.
Simulating a random walk with constant error
Combinatorics, Probability and Computing
(2006)