Flow-Achieving Online Planning and Dispatching for Continuous Transportation With Autonomous Vehicles
Konstantin M. Seiler, Andrew W. Palmer, Andrew J. Hill
Abstract
In large-scale industrial applications, goods must be continuously transported between locations, which in the absence of conveyor systems is by a fleet of individual vehicles. This article introduces flow-achieving scheduling tree (FAST), an online dispatching algorithm that allows vehicles to efficiently operate as a team to maximize the system’s throughput while meeting a production schedule. A high-performance model is developed for high-fidelity prediction of vehicle interactions and system performance. It is subsequently optimized using a self-tuning variant of Monte Carlo tree search (MCTS) to make agile dispatch decisions in real time. The method is validated using an open-cut mine site and is shown to outperform a commonly used algorithm in this domain. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Note to Practitioners</i> —This article was motivated by the problem of dispatching autonomous haul trucks on open-cut mine sites. The proposed method is suited to any industrial transportation system where a continuous stream of goods must be efficiently transported between the load and unload stations by a potentially heterogeneous fleet of automated vehicles. The system makes decisions in real time while reacting to performance variations and disturbances by using a receding horizon approach. Off-the-shelf software commonly used in this domain is based on heuristics with limited ability to optimize, leading to myopic decision making without taking vehicle interactions into account. Here, flow-achieving scheduling tree (FAST) overcomes this by optimizing over possible schedules and thereby implicitly accounting for knock-on effects. Future work will incorporate additional constraints into the optimization process and validate FAST in other industrial domains.