One Cool Day Job: Building Algorithms For Elevators 203
McGruber writes "The Wall Street Journal has an article about Theresa Christy, a mathematician who develops algorithms for Otis Elevator Company, the world's largest manufacturer and maintainer of people-moving products including elevators, escalators and moving walkways. As an Otis research fellow, Ms. Christy writes strings of code that allow elevators to do essentially the greatest good for the most people — including the building's owner, who has to allocate considerable space for the concrete shafts that house the cars. Her work often involves watching computer simulation programs that replay elevator decision-making. 'I feel like I get paid to play videogames. I watch the simulation, and I see what happens, and I try to improve the score I am getting,' she says."
maybe they should release it as a game (Score:5, Funny)
I've been looking for a more sophisticated follow-up to SimTower for a while now. I'd buy Otis Elevator Tycoon.
Re:maybe they should release it as a game (Score:4, Interesting)
I've been looking for a more sophisticated follow-up to SimTower for a while now. I'd buy Otis Elevator Tycoon.
This gets modded up as a joke, but the interaction of tech and people within a mega-structure seems to me a solid foundation on which to build a game. But I can think of only Sim Tower and Startopia as examples.
Re:maybe they should release it as a game (Score:4, Interesting)
Actually, long ago I remember reading the story of SimTower, and it actually started out as an elevator simulator research tool! It turned out that the simulator was so much fun to play that someone had the bright idea to morph it into a video game.
Re:maybe they should release it as a game (Score:4, Informative)
Re: (Score:2)
I can believe that, as your tower eventually grows to the point where you're pretty much screwing around the elevator system the whole time, which is pretty much the point where I get bored with SimTower.
Re: (Score:2)
I just drop the rent on offices to the point where everybody's happy, even if they're profoundly miserable from standing in line for 3 days.
Re:maybe they should release it as a game (Score:5, Informative)
Optimizing is worthwhile, but adds a lot of complexity. You have to take into account for car locations, direction, speed, where car and hall calls are locatedand have to figure in such things as door times to calculate which car can service a hall call soonest.
As the author says, it's a set of interesting problems and I've had fun with it. Yes, the equipment I designed and wrote the software for is obsolete now, but there's a lot of it out there so I'm anticipating writing updates for a while longer as I head toward eventual retirement.
Re:maybe they should release it as a game (Score:4, Informative)
I highly question whether or not anyone pays any attention at all to the timings of these things; It seems that they would have more luck getting anyone who has ever milked a cow to design one, as they would have some inner sense as to how timing results in smooth flow. Improperly time your efforts and you get no milk and infuriate the cow.
( You can tell where I was raised here ).
Re: (Score:2)
In my case, the lights on a local hwy are sync'ed for good driving by the city. The issue is that every time you cross city lines (about 4 times in 6 miles) the timing changes again.
I have also heard stories where there was pressure on the city to raise the speed limit from say 45MPH to 50MPH for a bit of road. Well the city gave in and raised the limit, but didn't change the timing. Driving the speed limit will get you stuck at lights, but driving the limit the city wanted it to be will mean lots of greens
Re: (Score:3, Insightful)
Re: (Score:2)
Re:maybe they should release it as a game (Score:4, Insightful)
As the parent mentioned, timing involves multiple cars. It's the same thing in optimizing traffic light timings, they can't just factor one direction on a single road. You have to consider parallell roads, crossing roads, highway on- and off-ramp locations and all the traffic loads and the resultant traffic flow patterns. Needless to say, for even a moderate-size city, it's an incredibly complex problem.
Re: (Score:3)
The problem is light timing is a very hard problem. First off, take a basic city with a grid s
Re: (Score:2)
It is not even slightly difficult to beat today's results with a simple annealer. I would *love* for someone to pay me to fix this.
Re: (Score:2)
Re: (Score:2)
So if everyone in it wants to go to 3 or 0 and the elevator is full when it's on 27 then it shouldn't stop on 26-4, but it should just go on to 3 as fast as the limits allow so the elevator can get empty on 3 an 0 and go back up to pick new people up.
Re: (Score:2)
Yep, the hick that designed your traffic light sequencing system obviously didn't have years of training required to work with a highly complex distributed system:
http://xkcd.com/277/ [xkcd.com]
Re:maybe they should release it as a game (Score:5, Insightful)
You have to take into account for car locations, direction, speed, where car and hall calls are locatedand have to figure in such things as door times to calculate which car can service a hall call soonest.
I wished more elevators took into account how full they were. There's no point having a full or near full elevator serving external requests. A full elevator should only do internal requests. An elevator might guess how full it is by the load it is carrying, or even whether anyone got in for a previous request (door opened but nobody got in- load stayed the same and is high, but the request button was pressed again soon after the door closed - which normally means there was someone there but he/she did not go in despite wanting an elevator).
Nice to have but not so important would be a standardized way to cancel requests.
Nowadays I think some elevators are on "least energy used" and not "fastest service" at least based on the way they seem to behave...
Re: (Score:2)
Mitsubishi elevators do that, using a camera and image recognition to see how packed the car is.
They also optimized the door opening and movement sequence a lot. In newer ones if you watch carefully the doors close fairly quickly, then right at the last moment slow down and gently shut so that any trapped fingers won't be harmed. At the same time the car also starts moving and you can see the floor outside rising/falling. It only saves maybe two seconds but in a busy building with many floors that makes a b
Sounds good but . . . (Score:5, Funny)
I expect the job has its ups and downs just like any other.
Re: (Score:3)
Re: (Score:3)
Yes, but for every door that closes, a new one opens elsewhere.
Re:Sounds good but . . . (Score:5, Funny)
Careful, I hear it's easy to get shafted.
Re: (Score:2)
Just don't push her buttons!
Code that must "never crash", no? (Score:3, Insightful)
Re:Code that must "never crash", no? (Score:4, Informative)
News flash: State machines don't crash.
Re: (Score:2)
Re: (Score:2)
True, they just screw up in other undesirable ways like getting stuck in an infinite loop or one particular state.
Re: (Score:3, Informative)
She probably just writes the logic part not the code that realizes that logic. The actual code will be a finite state machine with certified logic blocks. Those dont crash.
Re:Code that must "never crash", no? (Score:5, Informative)
Each elevator has its own controller, which is relatively simple. When there's more than one elevator, there's also a group controller, which makes the decisions about which elevator responds to which call. All the smarts are in the group controller.
Many elevators have a key switch for "independent service", which disconnects them from the group controller. Then they only respond to the buttons in the car. The group controller isn't necessary to basic elevator operation.
Re: (Score:3)
Elevator software is probably the most obvious use case for software with correctness proofs. Note that the elevator going up when you want to go down is not necessarily bad programming, the most efficient place to go next is not necessarily where the last person who entered the elevator wants to go.
Re: (Score:2)
parts that need to be a certified finite state machine
detect when at a floor and open doors only at safe times (when stopped at a floor unless overridden by fire key) and detect when car is over weight limit detect when fire alarm is active
parts that need to be really damned good code: always travel to specified floor number
parts that can be done with PHP and javascript
Re: (Score:2)
We don't use the term "crash" when talking about elevators.
Re: (Score:2)
Re: (Score:2)
And here I would have thought it would be things where loss of life could follow failure.
Re: (Score:2)
Generally when it happens to me it is a race condition, the elevator was idle but someone presses "summon" before I press "go".
Once in a while I will board an elevator going in the wrong direction to exploit the fact that many elevators consider getting people already inside to the right floor more important than serving passengers who are not on the elevator yet. That is antisocial of me, of course.
Re: (Score:2)
A lot of elevators do that - if the button pushed is going in the wrong way, they don't allow it to light up.
Then I've seen ones that do allow you to push it, but it will continue that way until the
Re: (Score:2)
Re: (Score:2)
The lifts at my workplace sometimes stop right at the floor I am, but stays there without opening the door for 30 seconds or so. I suspect the microcontroller crashes and recovers.
If (hospital elevator) (Score:2)
{
emit_audio_tone("Hey kid cut that out, people's lives might be at stake because you're playing in a place you shouldn't be playing.");
call_security("Kid pressed all the elevator floor again, go embarrass him to his parents.");
clear_all_floor_buttons();
}
Re: (Score:2)
Re:If (hospital elevator) (Score:4, Interesting)
Re: (Score:2)
My less than symbol got nixed because it was thinking I meant hypertext markup
You are welcome to use this one: < (written as < - all four characters required.)
Mathematician? (Score:5, Insightful)
Was a mathematician really needed for this job:
During the recent $550 million upgrade of the Empire State Building, Ms. Christy was asked whether she could help get more people up to the observation deck. She said she couldn't get more people into a car but could move them up more quickly. So she increased the elevators' speed by 20%, to 20 feet per second. Now the cars can rise 80 floors in about 48 seconds, 10 seconds faster than before.
Isn't making the elevator go faster a job for an engineer? Does one really need to be a mathematician to know that a faster elevator moves people faster?
Re: (Score:2)
Should be a CS job, really. All you need to do is modify the speed-up loop. [thedailywtf.com]
Re: (Score:2)
It might be one of those weird things where the faster it's going the longer it takes to come to a stop, so going faster makes sense if there are calls from fewer floors but not if someone wants to board at every one. Or something.
We actually use different speeds for... (Score:2)
Re:Mathematician? (Score:5, Interesting)
A professor once described to me an elevator system at his former place of employment that used machine learning to try and anticipate where the elevator should be when not in use. At the start of the day, for example, the elevators should rest on the ground floor, so that they can collect people going up; similarly, toward the end of the day, they should rest at the top, since the overwhelming majority of people would be going down.
In a real-world setting you may have other phenomena that actually need to be learned, such as different groups taking lunches at set times of day, large meetings that cause several floors to congregate on one, et cetera. This problem can be considered from several different angles within ML; either as a regression problem or classification, for example.
Speed also needs to be optimized not just based upon the desire to reach the destination quickly, but also considering the rate at which the mechanisms will wear out, the energy consumption caused by more rapid movement, and to encourage people to use the stairs.
Given the potential complexity of how many parameters and models can potentially be considered... yeah, you want someone with a serious background in applied optimization, statistics, or artificial intelligence.
Re: (Score:3)
http://hitchhikersguidetoearth.wikia.com/wiki/Sirius_Cybernetics_Corporation [wikia.com]
Re: (Score:2)
A professor once described to me an elevator system at his former place of employment that used machine learning to try and anticipate where the elevator should be when not in use.
I wonder how a machine learning program deals with the 10 year old who thinks it is funny to press every single floor button then get off on a random stop. Usually when at least half the building's population is running 5 minutes late for their flight.
Re:Mathematician? (Score:4, Insightful)
One fairly new building in south Manhattan has a system where you type the number you want to go to before entering the elevator waiting area, and it tells you what door to wait in front of. When the elevator arrives it lists the floors it will stop at. It seems to optimize for minimal elevator usage, minimal wait times, no overcrowding, etc. Once the elevator system has a little more information it can do a lot better.
Re: (Score:3)
That is pretty standard, we have those in New Zealand which is a pissy tiny little country.
Re: (Score:2)
Whereabouts? Granted, I don't work in an office tower, but I've never seen one. In fact, I don't actually think I've seen any smart elevators at all!
They just seem to respond to a call button, and go to the floors that people have selected. Once at the final floor the elevators just seems to hand around on the floor it stopped on. Same when I've travelled to the US.
The smartest thing I've seen elevators do is return the the ground floor (or lobby, or whatever the busiest floor is) to wait.
Re: (Score:2, Insightful)
Re: (Score:2)
Exactly, moreover there isn't any "optimal" solution.
This is an applied science & engineering problem. People will solve it by developing self-learning algorithms but based on methods, assumptions and data which are customized to the specific installation. Actual experience doing this for many years for paying customers is important. Methods need to be robust to changing assumptions and changing uses.
I work in machine learning and applications for business (not elevators). The real metric which counts
Re: (Score:2)
If the elevator can make stops along the way, it probably refers to mean travel time, and it's an entirely different problem.
That being said, the "surfboard feature" is really, really, old. A lot of elevators have on-demand overrides which prevent intermediate stops. So the article might just be an infomercial for the elevator company after all.
Re:Mathematician? (Score:5, Insightful)
Isn't making the elevator go faster a job for an engineer? Does one really need to be a mathematician to know that a faster elevator moves people faster?
I suspect that the problem here is a failure on the part of the article writer. The author was probably just looking for any sort of answer to 'What's the most famous building you've ever done any work for?', rather than 'what's the most mathematically-interesting part of your job?'
It's also possible that there's a little bit of complexity being glossed over here. For the Empire State Building, visitors take up to three consecutive elevator rides to get to the observation decks: one to get up to the 80th floor, another from 80 to 86 and the main observation deck (though the hearty can take the stairs), and an optional, extra-charge trip from 86 up to the topmost observation area on 102. Visitors form queues for tickets, security, and each elevator ride (both up and down).
While speeding up any of the elevators might seem like a good thing, it runs the risk of causing crowding and bunching of passengers waiting for the now-overloaded next stage. Making one set of elevators faster could increase wear and tear on those elevators (and increase both energy use and passenger discomfort) without improving overall throughput; I can see how there might be some serious mathematical optimization going on there. As well, it's possible that our mathematician was involved in optimizing all of the building's elevator speeds and timings, and not just the elevators dedicated to observation deck service: a much more difficult optimization problem.
Re: (Score:2)
Re: (Score:2)
The engineer knows how to make the elevator faster.
The mathematician knows how to make it move it less for the same result.
If both work together the effects multiply, since they are completely orthogonal.
As some physicist who converted to building control and analysis systems, i find it surprising how much mathematics you need to analyze the optimum point for control. It is even more amazing how complicated it is to predict the outcome of an investment, given different control strategies.
As it turns out, th
MLT, fuckhead (Score:2)
It certainly doesn't when it's expressed in feet per second.
In the elevator trade... (Score:2)
Never never never... (Score:3)
... say "I feel like I get paid to play videogames." That basically says "please cut my salary by $30,000.00"...
Future algorithm ... (Score:5, Funny)
Re: (Score:2)
... when elevators can move in more than one plane: 10 PRINT CHR$ (205.5 + RND (1)); : GOTO 10
I tried using an elevator based on that once. It took me all over the place, and gave the appearance of doing so intelligently, but I never actually managed to arrive where I wanted to be. I eventually caved and shelled out the money for a proper Wonkavator; Haven't had a problem since, except for the occasional child disappearing while using it.
Re: (Score:2)
... when elevators can move in more than one plane: 10 PRINT CHR$ (205.5 + RND (1)); : GOTO 10
I tried using an elevator based on that once. It took me all over the place, and gave the appearance of doing so intelligently, but I never actually managed to arrive where I wanted to be.
Yes. Many a day I used the stairs.
I eventually caved and shelled out the money for a proper Wonkavator; Haven't had a problem since, except for the occasional child disappearing while using it.
So there's an up-side.
P.S. Let me know when you finish your training, girl, and we'll talk... :-)
Improve the score!? (Score:2)
What do you mean improve the score?
You mean the programmers aren't even capable of solving the problem of finding the best solution?
Even if it's NP-complete, it's not like there are so many elevators that you can't find the best solution in reasonable time.
Re: (Score:2)
Sure, I'm a consultant. You can hire me for the right price, no problem.
and her iPOD has (Score:4, Funny)
one certain Aerosmith song on it.
Otis? Hmmm... (Score:3)
Rumour has it that Otis have (or at least had) a UK office in the town of Reading (for our American cousins, the town is pronounced "Redding").
Their receptionist answered the phone with "Hello, Otis Reading?"
Re: (Score:2)
Your American cousins say, "Thanks, but we really do know that. We've got Reading and North Reading here in MA. Now try figuring out how we pronounce Dorchester and Worcester."
Most needed optimization (Score:3)
Multiple forced door closings when people hold the door open to chat.
Second most needed optimization:
Give me an ETA so I know when I'd be better off taking the stairs.
Most annoying feature that needs to be removed (some elevators):
If you'd manually hold the door for someone (those door open buttons are hard to find in a hurry sometimes. I believe there's even a paper on it), the door would then close v_e_r_y s_l_o_w_l_y while beeping reproachfully at you. The last thing I need first thing in the morning is passive-aggressiveness from a machine.
It's called nudging in the trade... (Score:3)
Re: (Score:2)
In most of the elevators I have used in the US, they don't even work. I am really suspicious that they are even connected to anything and are just there as a placebo. Other countries don't seem to have a problem with this and the door close button closes the door.
Re: (Score:2)
Yes but.... (Score:5, Funny)
Does it also simulate who farted?
I don't think (Score:2)
I don't think there's any intelligent code running the elevators in my building.
I live in a 14 floor apartment building. I frequently come home in the evenings to see both elevators just chilling idle on the 14th floor....
It makes me want tear my hair out.
The elevators in the high rises I work in don't seem to have these problems. The building I specificlaly work in most of the time has 6 elevators though so its less of an issue though.
There are still a lot of relay controllers in use. (Score:2)
Re: (Score:2)
I don't think there's any intelligent code running the elevators in my building.
I live in a 14 floor apartment building. I frequently come home in the evenings to see both elevators just chilling idle on the 14th floor....
Does your building have any security? Maybe the policy is for the elevators to idle at the top floor after dark so that people coming in will have to hang around the lobby a certain amount of time before getting into the elevator?
Or maybe it's been determined that in a residential building, more people tend to be at home at nighttime than in during the day, which means that at night, residents are more likely to enter the elevator on a floor higher than the first floor, which means it's more efficient to ha
Pressing both the down and up buttons (Score:2)
I'd like to hear her comments on people that press the up and down buttons when they simply want to go down. It irritates the hell out of me because I believe this practice increases the average travel time for people already on the elevator as well as the impatient double-button-pusher himself.
For example, say someone on floor 6 (who wants to go to the ground floor) presses both buttons and then gets on while the elevator is on its way up. The extra delay caused by the unnecessary stop at floor 6 means,
Re: (Score:2)
The directional info from the buttons should only be used when the elevator is in use and it matters whether the elevator is going up or down. If, in that case, you call an elevator and don't get in this results in a useless extra delay for those in the elevator.
Slightly worrying lift (Score:2)
The lift (UK speak for elevator) I have at work is reasonably sensible - there's only 4 floors in the building, so it tends to keep one lift on the ground floor and one on the 4th floor when idle. However, I had a few fun things happen:
* All the lights went out in the lift as I was travelling in it, but it did get to the right floor and open the door.
* The computerised voice announced "floor five" one day, which is creepy when I got off at the top (4th) floor!
* The lift voice frequently says "please mind th
My retirement job (Score:2)
The elevators in my building are user-hostile. Door closing delays set so short that if the first person isn't fast, they'll close after the stream of people leave but before the first person enters. And while they won't actually cut you in half (that I know of), they will give you a bruise if you go in while they're closing. One elevator goes both up and down from the lobby but has no indicator for which way it's going. The annoying door beeper has no delay; it beeps whenever anyone is in the doorway.
Noooooo! (Score:2)
Re: (Score:2, Interesting)
Elevator pseudocode is the heart of many a CS course. And CS courses were promised to be devoid of practical application.
Little known fact--if you are on a moving elevator and start to force the doors open, it will stop in between floors. Just don't try to get out when the elevator floor is high enough above a building floor that the shaft is exposed. How do I know? In the words of my roommate, I was shafted, literally -- fell into the shaft on the 14th and caught my self on the cables level with the 11th floor doors. My partner (in elevator hacking) quickly ran down the three flights of stairs, I was able to swing over,
Re: (Score:2)
I'm having difficulty believing that:
A) You're stupid enough to force open the doors whilst the lift is moving.
B) Also stupid enough to step forward when the lift is between floors.
C) Also stupid enough to fall through the gap.
D) There is a gap large enough to easily fall through.
Re: (Score:2)
Ooops, the most unbelievable bit is due to physics, you would not be able to catch on to anything after falling 3 floors, especially not a cable, Mr Indiana Jones.
Efficiency may include power consumption (Score:2)
Firmware upgrade? (Score:2)
They need to release some kind of upgrade for existing elevators. At my office building of 35 floors with Otis elevators. When an elevator is already stopped at a certain floor. Instead of opening the door immediately when you press a button, the elevator leaves immediately and you need to wait forever for another elevator to arrive since the other elevators think you've already left. The solution is then to press both up and down buttons, irritating the hell out of every one in the building.
She should look at my jobs elevators (Score:2)
Re:Harddisks use something like it (Score:5, Interesting)
That's an undergraduate level general optimization problem.
The one in TFA is a graduate level optimization under a particular set of data constraints. So the generally optimal algorithm for elevators has to a assume a random distribution of people to be picked up and destination floors (head is in a random location wants data from some other random location) - but in practice you may be need sequential access or the like. With elevators, I would expect that in mornings in residential buildings people want to empty out so the 'resting' point would to close to 2/3rds or 3/4ths of the way up, but in the evenings it would be the reverse direction, and business would be the reverse of residential. Schools have a somewhat more random use of bursty every hour up and down, and really big businesses may want dedicated elevators between floors shared by particular companies because there's a lot of daily movement within the floors of a company but not so much outside their area.
Lunch of course adds another complication.
There's a lot of neat work into simulating the data for a building that doesn't exist yet, or measuring the data for a building that exists but has a bad algorithm. And then trying to tailor your elevator to the specific behaviours that actually exist.
Re:Harddisks use something like it (Score:4, Interesting)
So the generally optimal algorithm for elevators has to a assume a random distribution of people to be picked up and destination floors
It seems to me that assuming a poisson distribution [wikipedia.org]) or other random distribution, is a bad assumption. Passengers would be likely to arrive in clumps as meetings ended or buses arrived, and some destination floors would be far more popular than others
One thing that would help, but I have never seen, would be a way to cancel a button push (either the call button, or a floor button inside the elevator). Buttons are often pushed in error, resulting in wasted time.
I once heard a funny story about an engineer assigned to optimize an elevator system. The building supervisor had received numerous complaints about the elevator delays, so he told a young engineer to fix the problem. The engineer tried several adjustments, but still had just as many complaints. So he had mirrors installed next to each elevator, so people could adjust their hair, tie, clothing or whatever while they were waiting. Since people now had something to do while they were waiting, most of the complaints stopped.
Re: (Score:2)
It seems to me that assuming a poisson distribution [wikipedia.org]) or other random distribution, is a bad assumption.
it definitely is a bad assumption.
But if you are trying to solve the general problem of where to position an elevator or a disk head in general you have to. That's why it's an 'undergraduate' level problem. The serious research today comes in knowing what the real data will be like, and whether or not you can optimize for real data rather than an average best case for any arbitrary data set.
Re: (Score:2)
Re: (Score:2)
One thing that would help, but I have never seen, would be a way to cancel a button push (either the call button, or a floor button inside the elevator). Buttons are often pushed in error, resulting in wasted time.
And also you've got to take into account the fun kids could have cancelling everyone's requests, and sending them back to the ground floor :)
Well, the ONLY diff. I see? (Score:3, Interesting)
Is that the resting place of the diskdrive head probably doesn't vary (like you describe for start of workday, lunch, & of course, quitting time - moving it to the most optimal spots during certain daily time periods).
Afaik? The HDD tends to try to keep the read-write heads in the CENTER of the disk (or rather, center of the filemass (moved to outermost fastest tracks with defraggers for fastest access/seek due to larger rotational diameters)).
You can't "move" the MFT$ (master file table) & certain
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Not all elevators have load weighting.. (Score:2)
Re: (Score:2)
AND for cases where the elevator is not near the maximum weight but effectively full for other reasons[1] the elevator can guess if:
1) the load is high enough
2) the load does not change after the doors open (nobody gets in or out).
3) the external button is pressed again after the doors closed (someone actually is there who wants an e