Elevator Algorithms | Hacker News Reader

Elevator Algorithms

lisazhang.ca

144 pointssigna1171 comments

Hmmm, algorithms to control elevator behavior.

How about algorithms to punish inefficient human behavior on elevators:

a. If people are on the elevator, it stops on a floor for a button that has been pressed, and no one gets off (as measured by weight), this means that someone must have pressed a button by accident. Switch from soft muzac to loud Rich Ashley music until the next stop.

b. If someone enters an elevator (as measured by weight) and within 3 seconds 2 buttons are pressed within 1 second of each other by the same finger (as determined by biometrics), that means some dumbass couldn't even press the correct button. Shock them on the second button press.

c. If the elevator is planning to discharge passengers (see a.), and people get on before people get off (as measured by weight), dump hot liquid on the rude entering passengers (those closest to the door).

d. Photograph anyone who summons the elevator by pressing the up or down button on their floor. If the elevator stops and no one gets on (as measured by weight), post their picture on elevatordouchebags.com.

e. If anyone farts on an elevator (as determined by sensors), identify them with a spotlight so that the sufferers don't have to guess who made them suffer.

f. If anyone gets on the elevator without a cart or baby carriage (as determined by sensors) and presses 1 floor down, go up 1 floor instead. When the door opens, flash a message, "Use the stairs next time!"

g. If too many people get on (as measured by weight), open door slightly and shake violently, knocking people out until the weight is under the limit.

Any other ideas?

Why punish inefficient behavior? All of these seem slightly... inhumane ( :) I suspect that is the point). Really, though, what if the elevator were sped up if people started acting more efficiently (as determined by your multitude of sensors).

Instead of Jandy's suggestion:

>Am I crazy thinking it'd be a good idea to have an elevator which analyses its own usage patterns and adjusts its behaviour accordingly?

why not make the people adjust to the elevator's ideal behaviour?

EDIT: quote formatting

A good design works with human nature, not against it. If you want people to adjust to the elevator's ideal behavior, you have to subtly guide them to the right direction -- which is possible, but the way you asked it sounds along the lines of telling a whole office to start following arbitrary elevator efficiency rules.

That aside, I think Jandy was referring to a different scenario than what you're envisioning. If you have a skyscraper, and a trendy new bar opens on the 36th floor when the 36th floor use to be occupied by an office, but the elevator was programmed to rest at the 36th floor only at 9AM, lunch hours, and 5PM, telling the bar they have to make their clientele come and leave at those hours for "efficiency" will not go over well. Instead, having an elevator that notices no one's calling from the 36th floor before 8PM anymore doesn't sound like a bad idea.

> A good design works with human nature, not against it.

Although I agree, I was responding to the possibility of an elevator punishing behavior it didn't "like". Both what edw519 and I suggested would lead to "a whole office [...] following arbitrary elevator efficiency rules." It was intended to be a very tongue-in-cheek comment. I completely agree with both you and Jandy: a good elevator design would adjust itself to normal usage patterns and maximize efficiency within those constraints.

Clearly what is needed is an iElevator app for iPhone that teaches people how to make the most of their elevators.

> Rich Ashley music

FYI it's Rick Astley, not Rich Ashley.

There seems to be a lot of interest in minimizing the amount of time users need to wait to get onto the elevator, but this is not the only variable you can optimize. Elevators use a lot of power, and a lot of elevators (especially low traffic ones) are programmed to minimize the amount of power used. For example, the author's suggestion that elevators travel to the ground floor after every trip is highly inefficient and expensive.

I don't know alot about Physics, Engineering or Elevators, but I do know that there is some magical force at work in the world that once made an Apple fall on someone's head. Could we not utilise this force for the better and, perhaps even, recoup some energy?

I think elevators are usually counter-balanced so that the motor doesn't have to really lift anything except the occupants. Maybe not though ...

The are, with the effect (and I'm guessing intent) that an electrical/motor failure won't lead to the elevator plunging 20 stories and killing all occupants.

Software engineering could (and should) learn a few things from mechanical engineering. People have been saying that for decades, but it bears repeating...

Crash driven design. Design your software such that it can recover from a crash to a known state and continue. Make life so much simpler. Shutdown is just a matter of power off. Startup always does a recovery before starting.

There's a separate emergency brake system to prevent the elevator from falling, because you also need to be safe if the cables holding the elevator up break (this is actually the technology that lead to the first elevators). The counterweight is probably primarily just to reduce power/energy requirements.

Yeah, they have elevators that do that. Here's some marketing literature I found if you're interested: http://www.kone.com/countries/en_gb/products/elevators/konem...

Security mindset edw?

(a), (c) I press all buttons as I exit elevator.

(b) gummi bear attack or similar.

(d) Arrive carrying large cumbersome object "Heh, can you call the elevator for me?" (then run away)

(f) is easily reversible: should send people as far away as possible from their intended destination instead.

(g) throw dumbells into passing elevators.

Oh I have some. But I'd rather venture into traffic light algorithms at crossings. Quite simple and effective really:

If anyone presses the button more then once they'll get the same lights as the traffic. So green for the cars, green for them.

An old game called Sim Tower was pretty cool in that your success as a huge tower builder was directly linked to how well you could optimize elevators. There was a maximum number of elevators that you are allowed to construct and once your building gets large, if you don't optimize, people will get fed up with the waits and abandon your tower.

The game allows you to setup different patterns for different times of the day. It allows you to set wait floors, set which floors it will stop at, and even set patterns like skip to the top and drop off on way down. This last trick avoids the problem of needing to stop on the same floor on both your way up and way down, which would occur with normal elevators if say the elevator was taking two people up, one to floor 17, one to floor 20, and someone wanted to get on at 17 to go down.

In all the game was really fun (although construction was repetitive), and does make you think about elevator optimization for the rest of your life, I played it as a kid, and I am always thinking about how badly elevators are optimized!

Protip: Only build offices, no condos. I got to 5 stars without once optimizing the elevators.

There is a rating higher than 5 stars, called TOWER. It has been a while but if I recall it is very difficult to reach that with offices, because they have a large amount of traffic compared to other ways of getting population, making it to hard to not overload your elevators even with optimization.

What I did was sort of a hack, but worked, in the basement levels express elevators and escalators can go to any floor, so I made tons of them, and made tons of shops, all shops (they had highest population density). Virtually all of my tower was underground.

I just started working at a 31-story corporate office with sixteen elevators (A-H for 1-15, I-O for 15-31), and the elevators here incorporate a genius move... outside the elevator are little panels with numbers, and you choose the floor you want before you get on the elevator comes. The panel tells you which elevator you should get on. This way, the system can optimize ahead of time where the different elevators should stop. Since I've been here, I've never waited more than 15 seconds for an elevator.

Those work nicely in office buildings where people know the routine. When you put one in a hotel, you'll usually see someone paid to stand around and show guests how to call the elevator.

Is that just a customer comfort thing, or has nobody managed to invent a sign that people will read yet?

People see an open elevator door, they get in the elevator. They don't stop to read the instructions because they are not expecting the elevator to come with instructions and also because they know the elevator doors are not going to remain open forever.

These people are already getting on wrong elevators. The example given has banks of elevators for different floors, marked by sign and by buttons for the specific floors covered. If they don't pay attention they'll get a short tour.

If this was a deadly choice, between an elevator and a trash compactor, it might make sense to over-sign it. As is, it's a trivial and obvious mistake, especially if each bank has a sign saying 'Floors 1-x are reached via the other elevator bank' for someone to read on their round-trip.

Part of the reason users are so clueless is because we go too far in padding their environment. People don't slice off fingers because the sharp end of the knife wasn't properly labelled - they exercise caution.

There is no up/down button, just a keypad with numbers on them. People are accustomed to looking for the up button and, upon not finding one, immediately get into a confused state.

If you need lengthy instructions to show someone how to use your UI, you should reconsider your UI.

http://www.jnd.org/dn.mss/are_the_new_elevators_bad_design.h...

At the risk of completely derailing the discussion, sometimes the UI simply just needs to be learned. People who are unfamiliar with elevators would have no idea how to use one.. there's no instructions anywhere, just a panel with numbers. If you aren't familiar with those bathroom faucets that turn on when you put your hands under them, you'll spend a few minutes just staring at it looking for a knob. Eventually, it catches on.

You are right that there's an initial curve, though, and I don't know how to deal with that other than just through the painful experience you described.

Of the top of my head: start off with big up/down buttons. Then show a list of floors. Some people won't notice the second press required, but it's a start. I was confused by those things the first time too.

That's a good idea. Having that, plus an 'expected wait time' would be really useful. When I push the button, if it tells me I'll need to wait for 4 minutes and 23 seconds for the next elevator, I can use that time more effectively ... maybe go grab a coffee and come back, or perhaps even take the stairs instead.

I don't think owners of office buildings realize how painful it is to have slow elevators. We moved our office out of a 30 story building with 4 elevators, because the unbearable wait to get in and out of the building during peak times.

I saw this implemented at (I think) Times Square Tower a few years back. It had you enter your floor at a podium in the main lobby on the way to the elevators, and it worked beautifully. 49 floors and not once did I have to wait more than ten or 15 seconds for an elevator.

Then they retrofitted a similar system back at my corp HQ. It had you enter your floor on a screen on the wall right in the middle of the elevator lobby and it was (and is) kind of a pain in the ass...because when there's a crush of people waiting for the elevators, you can't get to the screen to enter your floor. When it was just the "up" and "down" buttons in the same location, the odds were pretty good that someone in the crush had already pushed the button you need, but...

Very interesting. A friend and I were interested in elevator algorithms last year, and ended up writing an elevator "simulator" in Java. I'll post the code somewhere if anyone's interested, but like chrislomax and TheCapn say is correct: depending on the time of day, the optimal algorithm changes.

The interesting thing about "elevator" algorithms is that they're really very similar to the algorithms used to schedule reads and writes on a hard drive. Reading in some data is similar to picking up a person, and writing data can be thought of as dropping the person off somewhere. Regular (i.e., not solid state) hard drives have large cylinders of addresses. This is sort of like a rolled up building.

I don't have the output in front of me, but I think that both LOOK [1] and SCAN [2] algorithms performed very well. It's cool to note that the SCAN algorithm is referred to as the "Elevator algorithm" by Wikipedia. Clearly we're not the first to go down this rabbit hole.

[1] http://en.wikipedia.org/wiki/LOOK_algorithm [2] http://en.wikipedia.org/wiki/Elevator_algorithm

I'm definitely interested in playing with your simulator!

This is a really simple analysis of elevator algorithms, mostly based on anecdotal evidence. If you really want to go down the rabbit hole of these algorithms, there's a whole lot of scientific papers written about them.

http://scholar.google.com/scholar?q=elevator+algorithm&h...

It's probably best to use a E*N entry LRU cache for elevator requests. In the morning it's going to be predominantly ground floor to upper floors, a complete mix during lunch, and in the afternoon upper to lower, by using the E floors that have most entries in the LRU cache you'll be able to fairly efficiently move the elevators to the correct floors most of the time, and also account for any discrepancies in office hours.

(E = the number of elevators, N probably should be the number of floors, no idea what would make a good N)

I'm sure that if you snap shotted the LRU cache every few minutes you could build a pretty good predictive index for the patterns through out the week and time of day.

What might be interesting would be wifi/cell signal detectors that could pick up a cell when it enters the hallway and start moving the elevator already.

I've been thinking about elevator algorithms lately too. My building applies the principle of least privilege to the elevator - residents are issued fobs which give them access to the floor where they live, plus any common areas. The problem is that waving the fob in front of the sensor pad before pressing the button for your floor takes a bit of time, and in that time, it's possible that someone else, somewhere in the building, will press the button to call the elevator. When that happens, the elevator may change it's direction. A race condition!

For example, you're on the 10th floor and want to go to the first floor. You press the down button. The elevator arrives, with it's "going down" arrow lit. You get on, and as you fumble with your fob, someone on the 18th floor presses the down button. The elevator now has a call on the 18th floor, and no destinations yet, because you haven't pressed the "1" button. Now you have a choice: press "1" and ride the elevator up to 18, knowing that it'll (eventually) go down to 1, or get off the elevator press "down" in the hope that another elevator will arrive before this one gets back. Of course, it's very likely that you don't notice the "going up" arrow, because you're fumbling with your fob.

I'm finding this happens surprisingly often, and I think it's a bug.

And amusingly, those fob systems increase the chance of a break-in to your apartment. In a building of 200-400 suites it'd be tedious to try found/stolen keys in every door.

But in a system such as you describe you get on the elevator, wave the fob at the sensor, and press all the buttons. It'll only take you to the specific floor your stolen key will work on - narrowing the search time down to mere minutes.

Am I crazy thinking it'd be a good idea to have an elevator which analyses its own usage patterns and adjusts its behaviour accordingly?

http://tierneylab.blogs.nytimes.com/2007/12/20/smart-elevato...

The only optimisation this one has (that the article tells us about) is that passengers choose their floor, but not the elevator to get there.

Not at all. Here's a similar idea, a thermostat with two inputs: too hot and too cold, plus some machine learning tuned for circadian rhythms: https://news.ycombinator.com/item?id=3153227

No, because as soon as we found out about this we'd all be going around trying to train strange behaviour into elevators.

Then they'd all end up sulking in the basement...

I use the "Build me a system that controls elevators" as an interview task. It's saddening how many I've interviewed that can't even get me a naive case of all destination floors get shoved on a FIFO queue. If we even get to the discussion on optimizing I've usually already decided to recommend the candidate for hiring.

it's interesting because I just got the elevator question for the first time a month or two ago and was still scratching my head trying to figure out where the decision point on that question is. i ended up spending about half the interview talking about different ways to optimize for minimal waiting time, but now it seems like that may have just been banter after we'd covered the FIFO queue.

I try to guide my candidates to produce a functional solution before premature optimization. Obviously once a candidate proves they can come up with at least the simplest case, it's good to get an idea how how they'd optimize it, but since it turns out only 1 out of every 10 candidates actually get that far, the fact that we're having that conversation is enough to push them above the competition.

This. I used to use it, too. We would start with trivial cases (one elevator, two stories), and gradually add more floors and elevator shafts. We never, ever got to the interesting algorithms. It took a surprisingly long for people to describe anything remotely like a working, naive algorithm.

(of course, the most simple algorithm doesn't even use a queue! It just moves the elevator up until it hits the top, and down until it hits the bottom, opening the doors wherever there's a call request)

Didn't anyone here play Sim Tower? Obviously you want the send all your elevators to the ground floor for the morning rush hour and distribute them evenly among your floors for the later part of the day. Perhaps leave a couple extra ones at the ground floor 24/7 for mid-day visitors. :-P

Why is this suddenly a trending topic? Elevator algorithms have are an old topic that have been studied in the 80's 90's in the database community in relation to doing efficient reading/writing for hard disk heads. The tradeoffs of each algorithm are already well known.

Just to point out the obvious problems of having the elevator door start open: 1) you now have a common case where the door starts to close as someone is just about to walk in, startling and/or annoying them, and 2) not only does closing the door first increase the time to get to any other floor, but the elevator doesn't even know whether the door close will be successful (it could be held or otherwise obstructed) -- leading to even more delays on another floor.

As several others have suggested, the elevator should behave differently at different times throughout day.

A smart elevator algorithm would adapt to the arrival behavior of people in a building through some clever stochastic simulation and modeling. For example, a simple model that could work quite well is to optimize for (read: minimize) the average time any passenger would wait for an elevator to arrive. But to do this, we need to model how frequently people request an elevator on each floor over the course of the day.

Modeling elevator requests - We can assume that the number of people who request the elevator on each floor is a Poisson process with a mean of n. On a representative day (i.e. for an office building, choose a weekday), we can observe the number of people who arrive at the elevator each hour. This data would drop in as the n in our Poisson arrival processes.

Computing optimal solutions - Using a statistical library, we can start generating simulated arrival data and apply integer optimization algorithms to determine which floor the elevator should rest on when there are no elevator requests, for each hour of the day.

Presuming this is using the North American floor conventions (which I presume to be the case based on University of Waterloo being in Canada, which according to wikipedia is likely to use the same naming conventions as America[1]), wouldn't it be better to optimize example 3 by having the second elevator on the seventh floor? This means floors 8-12 and 6-2 are only five floors away. If you station the second elevator on floor 6, then floor 12 is six spots away, and floor 2 four spots away.

Its definitely much more complex than that (e.g. the ground floor elevator could take people down from floors 2 & 3 or something, depends on time of day, etc.), but if the author's intention was to station one elevator at ground level and another in the middle, floor 7 is the better choice.

[1] http://en.wikipedia.org/wiki/Storey#North_American_scheme

I recently went to the office in Los Angeles that issues permits for filming. It's located inside a studio lot, so you sign in up front, have your ID scanned, get a printed badge to wear and walk to another building that has the permit office.

In that building, you go to the security desk and tell them where you're going. They call the elevator for you. You get on the elevator. It has no buttons inside. The desk sends you up to the permit office.

When you leave the permit office, you press a button next to the elevator and it shows up and takes you to the lobby. There are no other options for you.

Studios got paranoid about security post 9/11. Which I guess makes some sense.

But why the film permit office is inside one of them, I'll never know.

At the beginning of the day, assume most people are going up from the ground floor. At lunch time, you've got a balance of people going down to the ground floor to get lunch and people going up from the ground floor post-lunch. At the end of the day, most of the people are going down to the ground floor to leave at the end of the day. And at all times you've got deliveries that initiate from the ground floor.

Have your bank of elevators start with a simple "best guess" algorithm, and then learn how to improve that algorithm. If the last employee of the building is ready to leave at 11pm, there's no reason the elevator shouldn't be at that floor waiting after a learning period.

There was a guy on /r/iama that programs elevators for a living. He writes a lot of C :)

http://www.reddit.com/r/IAmA/comments/b1bpp/i_program_elevat...

Related: Double-deck Elevators - http://en.wikipedia.org/wiki/Double-deck_elevator - At what point do these become a worthwhile investment?

Why don't more elevators have these optimizations? On older buildings at least, I imagine it's because the landlord just doesn't care.

I walked by dozens and dozens of emergency vehicles this morning because of this horrible thing: http://cityroom.blogs.nytimes.com/2011/12/14/three-hurt-in-m...

My last office was in an older building like that and had a set of elevators that were chronically behaving erratically, so that kind of freaked me out more than it would otherwise.

Also there are choices on what to optimise for. Our elevators are triggered by swiping your company card, which then tells the elevator which floor you're going to. You're then assigned one of 16 elevators. Elevators frequently wait for a couple of minutes for more people to arrive. So instead of which floor(s) should I now go to, there's also how long should I wait to go there. I suspect the algorithm might be optimized to some degree for minimizing number of journeys (to save energy or whatever) instead of/as well as average/maximum wait time per person.

I would imagine that this is geared towards situations where the elevator is always going up. I would say that this is also affected by the business / time of day.

I would say that around 5pm you have more people going down than up so this algorithm falls flat on it's face.

I don't think you could write 1 algorithm and it works for everyone. You could generalise it to apartment buildings but I think there would be a pattern of more people going down at the beginning of the day than at the end of the day too.

I don't know whether an elevator algorithm is as simple as what is mentioned in the article.

The algorithm needs to take into consideration the type of lift (lifts in an housing complex vs commercial building) and time of the day. During morning hours, the lifts in an housing complex might more frequently travel towards the ground floor while the one in a business complex would be travelling up.

Also, there could be buildings where the top floors might have more tenants than bottom ones or the reverse.

There is a scope for self learning algorithm that can adjust its idle position depending on past behaviours.

But elevator algo becomes more complicated when two persons press the switch at same time for the lift. One is at 2nd floor and wants to go up, the other at 4th and wants to go down and lift is at 3rd floor :-)

Then what is the problem with treating elevators in the same way that traffic lights are treated in many cities: adjust for the time of day.

Using my workplace as the anecdote the elevators get massive usage at 8:00AM as people arrive at work, the majority of calls are from 1st & 2nd floors (you can enter the building on both floors at 8:00, noon and 5:00). After that there is the 9:30-10:30 coffee rush with elevators going up and down. The noon rush, afternoon coffee and evening rush.

Those are the peak points of the day with simple scenarios for when people are most commonly going up down so it wouldn't be difficult to implement scenarios where the algorithm changes at a time.

Reminds me of the following parable:

The tenants of a large well-to-do apartment block kept complaining that the elevators were always too slow, and they hated waiting in the lobby for the next available elevator. The apartment manager spent some time investigating the cost of installing faster elevator motors before he came up with a much cheaper solution: He installed large mirrors in the elevator lobby; the complaints stopped.

I've often wondered how well an adaptive learning system using cameras at each floor would work. The cameras would record how many people are waiting for the elevator and tweak the algorithms accordingly. Historical data could be collected based on time of day, day of week, etc. Could be combined with the building's existing security cameras for cost savings.

"What I don't understand is why so many buildings do not have these optimizations built into their elevators."

I suspect the author has observed more residential towers than corporate towers? Otherwise I would imagine he would find that these practices are usually followed. Except for the door remaining open one, I never see that... maybe a fire code thing?

Elevators should be able to see with a camera a percentage of the floor that is visible from the ceiling. Using this percentage (in addition to or just by weight), the elevator should be able to determine whether the elevator is full.

When the elevator is full, it should not stop for people who have pressed buttons not inside the elevator.

On a different perspective, if you may, ...

We don't walk enough, that's a known fact.

Elevators are bad for your health. Take a walk.

However Delevators are good because most accidents happen when you go downward.

Hence, Elevators going up should be for really older people only (unless you're in a hurry or carrying something heavy or already in good shape...).

Fight for Delevators!

Well, I agree we do not walk enough, but when you live in large buildings with more than 15 floors you cannot expect people to take the stairs up and down from top to bottom. Elevators are enablers of high people density in cities.

Makes me wonder if there's a different solution to the elevator problem entirely. Expand the scope to "moving people along a vertical axis efficiently". What would a safe continuous elevator look like? Or could the solution for going up be different than the solution going down?

There's the Paternoster[1], which is essentially what you're talking about, but as it probably fairly obvious, they're pretty difficult to make both safe and efficient.

I'm reminded of the 'Moving Platform'[2] idea proposed for high-speed trains fairly recently though, and I wonder if there's anything there that could be reused.

What would a packet-switched elevator shaft look like? (Lots of small cars, which divert to individual 'station' queues for each floor, and latch onto a continuous moving belt at fixed intervals - shades of ATM)

[1] https://en.wikipedia.org/wiki/Paternoster

[2] http://www.designweek.co.uk/home/blog/moving-platforms/30277...

Couldn't a smart elevator system know (approximately) how many people are on each floor and thus make smart decisions based on that information (excluding the fact that a few energetic people may have taken the stairs to move one or two floors).

I LITERALLY had the same interest about a month ago. I live in a college apt with 8 floors and one elevator, and it's a pain sometimes. My inner hacker definitely wanted to sit down and crank out ways to better create an elevator algorithm

What are the engineering standards around this? Like inter-request arrival time distribution, the elevator passenger's floor destination distribution, etc etc?

Also, what about escalators? What standard arrival distributions do designers work with?

http://www.reddit.com/r/IAmA/comments/b1bpp/i_program_elevat...

It's bizarre to have just read this and then seen the news from New York a few minutes later. http://www.nydailynews.com/new-york/elevator-accident-kills-...

What the hell kind of behavior is that?

Machine learning is the best algorithm for this because the floors most used change based on day of week, time of day, day of month, day of year and buttons pressed. The elevator should be at the floor where there is most likely to be a person that hour.

Reply on news.ycombinator.com