Moving Millions of Orders with Robotic Conveyance
Reducing conveyance time with predictive dispatch and multi-order pickup
Written by Tarun Pondicherry, member of the engineering teams that work on facility automation.
At CloudKitchens, we use autonomous mobile robots to quickly and efficiently move millions of orders inside our facilities around the world. Our facilities consist of dozens of kitchens that have kitchen operators cooking everything from tacos and pizza to sushi and donuts. After orders are cooked at a kitchen, they need to be conveyed down long hallways to the pickup lobby where our staff helps couriers pick up these orders and deliver them to hungry eaters.
Using conveyance robots to move orders from kitchens to the pickup lobby frees up over 30% of facility staff time — which means that staff can spend their time on more customer-centric tasks like assisting our kitchen operators or couriers. Additionally, robots can be more easily scaled with order volume, immediately respond to new information en route, and even be dispatched predictively. To control our fleet of conveyance robots, we built RCR, the Robotic Conveyance Routing service. RCR integrates order data from our orders platform with robot data from various robot vendor APIs in realtime to automatically dispatch our robots where they need to go.
Initially, RCR simply dispatched a robot to get an order as soon as it was cooked, waited for the order to be placed on the robot as measured by a sensor, and then dispatched the robot back to the pickup lobby with food onboard. However, traveling back and forth down long hallways for every single order resulted in an unacceptably high conveyance time — meaning that couriers might be waiting longer than they had to to pick up their orders. To ensure a great experience in our facilities, we implemented several optimizations that enable robots to get delicious food from kitchens to the pickup lobby as quickly as possible. This is an especially challenging task since robots can only go so fast — safely — when sharing hallways with people, ingredient carts and the hustle and bustle of a busy facility during lunch rush. Our robots have to work with people and may need to stop, move or slow down in response to what they see in the hallways.
Robotic Conveyance Routing
To better understand the inner workings of RCR, let’s trace what happens as an order is conveyed. Conveyance starts when the cook presses the order ready button on their order management tablet. This triggers a “cooking complete” event to be pushed onto the order event queue, a system-wide event bus that captures all the state changes that happen to the order from its creation to pickup to delivery. RCR observes the “cooking complete” event on this queue and then has a few decisions to make.
Controlling a global fleet of robots requires multiple instances of RCR for scale and reliability. So, the service first needs to decide which instance should handle this particular order event. We use our Work Distribution Service, an in-house distributed shard allocation system, to spread robots and order state between instances. This guarantees that each facility’s data is uniquely owned by a single facility handler which allows us to cache most state in memory more easily than with a stateless service and database. When RCR observes a “cooking complete” event, it first looks up the responsible facility handler for that order and forwards it there.
Next, the facility handler’s dispatch logic checks which robots are available to get the order and assigns it to the robot it deems best. Generally, it chooses the closest robot, but we also want to ensure that all robots stay charged as long as possible — after all, a robot won’t be moving any orders if its battery dies. Internally, RCR maintains a task queue for each robot and an execution loop that commands robots to execute the task at the head of the queue. To make a robot get an order, a new pickup task is added to the robot’s task queue, followed by a dropoff task.
Now, it’s up to the task execution loop to actually make the robot perform its tasks. Seeing the pickup task, it dispatches the robot to the kitchen that just finished cooking the order. RCR monitors the position of the robot and waits for it to arrive at the kitchen. Once the robot arrives, it keeps track of the weight on the robot to detect that the order is onboard. Having detected completed pickup, the task execution loop moves on to the dropoff task, and dispatches the robot back to the pickup lobby. When the order is taken off the robot, another weight change notifies the service to complete the dropoff task and the robot can either park or press onward to execute its next task.
Multi-Order Trips
A robot can only move so fast without getting jolted and dropping orders, especially when they’re also avoiding humans, other robots, and boxes of vegetables being unloaded. Since simply making robots move faster wasn’t an option, we started looking at other ways to improve conveyance time. One improvement is to have robots get orders from multiple kitchens on a single trip, but deciding which ones and when is tricky. With this approach, we also need to make sure that in our quest to bring down the average conveyance time, we don’t let any single order get starved for a robot too long.
Figuring out which robots should get which orders at what time is a variant of the NP-hard Traveling salesman problem. RCR needs to figure out both the robot to assign an order to and a position in its task queue. To do this, we found an insertion heuristic satisfying a few key requirements: it’s reasonably optimal, guarantees that no order will be indefinitely starved, and produces assignments that are understandable by facility staff. That last requirement turned out to be critical — if the robots behaved in a way folks on the ground couldn’t understand, they wouldn’t opt to use them.
With this heuristic, RCR first determines all allowable task queue positions for an order as soon as the cooking complete event is triggered. An allowable position is one where a robot will have capacity, can service that kitchen, and is not carrying a high priority order. Capacity is determined using a combination of the number of orders, the types of orders, and the weight of orders on the robots. Kitchen serviceability is mainly considered in multi-floor facilities where robots can’t use elevators. Order priority addresses situations where an order needs to get to the pickup lobby as soon as possible, for example, if a courier is already waiting for the order.
RCR then tests the effect of inserting the order at every allowable position in every robot’s task queue. For each possible insertion, the system computes the estimated average conveyance time using Dijkstra’s algorithm. Once the best insertion position is determined, the pickup task gets spliced into the task queue. There are a few edge cases we need to consider after splicing. If a robot is already waiting by the kitchen, we don’t need to make a whole new task for it. Also, if the robot happens to be on the move, the task execution loop needs to command the robot to cancel its current mission to take on the new one.
Predictive Dispatch
Half of the robot travel time is the time to get to the right kitchen. What if we knew exactly when orders would be cooked in advance? Then, a robot could arrive just in time and dramatically reduce conveyance time. It turns out, we already have a best-in-class prep time model that does exactly this (see post next week). Our prep time model can predict when orders will be done cooking to within 4 minutes. By itself, that error could introduce substantial re-routing of robots at a busy facility. However, we don’t actually need to know exactly which order is going to be cooked to predictively dispatch well. RCR only needs to know the general area where the next order is likely to get cooked.
When a robot is idle, RCR queries the prep time model to determine which cluster of kitchens is most likely to have an order to get next. Clusters are groups of kitchens that are in close proximity to each other and have an associated nearby parking spot for the robot. If no robot is already parked near that cluster, a robot is predictively dispatched to wait nearby. Now, when an order is done cooking at any of those kitchens, a robot will arrive in just a few seconds instead of a couple of minutes, making robotic conveyance feel even more magical to our staff and kitchen operators.
Conclusion
Using robotic conveyance at CloudKitchens has significantly optimized our order fulfillment processes by allowing us to leverage the efficiency and scalability of robots in our facilities worldwide. We have not only freed up human labor for more customer-centric tasks but also ensured quicker and more predictable facility operations. To make the system practical, we implemented routing optimizations like multi-order pickup and predictive dispatch to cut average conveyance times by more than half.
As the nature of our robotic fleet and facility operations evolves, we’re actively pursuing further improvements to RCR. New dispatch modes for higher capacity robots could allow robots to linger by kitchens longer and only leave when another robot can take its place. Wireless charging could allow us to convey more orders with fewer robots. Additional systems to load and unload orders from robots could create a fully automated end-to-end conveyance solution. We’re always striving to improve the efficiency of our facilities with robots in a way that cooperates with humans and lets humans focus on the customer-centric tasks they do best.