The Hidden Science of Elevator

How powerful algorithms decide when that elevator car is finally going to come pick you up.
— Jesse Dunietz —

 

You walk to the elevator bay, hit the “up” button, and stand around for what feels like forever before hearing that reassuring “ding.” It’s enough to make you scream, especially as you look up at the cars’ current locations and wonder why one can’t just come for you.

When you’re gritting your teeth in that hotel lobby, it’s easy to overlook the fact that we’ve given our elevators a doozy of a computational challenge. A lot happens when you push that button: The elevator system must decide which car to send for you, and when. It must decide whether to go up from the fifth floor to collect those people on the 7th before coming down to the lobby to answer your call. It must consider who’s been waiting longer, and which of the many paths is the most efficient and least painful for everybody. Elevator traffic is an elaborate, delicate dance, and once you see the steps, you can’t help but tip your hat to the engineers who choreograph it all.

Elevator routing wasn’t always so complex. The earliest electric elevators were controlled by the whims of their human operators. An attendant standing inside would drive the lift up and down with a throttle of sorts, stopping wherever he or a dispatcher saw a waiting passenger. But humans proved to be clumsy, expensive, and prone to strikes, and by the 1950s, electrical switches took over their jobs.

With the elevators directing themselves, engineers had to spell out rules for when to go where. The simplest method was for the elevators to shuttle back and forth between predefined “terminal floors” at scheduled intervals. It was like taking a bus—you waited for the 3:10 car up to the 10th floor, and then found your way from there. This, of course, was grossly inefficient. During busy times of day, the elevator cabs would waste everyone’s time sitting at a terminal floor until their scheduled departure. During off-peak hours they would make pointless empty trips.

By 1965 it was clear to everyone that this was a bad idea. So lift engineers settled on the model we all know and love: Passengers push buttons to call an elevator, and the elevators respond to these requests. But here it starts to get tricky. At any moment there could be any number of pickup and drop off requests from different parts of the building. With so many options for where to go next, what’s an elevator to do?

A LOT HAPPENS WHEN YOU PUSH THAT BUTTON

Try to picture the perfect elevator system. What makes that system so great? Does it serve the person who’s been waiting the longest? Or always go to the closest call? Where does it make the compromise between speedy service and keeping energy usage down?

Elevator engineers grapple with all these questions, and none of them are as simple as they seem. For example: clearly, an elevator should try to reduce travel time. But how should it prioritize your time? If you wait a minute instead of 20 seconds for a car to come, is that three times as bad, or perhaps six or even nine times worse?

Even the most basic of these goals isn’t a given. Sometimes, it’s actually better to make a passenger’s ride longer. Imagine two scenarios, one in which your elevator takes 10 seconds to arrive and then one minute to reach your destination, and another in which each portion takes thirty seconds. Many people find waiting so painful that they’d prefer the first option, even though they’d reach their destination 10 seconds later (though people who feel claustrophobic in elevators would prefer to minimize time inside the car). Accordingly, some elevators optimize not for time, but for a customized “pain index,” in which the computer system weighs the awfulness of each kind of delay.

Further complicating matters is the simple fact that an elevator operates under many constraints. It has physical limits on its speed, and it only has a second or two to choose its next move. It also shouldn’t do anything that will seriously piss off passengers, like bypassing someone’s desired floor without stopping, which is just asking for a fist in the control panel. A good system will aim to balance all these goals and worries, even when you needed to be upstairs 10 minutes ago. Hey, nobody said making the trains run on time was easy.

The Elevator Algorithm

The earliest and simplest reasonable approach to elevator dispatching is still surprisingly common. Known as “collective control,” or simply “the elevator algorithm,” it consists of two rules:

1. As long as there’s someone inside or ahead of the elevator who wants to go in the current direction, keep heading in that direction.
2. Once the elevator has exhausted the requests in its current direction, switch directions if there’s a request in the other direction. Otherwise, stop and wait for a call.

Pretty simple and straightforward. This is why your typical elevator bay has call buttons for going up and going down—so the car that’s already heading skyward can stop to collect anybody who’s going up. This policy doesn’t account for most of the factors above we mentioned earlier, but it’s not a bad place to start. The elevator algorithm is easy to follow, fairly energy-efficient, and everyone gets an elevator within one round trip. (Fun fact: the very same algorithm controls the read/write head on many hard drives for similar reasons.)

Small office buildings or apartment blocks, which typically don’t need to squeeze every bit of efficiency out of their elevators, tend to use this simple approach. In larger buildings, though, collective control starts to cause problems. For one thing, the elevator services the middle floors each time it passes by, but it’s never going to stop by the basement on its way to floor 7. In tall buildings, then, the wait at the very top and very bottom, the areas most in need of elevators, can be a nightmare.

More importantly, large buildings usually have banks of elevators, not just one. If each of them follows the elevator algorithm, then under heavy traffic the elevators start leapfrogging each other a few floors at a time. They bunch up in the middle of the building, potentially even serving the same calls twice. It’s the worst possible aggravation for the Monday morning blues.

To handle these larger setups, engineers developed a slew of tricks. Just having the lifts talking to each other goes a long way. If Car 1 is headed up, Car 2 can instead handle a lobby request. Furthermore, lifts can be assigned to specific clusters of floors. You also may have seen elevators hanging out in a lobby, doors wide open. This is the “parking” strategy, where idle elevators return to a commonly requested floor. Thanks to traffic prediction and real-time monitoring, the elevators can switch between strategies to adapt to the morning or close-of-business rush.

Computing Complexity

The coup that really carried elevator programming up a few floors happened in the 1970s, when reprogrammable computers came on the scene. If someone had a new elevator routing strategy, they no longer needed to sell a mogul on the idea and wait for a building to go up. Instead, they could test and fine-tune their ideas in software simulations.

A flurry of new algorithms hit the shafts. One strategy, still popular today, is called “estimated time of arrival control.” Basically, the computer considers all cars moving towards a call and assigns the one it thinks will get there the fastest. Another favorite was to always hand the most urgent call to the car predicted to create the “best” outcome for that passenger: minimize journey time, use the least energy, or whatever else the designers chose to prioritize.

DOES IT SERVE THE PERSON WHO’S BEEN WAITING THE LONGEST? OR ALWAYS GO TO THE CLOSEST CALL?

The apex of the computerization trend is “destination dispatch,” which you can experience if you visit the Marriott Marquis in New York, the Ameritech building in Indianapolis, or dozens of other skyscrapers built or modernized since the 1990s. In these buildings, rather than simply pressing “up” or “down,” you enter the floor you want to go to, and it tells you which elevator will come to take you there. (Popular Mechanics‘ home base, the Hearst Tower in Manhattan, uses this kind of elevator dispatch.)

Because they know exactly where you’re going, these systems edge closer to perfect efficiency. People headed to the same floor are bunched together, turning each elevator into an express train. As such, you might then have to wait longer for a lift, so destination dispatch systems often shift their priorities depending on the time of day. During the morning rush, when net capacity is key, you’ll suffer more of a wait so the system can reduce overall trip times. In the afternoon, when fewer people are riding at the same time, they can afford to collect you sooner to reduce the mental anguish of waiting.

With all of these strategy options, engineers are faced with a meta version of the original problem of how to choose the best algorithm. And frankly, one of the most successful approaches has been to throw up our hands and let the computer decide. Using machine learning techniques, engineers can specify what success looks like, then let the controller experiment on its own in simulation. At each moment, the system inspects the state of each simulated elevator and the parameters of each outstanding request, decides what to do, and measures the results. The software eventually learns a policy for each combination of factors. With these more sophisticated policies, even the people who built the software often don’t know why it’s doing what it is.

Elevator dispatching is an intricate balancing act. Every time you press a call button, you become part of the dance, another moving dot among the cacophony of ups and downs on which the dispatch system valiantly tries to impose order. So the next time you’ve got a minute to kill waiting for those steel doors to open, take a moment to admire the magnificent complexity of the humble elevator.

When you can see the the hidden magic behind the machines’ scurrying, even an elevator delay can be uplifting.

—————-

Source: Popular Mechanichs.com