Floor cleaning algorithms

I was meticulously sweeping the restaurant's floor when I came upon a nifty optimisation method. Meticulous sweeping means removing the chairs to properly clean under the tables before returning the chairs.

The simple, brute force procedures would be as follows:

Remove a few chairs
Clean under the table
Replace those chairs.
Repeat for other chairs.

It's tedious, moving those chairs back and forth. Here is an algorithm that will help slash chair-moving effort by about half (depending on inter-chair spacing and availability of space between chairs).

Form closed paths by going from chair to chair, and returning the starting point. The chairs on each loop must be identical. You can have as many closed loops as desired. Each chair must be traversed exactly once. The paths should be chosen so that the total path length is minimised.

Start working on one path.
Remove one chair, and sweep the area below it.
Remove the next chair, and place it in the first chair’s original position. Sweep the area below the second chair.
Proceed along the path.
Remove the last chair, and place it in the second last chair’s position. Sweep the area below the last chair.
Fill the last position with the first chair.

Repeat for other paths.

An efficiency comparison for a particular case of closely spaced, almost-isotropic chairs (little difference between the width and length). Assume that the chairs are arranged in a loop (such as around a large table), and there is plenty of space behind the chairs. Let the number of chairs be denoted by n.

Using the simplistic floor cleaning algorithm, each chair will have to be moved away, and replaced. Thus, the number of steps required will be 2n.

However, using the above proposed algorithm, the first chair will be removed and placed next to the last chair (which is next to the first chair, since the path forms a closed loop). The second chair is moved to the first chair’s place; the third chair is moved to the second chair's place...
And the removed chair is moved to the last chair’s place.
The total number of steps is n + 1, which is strictly less than 2n (the simple algorithm’s number of steps) for all n equal or greater than 2.


One can see that what happens is that a gap is created by removing the first chair, allowing the floor to be cleaned. The gap is then moved forward by bringing the front chair backwards. There are parallels to the study of semiconductors, where the propagation of the absence of electrons (a hole) is equivalent to the propagation of a positively charged particle.


Unfortunately not all lunches are free, and there is a downside to the improved algorithm. Parallels can be drawn to the Travelling Salesperson Problem (TSP), which should set bells ringing- this is not going to be a cheap lunch if we want to find the absolute optimum.

The TSP problem is as follows: a salesperson needs to visit several cities (or offices or houses), visiting each only once, and returning to the starting location. Find a route that would minimise travel time/ distance/ expense/ whatever.

It does not matter what cost we are trying to minimise, the cost can be defined as a function of travel time, distance, ticket fares, comfort… and using data for travel between cities, the cost function reduces to a simple function of 2 variables- the origin, and the destination.

Solution of the TSP can be obtained by brute force- by trying out all combinations. However, the number of steps required is proportional to the factorial of the number of cities/ nodes. Methods have been devised to reduce the computation cost be taking the number of steps down to the exponent of the number of cities/ nodes.


Returning to the floor cleaning problem, the costs associated with moving from chair to chair is the effort required to move the chair- distance, requirement to lift it above other obstacles, rotation required...


The above comparison had used number of steps, not the effort associated with moving the chairs. One trivial example of the closed-loop algorithm failing would be in a setting where the chairs are spaced very far apart (separation distances significantly greater than the width/ length of one chair). In this case, it would be less tedious to move the chairs back and forth a short distance instead of moving them to a distant location.


Remarkably, many real world problems can be reduced to the TSP. For example, optimising the path of a robotic drilling rig as it punches multiple holes in a sheet of metal is exactly the same as the TSP- many holes, each to be punched once, the drilling head to return to its initial position to start on the next sheet.

A less obvious problem would be scheduling the order of heat treatment tasks in an oven. If each task has a required initial and final temperature, how should the tasks be ordered so that the time required is minimised? In this problem, the nodes are the heat-treatment tasks, and the associated cost of going between the various tasks is the time and energy required to bring the oven to the correct temperature for the next task.


Interesting reads

Mathematics & Applied Sciences