Scalable Optimal Formation Path Planning for Multiple Interconnected Robots via Convex Polygon Trees

A Reconfigurable Modular Robotic System (RMRS) consists of multiple interconnected robots and can achieve various functionalities by rearranging its modular robots, such as transporting loads of various shapes. The path planning for an RMRS involves the system motion and also its formation arrangements. Sampling-based path planning for the RMRS might be inefficient due to the formation variety. Recently, convex subsets of the obstacle-free workspace, referred to as polygon nodes, are instead sampled to formulate constrained optimization problems. The success rate of sampling is however unsatisfactory due to connectivity requirements. This paper proposes an obstacle-aware mixture density network to guide the generation of polygon nodes, where the connectivity of polygon nodes is guaranteed by non-zero Minkowski differences between the formation geometry and the intersection of nodes. Subsequently, Convex-Polygon Trees* (CPTs*) are proposed to connect these polygon nodes in an RRT* manner, outputting candidates of convex optimization problems. The optimality degeneration due to distance approximation is proven bounded and the computational complexity is shown linear to the Lebesgue measure of the entire workspace space. Numerical simulations have shown that in most tested large and cluttered environments the CPT* is more than 8 times faster than an existing constrained optimization method. The results have also shown CPT*’ improved scalability to large environments and enhanced efficiency in dealing with narrow passages.