An Artificially Weighted Spanning Tree Coverage Algorithm for Decentralized Flying Robots

In this article, an artificially weighted spanning tree coverage (AWSTC) algorithm is proposed for the distributed path planning of multiple flying robots. To balance well the efficiency, redundancy, and robustness in the cooperative coverage problem, each robot simultaneously constructs its spanning tree, which grows toward the center of inertia of the uncovered area and keeps away from the trees of its partners. Based on this, each robot covers a concerned area with almost equal trajectory length and computational burden. To guarantee dynamical consistency, a trajectory-smoothing method is developed utilizing Bezier curve transition. As transition in the spanning tree path planning is always conducted around the corner with right angle, geometric and velocity profiles of this kind of transition can be preevaluated as a basic component and then connected to establish more complex real-time trajectories according to the constructed spanning trees. Numerical evaluations and real-time flight experiments are carried out at last. Results demonstrate that the proposed strategy can generate a smooth trajectory for an area coverage problem while ensuring efficiency and robustness. In particular, the efficiency of the proposed algorithm is quite close to the typical centralized spanning tree coverage (STC) algorithm, while ensuring the fulfillment of the coverage task regardless of any breakdown in the individual robot. Note to Practitioners-In applications such as infrastructure inspection and plant protection, the concerned area or terrain is required to be fully covered with the smallest possible time consumption. In view of these real-world requirements, multiple unmanned systems with proper path planning provide a promising solution that can significantly enhance the efficiency as well as the robustness, compared with a single-robot system. Especially, centralized STC algorithms, concerning the computation efficiency and trajectory redundancy of multiple unmanned systems, demonstrate satisfactory effectiveness, and thereby receive a lot of attention. Unfortunately, most of the STC algorithms are proposed in a centralized control framework. Therefore, it is worth to study its decentralized version that could exploit the advantages of the distributed multiple robots. With this consideration, a decentralized AWSTC algorithm is proposed in this article. This spanning tree-based strategy artificially assigns priority weight for each cell, with respect to each individual robot, in the concerned area. With specially designed weight assignment, each robot tends to construct a spanning tree with cells that are uncovered but keep away from the trees of its partners. Based on this, the task burden as well as computational cost of each robot are almost equal. To improve the real-time performance, a Bezier transition trajectory-generation method is also used. With proper parameter selection, robots can generate smooth trajectory with constant velocity in real-time missions. Numerical evaluations and experiments with real-time flight demonstrate the effectiveness of this methodology.