More modern vacuums have actual navigation systems - interesting can you be more specific

More modern vacuums have actual navigation systems

What do you mean by that?

[quote]If you divide your area into any form of elements, you need to traverse all of them. So it is travelling salesman,[/quote]

If I were a computer science professor, and a student gave that answer, I would fail them.

The traveling salesman is interested in going through a number of points at the minimum cost, which is what makes it an NP-complete problem. A vaccum cleaner doesn't need to do it at minimum cost; it just needs to “visit each cell at least once," which is a vastly simpler problem. The vacuum cleaner can, for example, use the “flood fill” algorithm used by tools such as the paint bucket in paint programs, and it will work fine. Nobody would say that the paint bucket tool in a paint program solves the “traveling salesman problem.”

Using the name “traveling salesman problem” for something which can easily be solved in polynomial time spreads significant misunderstanding of the point of the TSP. You'd have to try hard to come up with a solution with worse running time than n^3 in number of nodes, and it can be trivially solved in linear time. Words have meaning, and when they're used contrary to the accepted meaning, that removes the communcative power and clarity of those words, so please don't do that.

hplus0603 said:
The traveling salesman is interested in going through a number of points at the minimum cost, which is what makes it an NP-complete problem. A vaccum cleaner doesn't need to do it at minimum cost;

You claim the cleaner does not need to achieve minimum cost - i assumed minimizing it is desired and i still think so.

Using the name “traveling salesman problem” for something which can easily be solved in polynomial time spreads significant misunderstanding of the point of the TSP. You'd have to try hard to come up with a solution with worse running time than n^3 in number of nodes, and it can be trivially solved in linear time.

I did not say travelling sales man has to be solved, only it is the same problem. I proposed spanning tree as a starting point because it's often used to get practical solutions which are not optimal but acceptable.

I did not had in mind to solve travelling sales man exactly, nor do i assume cleaning bot software does so in practice.
I can imagine my post makes this impression, but that's not intended.
Actually my take on the problem depends on the robots ability to drive in curves or if straight paths are preferred for mechanical reasons.

hplus0603 said:
[quote]If you divide your area into any form of elements, you need to traverse all of them. So it is travelling salesman,[/quote] If I were a computer science professor, and a student gave that answer, I would fail them.

Ok, then rephrasing it to:

‘’If you divide your area into any form of elements, you need to traverse all of them.
It's also desired to visit each space only once to save power and time.
Optimal solution requires to solve a travelling salesman problem, but any space filling curve will do."

I hope to have passed the test now, but i'm ready to be corrected. (I'm self thought and lack any education in CS.)

What do i mean by that? Well they don't use GPS for that right?

In a game you can also build exact polygonal maps of accessible floor regions and compute efficient paths to clean regions (e.g. enter a convex polygon at corner A, exit it at corner B, zigzag between A and B by subdividing the floor into slabs that are perpendicular to the AB line and as wide as the robot, with adjustments at the endpoints).

Yeah but this involves awareness we don't fully understand, some may say we have now ai tthat should learn and handle this but yet atill in manner of learning and building the map this is a bottleneck

I did not say travelling sales man has to be solved, only it is the same problem.

It's not.

Most living rooms, when partitioned into grids/areas, aren't even solvable by “only visiting each area once.” Consider a simple “T” shape – the robot starts in one end, and goes out the end of the next end, but then can't magically jump to the third spoke without passing through any previously visited cell.

Well they don't use GPS for that right?

I recommended doing some reading on SLAM (Simultaneous Localization And Mapping) and I still think you should do that if you're interested in this area. It's a very important concept for robots moving in the real world.

One of the main technical advanced in the original Roombas were their low-cost LIDAR implementation, that gave them a 2D representation of blocking surfaces in the area, within which they could then do exploration. Later versions use better algorithms, because they have more memory available for storing previously-seen map data.

hplus0603 said:
It's not. Most living rooms, when partitioned into grids/areas, aren't even solvable by “only visiting each area once.” Consider a simple “T” shape – the robot starts in one end, and goes out the end of the next end, but then can't magically jump to the third spoke without passing through any previously visited cell.

My robot has only half the width you think it has :P

@JoeJ 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 :-)