Obstacle-aware MDNets for Sampling Polytope Trees in Multi-robot Formation Path Planning

We present obstacle-aware MDNets (OMDNets) for path planning of multi-robot formation. In contrast to the RRT tree, each node of the OMDNets tree represents a feasible region for one or more formations. Moreover, each tree edge connects two feasible region centers that share at least one configuration. The construction of this tree requires node sampling and connecting. However, the existing method based on random sampling is inefficient due to the lack of information about obstacles. Also, the formation is not considered while connecting nodes. Therefore, OMDNets accept obstacle information as input and output the next practical point that generates an obstacle-free convex polytope. Moreover, a rapid checker based on the Minkowski approach is proposed for determining if two feasible regions can be connected. After establishing the tree, tree search and nonlinear optimization identify the path to the objective with the lowest cost. OMDNets is compared to different algorithms in a variety of 2D situations. The results demonstrate that OMDNets is computationally efficient and capable of locating shorter feasible paths.