Level 2: Traffic lights, graphics (2D arrays)
Level 3: Flight control, simulations (3D arrays)
Level 4: Satellite tracking, virtual worlds (4D arrays)
...
So many problems can be cast to arrays to be solved with various linear algebra.
Considering LLMs are "Level 1000+" puzzles in this analogy, I wonder if every problem could be represented by an n-dimensional vector and solvable with algebra.
They at least make great interview questions - Tic-Tac-Toe is commonly given, but is obvious. The board already "looks" like arrays. The less obvious ones, like elevators (or load balancing), are always interesting.
An example iirc was waiting for luggage at the airport. It takes min of x minutes for the first bags to show. In one version, passengers went directly from the gate to the luggage carousel and waited x mins for the first bag → unhappy. Then the airport decided to add a long, round-about "walk" path from the gate to the luggage area that burned some of those minutes → same total "wait" but happier passengers.
Sounds like destination dispatch would work better if it didn't tell you which elevator to get into until the elevator arrived.
EDIT: already being discussed in the thread at https://news.ycombinator.com/item?id=49125423
Using such a primitive elevator gave me a newfound appreciation for the complexity of modern designs. The queueing algorithms are subtle but clever, and the difference in efficiency is instantly obvious once you've dealt with the alternative.
Even at that relatively reduced level of complexity, it's quite tricky to figure out how to prioritize who gets served when.
I want something similar for advanced sensor stop lights...
I've long toyed with creating an elevator simulator game, but every time I build a prototype I realize it's not that fun to manually dispatch elevators, and playing with algos only goes so far! Elevator Saga is great for the programming side: https://play.elevatorsaga.com/
For example, some elevators allow adjusting the door closing/opening speeds etc., I'd be curious what other things can be adjusted.
A cool connection is that a spinning-disk hard drive (HDD) is actually kind of like one really long elevator, just wrapped around a spindle instead of perfectly vertical. The SCAN algorithm is actually a disk-scheduling algorithm!
I wonder if this is an artifact of how the author used random destinations. I worked in a building that used Destination Dispatch, and the common travel pattern seemed to be:
- Everyone who is not on the ground floor generally want to go to the ground floor.
- People who are on the ground floor generally travel in large groups to the same destination.
This happens because people who worked on the same floor often leave for lunch at the same time, and return at the same time to the same floor. Destination Dispatch helps in this case because it's batching large groups of people with the same destination.
In the game, some of the elevators are automated, and I wanted to choose an algorithm that best aligned with what players would expect an elevator to do. I ended up going with something close to LOOK, which (as the article states) is mostly what people expect. Except in case of ambiguity, I had it prioritise floors that have been waiting longer, to improve the p90, which is important in the game.
But now, add in these challenges:
- double-deck cabs (where attached cabs cover two floors at once)
- transfer floors between shafts
- express shafts
and the best (or at least, most expected) algorithm becomes much less obvious! I'll leave it as an exercise for the reader to figure out the best one.
Luckily I was in charge of a game, not a real elevator system, so I just had to find a heuristic that was good-enough, and could tweak the rules to let players manually override the elevator's plan if they don't like where it's going. This seems to have satisfied most players.
There’s something so satisfying about watching a machine just dutifully work through queued tasks like this.
I swear no matter if it was busy or not, it seemed like everyone was assigned to the same one or two elevators. The wait was always so long too, I used the stairs most of the time if just going <6 flights.
Someone besides RCCL needs to study that algorithm.
Efficient elevator algorithms will often suggest moving an elevator into a preempted positioning strategy, based on time of day or peer elevator positions. The scheduler might move an elevator up to offset one coming down, for example. The demand-signal algorithms at least minimize movement in this way.
I think minimizing maintenance at the cost of increasing wait times is probably an important balance to get right. No doubt, the cost owners for maintenance are not going to perceive the wait time of passengers to be as important.
Of course, user error is also a factor, so this isn't accounting for people not understanding how to use it and making things worse that way.
I can see how that could be challenging when people get off on intermediate floors, making a full car available again, changing status. And, if 3 people are waiting and there is room for 1, should it stop or not? Etc.
My favorite takeaway from this is how simplicity often beats complexity.
0: https://news.ycombinator.com/item?id=35152341
1: https://computer.rip/2023-03-13-the-door-close-button.html
That will need planning and assignment I guess? But at what load figures does it become more efficient?
- Two elevators ascending and descending in near lock step, in a two-elevator building, effectively reduced to one elevator.
- When going in a different direction from the requested one (e.g. called elevator to go up, but actually going down), the doors wastefully close, open and close again. Seen this in many elevators.
- At 3 a.m. you take the elevator to a parkade, like to get something from a car. When you return to the elevator a minute later, it is gone; it spontaneously moved away even though nobody is using it but you.
[1]: https://clarkmoody.com/Moody_AgentBasedElevatorControl.pdf
Can't believe, that this [0] solution to Challenge #5 actually worked, lol
Challenge #6 is "Transport 40 people using 60 elevator moves or less". Unfortunately docs don't make it clear what exactly counts as a "move".
[0] https://gist.github.com/vovanz/66e4396934ac656a8f8c32fcee43d...
I work in a building with Destination Dispatch elevators so I'm used to them. I have the opposite problem where I'll get into a normal elevator and just stand there without pushing anything.
Surprisingly, claude failed to find a good one.
Also, part of destination dispatch (I'm guessing based on experience) removes the 'stopping on every floor problem', so the real test would be total time including wait at that point I think.
It's probably just the old 'fake loader' psychology, to be honest. Waiting without knowing when the elevator will arrive is boring/frustrating, where getting into an elevator that moves, even if the wrong direction, feels like progress.
Things are happening, and even if it takes longer ultimately that's a less frustrating state to be in.
I see hotels with the kiosk model changing the UI depending on breakfast rush hour
Also the group of people going to or returning from lunch is real as well. The grouping factor happens more at the middle of the day and less at the morning or evening. Primarily because of lunch.
I also thought that this is one of the biggest reasons destination dispatch was better.
There are even articles about switching to destination dispatch in office buildings or hotels lead to dramatic reductions in wait time.
Another thing I learned: If an elevator mechanic says: "I'll meet you first thing in the morning." He means something like 4:00AM. They want to get in and out before people start arriving to start their day.
Although I guess that's not quite what you're talking about.
> After my lecture, a Maxis employee who shall remain nameless buttonholed me. "You guessed right," she said. "Sim Tower was built around a real elevator simulation program we bought from a Japanese guy."
https://web.archive.org/web/20090916193335/http://www.gamasu...
I just visited a new building with destination dispatch, so it seems to be still around.
My EE roommate in college had to build an elevator circuit as a final problem. It was on a bread board and had a bunch of call buttons and had a motor and a clear disk with black squares so it could figure out where it was…. I think it was the simple algorithm…
Unless you're a hotel. Then the timing is flipped: Wait in a distributed manner in the morning/mid-day, gather on the floor in the evening.
I wish elevators accounted for load.
I've been to a couple of larger conferences where on the Monday morning after, the hotel elevator was just hammered. Everyone wanted to go down, and the elevator would dutifully stop on every single floor no matter how full it was. If you were mobility disabled on the 2nd floor, you were basically fucked if you had a flight to catch.
One would think that, if it's a 10 person elevator and it's already stopped on 10 floors requesting it, that it could save an extra 5 minutes by just going directly to the ground floor, instead of stopping on every floor with the same conversation of "Oof, can't fit in there. I'll get the next one!"
My guess is whoever hinted at that didn’t fully understand what they were taking about.
Everyone has shared the frustration of waiting for an elevator that never seems to arrive. "I pressed the button, why isn't it coming?" you ask. For something as commonplace as elevators, they are far more complex than meets the eye.
Over the course of this article, we'll unravel the mysteries of elevators. The way you push their buttons, and how they push yours.
4321
The simplest elevator algorithm is called SCAN and was patented in 1961. The elevator starts at the lobby and goes all the way to the top floor before reversing and coming back down. It picks up and drops off anybody on the way.
Most of the time you don't actually need to go to the TOP floor. If the elevator goes only as high as requested before reversing, the algorithm is called the LOOK algorithm. This is the algorithm most people know and expect.
4321
Here's where the mystery begins. If there are multiple elevators, how do the cars coordinate who picks up who?
In the most basic system, there's a central scheduler that tells each elevator which floors to stop on. When a new request comes in, it's assigned to the closest elevator. As we'll soon see however, we can do better.
4321
How do you actually measure how good an elevator algorithm is? The obvious metric is how long you wait for the elevator to arrive.
A very simple measure is "how often does the elevator arrive within 30 seconds?" Or "how often does the elevator arrive within 90 seconds?"
-
wait < 30s
-
wait < 90s
654321
flow14/min
More rigorously, we want to look at the DISTRIBUTION of wait times. If we plot the wait time across thousands of rides, we get the histogram below.
654321
010s
p50—p90—
flow14/min
A p90 of 2m means 90% of the time, riders wait 2m or less for the elevator. A p50 of 1m means half the time the elevator arrives within 1m.
People don't usually remember the average amount of time they wait. They fixate on those times when the elevator took FOREVER, the p90 case.
Not all passenger traffic is created equal. Imagine a large corporate office building. In the mornings, nearly all traffic is dominated by trips from the lobby to the upper levels.
In the evening this flips as everyone leaves the building. The lunch rush is a bit of both, and the remaining traffic is often from floor to floor.
-
wait < 30s
-
wait < 90s
654321
flow14/min
The distribution of wait times varies drastically depending on the time of day and the traffic patterns the elevators are facing. Morning rush notoriously has the worst wait statistics.
When analyzing the LOOK elevator algorithm, we LOOKED (ha ha) at how riders are assigned to cars. We naively assigned each request to the nearest car but said we could do better.
What if the nearest car is full? We can get smarter with Otis' RSR (Relative System Response) algorithm. RSR scores each car for how well suited it is to pick up a passenger. Lower scores being better.
RSR pickup score
Score=ETA to pickup+onboard load penalty+same-direction anti-bunching penalty-direction-match bonus-idle-nearby bonus-low-load bonus
Anti-Bunching
Penalize a car if another car is already headed to the same floor in the same direction.
Idle Nearby
Reward idle cars within two floors of the caller.
RSR also re-optimizes every 5 seconds. A passenger that's going to be picked up by elevator A can be re-routed to elevator B if elevator A encounters delays. This re-optimization turns out to be key for streamlining traffic flow.
In the graphic below, each elevator lights up when it's the best choice to service a call from floor 3 if the button happened to be pressed at that exact moment. This constantly changes as the elevators move, showing the optimizer in motion.
4321ABCDAScore 1
Armed with our elevator analysis toolkit, we can benchmark the performance of LOOK vs RSR to see how much a smarter elevator algorithm actually improves wait time.
LOOK
**-**wait < 30s
**-**wait < 90s
10987654321
RSR
**-**wait < 30s
**-**wait < 90s
10987654321
flow8/min
Interestingly as the flow rate gets higher, LOOK actually starts to outperform RSR. When the elevators are always full and stopping on every floor, the extra rules don't matter as much.
LOOK also tends to outperform RSR in small buildings with fewer elevators per bank. Sometimes it's better to just keep things simple.
Another metric you can track is journey time, how long you're actually waiting in the elevator before getting to your floor. RSR and LOOK have different characteristics here as well but that's beyond the scope of this article.
Not all elevators have buttons in them. Some of the fancy new elevators have a kiosk on each floor that allows you to specify what floor you're heading to before the elevator even arrives. The kiosk then points you to which elevator you should wait for.
This is called Destination Dispatch. At first glance, it seems great. The elevator optimizer now has full knowledge of who is going where, certainly we can use this to reduce wait times right?
RSR
**-**wait < 30s
**-**wait < 90s
87654321
Destination Dispatch
**-**wait < 30s
**-**wait < 90s
876543217
flow8/min
It turns out these fancy kiosks are in general worse for wait times compared to the traditional good ol' up and down buttons. There are certainly edge cases when the kiosks can win out (extremely tall buildings with 8+ cars per elevator bank) but for the majority of cases, simple up down buttons reign supreme.
This counterintuitive result is all thanks to the rebalancing step where every 5 seconds, the system re-optimizes each elevator's path. The kiosk enforces rigidity, you must get in the assigned elevator.
The state of the world 30sec after you called your elevator might be very different but the system is unable to adapt. Turns out the loss in flexibility is not worth the extra information for the optimizer.
Here's a simulation with all the buttons and knobs to play with. Go crazy!
-
wait < 30s
-
wait < 90s
87654321
floors8cars4flow18/min
This article just scratches the surface of elevator algorithms. Next time you're stuck waiting for an elevator, try not to take it personally. The elevator did hear you, it just has a lot to think about.
(BTW, going _down_ while empty is typically more energy-consuming for the elevators because they are counterweighted)
Edit: that's also why you shouldn't use elevators in a fire. If the brakes in the elevator machine room fail, the cab won't crash down. It will go _up_, possibly dragging you into the fire. Many firefighters died because of that.
In one of the buildings where I worked, "fancy Destination Dispatch kiosk" had a separate button with a wheelchair pictogram that would ensure that the elevator has enough space for a wheelchair.
It could also be that you and I simply aren’t privy to what is actually happening “the instant” you are waiting for the elevator.
…which makes me wonder how often the firmware in these get updated. Assuming it’s not just a pile of ancient relays and stuff. And if, when they do get updated, the algorithms get improved. Or if the algorithm is something that gets sold to the building and “upgrading” is an actual purchase.
Anyway, I could get a little LLM buddy to look it all up but where is the fun in that?
Yeah, it doesn't make any sense to optimize wait time instead of total time from pressing the button to reaching destination.
(I've never encountered destination dispatch myself, so I'm not really sure how it works in practice)
Forcing functions that dump people into well defined funnels can have such a high net positive effect it more than makes up for theoretical losses.
It's like narrow, hard road bike tires losing performance because of deflection from rough road surfaces and how long it took designers to factor that in to real bikes.
Apparently, the fastest known way to fill up a plane in real-life conditions is to let people board in random order, without pre-assigning a seat.
I've never been to China but wouldn't you learn quickly after getting in an elevator going the wrong way not to do that again?
The only exception I can see if there's way more people than elevators and you just need to get spot at all costs.
I remember this one, it deserves all sorts of praise
Sometime during Covid, the metal buttons were replaced with glass touch screens – which are totally unreadable on sunny days, because in our stunning glass-ceilinged atrium mezzanine they sit directly in sunbeams[0]. So now you have to walk up to the kiosk, shade it with your body, and squint at the screen to make out where to touch it.
But yes, this seems like a case of "unfortunately, people".
See also: the keep open / close doors button. I had one building administrator explain to me we should add a delay of 10 seconds to the "quickly shut door" button because otherwise she kept getting her arm hit by the door. When I asked why we would add a delay to the button that's meant to reduce delays (why not simply wait for the door to close on its own, then?), and whether we should fix the sensor that prevents doors from closing if there's an obstacle instead, she just kept staring blankly at me. I don't think she understood me at all.
Again, some people simply don't grasp how elevators work.
but imo, unlike farmer, these games reaaaaly lack the ability to make functions/subroutines
manually doing all the goto loops becomes tiring
