Robust distributed planning strategies for autonomous multi-agent teams

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2012.Cataloged from department-submitted PDF version of thesis. This electronic version was submitted and approved by the author's academic department as part of an electronic thesis pilot project. The certified thesis is available in the Institute Archives and Special Collections.Includes bibliographical references (p. 225-244).The increased use of autonomous robotic agents, such as unmanned aerial vehicles (UAVs) and ground rovers, for complex missions has motivated the development of autonomous task allocation and planning methods that ensure spatial and temporal coordination for teams of cooperating agents. The basic problem can be formulated as a combinatorial optimization (mixed-integer program) involving nonlinear and time-varying system dynamics. For most problems of interest, optimal solution methods are computationally intractable (NP-Hard), and centralized planning approaches, which usually require high bandwidth connections with a ground station (e.g. to transmit received sensor data, and to dispense agent plans), are resource intensive and react slowly to local changes in dynamic environments. Distributed approximate algorithms, where agents plan individually and coordinate with each other locally through consensus protocols, can alleviate many of these issues and have been successfully used to develop real-time conflict-free solutions for heterogeneous networked teams. An important issue associated with autonomous planning is that many of the algorithms rely on underlying system models and parameters which are often subject to uncertainty. This uncertainty can result from many sources including: inaccurate modeling due to simplifications, assumptions, and/or parameter errors; fundamentally nondeterministic processes (e.g. sensor readings, stochastic dynamics); and dynamic local information changes. As discrepancies between the planner models and the actual system dynamics increase, mission performance typically degrades. The impact of these discrepancies on the overall quality of the plan is usually hard to quantify in advance due to nonlinear effects, coupling between tasks and agents, and interdependencies between system constraints. However, if uncertainty models of planning parameters are available, they can be leveraged to create robust plans that explicitly hedge against the inherent uncertainty given allowable risk thresholds. This thesis presents real-time robust distributed planning strategies that can be used to plan for multi-agent networked teams operating in stochastic and dynamic environments. One class of distributed combinatorial planning algorithms involves using auction algorithms augmented with consensus protocols to allocate tasks amongst a team of agents while resolving conflicting assignments locally between the agents. A particular algorithm in this class is the Consensus-Based Bundle Algorithm (CBBA), a distributed auction protocol that guarantees conflict-free solutions despite inconsistencies in situational awareness across the team. CBBA runs in polynomial time, demonstrating good scalability with increasing numbers of agents and tasks. This thesis builds upon the CBBA framework to address many realistic considerations associated with planning for networked teams, including time-critical mission constraints, limited communication between agents, and stochastic operating environments. A particular focus of this work is a robust extension to CBBA that handles distributed planning in stochastic environments given probabilistic parameter models and different stochastic metrics. The Robust CBBA algorithm proposed in this thesis provides a distributed real-time framework which can leverage different stochastic metrics to hedge against parameter uncertainty. In mission scenarios where low probability of failure is required, a chance-constrained stochastic metric can be used to provide probabilistic guarantees on achievable mission performance given allowable risk thresholds. This thesis proposes a distributed chance-constrained approximation that can be used within the Robust CBBA framework, and derives constraints on individual risk allocations to guarantee equivalence between the centralized chance-constrained optimization and the distributed approximation. Different risk allocation strategies for homogeneous and heterogeneous teams are proposed that approximate the agent and mission score distributions a priori, and results are provided showing improved performance in time-critical mission scenarios given allowable risk thresholds.by Sameera S. Ponda.Ph.D