Predictive Fleet Routing and Assignment

People

Xiaoshan Bai - Postdoctoral researcher

Prof. Javier Alonso-Mora

Funding

This project is funded by an Amazon Research Award (ARA)

About the Project

An increasing number of logistics and delivery companies are today working with large fleet of vehicles or robots that navigate around a specific city or area and complete their deliveries. In addition to this, several robotic applications like terrain mapping, environmental monitoring or search-and-rescue require multi agent task assignment. This can be mathematically challenging as the number of vehicles can keep increasing or the area over which they have to operate gets extended. This project focuses on building several algorithmic solutions which can resolve task assignment and routing solutions for individual robots or vehicles. The solutions provided in this project can enable these fleets to dynamically update routes in real-time based on incoming requests as well as ensure the total distance traversed by each robot in the fleet is reduced substantially while sticking to the time constraints provided.

Previous research into multi agent pickup and delivery(MAPD) solve the problem sequentially by firstly assigning tasks and then paths. However, this project contributed an integrated solution which solves them simultaneously. This is achieved by using the real collision-free costs to guide the multi-task multi-robot assignment process. Numerical simulations demonstrated a marked improvement in time taken by each robot as well as the runtime required for computing these solutions. Another contribution has been to extend this work and consider cases where each robot can carry more than one task at a time which resembles modern robotic warehouse systems.

Another interesting outcome from this project has been a novel anticipatory insertion method for vehicle routing that solves for routes based on a combination of known requests and predicted requests based on historical data. This helps to exploit demand patterns in historical data which can help anticipate future delivery requests and reduce waiting time. Experimental simulations have shown that this solution helps to both reduce total distance traveled by the fleet as well as the number of vehicles required to fulfill all requests.

Project Demonstrations

Funding & Partners

This project is funded by Amazon through an Amazon Research Award.

Group-based Distributed Auction Algorithms for Multi-Robot Task Assignment
Xiaoshan Bai, Andres Fielbaum, Maximilian Kronmuller, Luzia Knoedler, Javier Alonso-Mora. In IEEE Transactions on Automation Science and Engineering (T-ASE), 2023.

abstract publisher pdf

This paper studies the multi-robot task assignment problem in which a fleet of dispersed robots needs to efficiently transport a set of dynamically appearing packages from their initial locations to corresponding destinations within prescribed time-windows. Each robot can carry multiple packages simultaneously within its capacity. Given a sufficiently large robot fleet, the objective is to minimize the robots' total travel time to transport the packages within their respective time-window constraints. The problem is shown to be NP-hard, and we design two group-based distributed auction algorithms to solve this task assignment problem. Guided by the auction algorithms, robots first distributively calculate feasible package groups that they can serve, and then communicate to find an assignment of package groups. We quantify the potential of the algorithms with respect to the number of employed robots and the capacity of the robots by considering the robots' total travel time to transport all packages. Simulation results show that the designed algorithms are competitive compared with an exact centralized Integer Linear Program representation solved with the commercial solver Gurobi, and superior to popular greedy algorithms and a heuristic distributed task allocation method.

Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery
Z. Chen, J. Alonso-Mora, X. Bai, D. D. Harabor, P. J. Stuckey. In , IEEE Robotics and Automation Letters (RA-L), 2021.

abstract publisher pdf code

Multi-agent Pickup and Delivery (MAPD) is a challenging industrial problem where a team of robots is tasked with transporting a set of tasks, each from an initial location and each to a specified target location. Appearing in the context of automated warehouse logistics and automated mail sortation, MAPD requires first deciding which robot is assigned what task (i.e., Task Assignment or TA) followed by a subsequent coordination problem where each robot must be assigned collision-free paths so as to successfully complete its assignment (i.e., Multi-Agent Path Finding or MAPF). Leading methods in this area solve MAPD sequentially: first assigning tasks, then assigning paths. In this work we propose a new coupled method where task assignment choices are informed by actual delivery costs instead of by lower-bound estimates. The main ingredients of our approach are a marginal-cost assignment heuristic and a meta-heuristic improvement strategy based on Large Neighbourhood Search. As a further contribution, we also consider a variant of the MAPD problem where each robot can carry multiple tasks instead of just one. Numerical simulations show that our approach yields efficient and timely solutions and we report significant improvement compared with other recent methods from the literature.

Anticipatory Vehicle Routing for Same-Day Pick-up and Delivery using Historical Data Clustering
J. van Lochem, M. Kronmueller, P. van 't Hof, J. Alonso-Mora. In Proc. IEEE Int. Conf. on Intelligent Transportation Systems (ITSC), 2020.

abstract publisher pdf video

In this paper we address the problem of same-day pick-up and delivery where a set of tasks are known a priori and a set of tasks are revealed during operation. The vehicle routes are precomputed based on the known and predicted requests and adjusted online as new requests are revealed. We propose a novel anticipatory insertion method which incorporates a set of predicted requests to beneficially adjust the routes of a fleet of vehicles in real-time. Requests are predicted based on historical data, which is clustered in advance. We exploit inherent patterns of the demand, which are captured by historical data and include them in a dynamic vehicle routing solver based on heuristics and adaptive large neighborhood search. The proposed method is evaluated using numerical simulations on a variety of real-world problems with up to 1655 requests per day. Their degree of dynamism ranges from 0.70 to 0.93. These instances represent dynamic multi-depot pickup and delivery problems with time windows. The method has shown to require less driven kilometers than comparable methods.