More Like this

1. Closed-Form Minkowski Sum Approximations for Efficient Optimization-Based Collision Avoidance

   https://doi.org/10.23919/ACC53348.2022.9867524  

   Guthrie, James ; Kobilarov, Marin ; Mallada, Enrique ( January 2022 , Proceedings of the American Control Conference)

   Motion planning methods for autonomous systems based on nonlinear programming offer great flexibility in incorporating various dynamics, objectives, and constraints. One limitation of such tools is the difficulty of efficiently representing obstacle avoidance conditions for non-trivial shapes. For example, it is possible to define collision avoidance constraints suitable for nonlinear programming solvers in the canonical setting of a circular robot navigating around $M$ convex polytopes over $N$ time steps. However, it requires introducing $(2+L)MN$ additional constraints and $LMN$ additional variables, with $L$ being the number of halfplanes per polytope, leading to larger nonlinear programs with slower and less reliable solving time. In this paper, we overcome this issue by building closed-form representations of the collision avoidance conditions by outer-approximating the Minkowski sum conditions for collision. Our solution requires only $MN$ constraints (and no additional variables), leading to a smaller nonlinear program. On motion planning problems for an autonomous car and quadcopter in cluttered environments, we achieve speedups of 4.0x and 10x respectively with significantly less variance in solve times and negligible impact on performance arising from the use of outer approximations. 

   more » « less
2. Chance-Constrained Sequential Convex Programming for Robust Trajectory Optimization

   https://doi.org/10.23919/ECC51009.2020.9143595  

   Lew, T ; Bonalli, R ; Pavone, M ( July 2020 , 2020 European Control Conference)

   Planning safe trajectories for nonlinear dynamical systems subject to model uncertainty and disturbances is challenging. In this work, we present a novel approach to tackle chance-constrained trajectory planning problems with nonconvex constraints, whereby obstacle avoidance chance constraints are reformulated using the signed distance function. We propose a novel sequential convex programming algorithm and prove that under a discrete time problem formulation, it is guaranteed to converge to a solution satisfying first-order optimality conditions. We demonstrate the approach on an uncertain 6 degrees of freedom spacecraft system and show that the solutions satisfy a given set of chance constraints. 

   more » « less
3. Robust Trajectory Execution for Multi-Robot Teams Using Distributed Real-time Replanning

   Baskın Senbaslar, Wolfgang Hoenig ( October 2018 , International Symposium on Distributed Autonomous Robotic Systems)

   Robust trajectory execution is an extension of cooperative collision avoidance that takes pre-planned trajectories directly into account. We propose an algorithm for robust trajectory execution that compensates for a variety of dynamic changes, including newly appearing obstacles, robots breaking down, imperfect motion execution, and external disturbances. Robots do not communicate with each other and only sense other robots’ positions and the obstacles around them. At the high-level we use a hybrid planning strategy employing both discrete planning and trajectory optimization with a dynamic receding horizon approach. The discrete planner helps to avoid local minima, adjusts the planning horizon, and provides good initial guesses for the optimization stage. Trajectory optimization uses a quadratic programming formulation, where all safety-critical parts are formulated as hard constraints. At the low-level, we use buffered Voronoi cells as a multi-robot collision avoidance strategy. Compared to ORCA, our approach supports higher-order dynamic limits and avoids deadlocks better. We demonstrate our approach in simulation and on physical robots, showing that it can operate in real time. 

   more » « less
4. Robust Trajectory Execution for Multi-robot Teams Using Distributed Real-time Replanning

   https://doi.org/10.1007/978-3-030-05816-6_12  

   Şenbaşlar, Baskın ; Hönig, Wolfgang ; Ayanian, Nora ( October 2018 , Distributed Autonomous Robotic Systems)

   Robust trajectory execution is an extension of cooperative collision avoidance that takes pre-planned trajectories directly into account. We propose an algorithm for robust trajectory execution that compensates for a variety of dynamic changes, including newly appearing obstacles, robots breaking down, imperfect motion execution, and external disturbances. Robots do not communicate with each other and only sense other robots’ positions and the obstacles around them. At the high-level we use a hybrid planning strategy employing both discrete planning and trajectory optimization with a dynamic receding horizon approach. The discrete planner helps to avoid local minima, adjusts the planning horizon, and provides good initial guesses for the optimization stage. Trajectory optimization uses a quadratic programming formulation, where all safety-critical parts are formulated as hard constraints. At the low-level, we use buffered Voronoi cells as a multi-robot collision avoidance strategy. Compared to ORCA, our approach supports higher-order dynamic limits and avoids deadlocks better. We demonstrate our approach in simulation and on physical robots, showing that it can operate in real time. 

   more » « less
5. Decentralized modular hybrid supervisory control for the formation of unmanned helicopters

   https://doi.org/10.1049/cth2.12375  

   Karimoddini, Ali ; Karimadini, Mohammad ; Lin, Hai ( November 2022 , IET Control Theory & Applications)

   Formation control of Unmanned Aerial Vehicles (UAVs) requires them to tightly cooperate to reach and keep the formation, while avoiding collision. This paper proposes a novel decentralized hybrid supervisory control approach for the formation control of multiple UAVs. This is achieved by developing a symbolic motion planning technique to polarly partition the motion space resulting in a finite state discrete event model for the motion dynamics of each UAV. Then, a modular discrete supervisor is designed for different components of the formation mission including reaching the formation, keeping the formation, and collision avoidance. Further, for the collision avoidance mechanism, a novel top‐down decomposition‐based approach is developed to design local supervisors decentralizedly. It is formally proved that with the proposed top‐down decomposition‐based approach, the (locally) supervised UAVs, as a whole, can cooperatively satisfy the desired (global) collision avoidance specification. The proposed decentralized supervisory control algorithm is also verified through a hardware‐in‐the‐loop simulator for the formation control of unmanned helicopters.

    

   more » « less