Multi-agent Motion Planning for Collaborative and Large-scale Applications

Abstract

Integrating multi-robot systems into applications such as automated warehouses, environmental monitoring, and other complex domains has revolutionized various aspects of the modern world. These systems, however, bring forth significant challenges. One of the primary challenges in multi-robot systems is enabling decentralized collaboration. In scenarios where robots must operate independently without a central controller, achieving effective coordination becomes difficult due to limited global information, communication constraints, and the dynamic nature of the environment. Another significant challenge lies in the motion planning of a large number of robots in continuous environments. As the number of robots increases, so does the complexity of finding safe and efficient trajectories through dynamic, obstacle-laden spaces. This dissertation focuses on creating practical solutions to address these challenges, which are crucial for effectively deploying multi-robot systems in real-world environments. To tackle decentralized collaboration, this work develops a consensus-based approach that enables robots to coordinate effectively despite limited global information and communication constraints. To ensure safety and efficient planning in the continuous environment, this dissertation introduces a Mixed-Integer Linear Programming (MILP) framework and techniques that improve its computational efficiency. A novel hybrid graph representation of the environments is proposed to achieve faster computation than fully continuous planning, and a safe-interval motion planning algorithm is designed. To manage a large number of agents in the continuous space, a traffic-aware two-level strategy is developed. The effectiveness of these methods is demonstrated through extensive simulations and real-world experiments, proving their potential for collaborative and large-scale applications. The structure of the dissertation is as follows: Chapter 1 introduces the key challenges in multi-agent motion planning and decentralized collaboration, outlining the motivation behind the research and its relevance to real-world applications. Chapter 2 introduces a consensus-based framework that allows robots to collaborate effectively without relying on a central controller. This framework employs distributed estimation and control techniques, enabling each robot to make decisions based on local information while contributing to the overall system's goals. The chapter demonstrates the effectiveness of the proposed method through simulations and real-world experiments. Chapter 3 presents a mixed-integer linear programming (MILP) approach to optimizing the trajectories of multiple robots navigating through environments, ensuring that the generated paths are both safe and efficient. This chapter also introduces techniques to enhance computational efficiency, making the approach feasible for real-time applications in large-scale robotic systems. Chapter 4 introduces a hybrid graph-based environment representation that lies between discrete and continuous representations. This hybrid approach leverages the strengths of each representation, allowing for faster computation and more scalable solutions without compromising the quality of the solution. Chapter 5 explores a traffic-aware planning strategy with a dual-level approach. High-level planning minimizes congestion by intelligently routing robots through the environment, while low-level tracking ensures precise and collision-free movement. Simulations demonstrate the effectiveness of this method in 100-agent experiments.