We consider the kinodynamic multi-robot planning problem in cluttered 3-D workspaces. Reachability analysis on position invariant geometric trees is leveraged to find kino- dynamically feasible trajectories for the multi-robot team from potentially non-stationary initial states. The key contribution of our approach is that a collision-free geometric solution guarantees a kinodynamically feasible, safe solution without additional refinement. Simulation results with up-to 40 robots and hardware results with 5 robots suggest the viability of the proposed approach for online planning and replanning for large teams of aerial robots in cluttered 3-D workspaces.

This work addresses planning for multi-robot formations online in cluttered environments via a data-driven search approach. The user-specified objective function governing formation shape and rotation is expressed in terms of offline demonstrations of robot motions (performed in an obstacle free environment). We leverage the offline demonstration to inform online planning for coordinated motions in the presence of obstacles. We formulate planning as a discrete search over demonstrated multi-robot actions, and select actions using a best-first approach to minimize edge expansions for fast online operation. Actions are selected using a heuristic based on their probability distribution exhibited in the demonstration, and we show that this approach is able to recreate coordinated motions exhibited in the demonstration when navigating in the obstructed conditions of the cluttered test environments. We demonstrate results in simulation over environments with increasing numbers of obstacles, and show that resulting plans are collision free and obey dynamic constraints.

In this work, we consider the problem of online centralized kinodynamic multi-robot replanning (from potentially non-stationary initial states) and coordination in known and cluttered workspaces. Offline state lattice reachability analysis is leveraged to decouple the planning problem into two sequential graph searches-one in the explicit geometric graph of the environment and the other in the graph of the higher-order derivatives of the robot's state-in a manner such that the intermediate vertices of a safe set of geometric paths are guaranteed to have a feasible assignment of higher-order derivatives. Without additional iterative refinement procedures, the resulting time parameterized polynomial trajectories are dynamically feasible and collision-free. Planning results with up to 20 robots in two and three dimensional workspaces suggest the suitability of the proposed approach for multi-robot replanning in known environments.

We consider the problem of generating dynamically feasible and safe plans for teams of aerial robots (quadrotors) while holding a fixed relative formation as well as transitioning between a sequence of formations. We extend the existing assignment and planning approaches for quadrotor teams to find minimal-time trajectories to enable team transition between non-rest initial and ending states while ensuring dynamic feasibility with respect to predefined kinematic, dynamic, and collision constraints. This work also presents a method for safe splitting and merging of robot formations according to input specification. The proposed methodology is capable of generating dynamically feasible and safe plans for teams of quadrotors in real time. We validate the performance of the proposed approach through various trials and scenarios conducted in simulation.