It is a common artifact of multi-agent motion planning for groups of agents, following similar paths, to converge to a line. This occurs because the agents' immediate goals, also known as waypoints, are frequently a common point in space. Contention for the point goal causes agents to line up and generally interferes with agent motion. By extending the definition of an immediate point goal to a line segment, which we call a "way portal", we enable the agents to better utilize the space available to them in responding to dynamic constraints. We present a novel multi-agent navigation algorithm to efficiently compute the trajectories of autonomous agents using these way portals. We have incorporated the concept into a velocity obstacle-based local navigation model and present a new segment optimization algorithm that efficiently computes a new agent velocity with respect to the way portal. We show how way portal data is extracted from current global navigation data structures, such as navigation meshes. The algorithm is relatively simple to implement and has a small run-time cost (approximately 3 μs per agent.) We highlight its performance in different game-like scenarios and observe improved agent behavior and better utilization of free space.

We present an approach for collision avoidance for mobile robots that takes into account acceleration constraints. We discuss both the case of navigating a single robot among moving obstacles, and the case of multiple robots reciprocally avoiding collisions with each other while navigating a common workspace. Inspired by the concept of velocity obstacles [3], we introduce the acceleration-velocity obstacle (AVO) to let a robot avoid collisions with moving obstacles while obeying acceleration constraints. AVO characterizes the set of new velocities the robot can safely reach and adopt using proportional control of the acceleration. We extend this concept to reciprocal collision avoidance for multi-robot settings, by letting each robot take half of the responsibility of avoiding pairwise collisions. Our formulation guarantees collision-free navigation even as the robots act independently and simultaneously, without coordination. Our approach is designed for holonomic robots, but can also be applied to kinematically constrained non-holonomic robots such as cars. We have implemented our approach, and we show simulation results in challenging environments with large numbers of robots and obstacles.

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.

We present an algorithm for collision-free navigation of multiple flying robots in three-dimensional workspace. Our approach extends the model of a simple car to a simple-airplane, which has constraints on speed and steering angle and includes a configuration variable for the altitude. We use a locally optimal reciprocal collision avoidance scheme that computes the trajectory without any collisions or oscillations for each airplane independently. In addition, our algorithm explicitly considers the kinematic and dynamic constraints of a simple-airplane and uses the notion of variable reciprocity when choosing velocities to ensure that simple-airplanes that are less constrained take more responsibility for avoiding collisions. We test our approach in two simulations and compute collision-free and oscillation-free trajectories that satisfy the kinematic and dynamic constraints of each simple-airplane.

We present a method for smooth and collision-free navigation for multiple independent robots under differential-drive constraints. Our algorithm is based on the optimal reciprocal collision avoidance formulation and guarantees both smoothness in the trajectories of the robots and locally collision-free paths. We provide proofs of these guarantees and demonstrate the effectiveness of our method in experimental scenarios using iRobot Create mobile robots navigating amongst each other.

We present an approach for smooth and collision-free navigation of multiple mobile robots amongst each other. 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 predict their future trajectory in order to avoid collisions. Moreover, our approach is reciprocal and avoids oscillations by explicitly taking into account that the other robots also sense their surroundings and change their trajectories accordingly. We build on prior work related to velocity obstacles and reciprocal velocity obstacles and introduce the concept of hybrid reciprocal velocity obstacles for collision avoidance that takes into account the kinematics of the robots and uncertainty in sensor data. We apply our approach to a set of iRobot Create robots using centralized sensing and show natural, direct, and collision-free navigation in several challenging scenarios.