Implementation of dispatching algorithms for elevator systems using reconfigurable architectures

ABSTRACT

Elevator Group Control Systems (EGCSs) manage multiple elevators in a building transporting efficiently passengers. The performance of an EGCS is measured by means of several metrics such as the average waiting time of passengers, the percentage of the passengers waiting more than some predetermined time, power consumption, among others. Four elevator dispatching algorithms are analyzed and implemented using reconfigurable architectures based on FPGAs. The system is based on Local Controller Systems (LCSs), one for each elevator, and a protocol based on an RS485 network for interconnecting the LCSs. The FPGAs implement the LCSs. A Java interface was implemented for testing and monitoring the system and the EGCS function. The novelty of this approach is that the LCSs are capable to run the different dispatching algorithms, which are suitable for different passenger traffic situations, while the EGCS only must determine the best algorithm to be run in each LCS. The data traffic in the network is reduced given that the EGCS is not directly involved in calculating next floors to be visited. The algorithms were described in VHDL and implemented on Spartan3 FPGA based boards.

REFERENCES

• 1: S. G. Akl. Parallel Computation:Models and Methods. Prentice-Hall, 1997.
• 2: G. C. Barney, S. M. dos Santos, Elevator traffic analysis, design and control. Peter Peregrinus, 1985.
• 3: J. Becker and R. W. Hartenstein, Configware and Morphware going mainstream. J. of System Architecture 49:127--142, 2003.
• 4: Y. Cho, Z. Gagov, W. Kwon. Elevator group control with accurate estimation of hall call waiting times. IEEE Proc. Int. Conf. on Robotics and Automation, pp. 447--452, 1999.
• 5: Digilent Inc. Available at www.digilentinc.com. Accesse in 2005.
• 6: A. Fujino, T. Tobita, K. Segawa, K. Yoneda. An Elevator Group Control System with Floor-Attribute Control Method and System Optimization using Genetic Algorithms. IEEE Trans. Ind. Elect. 44(4):546--552, 1997.
• 7: Muller-Glaser, K. D.; Frick, G.; Sax, E.; Kuhl, M. Mutiparadigm Modeling in Embedded System Design. IEEE Transactions on Control System Technology 12(2): 279--292,
• 8: D. Hauptmeirer, S. O. Krumke, J. Rambau and H.-C. Wirth. Euler is standing in line dial-a-ride problems with precedence-constraints. Discrete Applied Mathematics 113:87--107, 2001.
• 9: T. Hikihara, S. Ueshima. Emergent synchronization in multi-elevator system and dispatching control. IEICE Trans. on Fund. of Electron. Comm. and Comp. Scienc., E80-A(9):1548--1553, 1997.
• 10: C. Kim, K. A. Seong, H. Lee-Kwang, J. O. Kim. Design and Implementation of a Fuzzy Elevator Group Control System. IEEE Transactions on Systems Man and Cybernetics Part A 28(3):277--287, 1998.
• 11: ModelSim. Available at www.model.com. Accesse in 2005.
• 12: D. Nikovsky, M. Brand. Decision-Theoretic Group Elevator Scheduling. AAAI Proc. 13 th Int. Conf. on Automate Planning and Scheduling, pp. 133--142, 2003.
• 13: D. L. Pepyne, C. G. Cassandras. Optimal Dispatching Control for Elevator Systems during Up-peak Traffic. IEEE Trans. Contr. Syst. Technol. 5(6):629--643, 1997
• 14: B. A. Powell, J. N. Williams. Elevator dispatching based on remaining response time,US Patent, #5. 146.053, 1992.
• 15: B. Seckinger, J. Koehler. Online-Synthese von Aufzagssteuerungen als Plannungsproblem. Workshop Planen und Konfigurieren, Int. Bericht des Instituts fur Informatik der Universität Wurzburg, pp. 127--134, 1999.
• 16: M. Siikonen, J. Leppala. Elevator traffic pattern recognition. Proc. 4 th Int. Conf. Fuzzy Systems Association, pp. 195--198, 1991.
• 17: M. Siikonen. Elevator Group Control with Artificial Intelligence. Research Report A67. System Analysis of Technology, Helsinki University of Technology. 1997.
• 18: M. Siikonen. Planning and Control Models for Elevator in High-Rise Buildings. Research Report A68. System Analysis of Technology, Helsinki University of Technology. 1997.
• 19: V. Sklyarov, I. Skliarova, P. Almeida, M. Almeida. Desing Tools and Reusable Libraries for FPGA-Based Digital Circuits. IEEE Proc. Euromicro Symposium on Digital System Desing, pp. 255--263, 2003.
• 20: G. R. Strankosch. Vertical transportation:elevators and escalators. Jhon Wiley & Sons, 1998.
• 21: H. Ujihara, S. Tsuji. The revolutionary AI-2000 elevator group-control system and the new intelligent option series. Mitsubishi Electric Advance, 45:5--8, 1988.
• 22: H. Ujihara, M. Amano. The latest elevator group-control system. Mitsubishi Electric Adv., 67:10--12, 1994.
• 23: Xilinx Corporation. ISE User Guide. Available at www.xlinx.com. Accessed in 2005.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

General Terms:
Algorithms, Design, Performance

Keywords:
elevator group control system, field programmable gate arrays