One Cool Day Job: Building Algorithms For Elevators

← Back to Stories (view on slashdot.org)

One Cool Day Job: Building Algorithms For Elevators

Posted by timothy on Saturday December 1, 2012 @07:52AM from the getting-it-up-is-only-half-the-battle dept.

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."

40 of 203 comments (clear)

Min score:

Reason:

Sort:

maybe they should release it as a game by Trepidity · 2012-12-01 07:56 · Score: 5, Funny

'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.
I've been looking for a more sophisticated follow-up to SimTower for a while now. I'd buy Otis Elevator Tycoon.

--
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
1. Re:maybe they should release it as a game by westlake · 2012-12-01 08:21 · Score: 3, 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.
2. Re:maybe they should release it as a game by plover · 2012-12-01 09:35 · Score: 3, 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.
  
  --
  John
3. Re:maybe they should release it as a game by the_rajah · 2012-12-01 10:48 · Score: 5, Informative
  
  I designed the hardware and wrote the code for a much smaller elevator company for 25 years... All written in assembly language running on an 8085 CPU with 256 bytes (Yes, bytes) if RAM and 8K bytes of EPROM. It doesn't take much to handle the basics when you're using assembly language. I've done up to 26 stops in a multi-car group with that setup. Each elevator is independent and can run on its own, but they communicate with each other to handle dispatching so multiple cars coordinate their activity.
  
  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.
  
  --
  
  "Do the Right Thing. It will gratify some people and astound the rest." - Mark Twain
4. Re:maybe they should release it as a game by anubi · 2012-12-01 11:52 · Score: 4, Informative
  
  I sure wish cities would hire guys like you to work on their traffic lights.
  
  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 ).
  
  --
  "Prove all things; hold fast that which is good." [KJV: I Thessalonians 5:21]
5. Re:maybe they should release it as a game by T-Ranger · 2012-12-01 12:20 · Score: 3, Informative
  
  I'm not sure about that, but the original Sim City *was* based on Will Wight's previous project, Raid on Bungeling Bay. Or rather, how his Bungeling Bay map editor was as much fun as the end game.
6. Re:maybe they should release it as a game by Shinobi · 2012-12-01 13:52 · Score: 3, 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.
7. Re:maybe they should release it as a game by Culture20 · 2012-12-01 14:22 · Score: 2, Insightful
  
  It's usually the other way around. The lights are timed for 5-10 miles over the speed limit, and cops use it as a constant stream of speeders for ticketing.
8. Re:maybe they should release it as a game by tlhIngan · 2012-12-01 20:35 · Score: 2
  
  I sure wish cities would hire guys like you to work on their traffic lights.
  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.
  The problem is light timing is a very hard problem. First off, take a basic city with a grid style street layout. You can optimize the greens for flows in certain directions, but then the cross streets often get blocked up because they don't have an optimized pattern.
  You can try optimizing flows differently - perhaps two get timed greens southbound because everyone's heading home (and they turn northbound int he morning rush), while a third street goes the other way. If you go southbound on that, you'll hit lights (and it's actually faster to navigate to the other streets than taking a direct route). Yes, the longer way can be faster because only some streets have timed lights in order to not cause total gridlock looking for an optimal solution. The goal is to find which ones are timed in which direction at what times (because the primary flow differs due to morning and afternoon rushes), and to see if the time it takes to navigate to the longer but timed routes is faster than the time it takes to go by the obvious route. In some places, the lights are timed in a circle (one street north, one street west, one street south, one street east) so choosing the optimal path may mean going the opposite direction to join it quicker.
  Next, you have complications like parking, left/right turn lanes/lights/not-allowed. And idiot drivers who floor it at the green to hit the red in front, or more likely, those who see the light ahead is red, and don't move much above creeping speed to not have to slow down much.
  And the lights are also timed to a speed - a road with a limit of 40 might have its lights timed to 30.
  And yes, city planners have a headache of it all - allow a bicycle lane here, mess up traffic there, roadwork forcing diversions, etc. Illegal parkers and pickup/dropoffs don't help, either.
  Elevators are easy - when making decisions, you have all the information ahead of who - who's calling for an elevator, and which floors the elevator must stop at. Some more intelligent systems may even schedule elevators by requesting that those who call an elevator enter in their destination floor as well.
9. Re:maybe they should release it as a game by Jedi+Alec · 2012-12-01 22:17 · 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.
  
  --
  
  People replying to my sig annoy me. That's why I change it all the time.
10. Re:maybe they should release it as a game by TheLink · 2012-12-01 22:45 · Score: 4, 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...
  --
  
  Too many replies beneath your current threshold
Sounds good but . . . by Anonymous Coward · 2012-12-01 08:04 · Score: 5, Funny

I expect the job has its ups and downs just like any other.
1. Re:Sounds good but . . . by Hognoxious · 2012-12-01 08:12 · Score: 5, Funny
  
  Careful, I hear it's easy to get shafted.
  
  --
  Confucius say, "Find worm in apple - bad. Find half a worm - worse."
2. Re:Sounds good but . . . by davester666 · 2012-12-01 08:51 · Score: 2
  
  Just don't push her buttons!
  
  --
  Sleep your way to a whiter smile...date a dentist!
3. Re:Sounds good but . . . by Delarth799 · 2012-12-01 09:13 · Score: 2
  
  Sometimes you need to think outside of the box
4. Re:Sounds good but . . . by SeaFox · 2012-12-01 11:27 · Score: 2
  
  Yes, but for every door that closes, a new one opens elsewhere.
Code that must "never crash", no? by dryriver · 2012-12-01 08:04 · Score: 2, Insightful

I'm guessing that the hardest part of the job is writing code that does not crash, possibly leaving elevator riders stranded between floors, or going up when they want to go down. Over the years Otis must have developed a pretty good elevator usage simulator that plays through millions of possible elevator use scenarios, and tries to find one that either crashes or confuses the system. If yes, the developers responsible for that "possibility simulator" should have been named in the article alongside "The Elevator Algorithm Lady". They should have gotten some credit where credit is due...

--
Why did the chicken cross the road? Because Elon Musk put an AI chip in its head.
1. Re:Code that must "never crash", no? by Anonymous Coward · 2012-12-01 08:11 · Score: 4, Informative
  
  News flash: State machines don't crash.
2. Re:Code that must "never crash", no? by Anonymous Coward · 2012-12-01 08:19 · 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.
3. Re:Code that must "never crash", no? by Animats · 2012-12-01 08:22 · Score: 4, 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.
4. Re:Code that must "never crash", no? by amorsen · 2012-12-01 09:03 · Score: 2
  
  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.
  
  --
  Finally! A year of moderation! Ready for 2019?
Mathematician? by hawguy · 2012-12-01 08:05 · Score: 4, 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?
1. Re:Mathematician? by Samantha+Wright · 2012-12-01 08:19 · 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.
  
  --
  Bio questions? Ask me to start a Q&A journal. Computer analogies available for most topics!
2. Re:Mathematician? by dugjohnson · 2012-12-01 08:46 · Score: 2
  
  But can she program A Happy Vertical People Transporter?
  http://hitchhikersguidetoearth.wikia.com/wiki/Sirius_Cybernetics_Corporation
  
  --
  My brain is overly lubricated
3. Re:Mathematician? by samkass · 2012-12-01 10:06 · Score: 3, 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.
  
  --
  E pluribus unum
4. Re:Mathematician? by Idarubicin · 2012-12-01 10:08 · Score: 4, 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.
  
  --
  ~Idarubicin
5. Re:Mathematician? by DiSKiLLeR · 2012-12-01 11:09 · Score: 2
  
  That is pretty standard, we have those in New Zealand which is a pissy tiny little country.
  
  --
  You can tell how powerful someone is by the magnitude of the crime they can commit and be able to get away with.
Re:If (hospital elevator) by GoodNewsJimDotCom · 2012-12-01 08:08 · Score: 3, Interesting

I just realized something else, everyone would be playing with the elevator even more if it talked to you... so maybe it isn't a good thing to emit a sound... Maybe just call security.

--
God spoke to me
Never never never... by Ossifer · 2012-12-01 08:44 · Score: 2

... say "I feel like I get paid to play videogames." That basically says "please cut my salary by $30,000.00"...
Re:If (hospital elevator) by tftp · 2012-12-01 08:45 · 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.)
Future algorithm ... by fahrbot-bot · 2012-12-01 08:52 · Score: 4, Funny

... when elevators can move in more than one plane: 10 PRINT CHR$ (205.5 + RND (1)); : GOTO 10

--
It must have been something you assimilated. . . .
Re:Harddisks use something like it by Sir_Sri · 2012-12-01 09:04 · Score: 4, 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.
and her iPOD has by cellocgw · 2012-12-01 09:52 · Score: 3, Funny

one certain Aerosmith song on it.

--
https://app.box.com/WitthoftResume Code: https://github.com/cellocgw
Otis? Hmmm... by jimicus · 2012-12-01 10:08 · Score: 2

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?"
Most needed optimization by Richy_T · 2012-12-01 10:10 · Score: 2

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... by the_rajah · 2012-12-01 10:51 · Score: 2

You will most commonly find it in large urban areas like NY and Chicago. In the Midwest where I worked in the elevator business, it's rarely a requested feature because folks aren't in such a rush in general.

--

"Do the Right Thing. It will gratify some people and astound the rest." - Mark Twain
Yes but.... by guruevi · 2012-12-01 11:11 · Score: 4, Funny

Does it also simulate who farted?

--
Custom electronics and digital signage for your business: www.evcircuits.com
Re:Harddisks use something like it by ShanghaiBill · 2012-12-01 11:21 · Score: 3, 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) 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.
Well, the ONLY diff. I see? by Anonymous Coward · 2012-12-01 12:54 · 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 other system files during usermode after all!
(At least NOT during usermode access to accomodate for times it *MIGHT* be different for differing work patterns (say you work @ home, & do your work the 1st 8 hours you wake up, & then the rest is family usage, your leisure, etc./et al)).
However, with NTFS & probably other modern filesystems?
MFT$ is placed in the MIDDLE of the "filemass" though for "optimality", since it's needed for file accesses of any kind (time of access stampings too, etc.) & then binary search patterns (like NTFS uses in b-tree seeks) do the rest!
I find this algorithm pretty amazing & VERY "common-sense", & that elevator algorithm & its variants, do one hell of a good job on QUEUEING UP REQUESTS, & then issuing them in the order the disk drive head passes over the areas concerned, in the most efficient order possible.
1 of its variants use 2 buffers (1 = currently being serviced requests, & 2 = upcoming requests to service): THIS seems like the smartest way to go about it imo @ least.
* Anyhow/anyways - I didn't think you were being a jerk, I hope you feel the same way regarding myself...
(Actually? I thought you offered some decent enough points, but you MUST ADMIT, the algorithms here are AMAZINGLY similar & I didn't SAY they were the "exact same" either)
Plus - I'd wager since the one for HDD's is named "Elevator Algorithm", the harddisk folks GOT THE IDEA from folks like this lady!
APK
P.S.=> Lastly - Sorry: Not "graduate level student"/postgrad/postdoc etc., in CSC!
I got the AAS 60 credit hours outta the way & went to work in the field as a programmer back in 1994 onwards!
(I've been "chipping away @ the stone" since then, & am 90/120 credit hours into the B.S. in CSC currently, taking coursework here and there as time & money permit)...
... apk
Re:Noooooo! by Anonymous Coward · 2012-12-01 14:44 · 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, release the door catch and he opened the doors so I could swing out of the shaft...
As I was falling, my partner claims that he shouted "Nooooooo!", but I never heard him, I guess my reflexes were too busy getting a grip on the control cables?