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.
The state-of-the-art Optimal Reciprocal Collision Avoidance" (ORCA) algorithm uses reciprocal velocity obstacles to control multiple agents in unstructured environments @cite_4 . This approach is popular due to its ease of implementation and guarantees that a collision-free trajectory will be found for @math time, if one is available. However, ORCA assumes that all obstacles in the workspace are either static or operating according to the same policy. Violations of this assumption can lead to catastrophic behavior, as shown in Figure . We demonstrate in simulation that our NPVO approach is able to avoid such obstacles, and prove bounds on our algorithm's safety and scalability in reciprocal and multi-agent scenarios.
@cite_4
2524264252 2097639646 6827933 2142943472
Finding feasible, collision-free paths for multiagent systems can be challenging, particularly in non-communicating scenarios where each agent's intent (e.g. goal) is unobservable to the others. In particular, finding time efficient paths often requires anticipating interaction with neighboring agents, the process of which can be computationally prohibitive. This work presents a decentralized multiagent collision avoidance algorithm based on a novel application of deep reinforcement learning, which effectively offloads the online computation (for predicting interaction patterns) to an offline learning procedure. Specifically, the proposed approach develops a value network that encodes the estimated time to the goal given an agent's joint configuration (positions and velocities) with its neighbors. Use of the value network not only admits efficient (i.e., real-time implementable) queries for finding a collision-free velocity vector, but also considers the uncertainty in the other agents' motion. Simulation results show more than 26 percent improvement in paths quality (i.e., time to reach the goal) when compared with optimal reciprocal collision avoidance (ORCA), a state-of-the-art collision avoidance strategy. We present the hybrid reciprocal velocity obstacle for collision-free and oscillation-free navigation of multiple mobile robots or virtual agents. Each robot senses its surroundings and acts independently without central coordination or communication with other robots. Our approach uses both the current position and the velocity of other robots to compute their future trajectories in order to avoid collisions. Moreover, our approach is reciprocal and avoids oscillations by explicitly taking into account that the other robots sense their surroundings as well and change their trajectories accordingly. We apply hybrid reciprocal velocity obstacles to iRobot Create mobile robots and demonstrate direct, collision-free, and oscillation-free navigation. This paper describes a multi-robot collision avoidance system based on the velocity obstacle paradigm. In contrast to previous approaches, we alleviate the strong requirement for perfect sensing (i.e. global positioning) using Adaptive Monte-Carlo Localization on a per-agent level. While such methods as Optimal Reciprocal Collision Avoidance guarantee local collision-free motion for a large number of robots, given perfect knowledge of positions and speeds, a realistic implementation requires further extensions to deal with inaccurate localization and message passing delays. The presented algorithm bounds the error introduced by localization and combines the computation for collision-free motion with localization uncertainty. We provide an open source implementation using the Robot Operating System (ROS). The system is tested and evaluated with up to eight robots in simulation and on four differential drive robots in a real-world situation. 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.