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. 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
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. 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
5. NH-TTC: A gradient-based framework for generalized anticipatory collision avoidance

   https://doi.org/10.15607/RSS.2020.XVI.078  

   Davis, Bobby; Karamouzas, Ioannis; Guy, Stephen J. (January 2020, NH-TTC: A gradient-based framework for generalized anticipatory collision avoidance)

   null (Ed.)

   We propose NH-TTC, a general method for fast, anticipatory collision avoidance for autonomous robots with arbitrary equations of motions. Our approach exploits implicit differentiation and subgradient descent to locally optimize the non-convex and non-smooth cost functions that arise from planning over the anticipated future positions of nearby obstacles. The result is a flexible framework capable of supporting high-quality, collision-free navigation with a wide variety of robot motion models in various challenging scenarios. We show results for different navigating tasks, with various numbers of agents (with and without reciprocity), on both physical differential drive robots, and simulated robots with different motion models and kinematic and dynamic constraints, including acceleration-controlled agents, differential-drive agents, and smooth car-like agents. The resulting paths are high quality and collision-free, while needing only a few milliseconds of computation as part of an integrated sense-plan-act navigation loop. For a video of further results and reference code, please see the corresponding webpage: http://motion.cs.umn.edu/r/NH-TTC/ 

   more » « less