Next generation Unmanned Aerial Vehicles (UAVs) must reliably avoid moving obstacles. Existing dynamic collision avoidance methods are effective where obstacle trajectories are linear or known, but such restrictions are not accurate to many real-world UAV applications. We propose an efficient method of predicting an obstacle's motion based only on recent observations, via online training of an LSTM neural network. Given such predictions, we define a Nonlinear Probabilistic Velocity Obstacle (NPVO), which can be used select a velocity that is collision free with a given probability. We take a step towards formal verification of our approach, using statistical model checking to approximate the probability that our system will mispredict an obstacle's motion. Given such a probability, we prove upper bounds on the probability of collision in multiagent and reciprocal collision avoidance scenarios. Furthermore, we demonstrate in simulation that our method avoids collisions where state-of-the-art methods fail.
Given probabilistic predictions of obstacle movement, we propose an uncertainty-aware multi-agent dynamic collision avoidance algorithm based on Nonlinear Probabilistic Velocity Obstacles (NPVO), a novel extension of existing velocity obstacle notions. These include Probabilistic Velocity Obstacles, which provide an uncertainty-aware policy in static environments @cite_1 , and Nonlinear Velocity Obstacles @cite_10 , which can guarantee collision avoidance for obstacles moving along known trajectories. Our NPVO, which considers the future behavior of an obstacle in a probabilistic sense, is a generalization of these notions.
@cite_10 @cite_1
2150765347 2738812057 2142943472 2157304242
Obstacle avoidance, and by extension collision checking, is a basic requirement for robot autonomy. Most classical approaches to collision-checking ignore the uncertainties associated with the robot and obstacle's geometry and position. It is natural to use a probabilistic description of the uncertainties. However, constraint satisfaction cannot be guaranteed, in this case, and collision constraints must instead be converted to chance constraints. Standard results for linear probabilistic constraint evaluation have been applied to probabilistic collision evaluation; however, this approach ignores the uncertainty associated with the sensed obstacle. An alternative formulation of probabilistic collision checking that accounts for robot and obstacle uncertainty is presented which allows for dependent object distributions (e.g., interactive robot-obstacle models). In order to efficiently enforce the resulting collision chance constraints, an approximation is proposed and the validity of this approximation is evaluated. The results presented here have been applied to robot-motion planning in dynamic, uncertain environments. This work addresses the problem of motion planning among obstacles for quadrotor platforms under external disturbances and with model uncertainty. A novel Nonlinear Model Predictive Control (NMPC) optimization technique is proposed which incorporates specified uncertainties into the planned trajectories. At the core of the procedure lies the propagation of model parameter uncertainty and initial state uncertainty as high-confidence ellipsoids in pose space. The quadrotor trajectories are then computed to avoid obstacles by a required safety margin, expressed as ellipsoid penetration while minimizing control effort and achieving a user-specified goal location. Combining this technique with online model identification results in robust obstacle avoidance behavior. Experiments in outdoor scenarios with virtual obstacles show that the quadrotor can avoid obstacles robustly, even under the influence of external disturbances. In this paper, we propose a new concept - the "Reciprocal Velocity Obstacle"- for real-time multi-agent navigation. We consider the case in which each agent navigates independently without explicit communication with other agents. Our formulation is an extension of the Velocity Obstacle concept [3], which was introduced for navigation among (passively) moving obstacles. Our approach takes into account the reactive behavior of the other agents by implicitly assuming that the other agents make a similar collision-avoidance reasoning. We show that this method guarantees safe and oscillation- free motions for each of the agents. We apply our concept to navigation of hundreds of agents in densely populated environments containing both static and moving obstacles, and we show that real-time and scalable performance is achieved in such challenging scenarios. Most of present work for autonomous navigation in dynamic environment doesn't take into account the dynamics of the obstacles or the limits of the perception system. To face these problems we applied the probabilistic velocity obstacle (PVO) approach (Kluge and Prassler, 2004) to a dynamic occupancy grid. The paper presents a method to estimate the probability of collision where uncertainty in position, shape and velocity of the obstacles, occlusions and limited sensor range contribute directly to the computation. A simple navigation algorithm is then presented in order to apply the method to collision avoidance and goal driven control. Simulation results show that the robot is able to adapt its behaviour to the level of available knowledge and navigate safely among obstacles with a constant linear velocity. Extensions to non-linear, non-constant velocities are proposed.