I Got Paid Minimum Wage to Solve an Impossible Problem

Step 1 in this situatoon is to try and see if this is a known mathematically unsolved problem, and if it is, giving up.

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.

The problem isn't so much finding the shortest path, but finding the right cost function that adequately matches human satisfaction. Not just distance, not just turns, but also knowing which areas are done, and other small factors.

Did you ever get a programming job? I'm just curious since this write up is pretty good, and I'm hoping someone that could do it would eventually get better job than sweeping.

>But building this taught me something that I think about constantly: technical correctness is worthless if you’re solving the wrong problem.

>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.

This article even discounts that at minimum wage jobs, you're paid for your time, not the job you do. So this is doing the reverse of what's reasonable. You're better off sweeping the floor slower, because if you finish faster, there is no way any manager will let you go home, job well done. You'll get more work.

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?

Duplicate, comments hither? https://news.ycombinator.com/item?id=46536753

Clickbait title.

The observation is half right. Optimizing the wrong function definitely causes misery. What this misses is that there is no right function. Certainly not when there is more than one person involved (no two people will have the same preference vector.) But even individuals have conflicts among their own objectives. This is true even if you reduce your view of humanity to the homo economicus who seeks to maximize profit and sees all value in dollars. This is a controversial take, but I don’t think you can even measure dollars against dollars. I disagree with the notion that one can balance near future and far future money with an appropriate discounting formula. They’re incommensurable: you’re making assumptions about what you will value in the future based on what you know in the present. If you’ve ever encountered the ennui of an early retiree, you will know how hard it is to judge these things. Philosophy has much better frameworks for addressing these questions than economics.

Actually even when a Roomba(RIP) turns to follow the optimal plan like that, the time taken to pivot 90 to manage planb is pretty large.

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.

In court the cleaning lady gives testimony about the attack:

- 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

Loving this prime example of why I say we need to identify the genuine systems-theoretic needs of humans and our natural environments. And mathematically/experimentally define & verify them. Optimizing for anything outside of what's literally needed seems to be fundamental to oppression, intended or not.

"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."

The point about grid size assumptions is interesting. I studied physics and one of the first things you learn is that your choice of coordinate system can make a problem trivially easy or impossibly hard. Same underlying reality, wildly different solution paths.

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.

I don't get it. This entire article seems to be talking around the actual issue. You need to have a dynamics model inside your trajectory planner.

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.

What is funny to me is that once the plan was drawn, much of the usefull "hard" work was done. Humans are not perfect like robot so it is pointless to try to find the "perfect" path, in any case, mistakes will be made. It is also solving for the wrong thing, there is not much benefits travelling less distance, but minimising time spent on the task is the real problem. For those sort of tasks, it is very much like driving: the shortest path is not necesserally the fastest. Another very important point is that ease of application is of prime importance, it's not very usefull if you need to think hard about which way you should go just to minimize distance, it increase task complexity tremendously for no real benefit.

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.

I enjoyed reading this article and I enjoyed the conclusion the author draws from his experiment very much, but I think some assumption he made at the early stages could a have been improved or are not explained very well:

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.

Why would you optimize for a tile and grid pattern when the real world uses sweeping curves?? Just look at how underfloor heating layouts are created and then think about that for a minute.

The best part about these sorts of problems is learning about heuristics. I spent years as a self-taught developer without using heuristics, and once I got the opportunity to use them, it made so many things make more sense, like why do Mathematicians and Physicists take shortcuts instead of doing all the work to do the problem correctly? Because you reduce time by limiting complexity! Big O notation never resonated with me, but I can look at loops, recursion, and just think about problems and say “That will take too long.” With heuristics, you eliminate that. It was eye-opening.

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

This problem is called Coverage Path Planning.

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.

Optimize for sweeping efficiently: NP-hard

Optimize for human satisfaction: NP-hardest

Overoptimization is the root of all evil.

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

That floor plan is typical Albert Heijn. I remember from my time living in The Hague. Grocery stores in most other countries are usually a lot less complex.

The obvious solution is to ask the persons who cleaned the floor before you for advice.