Dive Brief:

• A new method for robotic route planning and collision avoidance outperformed existing methods, in terms of throughput, according to a paper published by researchers at the University of Southern California and Amazon Robotics. The paper defined throughput as the average number of goal locations visited in a given time period.
• The paper's proposed framework gives each robot plans for multiple goal locations and only requires a collision-free path for the first part of the trip, or "first w timesteps," as the paper puts it. The route is then replanned to be collision-free after a user-defined period of time. The method "keeps the agents continually engaged, avoiding idle time, and increasing throughput," the paper reads. The researchers defined a collision of two robots as an event where the two drive units occupy the same location at the same time.
• "Multi-Agent Path Finding" (MAPF), the practice of ensuring a fleet of robots can go where they need to without running into each other, is common in robotics. Planning out entire paths as collision-free, as existing frameworks do, is often unnecessary because a path can change as new locations are assigned, the researchers explain. The new method is able to avoid the idle time of other frameworks

Dive Insight:

Amazon has added more than 200,000 robotic drive units to its operations since it acquired Kiva Systems in 2012. The company credits the technology with increasing building storage capacity by 40%, company executives explained at last year's re:MARS conference in Las Vegas.

Increasing throughput for robots would help Amazon's efforts to increase the overall throughput for its fulfillment and sort centers. If robots hit more goal locations in a warehouse, items can move throughout a location faster. The paper doesn't define "goal location," but Amazon uses drive units in the picking process and in sorting centers, so it could be a move to a picker or a move to a chute where a package needs to be deposited.

Existing MAPF techniques take approaches that include replanning paths every time a defined period of time elapses or replanning only if an agent has a new goal location. But it can take a lot of computing power to plan an entire collision-free route for dozens of robots, so the researchers suggest just avoiding collisions over a certain time span and not the entire trip.

"For our method, we use a time horizon of w = 20 timesteps and replan every h = 5 timesteps," the paper reads.

The method was tested in a simulated environment that was a 33 by 46 grid, with 16% of the space taken up by obstacles the robots had to avoid. It took longer to compute routes, but the method still increased throughput because other techniques use methods that can result in "unnecessary waits or longer paths in its solutions.​"

"The disadvantages of these methods are that they need to replan at every timestep, achieve a lower throughput on this well-formed map, and are not applicable to all maps," the researchers noted of existing methods, compared to the new framework.