Deadlock Resolution and Recursive Feasibility in MPC-based Multi-robot Trajectory Generation
2202.06071
0
0
🛸
Abstract
Online collision-free trajectory generation within a shared workspace is fundamental for most multi-robot applications. However, many widely-used methods based on model predictive control (MPC) lack theoretical guarantees on the feasibility of underlying optimization. Furthermore, when applied in a distributed manner without a central coordinator, deadlocks often occur where several robots block each other indefinitely. Whereas heuristic methods such as introducing random perturbations exist, no profound analyses are given to validate these measures. Towards this end, we propose a systematic method called infinite-horizon model predictive control with deadlock resolution. The MPC is formulated as a convex optimization over the proposed modified buffered Voronoi with warning band. Based on this formulation, the condition of deadlocks is formally analyzed and proven to be analogous to a force equilibrium. A detection-resolution scheme is proposed, which can effectively detect deadlocks online before they even happen. Once detected, it utilizes an adaptive resolution scheme to resolve deadlocks, under which no stable deadlocks can exist under minor conditions. In addition, the proposed planning algorithm ensures recursive feasibility of the underlying optimization at each time step under both input and model constraints, is concurrent for all robots and requires only local communication. Comprehensive simulation and experiment studies are conducted over large-scale multi-robot systems. Significant improvements on success rate are reported, in comparison with other state-of-the-art methods and especially in crowded and high-speed scenarios.
Create account to get full access
Overview
- Collision-free trajectory generation is essential for multi-robot applications, but existing methods have limitations
- Model predictive control (MPC) approaches lack theoretical guarantees on optimization feasibility
- Distributed MPC can lead to deadlocks where robots block each other indefinitely
- Heuristic methods to address deadlocks lack rigorous analysis
Plain English Explanation
When multiple robots operate in the same workspace, they need to generate trajectories that avoid collisions with each other. One approach is to use model predictive control (MPC), where the robots plan their movements by solving optimization problems that consider their current state and predicted future states.
However, many MPC-based methods do not have strong guarantees that the underlying optimization problems will always have feasible solutions. Additionally, when multiple robots use distributed MPC without a central coordinator, they can end up in "deadlock" situations where several robots block each other and stop moving.
Researchers have tried to address deadlocks by introducing random perturbations to the robots' plans, but these heuristic approaches have not been rigorously analyzed to understand their effectiveness.
Technical Explanation
The paper proposes a new systematic method called "infinite-horizon model predictive control with deadlock resolution." The key ideas are:
-
Convex MPC Formulation: The MPC is formulated as a convex optimization problem using a modified "buffered Voronoi with warning band" approach. This ensures the underlying optimization is feasible under both input and model constraints.
-
Deadlock Analysis: The condition for deadlocks is formally analyzed and shown to be analogous to a force equilibrium. This allows the method to detect potential deadlocks before they occur.
-
Deadlock Resolution: When a deadlock is detected, an adaptive resolution scheme is used to break the deadlock. Under certain conditions, this ensures no stable deadlocks can form.
-
Concurrent and Distributed: The proposed planning algorithm runs concurrently for all robots and requires only local communication, without a central coordinator.
Comprehensive simulations and experiments on large-scale multi-robot systems showed significant improvements in success rate, especially in crowded and high-speed scenarios, compared to other state-of-the-art methods.
Critical Analysis
The paper provides a rigorous theoretical analysis of deadlocks in distributed MPC and proposes an effective solution. However, the authors acknowledge some limitations:
- The deadlock resolution scheme relies on certain assumptions, such as robots having equal priorities. Extensions to handle heterogeneous robot priorities would be valuable.
- The method assumes perfect communication between robots, which may not always be the case in real-world scenarios. Robustness to communication delays or failures could be investigated.
- While the experiments demonstrate promising results, further testing in more complex and dynamic environments would help validate the method's broader applicability.
Overall, the paper presents a significant advance in addressing the challenging problem of deadlock resolution in multi-robot systems, but there are still opportunities for further research and real-world deployment.
Conclusion
This paper introduces a novel approach for generating collision-free trajectories in multi-robot systems that can effectively detect and resolve deadlocks. By formulating the MPC problem in a convex manner and rigorously analyzing the conditions for deadlocks, the authors have developed a systematic solution that outperforms existing methods, especially in crowded and high-speed scenarios. While the method has some limitations, it represents an important step forward in enabling reliable and efficient multi-robot coordination, with potential applications in areas like autonomous transportation, warehouse logistics, and search and rescue operations.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
Embedded Hierarchical MPC for Autonomous Navigation
Dennis Benders, Johannes Kohler, Thijs Niesten, Robert Babuv{s}ka, Javier Alonso-Mora, Laura Ferranti
0
0
To efficiently deploy robotic systems in society, mobile robots need to autonomously and safely move through complex environments. Nonlinear model predictive control (MPC) methods provide a natural way to find a dynamically feasible trajectory through the environment without colliding with nearby obstacles. However, the limited computation power available on typical embedded robotic systems, such as quadrotors, poses a challenge to running MPC in real-time, including its most expensive tasks: constraints generation and optimization. To address this problem, we propose a novel hierarchical MPC scheme that interconnects a planning and a tracking layer. The planner constructs a trajectory with a long prediction horizon at a slow rate, while the tracker ensures trajectory tracking at a relatively fast rate. We prove that the proposed framework avoids collisions and is recursively feasible. Furthermore, we demonstrate its effectiveness in simulations and lab experiments with a quadrotor that needs to reach a goal position in a complex static environment. The code is efficiently implemented on the quadrotor's embedded computer to ensure real-time feasibility. Compared to a state-of-the-art single-layer MPC formulation, this allows us to increase the planning horizon by a factor of 5, which results in significantly better performance.
6/18/2024
Convex MPC and Thrust Allocation with Deadband for Spacecraft Rendezvous
Pedro Taborda, Hugo Matias, Daniel Silvestre, Pedro Lourenc{c}o
0
0
This paper delves into a rendezvous scenario involving a chaser and a target spacecraft, focusing on the application of Model Predictive Control (MPC) to design a controller capable of guiding the chaser toward the target. The operational principle of spacecraft thrusters, requiring a minimum activation time that leads to the existence of a control deadband, introduces mixed-integer constraints into the optimization, posing a considerable computational challenge due to the exponential complexity on the number of integer constraints. We address this complexity by presenting two solver algorithms that efficiently approximate the optimal solution in significantly less time than standard solvers, making them well-suited for real-time applications.
6/26/2024
🔍
A Distributed Multi-Robot Coordination Algorithm for Navigation in Tight Environments
Roya Firoozi, Laura Ferranti, Xiaojing Zhang, Sebastian Nejadnik, Francesco Borrelli
0
0
This work presents a distributed method for multi-vehicle coordination based on nonlinear model predictive control (NMPC) and dual decomposition. Our approach allows the vehicles to coordinate in tight spaces (e.g., busy highway lanes or parking lots) by using a polytopic description of each vehicle's shape and formulating collision avoidance as a dual optimization problem. Our method accommodates heterogeneous teams of vehicles (i.e., vehicles with different polytopic shapes and dynamic models can be part of the same team). Our method allows the vehicles to share their intentions in a distributed fashion without relying on a central coordinator and efficiently provides collision-free trajectories for the vehicles. In addition, our method decouples the individual-vehicles' trajectory optimization from their collision-avoidance objectives enhancing the scalability of the method and allowing one to exploit parallel hardware architectures. All these features are particularly important for vehicular applications, where the systems operate at high-frequency rates in dynamic environments. To validate our method, we apply it in a vehicular application, that is, the autonomous lane-merging of a team of connected vehicles to form a platoon. We compare our design with the centralized NMPC design to show the computational benefits of the proposed distributed algorithm.
6/11/2024
Robot Safe Planning In Dynamic Environments Based On Model Predictive Control Using Control Barrier Function
Zetao Lu, Kaijun Feng, Jun Xu, Haoyao Chen, Yunjiang Lou
0
0
Implementing obstacle avoidance in dynamic environments is a challenging problem for robots. Model predictive control (MPC) is a popular strategy for dealing with this type of problem, and recent work mainly uses control barrier function (CBF) as hard constraints to ensure that the system state remains in the safe set. However, in crowded scenarios, effective solutions may not be obtained due to infeasibility problems, resulting in degraded controller performance. We propose a new MPC framework that integrates CBF to tackle the issue of obstacle avoidance in dynamic environments, in which the infeasibility problem induced by hard constraints operating over the whole prediction horizon is solved by softening the constraints and introducing exact penalty, prompting the robot to actively seek out new paths. At the same time, generalized CBF is extended as a single-step safety constraint of the controller to enhance the safety of the robot during navigation. The efficacy of the proposed method is first shown through simulation experiments, in which a double-integrator system and a unicycle system are employed, and the proposed method outperforms other controllers in terms of safety, feasibility, and navigation efficiency. Furthermore, real-world experiment on an MR1000 robot is implemented to demonstrate the effectiveness of the proposed method.
4/10/2024