Shinsung-KAIST AI automated material handling system (AMHS) research center

Algorithms and methods have been investigated to control the massive fleet of vehicles used in automation systems in factories and warehoused using advanced artificial intelligence (AI) techniques. An algorithm was verified to be able to control massive fleet of vehicles effectively and was implemented to the hardware testbed.

Article | Spring 2019

Modern production lines or warehouses and distribution centers require unprecedented levels of flexibility and service. To respond to this challenge, manufacturing systems and warehouses and distribution centers are actively adopting vehicle-based AMHSs such as overhead hoist transporter (OHT), as shown in Figure 1, and automated guided vehicles (AGVs). Kiva robots in the warehouses of Amazon are an example.

A newly-opened refrigerator assembly line of LG Electronics at Monterrey, Mexico moved away from the conventional conveyor type production line and instead adopted AGV and work-center type production lines. In the assembly line, each AGV loaded with a refrigerator travels around work-centers for the required processing and assembly steps. This type of assembly line increases flexibility significantly, but poses another challenge. Hundreds of vehicles are moving around in a factory, so an advanced vehicle control system that effectively coordinates the huge amount of vehicles is required. A good example of massive control is OHTs in semiconductor fabrication facilities or simply called fabs. The size of modern fabs is continually increasing to meet the expanding market demand, which requires many transportation moves between machines with a large number of OHTs. The new DRAM fab currently being planned will be built in a few years by Samsung Electronics, and will operate with more than 1,000 OHTs. This is almost double the number running in existing DRAM fabs.

 

AGV or OHT feet control has been developed, particularly in routing and dispatching algorithm developments, but most approaches are only applicable to controlling a limited number of vehicles [1]. Few studies have addressed the problem of controlling a large amount of feet. Thus, the existing methods have limited applications for actual industry cases.

Prof. Young Jae Jang and his research team in the Department of Industrial and Systems Engineering at KAIST have been investigated algorithms and methods to control the massive fleet of vehicles using advanced artificial intelligence (AI) techniques.

 

The research team has made a significant progress in the development. Specifically, Prof. Jang and Dr. Hwang, who is the lead investigator in the algorithm development, introduced the dynamic routing algorithm for OHT systems for semiconductor fabs using a Q(λ) learning. The routing is the traveling-path decision when an OHT performs a lot delivery job. In general, routing is categorized into static routing and dynamic routing. Static routing refers to the planning approach where the path is fixed for given starting and destination points. A typical static routing involves deterministic shortest path planning. In contrast, in dynamic routing the path may perpetually change depending on traffic conditions. If there is heavy congestion on the shortest route in terms of distance, then a dynamic routing system might reroute the delivery to a different path to avoid delays.

The approach in the study is based on reinforcement learning (RL), one of AI approaches which can adapt to environmental change such as congestion for online routing, and base routing decisions on continuously updated information. The developed algorithm QLWBRH(λ) is tested using a benchmarking study conducted by researchers (Bartlett, Nemhauser, Ahmed, and Sokol) at Georgia Tech [2]. The performances of the algorithm are analyzed with simulation analyses. Figure 3 shows the simulation results of the algorithm compared to those from the Georgia Tech approach. Note that the Georgia Tech approach is the only available benchmarking algorithm able to perform dynamic routing for more than 200 OHTs. For the performance analysis, average delivery time and computation time are compared.

 

Figure 3 (left) shows the average delivery time (y-axis) on varying delivery volume scenarios (x-axis). The three cases are compared for each volume scenario. The first bar is the result from a static Dijkstra’s algorithm. The second and third bars are results from the Georgia Tech algorithm and the proposed QLWBRH(λ) algorithms, respectively. As clearly indicated, the delivery times for the both Dijkstra’s algorithms and Georgia Tech algorithm are increasing as the delivery request volumes increase. However, the QLWBRH(λ) performs the delivery tasks in a more stable manner.

Figure 3 (right) depicts the computation time comparison between the Georgia Tech approach and QLWBRH(λ). The histogram indicates the distribution of unit calculation times for routings. As shown, QLWBRH(λ) calculates the routing for each OHT significantly faster than the Georgia Tech algorithm. The calculation time is a critical factor, particularly from a commercialization perspective. The algorithm must deal with thousands of routing requests for hundreds of OHTs, so a speedy decision with fast computation is crucial in a practical setting.

References

[1] Illhoe Hwang and Young Jae Jang*, “Overhead Hoist Transport (OHT) Route Guidance Algorithm using Q-Learning Method in Automated Material Handling System,” International Journal of Production Research (invited for publication by Editor’s Pick from ICPR 2017). 

[2] Bartlett, Kelly, et al. “Congestion-aware dynamic routing in automated material handling systems,” Computers & Industrial Engineering 70 (2014): 176-182.