AI Planning for Destination Control in Lifts

In a destination control system, a passenger enters his/her desired destination floor via some input device and is then allocated to a specific lift in the group of lifts. Since the destination is known in advance, new opportunities to optimize the travel routes of lifts become available. Additionally, individual service requirements for each passenger can be defined:

• some passengers are subject to access restrictions and are not allowed to reach certain floors,
• passengers can be declared as VIPs, which have to be served with the highest priority,
• passengers can request a direct transport to their destination without going through intermediate stops,
• passengers can belong to conflicting groups that should never travel together in the elevator,
• passengers could also be declared as requiring an attendant during the travel, which could be selected from the currently known passengers. Given this requirement, the planning systems had to make sure that always an accompagnying person is present in the elevator, but the attendant could even change during the trip.

Based on AI Planning techniques, a new intelligent lift controller has been developed that is currently brought to the market.

A model of this domain in PDDL was used in the final round of the AIPS2000 planning competition where Schindler Lifts Ltd. donated awards for the best performing planning systems in this domain during the competition.

• A collection of 30 test problems in PDDL ranging from 2 floors, 1 passenger up to 60 floors, 30 passengers. The problems use a simplified representation of the domain, which is suitable to all planning systems, which can handle conditional effects, but only simple conjunctive preconditions.
• A collection of 30 test problems in PDDL ranging from 2 floors, 1 passenger up to 60 floors, 30 passengers, but exploiting the full representation of Miconic10 including Liftloc extensions. This adds full first order preconditions to the simplified domain.
• A generator programm written in C that allows to generate Miconic 10 planning problems, provided by Joerg Hoffmann. For further explanation have a look at the Readme file included in this gziped tar archive.

Publications:

• J. Koehler , K. Schuster: Elevator Control as a Planning Problem, AIPS 2000, pages 331-338.

  Abstract: The synthesis of elevator control commands is a difficult problem when new service requirements such as VIP service, access restrictions, nonstop travel etc. have to be individually tailored to each passenger. AI planning technology offers a very elegant and flexible solution because the possible actions of a control system can be made explicit and their preconditions and effects can be specified using expressive representation formalisms. Based on the specification, a planner can flexibly synthesize the required control and changes in the specification do not require any reimplementation of the control software. In this paper, we describe the application and investigate how currently available domain-independent planning formalisms can cope with it.

• J. Koehler: From Theory to Practice: AI Planning for High-Performance Elevator Control, KI 2001, pages 459 -462 .

  Abstract: Offering an individually tailored service to passengers while maintaining a high transportation capacity of an elevator group is an upcoming challenge in the elevator business, which cannot be met by software methods traditionally used in this industry. AI planning offers a novel solution to these control problems: (1) by synthesizing the optimal control for any situation occurring in a building based on fast search algorithms, (2) by implementing a domain model, which allows to easily add new features to the control software. By embedding the planner into a multi-agent system, real-time interleaved planning and execution is implemented and results in a high-performing, self-adaptive, and modular control software.

• J. Koehler, D. Ottiger: An AI-based Approach to Destination Control in Elevators, AI Magazine, 23(3): pages 59-78, Fall 2002.

  Abstract: Not widely known by the AI community, elevator control has become a major field of application for AI technologies. Techniques such as neural networks, genetic algorithms, fuzzy rules, and, recently, multi-agent systems and AI planning have been adopted by leading elevator companies not only to improve the transportation capacity of conventional elevator systems, but also to revolutionize the way in which elevators interact with and serve passengers. In this article, we begin with an overview of AI techniques adopted by this industry and explain the motivations behind the continuous interest in AI. We review and summarize publications that are not easily accessible from the common AI sources. In the second part, we present in more detail a recent development project to apply AI planning and multi-agent systems to elevator control problems.

• Information Brochure about Schindler ID, the product based on the AI planner