Group Elevator Control
We have developed decision-theoretic solutions for (western-style) re-assignment elevator scheduling and minimal-energy elevator scheduling.
Background & Objective: Optimal assigning multiple elevator cars to pick up multiple waiting passengers is probably an NP-hard problem. In "Japanese-style" scheduling, all assignments are final. In "western-style" re-assignment scheduling, all assignments can be revised opportunistically. Although a much harder problem, advances in this area will be useful for increasing market share in the U.S. and E.U.
Technical Discussion: The optimal approach is to calculate the exact costs of a decision, marginalizing over all future scenarios compatible with unknown or uncertain variables. These variables include future passengers, unspecified destinations of current passengers, and the number of waiting passengers. The full calculation is intractable but in recent years we have found efficient algorithms to compute most of these marginalizations in the Japanese setting. This year we found a set of proxy costs that allow the "Japanese-style" solution to be used in the inner loop of a very efficient branch-and-bound solution for the "Western-style" re-assignment problem. We ported this algorithm to "ELEVATE 6.0", which is now the most commonly used elevator simulator and control testbed in the industry. MERL's western-style algorithm strongly outperforms all other controllers available on this platform, reducing waiting times by 10-40% and increasing the throughput of each shaft.
In an unrelated and mainly academic result, we have also developed an exact solution for the minimal-energy schedule, assuming symmetric up and down energy costs.
Publications:
Technology Areas:
Sensor and Data Systems
Artificial Intelligence
Modification Date: September 12, 2007