Online Conflict-Free Scheduling of Fleets of Autonomous Mobile Robots

摘要

This work presents a Fleet Manager for a fleet of Autonomous Mobile Robots (AMRs) that perform material handling tasks in a shared environment. The Fleet Manager assigns AMRs to newly released tasks, computes paths for them to travel to the task’s locations, and schedules their travel along the computed paths so that conflicts with other AMRs are avoided. The objective is for each AMR to complete its task as quickly as possible, to then be assigned a new task.The Fleet Manager works online, assigning a released task to the AMR closest to the task’s location, and then computing the path and schedule to fit in with the already assigned and executing AMRs. Conflicts occur when, in order to reach their targets, AMRs would have to simultaneously occupy the same space. Resolving this is done by appropriate scheduling, or by moving idle AMRs out of the way. For fleet management to be practicable, the computation time for assigning an AMR to a task and computing its path and schedule must be negligible compared to other system times.Tests were conducted to evaluate the performance of the Fleet Manager on a number of benchmark problem instances, counting up to hundreds of AMRs. The results show that the presented Fleet Manager can handle these systems quickly enough to be practically useful in real industrial scenarios.