This question, as indicated in the title, is motivated by the Roomba vacuum, but I am going to formulate it in slightly more mathematical terms:
Suppose that I am given a union $U$ of finitely many almost disjoint squares of area $A\in \mathbb{N}$. Moreover, a point $p$ were chosen from $U$ randomly (evenly distributed). Finally, assume that I know if any point $q$ is within distance $\frac{\sqrt{A}}{2}$ of the boundary of $U$.
Can I come up with an algorithm to find a path that is piece-wise linear and will pass through each square once?
My initial thoughts are to think about this like a graph theoretic problem. You can construct a graph out of $U$ by treating it like a graph (corners as nodes) and taking the dual graph, which we will call $U^*$. This graph tells you about the connectedness of the squares. Then you start on a random node $v_1$ of $U^*$ and the probability of moving to an adjacent node $v_2$ is as follows $$ P(v_2|v_1) = \begin{cases} 1/n \quad d(v_1,v_2) > \frac{\sqrt{A}}{2}\\ 0 \quad\quad d(v_1,v_2) \le \frac{\sqrt{A}}{2} \end{cases}$$
where $n$ is the number of adjacent nodes with $d(v_1,v_2) > \frac{\sqrt{A}}{2}$.
Then you do the same thing for all the following nodes. The thing you would try to prove is that $\forall 1 \geq \epsilon > 0$, there is a $k \in \mathbb{N}$ such that, after $k$ steps, the probability that you have been to every node is $1 - \epsilon$. But I have no idea how to prove that sort of thing.
Any thoughts on how to better approach this problem? (Or on how Roombas actually work?)
Is there any reason to think that your region $U$ is connected? If not, there's no hope. If yes, note that a random walk on a connected graph will almost surely reach every node.