A cell decomposition approach to cooperative path planning and collision avoidance via disjunctive programming

This paper presents a novel approach for planning the minimum-distance path of multiple robotic vehicles with discrete geometries in an obstacle-populated workspace. The approach utilizes approximate cell decomposition to obtain a disjunctive program representation of C-obstacles for obstacles that are not necessarily convex polyhedrons, and robot geometries that are capable of rotating and translating in a Euclidian workspace. In order to produce programs that are computationally tractable, this approach derives a subset of all possible inequality constraints by pruning the connectivity graph based on adjacency relationships between cells, and the principle of optimality. The approach overcomes the limitations of existing approaches by simultaneously planning the paths of multiple robots, subject to any kinodynamic constraints, in environments populated by a large number of non-convex non-polyhedral obstacles. The approach is implemented using readily-available software, such as TOMLAB/CPLEX, and is illustrated here through several numerical simulation examples.