5
$\begingroup$

I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search can do this, but I was left wondering if you could minimize the backtracking.

I looked into how it's actually done for Roomba and from what I read on Robotics stack exchange, it doesn't use a deterministic algorithm that guarantees shortest distance, because it doesn't know the room layout and obstacles ahead of time.

But what if we did know the full layout of the room at the start? Is there a way to use a map to generate a path through the room with minimum backtracking? In this example, the map is an undirected graph without weights (or every joining edge distance is 1), and it likely contains cycles.

The problem sounds similar to travelling salesman and Hamiltonian paths, but I don't think it maps to them exactly. Travelling salesman and Hamiltonian paths have the requirement that vertices are only visited once. In the Roomba example, we don't care if it vacuums the same spot twice, we just want it to thoroughly vacuum the whole room (don't miss anywhere) as fast as possible.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ TSP with multiple visits is approx-equivalent to metric TSP, meaning they have the same time complexity and approximation factor, and that factor is at most $2$. These slides (Stanford's CS 261: Optimization of 2011) contain proofs of these facts. General TSP, on the other hand (i.e. edge weights not necessarily a metric function, and no repetitions allowed), does not have a constant approximation unless $P = NP$ (also proven there). Note, however, that for any TSP variant, the input graph is a clique. $\endgroup$
    – G. Bach
    Jan 15, 2016 at 15:06
  • 2
    $\begingroup$ If the graph isn't necessarily complete (but allowed to be), the TSP reduces to that generalization, and you get lower bounds on the hardness of the problem that way, i.e.: the problem is NP-hard, and deriving an approximation factor better than the best known approximation factor for metric TSP would be publishable. $\endgroup$
    – G. Bach
    Jan 15, 2016 at 15:10
  • 3
    $\begingroup$ @G.Bach For any reasonable notion of "cell", the graph will be a (subgraph of) a grid graph here. The situation does not seem to be as clear on such graphs. There seems to be some literature that may be relevant here. $\endgroup$
    – Raphael ♦
    Jan 15, 2016 at 16:14
  • $\begingroup$ @Raphael I thought it might be considered a grid graph, but didn't look into it; knowing that the problem is equivalent to metric TSP in general-topology graphs should be a reasonable starting point, though. $\endgroup$
    – G. Bach
    Jan 15, 2016 at 16:58
  • $\begingroup$ Thanks for the comments Raphael and G.Bach. Some extra reading for me. $\endgroup$
    – Niall Connaughton
    Jan 18, 2016 at 6:39

1 Answer 1

Reset to default
-2
$\begingroup$

the classic A* algorithm was invented in 1968 and is used for the purpose of shortest path-finding by robots, and it is provably optimum in a limited sense (eg given an unchanging layout and other constraints). there are many other pathfinding algorithm variants, basically "smart graph traversal" algorithms, eg focused on the online problem with changing constraints, see eg "how do state of the art pathfinding algorithms differ", cstheory.

here is some information on the roomba algorithm which is somewhat proprietary based on an interview with one of the designers (the interview seems no longer available). it is somewhat random and apparently uses a locally optimizing algorithm aka "greedy".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.