Robust and decentralized task assignment algorithms for UAVs

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2007.Includes bibliographical references (p. 149-158).This thesis investigates the problem of decentralized task assignment for a fleet of UAVs. The main objectives of this work are to improve the robustness to noise and uncertainties in the environment and improve the scalability of standard centralized planning systems, which are typically not practical for large teams. The main contributions of the thesis are in three areas related to distributed planning: information consensus, decentralized conflict-free assignment, and robust assignment. Information sharing is a vital part of many decentralized planning algorithms. A previously proposed decentralized consensus algorithm uses the well-known Kalman filtering approach to develop the Kalman Consensus Algorithm (KCA), which incorporates the certainty of each agent about its information in the update procedure. It is shown in this thesis that although this algorithm converges for general form of network structures, the desired consensus value is only achieved for very special networks. We then present an extension of the KCA and show, with numerical examples and analytical proofs, that this new algorithm converges to the desired consensus value for very general communication networks. Two decentralized task assignment algorithms are presented that can be used to achieve a good performance for a wide range of communication networks. These include the Robust Decentralized Task Assignment (RDTA) algorithm, which is shown to be robust to inconsistency of information across the team and ensures that the resulting decentralized plan is conflict-free. A new auction-based task assignment algorithm is also developed to perform assignment in a completely decentralized manner where each UAV is only allowed to communicate with its neighboring UAVs, and there is no relaying of information.(cont.) In this algorithm, only necessary information is communicated, which makes this method communication-efficient and well-suited for low bandwidth communication networks. The thesis also presents a technique that improves the robustness of the UAV task assignment algorithm to sensor noise and uncertainty about the environment. Previous work has demonstrated that an extended version of a simple robustness algorithm in the literature is as effective as more complex techniques, but significantly easier to implement, and thus is well suited for real-time implementation. We have also developed a Filter-Embedded Task assignment (FETA) algorithm for accounting for changes in situational awareness during replanning. Our approach to mitigate "churning" is unique in that the coefficient weights that penalize changes in the assignment are tuned online based on previous plan changes. This enables the planner to explicitly show filtering properties and to reject noise with desired frequencies. This thesis synergistically combines the robust and adaptive approaches to develop a fully integrated solution to the UAV task planning problem. The resulting algorithm, called the Robust Filter Embedded Task Assignment (RFETA), is shown to hedge against the uncertainty in the optimization data and to mitigate the effect of churning while replanning with new information. The algorithm demonstrates the desired robustness and filtering behavior, which yields superior performance to using robustness or FETA alone, and is well suited for real-time implementation. The algorithms and theorems developed in this thesis address important aspects of the UAV task assignment problem. The proposed algorithms demonstrate improved performance and robustness when compared with benchmarks and they take us much closer to the point where they are ready to be transitioned to real missions.by Mehdi Alighanbari.Ph.D