IJAT Vol.6 No.6 pp. 792-801
doi: 10.20965/ijat.2012.p0792


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

June 27, 2012
October 2, 2012
November 5, 2012
AS/RS, cooperative operation, control, trajectory generation, warehouses

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.

Cite this article as:
Hisato Hino, Yoshimasa Kobayashi, Toshimitsu Higashi, and
and Jun Ota, “Motion Planning Method for Two Stacker Cranes in an Automated Storage and Retrieval System,” Int. J. Automation Technol., Vol.6, No.6, pp. 792-801, 2012.
Data files:
  1. [1] 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.
  2. [2] 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.
  3. [3] 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.
  4. [4] 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.
  5. [5] R. D. Meller and A. Mungwattana, “Multi-shuttle automated storage/retrieval systems,” IIE Trans., Vol.29, Issue 10, pp. 925-938, 1997.
  6. [6] 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.
  7. [7] 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.
  8. [8] 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.
  9. [9] 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.
  10. [10] 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.
  11. [11] 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.
  12. [12] 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.
  13. [13] 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.
  14. [14] 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.
  15. [15] 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.
  16. [16] 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.
  17. [17] 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.
  18. [18] 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.
  19. [19] K. Fujimura, “Motion Planning in Dynamic Environments,” Springer-Verlag, Tokyo, Japan, 1991.
  20. [20] 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.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Feb. 25, 2021