THIS IS A CONTINUATION OF N00014-12-1-0999 Decentralized online optimization in multi-agent systems in dynamic and uncertain environments
Abstract
Statement of Work:The research will concentrate on two main problem areas: one dealing with deploying autonomous multi-agent systems for spatial exploration, information harvesting, and/or information transmission; and the other dealing with dynamic decentralized resource allocation problems with local and global controls and objectives.Objective:In the research discussed in this proposal, the PI proposes to concentrate on two main problem areas within this context: one dealing with (i) deploying autonomous multi-agent systems for spatial exploration, information harvesting, and/or information transmission; and the other dealing with (ii) dynamic decentralized resource allocation problems with local and global controls and objectives.Approach:Both areas address key decentralized online optimization issues associated with multi-agent systems operating under dynamic and uncertain environment and under limited communication capabilities, but each with its own speci cchallenges (the first stressing online mobility and spatial exploration with a common objective in an unknown and possibly adversarial terrain; the second stressing decentralized online resource allocation with both local and global objectives). In both cases, the PI proposes key canonical models on which they will to concentrate their efforts in designing and rigorously analyzing algorithmic strategies. Their technical approaches will come from the perspectivesmost naturally linked to the operations research, optimization, and computer science communities. More specically, they will use and develop state-of-the-art techniques from online optimization and robust optimization, and their interplays.Overall Merit and ONR Mission/Relevance:The research is innovative in that it includes the development of rigorous algorithmic-analysis techniques for decentralized online optimization that provides performance predictions through sound estimates of the closeness a decentralized online solution to a centralized, global offline optimal solution; such performance guarantees contribute tremendously to trust in these systems, which is critical for their deployment. The Navy is moving towards deploying large, complex systems that are beyond centralized control. A canonical example of such a system is a fleet of unmanned vehicles with limited communications operating in a dynamic environment. Important characteristics of these systems are that 1) they are decentralized (i.e., system componentscan take independent actions), and 2) the environment in which the system operates is not necessarily known a priori, and is revealed over time. The objective of this topic is to develop scientific principles and algorithms for solving decentralized, online optimization problems.Progress: In this continuing work, the PIs consider several extensions of the weapons coordination problem whose objective is to protect assets in a fleet from incoming threats. They prove that this highly nonlinear discrete optimization problem can be solved with MIP callback techniques, and therefore optimal solution can be obtained online for instances of a practical size. This paper also introduces a new extended MIP formulation for multi-period scenario, when the fleet hasto plan the defense strategy for several consecutive attacks. Finally, we develop a communication and coordination protocols for the decentralized version of the problem, in which captains of the assets have to make local decisions based on their own objectives and some limited communication with other ships. Under some practical assumptions, suggested protocol is proven to be optimal from perspective of communication capacities allocation and weapon assignment under uncertainty. More precisely, this paper provides the following main new contributions:a. Automated centralized defense algorithm previously obtained in [1] has the form of highly nonlinear mixed integer assignment problem. The suggested second-order formulation allows to find solutio
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 23, 2016
- Source ID
- N000141612786
Entities
People
- Patrick Jaillet
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy