Constraint based coordination algorithm for a fleet of AGVs

Abstract

With the advent of advanced autonomous cars driving on public roads, the logistic industry is looking forward to deploying new, high-tech fleets of Automated Guided Vehicles. In addition to autonomous driving related problems, the logistic sector needs to consider fleet management issues, including the coordination of the fleet movements in order to prevent the agents to interfere with each other.

The work on which this thesis is based is part of a project that aims to design and develop a robotic platform, an integrated fleet management, and a logistic system to handle the transportation of resources among warehouses of an industrial site. The role of this thesis in the project was to design a fleet coordination software component that has to manage the safe navigation of the fleet, ensuring the absence of collisions between agents and infinite waiting times, i.e., deadlocks, while they drive their assigned trajectories.

This thesis proposes the design of a constraint based fleet coordination algorithm which can handle tens of robots in a real scenario of an outdoor environment. This algorithm generates a suboptimal navigation plan that is able to satisfy all the demands of the industry and it is, nevertheless, much faster to compute with respect to performing optimal navigation planning, which does not scale to manage a realistic number of agents. Besides, a centralized solution offers more control and predictability which are of great value for the logistic industry.

The proposed method leverages spatial and temporal constraints to represent the fleet coordination problem in the form of Simple Temporal Problem (STP). A scheduling algorithm searches for possible conflicts in space and time and modifies the constraints of the problem accordingly. Then, an STP solver evaluates the consistency of the input constraints and forms the most efficient and safe navigation plan that respects those constraints.

Experiments evaluate the performance of the proposed coordination algorithm and the results show that this method can handle, under fair assumptions, tens of AGVs without imposing strict limitations on the working environment and the type of robot platform.