Many Amazon fulfillment centers use mobile robots to move shelves, retrieve products, and deliver them to workers for sorting, reducing the need for employees to walk long distances. For simplicity and scalability, the path-planning algorithm those robots currently use focuses on individual agents and ignores interactions between multiple agents.
We want to develop a model that can extract useful traffic and interaction information from data on robots’ past positions and planned trajectories, which will help the current single-agent path-planning algorithm make smarter plans for the overall fleet.
In a paper we presented at this year’s International Conference on Robotics and Automation (ICRA), we propose a deep-learning model that can predict congestion on the floor in real time. We tested the model’s predictions in simulations of two downstream applications: dynamic path planning in sortation centers, where our model improved throughout by 4.4%, and travel time estimation, where it improved the mean absolute percentage error by 30% to 40% relative to the current production methods.
Congestion
Globally optimizing the planned trajectories for all robots simultaneously would be prohibitively time consuming, so our goal is to build a model that can predict future congestion levels on the floor. The individual robots’ path planners can then use that prediction when computing their paths.
To start with, we define congestion as delay — that is, the additional time a robot needs when traversing a planned path compared to the “free-flow scenario”, which involves a single robot and no other interventions. Specifically, we are interested in dynamically predicting the expected delay at each location on the floor throughout the duration of a robot’s typical path traversal.
We represent the warehouse floor as a regular grid, with grid cells sized so that only one robot can inhabit one cell at a given time. Pickup locations, delivery locations, and obstacles are all indicated on the grid.
More particularly, we represent the grid as a graph, in which each node represents a grid cell, and edges indicate cells accessible from each other.
We use the graph to represent inputs to our congestion prediction model. Those inputs include each robot’s path history and its planned trajectory. Histories are represented as the robots’ locations and poses at discrete points in the past. Trajectories are represented as the robots’ probable locations at discrete points in the future. We represent a given robot’s location at a given time as a Gaussian distribution over possible locations.
Aggregating probabilities across multiple robots gives us the likelihood that any given cell of the grid will be occupied at any given time in the future.
Our goal is to dynamically predict delays across the time it takes for a robot to complete a typical path trajectory. That time is about 60 seconds, which we divide into six time windows, predicting one delay per time window. Within each 10-second window, we supply six predictions of cell occupancy, based on our probabilistic model.
Our congestion prediction model uses the ConvLSTM architecture, which combines a convolutional neural network (CNN) and a long-short-term-memory (LSTM) network. CNNs apply the same sets of filters to overlapping chunks of a grid; designed for image processing, they’re also well suited to the grid representation of a warehouse floor.
LSTMs process sequential data in order, so that the output corresponding to each new input factors in the inputs and outputs that preceded it. In this case, the inputs are the features — the historical locations and the projected locations — corresponding to each time window, and the output is the predicted delay at each point in the grid during that time window.
We tested our approach in simulations involving real data on robot trajectories in two different warehouse layouts, and we used our model’s predictions for both dynamic path planning and travel time estimation, with the 4.4% and 30–40% improvements we reported above. The advantages of better path planning are clear; the expectation is that the improved travel time estimation should lead to more efficient task assignment — that is, determining which robot should retrieve which item from which location. But the evaluation of that application is a task for future research.
