In a recent technical paper, researchers affiliated with the University of Southern California and Amazon Robotics explored a solution to the problem of lifelong multi-agent path finding (MAPF), where a team of agents must be moved to constantly changing goal locations without collisions. They say that in experiments, it produces “high-quality” solutions for up to 1,000 agents, significantly outperforming existing methods.
MAPF is a core part of a number of autonomous systems, like driverless vehicles, drone swarms, and even video game character AI. No doubt of interest to Amazon is its applicability to warehouse robots — as of December, Amazon had more than 200,0000 mobile machines inside its fulfillment network. Drive units automatically move inventory pods or flat packages from one location to another, and they must continue moving — they’re assigned new goal locations on a continuous basis.
The researchers’ solution models the MAPF problem as a graph containing vertices (nodes) connected by a series of edges (lines). The vertices correspond to locations, while the edges correspond to connections between two neighboring locations and a set of agents (e.g., drive units). At each timestep, every agent can either move to a neighboring location or wait at its current location. A collision occurs if two agents plan to occupy the same location at the same timestep.
The proposed solution aims to plan collision-free paths that move agents to their goal locations while maximizing the average number of locations visited. Given the time horizon within which collisions have to be resolved and the frequency at which the paths need to be replanned, the solution updates each agents’ start and goal locations at every timestep and calculates the number of steps the agents need to visit all locations. It also continually assigns new goal locations to agents and then finds collision-free paths, and it moves the agents along those generated paths and removes the visited goal locations from a sequence.
In simulated experiments involving a fulfillment warehouse mapped to a 33-by-46 grid with 16% obstacles, the researchers say their method outperformed all others in terms of throughput. And in a logistic sorting center mapped to a 37-by-77 grid with 10% obstacles, in which certain cells represented delivery chutes and workstations where humans put packages on the drive units, they report that a small number of timesteps sped up the framework by up to a factor of 6 without compromising throughput.
“[O]ur framework not only works for general graphs but also yields better throughput,” wrote the coauthors. “Overall, our framework works for general graphs, invokes replanning using a user-specified frequency, and is able to generate pliable plans that can not only adapt to an online setting but also avoid wasting computational effort in anticipating a distant future.”