>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.
You can take it one step further: imagine you live in a smallish country (10 million people).
If your market share is 10% of the population and they make 1 request per day, that is just 10 requests per second.
10% is a large market share for everyday use. So you can use 1% market share and 10 requests and it will still be just 10 reqs/sec.
In fact, 1% market share of 10 million people and you can use the number of requests each user makes as the number of requests that your server will get (on average) per second.
There is a lot of business in small countries that never need to scale (or business in narrow sectors, e.g. a lot of B2B).
If an application gets 4 thousand req/s for an hour, and an additional 10% requests in the rest of the day, it is handling nearly 15 million reqs/day, which is completely different and of course requires scaling in most cases.
That said, even then, there are a lot of business cases where you are not constrained by the time required to sort or traverse a custom data structure, because you spend more time waiting for an answer from a database (in which case you may want to tune the db or add a cache),or the time needed to talk to a server or another user, or a third party library, or a payment processing endpoint.
There are also use cases (think offline mobile apps) where the number of concurrent requests is basically 1, because each offline app serves a single user, so as long as you can process stuff before a user notices the app is sluggish (hundreds of milliseconds at least) you're good.
What do you do with those 4 thousand req/s? That's what makes the difference between "processing everything independently is fast enough for our purposes", "we need to optimize database or network latency", or "we need to optimize our data structures".
>And having some hashmap added at one point because I know how stuff works properly doesn't cost me anything.
Sure if it costs nothing, go for it.
With that said,
1) time complexity is just one kind of complexity. In real life, you may be interested in space complexity, too. Hashmaps tend to use more "space" than regular arrays, which might be an issue in some cases. Also, some data have a lot of collisions when managed using hashmaps, which may not be ideal.
A well thought design with respect to performance and scalability relies on a few assumptions like these, which could lead to one solution or another.
2) a real-world application is not necessarily constrained (in space or time) by traversing an array or a hashmap. Unless your application is mostly processing, sorting,... data structures, this is probably not the case.
For example, consider a simple application which lets users click and reserve a seat at a theater/conference/stadium/train/whatever.
The application is essentially a button which triggers a database write and returns a 'Success' message (or maybe a PDF). In this case, you are mostly constrained by the time needed to write on that database and maybe the time needed for a PDF generation library to do its things. You are in fact interacting with two "APIs" (not necessarily Web, REST APIs!): the database API and the third-party PDF library API. I don't have any special knowledge about PDF libraries, but I suspect their performance depends on the amount of data you have to convert to PDF, which is more or less the same for every user. And when it comes to databases your performance is mostly limited by the database size and the number of concurrent requests.
If you think this is too simple, consider additional features like authentication, sending an email notification, or maybe choosing between different seat categories. In most cases, your code is doing very little processing on its own and it's mostly asking stuff to other libraries/endpoints and getting an answer.
Consider another example. You want to find out the distance between a user (which is assumed to have a GPS receiver) and a known place like Times Square or whatever. What you have is a mobile app which gets the GPS position from the phone and computes the distance between the user and the known coordinates, using a known formula. The input size is always the same (the size of the data structure holding GPS coordinates), the formula to compute the distance is always the same, so processing time is essentially constant.
Now let's say you have a bunch of well known places, let's say N. The app computes the distance for all N places, effectively populating an array or an array of dicts of whatever, with length N. Maybe the app also sorts the data structure to find the 5 closest places. How long will that take? How many places you need to compute and sort before a user notices the app is kinda slow (i.e. before, say, 200 milliseconds) or exceedingly slow (let's say above 1 second, or even 500 ms)?
There are a lot of scenarios and real-world applications where, using modern hardware and/or external APIs and reasonable expectations about clients (users don't care about microseconds, sending an email or push notification in one second is totally acceptable in most cases,...), you are not constrained by the data structure you are using unless you're working at a large scale.
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.
For an employee the cost function is maximum wage for minimum work. Since at minimum wage, you're paid for your time, this means sweeping as badly and slowly as the minimum the manager accepts.
Hell, given that there is a social safety net, and you'll have costs to do the job (food, public transport, ...) you're probably even better off doing worse than that, and getting fired when the manager is "tired of your shit" or whatever.
Then you'll get unemployment, which is slightly less, but you can invest the time in cooking at home, and you'll eat better and have more money left over.
It's a very cynical view but I kind of agree. In those kinds of jobs, the only rewards for doing the job well and fast is just more mindless jobs of the same type.
It would be usefull if you would receive a benefit for doing the job better or you could leave earlier for the same pay but that is rarely the case, since as you said, employers generally pay for your time instead of task completion (which is rather dumb because it offers bad incentives for both sides).
I have talked about this with some business owners who were getting kinda angree that some employes were not putting in a lot of efforts. In all case they were paying the minimum wage with absolutly zero compensation for doing the job better and/or faster.
I can't decide if they are just stupid or simply corrupt but they really should realise that with a strong welfare state and plenty of similar shitty jobs available, the stick really cannot work all that well and they should really use the carrot a lot more.
But of course those people generally make at least 3-4 times the minimum wage and they feel they deserve the premium because they deserve it and are so much better. Funnily enough, those that I know consistenly do a worse job than their employees at most things and it's obvious they didn't get there by starting at the bottom.
That is exactly right as anybody who has done the work in a wrong way recognizes.
In a way, the computer science student may or may not have realized that he has stumbled upon one of the biggest problems in software development--the arrogance of ignorance.
Especially with lawn mowers, turns are highly weighted over distance. Also, if you are regularly mowing, then it's not so obvious what has been mowed and what not. So regularization and simplification of the path is even more important than turns so that you can discard whole plots in the to-do list.
Roomba's (RIP) don't have the same memory and turn weight function that humans do, of course.
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.
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!
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.
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.
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 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.
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.
Edit: Of course you don't have to give up, but it's good to know what you get yourself into
Why would you give up just because something is NP hard if there are good algorithms to approximate a solution, and an approximate but good solution is useful?
Yeah, there are many problems which are np-hard in theory, but then realistic cases give you way more constraints that make them solvable. So many hard graph problems become way simpler when applied to real maps, because you know that if you start getting away from something, your minimum remaining distance grows. But on an abstract graph there's no real mapping to our dimensions.
There's no "information you wanted" in the plain np-hard version of traveling salesman for example. There's only cost. My point was that things get easier if you have the extra information and aren't solving the plain version anymore.
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.
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?
I think you are minmaxing to a cynical degree. Some people just want to do a good job, because somewhere down the line it probably will benefit them to know how to do it.
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.
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.
You're making assumptions on what the OP should optimize for. You're probably equating “better job” with “higher pay”. For all you know they could be optimizing for happiness and happen to be someone who totally enjoys floor cleaning.
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.
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.
>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.
Yep.
You can take it one step further: imagine you live in a smallish country (10 million people).
If your market share is 10% of the population and they make 1 request per day, that is just 10 requests per second.
10% is a large market share for everyday use. So you can use 1% market share and 10 requests and it will still be just 10 reqs/sec.
In fact, 1% market share of 10 million people and you can use the number of requests each user makes as the number of requests that your server will get (on average) per second.
There is a lot of business in small countries that never need to scale (or business in narrow sectors, e.g. a lot of B2B).
Exactly. In those cases, getting 100 reqs/sec or 1000 reqs/s probably means you're getting DOS'd. Any rate limiter is enough.
Or you could still use multiple instances, not for scaling but for patching without downtime and so on.
Availability can be way more important than sheer performance or number of concurrent requests.
Of course, they make 90% of requests between 6 and 7 PM, with a general peak of 4 thousand req/s.
If an application gets 4 thousand req/s for an hour, and an additional 10% requests in the rest of the day, it is handling nearly 15 million reqs/day, which is completely different and of course requires scaling in most cases.
That said, even then, there are a lot of business cases where you are not constrained by the time required to sort or traverse a custom data structure, because you spend more time waiting for an answer from a database (in which case you may want to tune the db or add a cache),or the time needed to talk to a server or another user, or a third party library, or a payment processing endpoint.
There are also use cases (think offline mobile apps) where the number of concurrent requests is basically 1, because each offline app serves a single user, so as long as you can process stuff before a user notices the app is sluggish (hundreds of milliseconds at least) you're good.
What do you do with those 4 thousand req/s? That's what makes the difference between "processing everything independently is fast enough for our purposes", "we need to optimize database or network latency", or "we need to optimize our data structures".
I don't need to optimize if my design is well though of from the getgo and it happens when Im good at it.
I would just never write code which struggles with n.
And having some hashmap added at one point because I know how stuff works properly doesn't cost me anything.
>And having some hashmap added at one point because I know how stuff works properly doesn't cost me anything.
Sure if it costs nothing, go for it.
With that said,
1) time complexity is just one kind of complexity. In real life, you may be interested in space complexity, too. Hashmaps tend to use more "space" than regular arrays, which might be an issue in some cases. Also, some data have a lot of collisions when managed using hashmaps, which may not be ideal.
A well thought design with respect to performance and scalability relies on a few assumptions like these, which could lead to one solution or another.
2) a real-world application is not necessarily constrained (in space or time) by traversing an array or a hashmap. Unless your application is mostly processing, sorting,... data structures, this is probably not the case.
For example, consider a simple application which lets users click and reserve a seat at a theater/conference/stadium/train/whatever.
The application is essentially a button which triggers a database write and returns a 'Success' message (or maybe a PDF). In this case, you are mostly constrained by the time needed to write on that database and maybe the time needed for a PDF generation library to do its things. You are in fact interacting with two "APIs" (not necessarily Web, REST APIs!): the database API and the third-party PDF library API. I don't have any special knowledge about PDF libraries, but I suspect their performance depends on the amount of data you have to convert to PDF, which is more or less the same for every user. And when it comes to databases your performance is mostly limited by the database size and the number of concurrent requests.
If you think this is too simple, consider additional features like authentication, sending an email notification, or maybe choosing between different seat categories. In most cases, your code is doing very little processing on its own and it's mostly asking stuff to other libraries/endpoints and getting an answer.
Consider another example. You want to find out the distance between a user (which is assumed to have a GPS receiver) and a known place like Times Square or whatever. What you have is a mobile app which gets the GPS position from the phone and computes the distance between the user and the known coordinates, using a known formula. The input size is always the same (the size of the data structure holding GPS coordinates), the formula to compute the distance is always the same, so processing time is essentially constant.
Now let's say you have a bunch of well known places, let's say N. The app computes the distance for all N places, effectively populating an array or an array of dicts of whatever, with length N. Maybe the app also sorts the data structure to find the 5 closest places. How long will that take? How many places you need to compute and sort before a user notices the app is kinda slow (i.e. before, say, 200 milliseconds) or exceedingly slow (let's say above 1 second, or even 500 ms)?
There are a lot of scenarios and real-world applications where, using modern hardware and/or external APIs and reasonable expectations about clients (users don't care about microseconds, sending an email or push notification in one second is totally acceptable in most cases,...), you are not constrained by the data structure you are using unless you're working at a large scale.
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.
Yeah. Human preference are like snowflakes. One mans "clean-enough" is another man's OCD driven nightmare.
For an employee the cost function is maximum wage for minimum work. Since at minimum wage, you're paid for your time, this means sweeping as badly and slowly as the minimum the manager accepts.
Hell, given that there is a social safety net, and you'll have costs to do the job (food, public transport, ...) you're probably even better off doing worse than that, and getting fired when the manager is "tired of your shit" or whatever.
Then you'll get unemployment, which is slightly less, but you can invest the time in cooking at home, and you'll eat better and have more money left over.
It's a very cynical view but I kind of agree. In those kinds of jobs, the only rewards for doing the job well and fast is just more mindless jobs of the same type. It would be usefull if you would receive a benefit for doing the job better or you could leave earlier for the same pay but that is rarely the case, since as you said, employers generally pay for your time instead of task completion (which is rather dumb because it offers bad incentives for both sides).
I have talked about this with some business owners who were getting kinda angree that some employes were not putting in a lot of efforts. In all case they were paying the minimum wage with absolutly zero compensation for doing the job better and/or faster.
I can't decide if they are just stupid or simply corrupt but they really should realise that with a strong welfare state and plenty of similar shitty jobs available, the stick really cannot work all that well and they should really use the carrot a lot more. But of course those people generally make at least 3-4 times the minimum wage and they feel they deserve the premium because they deserve it and are so much better. Funnily enough, those that I know consistenly do a worse job than their employees at most things and it's obvious they didn't get there by starting at the bottom.
That is exactly right as anybody who has done the work in a wrong way recognizes.
In a way, the computer science student may or may not have realized that he has stumbled upon one of the biggest problems in software development--the arrogance of ignorance.
Especially with lawn mowers, turns are highly weighted over distance. Also, if you are regularly mowing, then it's not so obvious what has been mowed and what not. So regularization and simplification of the path is even more important than turns so that you can discard whole plots in the to-do list.
Roomba's (RIP) don't have the same memory and turn weight function that humans do, of course.
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.
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
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.
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.
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 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.
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.
Edit: Of course you don't have to give up, but it's good to know what you get yourself into
Why would you give up just because something is NP hard if there are good algorithms to approximate a solution, and an approximate but good solution is useful?
Yeah, there are many problems which are np-hard in theory, but then realistic cases give you way more constraints that make them solvable. So many hard graph problems become way simpler when applied to real maps, because you know that if you start getting away from something, your minimum remaining distance grows. But on an abstract graph there's no real mapping to our dimensions.
That just means you didn’t encode the information you wanted into the graph.
There's no "information you wanted" in the plain np-hard version of traveling salesman for example. There's only cost. My point was that things get easier if you have the extra information and aren't solving the plain version anymore.
For constant n even exponential complexity reduces to constant time
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.
Duplicate, comments hither? https://news.ycombinator.com/item?id=46536753
Overoptimization is the root of all evil.
See also https://sohl-dickstein.github.io/2022/11/06/strong-Goodhart....
The obvious solution is to ask the persons who cleaned the floor before you for advice.
Optimize for sweeping efficiently: NP-hard
Optimize for human satisfaction: NP-hardest
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?
I think you are minmaxing to a cynical degree. Some people just want to do a good job, because somewhere down the line it probably will benefit them to know how to do it.
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.
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.
You're making assumptions on what the OP should optimize for. You're probably equating “better job” with “higher pay”. For all you know they could be optimizing for happiness and happen to be someone who totally enjoys floor cleaning.
Based on the post I was under the impression they’re a current CS student. So this is probably a part time job whilst studying
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."
Clickbait title.
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.