A vacuum robot runs on randomized direction when it is operating in a room.

I want to know how long it takes to fully cover the whole area (or at least most part of the area) with given information:

  1. the area in the room is 10 square meters.
  2. the dimension of the round shape robot is 40 centimeter.
  3. the robot travels at a speed of 20 meters per minute.
  4. the robot only travels straightly.
  5. the robot forwards to a random direction when hit the wall.

Below the left is a vacuum robot. The right is the imagination of a working robot.

I'm not sure if it relates to routing problem or other Operations Research method. (neither sure if it is a problem that can be optimized by Operation Research but just allow me to put it here.)

Can you please advise how to solve this problem? Thank you

enter image description here

  • 2
    $\begingroup$ "or at least most part of the area" needs to be defined properly. There might be an area on the plain (in the extreme case a point) that is never touched with a positive probability which implies that the expected time of covering the entire area is infinity. $\endgroup$ – r.beigi Jan 3 at 0:35
  • 1
    $\begingroup$ I think this is a very interesting mathematics question. I suggest that you post this question to either math.stackexchange or mathoverflow and use the keywords expectation, expected-value and geometric-probability. This question or its variants may have already been solved. Otherwise, you will know if the question is relatively new or still open. $\endgroup$ – r.beigi Jan 3 at 1:34
  • 1
    $\begingroup$ @Mark K, would you see this or this links. They would be helpful. $\endgroup$ – A.Omidi Jan 3 at 7:22
  • $\begingroup$ @r.beigi, A.Omidi, thank you both for the comments! $\endgroup$ – Mark K Jan 4 at 0:56

I don't know if a closed form solution is achievable. Assuming you can quantify how the robot selects its next direction when it hits a boundary (uniform over the entire circle, uniform over directions not within some angle of its last direction, some nonuniform distribution, ...), you could fairly easily build a simulation model (starting with an empty room -- furniture could be included but would make the model much more complex). Run the simulation a zillion times and you have an estimated distribution for the time to achieve a specified level of coverage. There are other complicating factors you could build in if you chose (such as battery life -- the vac might run out of juice before it achieved the target coverage level).


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.