Did You Ever Wonder How Elevator Algorithms Work? Story About Lifts and What Do They Have to do With The Hydrogen Bomb.
Press and button and wait.
That is what most people do when they encounter a lift, or an elevator if you come from the US. Press the button and when the lift arrives press another button, you are guaranteed to get wherever you are going in a convenient way. Like most people, right? When I moved to a place where I used a lift to get to my floor I started wondering how the algorithms behind the lift work behind the curtains. What does the lift optimize for, the smallest mean or the smallest variance? Does it always go the the ground floor when idle for some time? If so, after how long does it do so? Does it differ during the day and the night? Why would that be?
If you are anything like me, you came up with similar questions yourself. In this article I show some of my findings about how the intriguing systems behind elevators work, and I will answer the question of what do they have to do with the hydrogen bomb.
It's so simple, they surely just use some optimization algorithm.
Yeah, well, they do. But, what optimization algorithm? What is the objective that the algorithm tries to optimize? What is the best metric to optimize after all? After pondering about how these systems might work for some time you might find yourself coming up with different metrics that they might be optimizing for. A few reasonable guesses could be mean waiting time, mean ride time, energy usage, number of people serviced in a unit of time, or perhaps one could care about optimizing some other metric than a mean, like variance or the chance of some extreme event not happening.
As you can probably tell by now, there are quite a few different things one can optimize for when working on the algorithm of a seemingly simple lift. Actually, there are whole fields that tackle these subjects, in particular look into the queueing theory subfield of operations research if you want to see how did people in the past figure this stuff out. Modern elevators are quite efficient at what they do - transport passengers. If look at them per trip, or possibly by the time their users are exposed to them, they rank among the safest modes of transport, closing in, or surpassing even commercial flights. That being said, there is quite a bit of interesting technical details that go into how lifts function. While doing research for this post I stumbled across some interesting facts about lifts, like their special operating modes, but in this post I will try to limit my focus on the algorithmic part.
Okay, what are the lifts optimizing then?
Among the most widely used elevator algorithms is SCAN, which makes an elevator continue travel in the same direction (up or down) while making stops to let people off or to pick them up, if they are heading in the same direction. Lifts moving with this algorithm always move to the last floor in a particular direction, and reverse only then. SCAN looks to optimize travel time, i.e. waiting time + ride time. A popular, more efficient version of SCAN is called LOOK, which behaves the same as the previous algorithm, with the difference being that it only goes as far as the last requested stop in a particular direction, and not the last possible stop, before reversing to the other direction.
Both of these algorithms have an important feature, they avoid what is called starvation. Imagine a scenario with a single lift in a building with one hundred floors, optimizing the mean travel time, with majority of the people in the lobby on the ground floor, travelling to floors 1-5, and a single person on the floor 100. If people keep coming to the lobby and pressing the button, the lift that just optimizes the mean travel time wouldn't go all the way up to pick up that one passenger from floor 100, as long as there would be passengers on the lower floors. That's called starvation, because one user is starved of the service while others use it repeatedly, by using the SCAN or LOOK algorithms lifts are able to ensure such situations don't happen. The example of starvation shows that looking to minimize only one metric for cost, is not enough (wink wink my finance friends) because optimizing for low averages doesn't take into account extreme scenarios, which is not desirable.
In reality, in buildings which have a lot of floors, there are usually lifts servicing only a selection of them, effectively partitioning the building into smaller parts. For example, lift "A" travels only between the ground floor and floors 1-15, while lift "B" starts at floor 0 and travels between floors 16-30. There can also be high-speed lifts, going rapidly from the ground floor to the upper levels.
Right, what if we have multiple lifts in a building?
The setup if quite simple if we talk about a single, relatively short, building and a single lift. But when buildings get taller and multiple lifts are operating things start to be a little more interesting. Some skyscrapers make users choose the floor they want to go to before entering the lift itself by choosing a button on a terminal screen in a lobby. The people are then informed, on the same terminal screen, the lift number they should get into to travel to their destination. When they get into that elevator, they can't change their minds, as their are no buttons inside the lifts, they can only call a new one once they get out. This way, destinations control systems can be employed to optimize traffic in high-rise buildings.
In such buildings, people wait for their designated car, and do not simply board the next available car. This allows to reduce travel time, enabling elevators to make fewer steps for individual passengers. Despite travel time being reduced, the trip might seem longer because the time one has to wait to get into the lift is increased. To avoid one user requesting multiple lifts at a time and messing up the queue, some systems make everyone use an RFID card which they have to scan when ordering the lift. This way, when a user wants to change their destination of travel by calling the elevator two times, the system doesn't double count him, but instead cancels the first ride and orders him a second one.
What about the hydrogen bomb?
Yes, the bomb. But first consider this; as you have already seen operating multiple lifts at a time can get quite complex. If you watched the Nolan's Oppenheimer you might recall one particularly with a pair of bushy brows. That person was Benny Safdie, playing a person with an even more bushy pair of brows, a Hungarian mathematician and physicist Edvard Teller, who worked on the Manhattan project, focused on building the first nuclear bomb. Teller's involvement in Project Manhattan was remarkable, but even more remarkable was his involvement in the design of the hydrogen bomb, a bomb thousands times stronger then the nuclear bombs dropped on Hiroshima. There you have the bomb, now, wait a bit and you will understand how it connects to the elevators we have been talking about.
While Oppenheimer was, in my opinion, great, it failed to portray the second father of the H-Bomb, a Polish mathematician called Stanisław Ulam who was also involved in Project Manhattan. Ulam's input into the design of the H-bomb was big, and there are debates going over who of the two designers contributed more. Ulam however, is also remembered for another invention he made.
Tailor-made lift algorithms.
Because of the complexity of systems that utilize numerous lifts in buildings with a lot of floors, there is demand for algorithms optimized specifically for that particular buildings, at particular times of operation. One, efficient, way to achieve this is through computer simulation. One of the most widely recognized kinds of computer simulation is the second popular invention of Ulam, namely the Monte Carlo simulation, named after the casino in Monte Carlo that has a lot to do with probabilities and randomness. The Monte Carlo method utilizes randomness to solve deterministic problems. It enables to derive approximate solutions to problems too complex for mathematical analysis, such as the ones within big and complicated building's lift systems. While the method deserves a post of its own, luckily there have been thousands of people on the internet who wrote about how it works.
In short, by replicating the lift system of a building within a computer environment, and modeling the flow of people within a building, you can run hundreds of thousands of simulations with different strategies and measure metrics of choice in the process. By following this process you can get closer to picking a tailor-made, optimal solution to implement in your skyscraper, if you ever happen to own one. This is how systems learned that during daytime it might make sense to have lifts idle on the lobby floor, while in the night it might make more sense to keep some of them in the middle of a building or elsewhere.
There is a lot of interesting tangents that one can go off when trying to optimize different objectives. Most importantly, you do not have to be a real estate owner to think about such issues. If you care about them from a purely intellectual perspective, you will be just fine grappling with different online simulators, like this elevator programming game, or building your one. If this whole elevator algorithm thing grabbed your attention, expect more of such content in the future here.