hplus0603 said:
Yeah, well, my kids will jam the couch even closer to the wall to make more space for the Valve Index, and here we are again :-)

That's why my factory makes smaller and smaller robots. They even have sensors to dodge VR-Goggle-kids so they don't tumble over the robot.
BTW, i always wanted to know if room scale VR goggles is a safety risk for kids (or grown ups too), so if you can talk? : )

To defend my TS algorithm, i would handle narrow dead end passages with preprocessing the graph, so a vertex on the passage entry is duplicated. Requires also to duplicate edges, and probably i'd also need to ensure they do not cross each other:

TS would still give a working and optimal solution then, without awareness of going forth and back or crossing the same space twice.

I had to do this once for mesh processing. Multiple paths could cross the same edges of the mesh, and keeping it in order so crossing is prevented was a nightmare to implement. But it worked.

The traveling salesman problem assumes that you start with an accurate map. You can't assume that your old map is still accurate because people move furniture around, so you first have to map the room. You can map the room with long-range sensors, but you'll probably get more accurate results if you visit every location in the room that you can get to. And as a bonus, by the time your map is finished the room is already clean because you have been vacuuming while you were mapping the room.

I would try to avoid making the robots too small. Tiny robots can hold less dirt at once, take longer to cover the same area, are more likely to be accidentally crushed when somebody steps on them, and have less suction. And beyond a certain point, making them smaller actually makes them more expensive.

a light breeze said:
You can't assume that your old map is still accurate because people move furniture around

uhhm… constantly moving furniture is a point. I give up. You guys won. PacMan AI > TS in practice. : )
The robot could constantly update the map with sensors for the next day. But if we assume dynamic environment it would never be optimal and not worth the trouble.

The ‘small robot' was only meant as a joke.

Given that you need to visit every location anyway in order to clean it, I would just use touch-range sensors. Touch range sensor can detect perfectly transparent glass and work in heavy fog because they can use actual touch.

If your robot is heavy and fast enough that ramming into obstacles at full speed is a problem, give it enough sensor range that it can avoid doing so.