Multi-Robot Coordination via Learning-Based Combinatorial Optimization

1. Multi-Robot Cooperative Task Allocation and Scheduling with Dynamic Coalition Formation

Multi-robot systems have gained increasing attention due to the recent technological advancements in computation, sensing, and communications and their potential applications in various fields such as logistics, surveillance, agriculture, and extraterrestrial exploration. The growing complexity of such tasks, which often require simultaneous operations, has also made the deployment of single robots, even very complex/capable ones, insufficient. On the other hand, a team of agents with heterogeneous sensing/actuators capabilities may identify and leverage potential synergies that can lead to higher robustness and efficiency. Given a team of agents and tasks with various constraints on time, abilities, and precedence, how to allocate agents to tasks and finish them in a more efficient and cooperative manner remains a key, open challenge.

In various applications such as the regular maintenance of an large number of machines in factories, each maintenance task requires simultaneous operation by teams of mobile robots to shorten machine’s downtime. Motivated by such problems, we consider the joint task allocation and task scheduling problem, based on the agents’ abilities and task requirements, which also implicitly requires agents to dynamically form coalitions, disband and reform to execute tasks cooperatively and shorten the overall repair time. This project investigates the use of distributed deep reinforcement learning to solve such allocation problems, aiming to minimize the makespan and the wasted time resulting from agents waiting for their partners to initiate tasks at the same time.

2. Learning based Combinatorial Optimization

Combinatorial optimization problems are of utmost importance in robotics, as they directly impact the efficient allocation of limited resources. These problems commonly arise when determining the optimal task allocation among robots or planning the most favorable paths for single- or multi-agent robot motion. There, the objective is to identify the best arrangement or combination of elements from a given set while considering constraints and optimizing a specific objective function. However, solving these problems can be extremely challenging and time-consuming due to the exponential growth of potential solutions as the problem size increases. Traditional hand-crafted heuristics can only generate specific solutions for predefined problems and struggle with general policies, resulting in significantly increased inference time as the problem complexity escalates.

To bridge this gap, this project aims to develop effective and efficient methods to tackle combinatorial optimization problems in robotics. Building upon distributed reinforcement learning (RL) and Transformer, some of our recent work (DAN) successfully addressed the multiple traveling salesman problem, demonstrating natural scalability in terms of the number of agents and nodes. Our more recent work (CNH) also tackled multi-objective robot routing problems, i.e., minimizing the total distance of all agents’ routes while minimizing the makespan, using a dual attention mechanism and a size-aware decoder. By addressing combinatorial optimization problems in robotics, researchers and engineers strive to enhance robotic systems’ efficiency, autonomy, and overall performance across diverse applications, including manufacturing, logistics, surveillance, and exploration.

Related recent publications:

• DAN: Decentralized Attention-based Neural Network to Solve the MinMax Multiple Traveling Salesman Problem
• Deep Reinforcement Learning for UAV Routing in The Presence of Multiple Charging Stations.

People

Guillaume SARTORETTI

Assistant Professor

Weiheng DAI