Scalable and Conflict Free Routing Algorithms for Large Fleets of Mobile Robots

Abstract

Abstract This thesis explores methods for pathfinding and scheduling for large fleets of mobile robots, such as those used for material handling in factories and warehouses. The intention is to be able to handle larger fleets than is currently possible by conventional means. A path is a sequence of segments in a directed graph representing the warehouse layout in which the robots move, and pathfinding determines the paths from starting points to destinations. Scheduling then determines at which time each section of a path is travelled. For the robots not to deadlock each other, a schedule has to be conflict free, and we also want the schedule to minimise the overall work time. As conflicts can only occur when paths overlap, it can be hypothesized that choosing to schedule paths that minimise overlaps could potentially lessen the computational burden of scheduling, as well as minimising overall work time. The thesis demonstrates that identifying paths that minimise overlaps has this effect, but is itself a computationally challenging task.