>You can write perfect code. You can build flawless systems. You can optimize the sh*t out of your cost function. And you can still end up with something that sucks.

>The important part isn’t the optimization algorithm. The important part is figuring out what you should be optimizing for in the first place.

>Most of the time, we don’t even ask that question. We just optimize for whatever’s easy to measure and hope it works out.

>Spoiler: it probably doesn’t.

As tech people, it's kinda hard to admit it, but it's totally correct. Sometimes you actually have to optimize for X, sometimes you don't. It's totally ok to optimize stuff just for passion or to try out new stuff, but if you expect external validation you should do this for things people actually care about.

As an aside, this is also related to the way random companies carry out technical interviews, cargo-culting FAANG practices.

FAANGs tend to care about optimizing a lot of stuff, because when you have billions of customers even the smallest things can pile up a lot of money.

If you are a random company, even a random tech company, in many domains you can go a long way with minimal tuning before you have to turn to crazy optimization tricks.

For example, one day has almost 100k seconds, so if you have 100k daily requests (which is still a lot!), even if you have 10x peaks during the day, you are most likely getting <= 10 requests per second. It's not that much.

Considering all that, it is obvious that the real winner solution would be just look at the map and draw a path by hand, using human intuition and heuristics as an algorithm. Even if you would have to make a few corrections, this could be done in minutes instead of hours.

But of course I understand that the point was really to find an application as an excuse to practice working with optimisation algorithms. In that sense, it is a well done job !

Now for how "normal" humans would do it: they would try a few ways and settle on an approximate optimun depending on how much time each pass took and how easy it was to complete. The thing about those sort of task is that they are not really uniform (some places are bound to be dirtier than others and it is easier to approach some features in a certain way), so a naive optimisation like that is unlikely to be what's truly needed even if the solution is technically perfect.

- And you didn't try to escape?

- I couldn't, the hallway has only two doors; the attacker come trough the front door, in the back... I just finished sweeping

So, good for the author that they spent the time to learn path optimization. Now onto 3D bin packing!

One option one could use is eg. https://fields2cover.github.io/ but that doesn't work too well if there's lots of obstacles in the fields like in this case. I'm having the same issue at work right now in agricutrural robots, covering the area between rows and rows of trees. Some implements on our robot hang off to one side so paths can't be bidirectional, etc. Lots of interesting constraints.

Reminded me of a pattern I keep seeing in business software - teams spend months optimizing the wrong abstraction. They'll build an incredibly efficient data pipeline that turns out to process information nobody actually needs, or an algorithm that minimizes compute time when the real bottleneck is waiting for a human approval that takes 3 days.

The simulated annealing approach wasn't wrong per se - it's just that "minimise distance walked" was never actually the objective function that mattered to the humans doing the walking.

1. Why a grid system, and what justifies the grid size? As a person who works on algorithmic optimizations since decades (god, I am old), I would have chosen a different approach: Since we know that the shortest distance between to points is the straight line, I would only consider points at a junction for a path decision. Basically this could be seen as either a one-way road system (start to end of an aisle) or a two-way road system, with ony one lane per direction. With this system your graph is much smaller and can be traversersed more easily.

2. I wouldn't have chosen Simulated Annealing for this job. It guarantees you to find a solution in a short period of time, but the chance that you get stuck in local minima is very high in contrast to finding the global minimum (which you couldn't even proove you found). Path finding is well documentated and there are heuristics (if you need them) to solve that problem reasonably without using such a complicated algorihtm. I would have probably build a Dijkstra Matrix between all points (from above) then you know all distances going from A to C via B, for example.

3. I think the problem is a bit similar to the Traveling Saleman Problem (which has been solved optimally in a mathematical way now, AFAIK), however, one needs to make sure that each path is traversed at least once. (We don't want to skip an aisle).

I often have the feeling that people are trying to solve problems by just throwing data aimlessly on (AI) algorithms which is compuational expensive without realising that the data needs to be filtered and maybe converted (i.e. feature extraction). Furthermore the right algorithms need to be used to solve a job (e.g: Do you need a quick solution that's not optimal? and so on.). Having said that, of course, any simulation (optimization) is just a positive, simplified view of the real world. To stay with the author's example, there might be some aisles where sweeiping needs to be done more often then on other aisles depending on the groceries on the shelves etc.

Isn't this just trying to find a hamiltonian cycle, isn't this NP hard? That's when I would give up, especially because you put so many constraints in it to make it human walkable.

Edit: Of course you don't have to give up, but it's good to know what you get yourself into

My Roomba will take less time when it dead reckons as opposed to avoiding visiting tiles twice. I guess energy and time are still spent poorly by humans and Roomba for following the optimal plan.

See also https://sohl-dickstein.github.io/2022/11/06/strong-Goodhart....

Optimize for human satisfaction: NP-hardest

Put on headphones with music or a podcast or even youtube, and take 1-2 or even 4 hours more than you would normally do. Have an accident every few days.

Oh, and here's another problem with the best solution. Managers are idiots. They actually have zero clue what's a good time/performance for floor sweeping since they'd never stoop to the level of doing it themselves, even once. If you're going close to best possible, any slight disturbance will make a large difference in your performance, since that's what the manager actually measures. If you're doing a piss-poor job but by changing your speed a bit when something inevitably goes wrong, and you do about the same quality in about the same time every time, your manager will be more happy. Hell, it'll make it easier for him to organize the store so it may actually be better economically too.

The better you optimize this, the worse you're off. Hell, given that many consider you're better off on unemployment you should do worse than the worst the manager accepts (since you get unemployment if the manager fires you but not if you quit). Then you get a bit less money, but you have no costs (you have to pay for food, and public transport, every day, but only if working. Unemployed you can stay at home and cook)

So ... does this optimization tool have a way to accomplish the actual best outcome?

If you have non zero inertia, then refusing to model inertia isn't technically correct or optimal.

The turn penalty is a way to avoid having an explicit dynamics model, which is a nice hack that will probably return pretty good results.

There is also a missing reference to liquidity preference. People don't make expensive and costly plans, because they represent a commitment and obligation to follow the plan through. Unlike what economists say, people don't actually make lifelong commitments at birth and then just follow them. They usually make decisions on the spot with the information they learned during the course of their life.

"The important part is figuring out what you should be optimizing for in the first place.

Most of the time, we don’t even ask that question. We just optimize for whatever’s easy to measure and hope it works out.

Spoiler: it probably doesn’t."