Research on pull-type multi-AGV system dynamic path optimization based on time window

Abstract

This paper is a study of the dynamic path planning problem of the pull-type multiple Automated Guided Vehicle (multi-AGV) complex system. First, based on research status at home and abroad, the conflict types, common planning algorithms, and task scheduling methods of different AGV complex systems are compared and analyzed. After comparing the different algorithms, the Dijkstra algorithm was selected as the path planning algorithm. Secondly, a mathematical model is set up for the shortest path of the total driving path, and a general algorithm for multi-AGV collision-free path planning based on a time window is proposed. After a thorough study of the shortcomings of traditional single-car planning and conflict resolution algorithms, a time window improvement algorithm for the planning path and the solution of the path conflict covariance is established. Experiments on VC++ software showed that the improved algorithm reduces the time of path planning and improves the punctual delivery rate of tasks. Finally, the algorithm is applied to material distribution in the OSIS workshop of a C enterprise company. It can be determined that the method is feasible in the actual production and has a certain application value by the improvement of the data before and after the comparison.

Keywords

Time window multi-AGV system dynamic path planning dijkstra algorithm

Get full access to this article

View all access options for this article.

References

Bozer

Srinivasan

MM.

Tandem configurations for automated guided vehicle systems and the analysis of single vehicle loops. IIE Trans 1999; 23: 72–82.

Dantzig

Ramser

JH.

The truck dispatching problem. Manag Sci 1959; 6: 80–91.

Dijkstra

EW.

A note on two problems in connexion with graphs. Numer Math 1959; 1: 269–271.

Dunkin

An introduction of automated guided vehicle system. Ind Eng 1994; 8: 47–51.

Fan

Yin

, et al. Time window based path planning of multi-AGVs in logistics center. Int Symp Comput Intell Des 2017; 10: 161–166.

Groover

MP.

Modeling of automation production system. Comput Integr Manuf 1987; 12: 660–666.

Hart

Nilsson

Raphael

A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 1968; 4: 100–107.

Lou

Qian

, et al. Time-window-based automatic guided vehicle collision-free path planning. Comput Integr Manuf Syst 2010; 16: 2630–2634.

Wang

, et al. A time window based automatic path planning method for automatically guided vehicles. J Shanghai Jiao Tong Univ 2012; 46: 967–971.

10.

Kaspi

Kesselman

Tanchoco

JMA

. Optimal solution for the flow path design problem of a balanced unidirectional AGV system. Int J Prod Res 2002; 40: 389–401.

11.

Khatib

Real-time obstacle avoidance for manipulators and mobile robots. Auton Robot Veh 1986; 42: 396–404.

12.

Lei

Zhang

Scheduling optimization model of AGV system. Sci Technol Eng 2008; 1: 66–69.

13.

Liu

Gruver

Kotak

DB.

Holonic coordination and control of an automated guided vehicle system. Integr Comput Aided Eng 2002; 9: 235–250.

14.

Lozano-Perez

Spatial planning: a configuration space approach. IEEE Trans Comput 1983; 2: 108–120.

15.

Maxwell

Muckstadt

JA.

Design of automatic guided vehicle systems. IIE Trans 1982; 14: 114–124.

16.

Qiao

Qian

Lou

PH.

AGVs collision avoidance path planning based on improved time window. Comput Integr Manuf Syst 2012; 18: 2683–2688.

17.

Wang

DJ.

Path planning of indoor mobile robot based on improved A* algorithm. J Tsinghua Univ (Sci Technol) 2012; 52: 1085–1089.

18.

XX.

Application status and development trend of AGV autonomous guided vehicles. Robot Appl 2012; 3: 16–17.

19.

Xie

Ban

YR.

Research on AGV path planning based on A* algorithm. Manuf Autom 2011; 33: 113–114.

20.

Zhang

Yan

YN.

Modern production logistics and simulation. Beijing: Tsinghua University Press, 1998, pp.15–18.

21.

Zhang

Guo

Chen

, et al. Collision-free route planning for multiple AGVs in an automated warehouse based on collision classification. IEEE Access 2018; 6: 26022–26035.

22.

Zhang

Chen

WD.

AGV dynamic path planning under time window constraints. Microcomput Appl 2016; 32: 46–49.

23.

Zhu

Wang

, et al. Research on path planning of parking system based on dynamic time window. J Eng Des 2017; 24: 440–448.