Motion Planning Method for Two Stacker Cranes in an Automated Storage and Retrieval System
Hisato Hino*, Yoshimasa Kobayashi**, Toshimitsu Higashi**,
and Jun Ota*
*Research into Artifacts, Center for Engineering (RACE), The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8568, Japan
**Murata Machinery, Ltd., 2 Nakajima, Hashizume, Inuyama-shi, Aichi 484-0076, Japan
In this paper, a motion planning method for two stacker cranes in an Automated Storage and Retrieval System (AS/RS) is proposed. For the cranes to operate cooperatively, they must perform tasks while avoiding collisions. In addition, the requirements, which include fast operation and short calculation time, must be satisfied, along with a specific mechanical constraint on the motion of the stacker cranes. For these problems, an approach is proposed in which a motion is generated on two levels. On the first, collision is avoided by using constraint on trajectories. A trajectory generated on this level ensures the shortest travel time. If a collision cannot be avoided on the first level, the system shifts to the second, in which heuristics are used for collision avoidance. The proposal is for highspeed heuristics based on a binary search. The effectiveness of the proposed algorithm is shown through simulations. The simulation results indicate that, in a layout of 60 racks in the horizontal direction and 10 in the vertical direction under standard task conditions, the method has an efficiency of 1.91 with respect to a single crane system and 1.66 seconds for the motion planning of one task when a computer with a 3.0 GHz CPU is used.
-  K. J. Roodbergen and I. F. A. Vis, “A survey of literature on automated storage and retrieval systems,” European J. of Operational Research, Vol.194, Issue 2, pp. 343-362, 2009.
-  Y. A. Bozer and J. A. White, “Travel time models for automated storage/retrieval systems,” IIE Trans., Vol.16, Issue 4, pp. 329-338, 1984.
-  B. A. Peters, J. S. Smith, and T. S. Hale, “Closed form models for determining the optimal dwell point location in automated storage and retrieval systems,” Int. J. of Production Research, Vol.34, Issue 6, pp. 1757-1771, 1996.
-  A. Keserla and B. A. Peters, “Analysis of dual-shuttle automated storage/retrieval systems,” J. of Manufacturing Systems, Vol.13, Issue 6, pp. 424-434, 1994.
-  R. D. Meller and A. Mungwattana, “Multi-shuttle automated storage/retrieval systems,” IIE Trans., Vol.29, Issue 10, pp. 925-938, 1997.
-  C. J. Malmborg, “Interleaving models for the analysis of twin shuttle automated storage and retrieval systems,” Int. J. of Production Research, Vol.38, Issue 18, pp. 4599-4610, 2000.
-  I. Potrĕ, T. Lerher, J. Kramberger, andM. Šraml, “Simulation model of multi-shuttle automated storage and retrieval systems,” J. of Materials Processing Technology, Vols.157-158, Issue 20, pp. 236-244, 2004.
-  S. Tanaka, “A hybrid algorithm for the input/output scheduling problem of multi-shuttle AS/RSs,” Proc. SICE Annual Conf. 2007, pp. 2643-2648, 2007.
-  S.-M. Guo and T.-P. Liu, “Performance analysis of single shuttle and twin shuttle AS/RS,” 2007 IEEE Int. Conf. on Industrial Engineering and Engineering Management, pp. 763-767, 2007.
-  S.-M. Guo and T.-P. Liu, “An evaluation of storage assignment policies for twin shuttle AS/RS,” 2010 IEEE Int. Conf. on Management of Innovation and Technology (ICMIT), pp. 197-202, 2010.
-  D. R. Dooly and H. F. Lee, “A shift-based sequencing method for twin-shuttle automated storage and retrieval systems,” IIE Trans., Vol.40, Issue 6, pp. 586-594, 2008.
-  T. Lerher, M. Šraml, and I. Potrě, “Simulation analysis of miniload multi-shuttle automated storage and retrieval systems,” Int. J. of Advanced Manufacturing Technology, DOI 10.1007/s00170-010-2916-8.
-  H. Hino, Y. Kobayashi, T. Higashi, and J. Ota, “Control methodology of stacker cranes for collision avoidance considering dynamics in a warehouse,” Proc. of the 2009 IEEE Int. Conf. on Robotics and Biomimetics (ROBIO 2009), pp. 983-988, 2009.
-  J. E. Hopcroft, J. T. Schwartz, and M. Sharir, “On the complexity of motion planning for multiple independent objects; pspace-hardness of the “warehouseman’s problem”,” Int. J. of Robotics Research, Vol.3, Issue 4, pp. 76-88, 1984.
-  S. W. Lee, B. H. Lee, and K. D. Lee, “A configuration space approach to collision avoidance of a two-robot system,” Robotica, Vol.17, Issue 2, pp. 131-141, 1999.
-  C. Chang, M. J. Chung, and B. H. Lee, “Collision avoidance of two general robot manipulators by minimum delay time,” IEEE Trans. on Systems, Man and Cybernetics, Vol.24, Issue 3, pp. 517-522, 1994.
-  K. J. Kyriakopoulos and G. N. Saridis, “Collision avoidance of mobile robots in non-stationary environments,” Proc. of the IEEE Int. Conf. on Robotics and Automation, Vol.1, pp. 904-909, 1991.
-  S.-H. Ji, J.-S. Choi, and B.-H. Lee, “A computational interactive approach to multi-agent motion planning,” Int. J. of Control, Automation, and Systems, Vol.5, No.3, pp. 295-306, 2007.
-  K. Fujimura, “Motion Planning in Dynamic Environments,” Springer-Verlag, Tokyo, Japan, 1991.
-  A. Schweikard, “A simple path search strategy based on calculation of free sections of motions,” Engineering Applications of Artificial Intelligence, Vol.5, Issue 1, pp. 1-10, 1992.