One Cool Day Job: Building Algorithms For Elevators

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

Comments

maybe they should release it as a game

[Trepidity]

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

Re:maybe they should release it as a game

[westlake]

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

[plover]

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

[the_rajah]

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.

Re:maybe they should release it as a game

[anubi]

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

Re:maybe they should release it as a game

[T-Ranger]

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.

Re:maybe they should release it as a game

[Shinobi]

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:maybe they should release it as a game

[TheLink]

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

Sounds good but . . .

[Anonymous Coward]

I expect the job has its ups and downs just like any other.

Re:Sounds good but . . .

[Hognoxious]

Careful, I hear it's easy to get shafted.

Mathematician?

[hawguy]

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:Mathematician?

[Samantha Wright]

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:Mathematician?

[samkass]

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:Mathematician?

[Idarubicin]

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:If (hospital elevator)

[GoodNewsJimDotCom]

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.

Re:Code that must "never crash", no?

[Anonymous Coward]

News flash: State machines don't crash.

Re:Code that must "never crash", no?

[Anonymous Coward]

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?

[Animats]

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.

Future algorithm ...

[fahrbot-bot]

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

Re:Harddisks use something like it

[Sir_Sri]

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

[cellocgw]

one certain Aerosmith song on it.

Yes but....

[guruevi]

Does it also simulate who farted?

Re:Harddisks use something like it

[ShanghaiBill]

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?

[Anonymous Coward]

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