Multi Agent Motion Planning

About the Project

Multi-robot systems are designed to achieve tasks by collaboration. A key requirement for their efficient operation is good coordination and collision avoidance. Various methods have previously been proposed for single robot cases but when applied to multi-robot systems they often are computationally expensive. This project proposes novel collision avoidance strategies for a group of non-holonomic robots such as non-holonomic optimal reciprocal collision avoidance(NH-ORCA). A set of planners are developed for aerial vehicles as well that have low-computational complexity.

NH-ORCA works by controlling robots to stay within a maximum tracking error of the ideal trajectory. This builds on an approach called ORCA which worked well for holonomic robots. NH-ORCA is a fast and distributed method that can deal with crowded situations as well and helps robotic systems achieve smooth and visually appealing trajectories. Several experiments are conducted and recorded with a number of non-holonomic puck robots which help demonstrate the effectiveness of this method.

Another contribution of this project was the development of methods based on Velocity Obstacles(VO) to provide real-time motion planning for quadrotors. This provides a local motion planner which considers motion constraints, static obstacles and other agents. The approaches are either centralised or distributed and have been applied to varying sizes of quadrotor agent groups. Succesful performance was shown in these experiments with up to four quadrotors in close proximity and including humans.

Project Demonstrations

Funding & Partners

This project was performed at ETH Zurich and funded by Disney Research Zurich.

In this paper, we present a method, namely € CCA, for collision avoidance in dynamic environments among interacting agents, such as other robots or humans. Given a preferred motion by a global planner or driver, the method computes a collision-free local motion for a short time horizon, which respects the actuator constraints and allows for smooth and safe control. The method builds on the concept of reciprocal velocity obstacles and extends it to respect the kinodynamic constraints of the robot and account for a grid-based map representation of the environment. The method is best suited for large multirobot settings, including heterogeneous teams of robots, in which computational complexity is of paramount importance and the robots interact with one another. In particular, we consider a set of motion primitives for the robot and solve an optimization in the space of control velocities with additional constraints. Additionally, we propose a cooperative approach to compute safe velocity partitions in the distributed case. We describe several instances of the method for distributed and centralized operation and formulated both as convex and nonconvex optimizations. We compare the different variants and describe the benefits and tradeoffs both theoretically and in extensive experiments with various robotic platforms: robotic wheelchairs, robotic boats, humanoid robots, small unicycle robots, and simulated cars.

This article describes an investigation of local motion planning, or collision avoidance, for a set of decision-making agents navigating in 3D space. The method is applicable to agents which are heterogeneous in size, dynamics and aggressiveness. It builds on the concept of velocity obstacles (VO), which characterizes the set of trajectories that lead to a collision between interacting agents. Motion continuity constraints are satisfied by using a trajectory tracking controller and constraining the set of available local trajectories in an optimization. Collision-free motion is obtained by selecting a feasible trajectory from the VO’s complement, where reciprocity can also be encoded. Three algorithms for local motion planning are presented—(1) a centralized convex optimization in which a joint quadratic cost function is minimized subject to linear and quadratic constraints, (2) a distributed convex optimization derived from (1), and (3) a centralized non-convex optimization with binary variables in which the global optimum can be found, albeit at higher computational cost. A complete system integration is described and results are presented in experiments with up to four physical quadrotors flying in close proximity, and in experiments with two quadrotors avoiding a human.

In this paper the problem of estimation and correction of wind effects on a quadrotor UAV, without using wind sensors, is discussed. A large body of research addresses the effects of wind on a quadrotor, however most of them consider it only as a disturbance in their control loop and, for this reason, they solved the problem compensating for the wind with a powerful controller. The main part of this paper is related to the modeling of wind on a quadrotor and to the wind tunnel tests performed at the IFD wind tunnel of ETH Zurich. The approach presented can be used as a starting point for future works. The results obtained in the wind tunnel are really promising for the formulation of a complete aerodynamic model of the quadrotor that has been missing until now.

About the Project

Project Demonstrations

Funding & Partners

Related Publications