> Writing the simulation in Python was probably a bad idea in retrospect: it turns out to be incredibly slow to run Dijkstra’s shortest path algorithm on a large grid.
Dijkstra's algorithm is the completely wrong approach for this problem. First of all, the cost to enter any grid square is the same, so Dijkstra's priority queue is needless overhead. When all edges have the same weight Dijkstra's behaves identically to breadth-first search.
BFS is obviously a poor approach for a mostly open grid like you have here. It will explore every single open vertex whose distance is less than the distance to the goal. Imagine the person standing in the center of a circular room with the food at the edge. With DFS, the pathfinder will look at every single vertex in that room.
What you want is A-star, which is no harder to implement than Dijkstra's. Even better would be something like jump-point search that handles open spaces better. But just A-star alone will yield a massive improvement for problems like this.
1. Diagonal moves have a slightly higher weight.
2. I have an edge weight of 100 to go through another person. This makes it possible to go _towards_ the right direction even though there is no path
3. For the perpendicular lines method, the distance is modified to 1e-3
4. A* doesn't work because the heuristic becomes pretty useless when you have moves that are very "cheap": you need a lower bound that's pretty much zero
So for all those reasons, I just went with plain old Dijkstra!
> A* doesn't work because the heuristic becomes pretty useless when you have moves that are very "cheap"
I don't see where you have cheap moves. If your move costs are unit for straight lines, slightly longer for diagonal (i.e. probably close to sqrt(2)), and much longer for obstacle, then A* will work fine. The lower bound is just the usual Cartesian or Manhattan (depending on your diagonal cost) distance.
Really what you want is a flow field, since this is mainly a problem of many actors with a few shared goals: pathfinding can be computed once every turn and reused by everyone
you're recomputing it every turn, so you can treat actors as obstacles; simply make tiles that are taken non-traversable (same as you'd make a boundary wall). When moving each actor, by flowing downwards, if they collide then undo the move and select the next best downward tile. In the case he's surrounded at the start of the turn, the flowfield will simply not allow him to move (he'll be surrounded by obstacles). If he's surrounded by newly moved actors, he'll bump into people in all directions, and not move.
Assuming the crowd keeps moving, the problem will naturally resolve itself eventually (and the results are the same as if you'd done direct pathfinding -- a traffic jam is a traffic jam).
There's also the possibility an actor gets stuck holding the door: He's the last to move, so by the time he takes his turn, he's surrounded again; The gamey solution would be to cheat and let him phase through or temporarily merge with an actor.. alternatively increase his iteration priority if he doesn't get to move, so he gets the first move next turn.
But in the case of this simulation, such extreme crowding is an unnecessary edge-case to care about, since the goal really is to simulate to the point when crowding just starts to occur, so just "bump and undo" collision logic is probably more than sufficient.
If you want to go way too far, you end up with potential fields like [0] or [1] but I don't think a buffet line really necessitates that level of intelligent behavior
Alas, this post suffers from mathematician syndrome ("first, assume cows are spherical..."). Actual buffet queues can't be modeled like this; because of the physical constraints, they should be modeled as particle flows and hence take into account that one person cannot occupy the same space as another, and the overhead of routing, blocking etc.
While I agree that the 'default' buffet queue is inefficient, I don't agree with the proposed methodology of finding an improvement.
(also, I missed a literature study - there is so so so much research on this already)
I do not think this is a fair criticism. The author is building a model which accurately captures a certain dynamic. Of course it isn't perfect, but it does get us to several proposed solutions.
Also, I think it is really unhelpful to quickly dismiss his analysis because you don't agree with his methods instead of showing why his proposed solutions fail when you add more realistic constraints to the simulation.
> hence take into account that one person cannot occupy the same space as another, and the overhead of routing, blocking
I'm not sure what you mean by this beyond what the author already implemented—people occupy space that can't overlap, several of the simulations break down because of blocking, and many of the simulations even display the routing paths that the agents are planning.
What I meant was that agent behaviour is linear and predictable, assumptions that don't hold when modeling actual people in the wild (it's fine for modeling e.g. factory queues and stuff, not knocking on queue theory as a field). Reasonable people can disagree on the assumptions made here though.
I read a study done some time after the deaths at a Pearl Jam concert in Roskilde, Denmark. If I recall correctly (I can't seem to find the paper now) they posited that crowds could be simulated by way of particles in a fluid dynamics system, and that a common property of concert accidents such as Roskilde was the lack of pressure release "valves" for lack of a better word. If you only have one exit from the mosh pit, then pressure will mount at that choke point, possibly causing further accidents, and making it harder for emergency services to reach the injured parties. With multiple exits acting as release valves this problem is alleviated, and they used simulations of particles to prove this. Or something like that.
Point is, your comment on particle flows dug this reference up from somewhere deep in the back of my mind. It was a really interesting study, I'll try to find a link.
Yes there is lots of research on this, years ago I was in a project with a group (CASA) at UCL (Leeds) where this is one of their main topics of study - https://www.ucl.ac.uk/bartlett/casa/ . If you google e.g. 'agent based simulation pedestrian' you'll find 100's of papers doing this at various scales, as well as dedicated software packages to simulate for studies of shopping mall layout, sports stadium layout etc.
Years ago I entertained starting a business in this field - it was essentially exactly what you say, doing analysis for events as part of their risk assessment to see if event locations are safe under various patterns of (aggregate) visitor movement. At the time (15ish years ago?) that wasn't really done for anything but the largest events. The idea never really went anywhere but it's an interesting topic I still think about every now and then.
> they posited that crowds could be simulated by way of particles in a fluid dynamics system
I sometimes have the same thought when traversing a particularly packed mall. Crowds appear to me to be a non-Newtonian fluid, because internal friction increases rapidly under pressure.
I think the problem is the other way around; it could be simplified further.
You don't need that much detail to model the simulation; really all you care about is that you have some distribution of arrival rates, and a distribution of processing time (to get a particular food), and some distribution of food preference, and it takes some x seconds to move to then next food. Perhaps with a food ordering as well.
The simulation could have been purely numerical with that (no need for pathing algorithms and whatnot, and avoid his day-long computations for such a simple simulation..), and the main variables to play with are:
1. Food preference
2. Food order
3. Number of instances of food stations
4. Processing time per food
But the author included pathing, and all his alternative-strategies then revolved around pathing, but really any path that isn't a simple line (or parallel lines) is probably non-viable, as they would quickly become a mess of people operating at random when they fail to understand whatever convoluted ruleset has been created unless its heavily enforced by the administration .
More likely than not, the best solutions probably would have been those that reduce processing time for high-preference food (a designated server), and increasing the number of food stations for those high-preference foods (eg split off deserts from the main food line to a new table, and add 4 locations to pick it up on that table)
It'd also address your concerns
>hence take into account that one person cannot occupy the same space as another
Modeled by the fact that its a queue, and there's only one person being processed at at time at any given station
>overhead of routing, blocking
Routing only really comes in two forms: Time to move from current station to the next one
1. and enter the queue
2. and skip the queue, and start moving to the next station
Blocking probably doesn't matter much; it's doubtful people will actually block each other off beyond the normal block of being processed, except when the buffet has overloaded and all the starving people swarm the tables, and all hell breaks loose; whatever physical blocking does occur will most likely have negligible impact on the system and if necessary, can be easily modeled in the time to switch stations
This would be my approach order and time/space/multiples of the busy stations. It’s crazy how often I see them load up the first station with things that aren’t necessary at that point but will fill up your hands and slow down the process for everyone that is putting food on their plates. Napkins and cutlery and prime examples. They should be at the end once your plate is loaded you can pick these up and move along.
I don’t think I agree with that. If we imagine people can pass through each other but must still obey the rules of the queue (one person at an item at a time) the overall wait time is not going to change much. When you think back to your buffets, I hope it’s not the physical difficult of maneuvering around people stalled at an item you don’t want that takes up the most time.
Queuing theory is very appropriate for this. It’s a queue.
But people don't obey the rules of abstract queues at buffets. People circle around, bump into each other so that both change directions, squeeze themselves between others, and so on. To model this, you need to (IMO) model them as a system of interacting particles with properties that vary as the 'pressure' in the system increases (e.g. the 'diameter' of the particle increases by people holding in their arms, their speed varies as people slow down when it gets more crowded, etc.
Buffets are not like bank teller queues. Or maybe I should just visit different restaurants.
However, they're not significantly less-ordered than bank teller queues; They're hardly a "crowd" of independent actors following no rules beyond physics + goal that would necessitate treatment as a particle simulation.
You're right if you wanted a really in-depth and granular model, but it's doubtful you'll find significantly improved insights versus treating it as a simple queue, and ignoring the fact that people are a little dynamic.
As far as I've seen, most buffets constitute a line with a little bit of people skipping around. But it's very close to well-ordered.
I recently visited the Schönbrunn Palace in Vienna. My ticket had an entry time printed on it. I arrived at the entrance a few minutes before that time.
There was a long line. I asked a few people to see their tickets. All of them had entry times after mine. When my time was on the display, I asked the person in the front of the queue to see his ticket. He still had a few minutes to go. So I pointed at the time on my ticket and entered before him. He felt cheated, but as we together wondered through the museum, he agreed with my logic.
My point is that online booking systems can make many lines obsolete.
This article though touches on a more difficult problem, namely congestion.
Disney parks do this with their fast-pass technique: show up early to a ride, get a ticket for a later time and vastly reduced wait time. This allows patrons to have more manageable waiting times, but also allows the park to make more money since people will buy things as they wait instead of just waiting in a line.
IIRC park passes with this ability cost more, so Disney has already selected for people with expendable income.
Back in college, I remember waiting in a buffet line and there were, what I gathered to be, two of the cafeteria managers in front of me.
They were chatting about the efficiency of buffet lines and one of them mentioned "It's well known that a buffet line with a server is 30% faster than a line with no server."
Made total sense at the time because in a self service line, people have to:
- stop
- pick up the utensil
- some people then take a while deciding which piece of food is the best
- grab the food
- put the utensil down and move on etc
With a food server, it goes so much quicker if only because the server isn't waiting around to pick the best piece for you.
I wonder if there's some psychological factor of a person standing there waiting to put food on your plate, making you more conscious about how much time you're taking to make a decision
If your workplace ever has a big pizza lunch, take a few boxes and just walk somewhere else to open them. Turn an O(n) problem into O(1) with just a few people helping.
When all pizzas are the same (or maybe of two types), that works. When there are 10+ different types of pizzas ordered, this algorithm turns it into a likely worse search problem.
...so if there are x tables, each with y different pizzas, unknown to you at the start, and you have a mental algorithm that assigns each pizzas a score between 0 and 1, how many tables do you need to visit before you are confident you are selecting a pizza that is in the 90th percentile of available pizzas, if we assume you're not allowed to return to a table after dismissing it..?
It doesn't matter because the pepperoni is already gone and all that is left is the three vegan pizzas for the two one hundred pound members of the team.
This is like the microwave problem at work though.
My food only needs 30 seconds to microwave, but Slow Joe brought thanksgiving to work and needs to use the microwave for 4 minutes. We have 2 microwaves M1-2.
With your system this is what happens:
- Slow Joe blocks M1 with a 4 minute meal
- Several 30-60 second users cycle through M2
- Another Slow Joe blocks M2
- The queue grows until M1 is free
- The feedback loop gets worse the next iteration
Basically, you need a dedicated "express lane" for quick people to use. If there are no quick people in the queue, then a slow joe can use it. Otherwise you need to increase N such that there is always at least one unblocked lane, which might not be viable.
Indeed the main problem, counter to queuing theory, is that the individuals are not pushed anymore from behind, hence they take their time, slowly without feeling any pressure.
I've seen the same in traffic simulations.
If none of the routes are optimized for tons of traffic, 1 slow driver can gridlock an entire city at rush hour.
I did a similar analysis with a nearly-identical model but without the assumption of a constant stream of people coming from the left. In my analysis, the best model depends heavily on the assumptions: http://blog.maxshinnpotential.com/2019/03/02/are-buffets-eff...
I think there are two additional drawbacks of the "classical" method that the simulation does not cover.
1. Ordering of the food does not matter in the classical method (you always have a bottleneck at the most popular option), whereas in practice some buffet options will be more popular than others, and spreading them out will help in the rogue and don't go backwards models.
2. In the classical model you have to wait for each food, so you might as well take everything (or at least more options), in the other options there is a market-based mechanism to discourage people to get the more popular option (because they would have to spend more time queueing), that could help spread people more evenly across the buffet.
There are some obvious problems. While we can argue about whether Dijkstra is efficient, the real problem is it's unnecessary. The queue can, and should, be fully defined, not dynamic. There is no reason to let each individual actor search for the best location to go. If we are looking for an optimal solution, then there is no need for individual decision making.
Consider: Imagine every parallel queue, but with a "gap" every 3 people to allow others to pass by. In real life, humans wouldn't walk all the way around the queue, they'd find someone who would step momentarily aside to let them pass. Representing this by forcing the individual queues to not be fully solid would allow that behavior to be represented.
Anyway, this work doesn't even get to some of the more interesting aspects of buffet design, like handling multiple tables, popular items, correlated items, etc.
The best large-scale buffet option I've seen is how they do it at AWS re:Invent (at least last time I was there a few years ago). They have a large number of identical buffet stations, with catering employees directing attendees on which line to join. As soon as one buffet line is full (maximum length is still pretty short), they start directing new arrivals to the next line, and so on. It's not perfect, but it's quite an impressive operation and I have never had a significant wait for food there (though sometimes it's a bit of a walk because the dining hall is MASSIVE and you might end up getting sent to a buffet line at the far end).
Single queue, multiple server seems to work well in theory and in practice.
I'm often disappointed at computing or networking conferences or meetings of some sort where the buffet is strictly serialized with head-of-line blocking, resulting in massive, slow queues that waste most of the lunch break time.
I eat at buffets probably more than I should, and in my experience, the biggest slowdown are people that walk up to an item, stare at it for a minute, then decide to grab the utensil and serve themselves, put the utensil down, then stand there for another minute contemplating what they just did before getting the hell out of the way.
It's especially bad on large cruise ships where the average age of the clientele is probably 90 years old.
Of course there is the wonderful hygiene of the buffet, the sneezing, the coughing, the tasting off the serving spoon, dropping the serving spoon on the floor and putting it back into the food. Let's not forget all the wasted food, and the encouraged gluttony.
Dijkstra's algorithm is the completely wrong approach for this problem. First of all, the cost to enter any grid square is the same, so Dijkstra's priority queue is needless overhead. When all edges have the same weight Dijkstra's behaves identically to breadth-first search.
BFS is obviously a poor approach for a mostly open grid like you have here. It will explore every single open vertex whose distance is less than the distance to the goal. Imagine the person standing in the center of a circular room with the food at the edge. With DFS, the pathfinder will look at every single vertex in that room.
What you want is A-star, which is no harder to implement than Dijkstra's. Even better would be something like jump-point search that handles open spaces better. But just A-star alone will yield a massive improvement for problems like this.