You are here

Managing Emergent Behavior of Interacting Autonomous Systems

Description:

 
 

PROPOSALS ACCEPTED: Phase I and DP2. Please see the 16.2 DoD Program Solicitation and the DARPA 16.2 Direct to Phase II Instructions for DP2 requirements and proposal instructions.

TECHNOLOGY AREA(S): Battlespace, Information Systems

The technology within this topic is restricted under the International Traffic in Arms Regulation (ITAR), which controls the export and import of defense-related material and services. Offerors must disclose any proposed use of foreign nationals, their country of origin, and what tasks each would accomplish in the statement of work in accordance with section 5.4.c.(8) of the solicitation.

OBJECTIVE: Develop meta-heuristic algorithms for the management of interacting autonomous agents by leveraging insights from highly resilient biological systems.

DESCRIPTION: Modern warfare requires reacting to ever-greater numbers of autonomous systems, not only in the form of vehicles, but also as agents working in cyber defense [1,2] and in social media [3,4]. As a result, there is a critical DoD need for the development of control strategies for groups of autonomous agents ("swarms"), in particular, strategies that would allow for resilient performance when interacting with other (friendly, neutral, or hostile) swarms employing their own, potentially unknown, strategies. Such interactions can lead directly to unexpected and potentially adverse emergent behaviors. The U.S. stock market “flash crash” of 2010 [5,6] is one example of adverse emergent behavior resulting from, in part, the interaction of autonomous agents with proprietary and largely unobservable internal workings.

In future joint operations, coordination of swarms will become a strict requirement to prevent unwanted emergent behavior. Similarly, managing interactions with neutral and adversarial autonomous agents in “gray zone” [7] and major combat operations will be essential. In all cases, the autonomous agents may be required to function and coordinate/manage interactions under a large variety of conditions without a robust model of their interacting partner or adversary systems. This lack of models makes the common modeling- and simulation-based approach to the design of autonomous system control strategies [8] less effective. An alternative approach is to focus on developing novel control strategies based on advanced meta-heuristic algorithms [9] that provide the necessary resilience to interactions with other systems.

Research into the social behavior of species such as wasps, ants, and bees [10-12] (as well as the collective behavior of cells [13], such as bacteria, yeast, and amoebae) has the potential to help identify useful such meta-heuristic control strategies, as they (a) exhibit strong parallels to autonomous agents, with processing and action at both individual and group levels [10], (b) necessarily and routinely engage in interactions within colonies, across colonies, across species, and across varied environments, and (c) have evolved highly resilient policies governing a number of forms of synchronized and coordinated behavior. The study of biological systems and their control strategies—which have evolved over millions of years to provide resilience in the face of a wide array of challenges—has already contributed significantly to computer science [14–17] and autonomous systems research [18–20].

Furthermore, research on non-vertebrate species can typically be done rapidly and at low cost, with established rigorous experimental practices for investigating specific classes of interactions. These biological systems therefore represent a vast natural library of meta-heuristic algorithms that could be used in the design of control strategies, and, in addition, can serve an experimental platform for investigating specific classes of interactions.

The focus of this work will be on leveraging research in biological systems to identify strategies and develop algorithms for coping with emergent behavior in shared environments with both competitive and non-competitive autonomous systems. Domains of interest include, but are not limited to: cyber defense, social media, data-mining, unmanned vehicles, and complex system design (see, e.g., [21]).

PHASE I: Define one or more compelling problem domains related to national security where swarms of autonomous agents interact in shared environments. Identify one or more non-vertebrate species (not subject to animal use guidelines) that can provide insights into the control of autonomous agents and provide detailed rationale for their selection. Develop experimental design for biological system study and conduct a pilot study. Prototype a software framework for testing, in simulation, algorithms embodying new meta-heuristic control strategies. Develop and demonstrate simple algorithms based on the result of the pilot study and/or prior research data, explicitly show the biological system basis for the strategies, and compare performance to existing algorithms. The Phase I final report will include an experimental plan to be executed under Phase II.

PHASE II: Execute the experimental plan developed under Phase I to study the most informative forms of interaction in the chosen species. Develop and demonstrate algorithms based on results of the experiments, explicitly show the biological basis for the strategies, and compare performance to existing strategies. Implement the software framework for testing, in simulation, algorithms embodying higher-level control strategies. Evaluate algorithms against existing state of the art, and demonstrate the biological system basis for the strategies. Identify target autonomous systems that could adopt resulting algorithms. Deliverables will include software (source code) and technical reports, and the Phase II final report with recommendations for transitioning the algorithms to operational systems.

PHASE III DUAL USE APPLICATIONS: The DoD has considerable interest in ensuring successful interoperation of autonomous systems (and systems of such systems) in joint operations with partner nations. Therefore, the goal during Phase III will be on transitioning algorithms to specific platforms and their respective programs of record, as well as transitioning the software framework for testing control strategies for use in laboratory environments. This will entail development of application-specific software, hardening the algorithms, and ensuring performance on application-specific hardware as well as in real-world and real-time environments.

REFERENCES:

  • Tirenin, W. & Faatz, D. A concept for strategic cyber defense. In Proceedings of the Military Communications Conference MILCOM 1999, vol.1, 458–463, (1999).
  • Saydjari, O. S. Cyber defense: Art to science. Communications of the ACM, 47, 52–57, (2004).
  • Duggan, P. M. Strategic Development of Special Warfare in Cyberspace. Joint Force Quarterly, 79, 46–53, (2015).
  • Boshmaf, Y., Muslukhov, I. & Beznosov, K. Key challenges in defending against malicious socialbots. In Proceedings of the 5th USENIX conference on Large-Scale Exploits and Emergent Threats, (2012).
  • Kirilenko, A., Kyle, A., Samadi, M., &smp; Tuzun, T. The Flash Crash: The Impact of High Frequency Trading on an Electronic Market, SSRN, (2011).
  • Easley, D., de Prado, M., & O’Hara, M. The Microstructure of the ‘Flash Crash’: Flow Toxicity, Liquidity Crashes and the Probability of Informed Trading. J. of Portfolio Mgt., 37 (2), 118-128, (2011).
  • Kapsuta, P. The Gray Zone. Special Warfare, October-December, (2015).
  • Hodicky, J. (Ed.) Modelling and Simulation for Autonomous Systems, Proceedings of 2nd International Workshop, MESAS, (2015).
  • Glover, F., & Kochenberger, G.A. Handbook of metaheuristics 57. Springer, International Series in Operations Research & Management Science, (2003).
  • Fewell, J. H. Social Biomimicry: What do ants and bees tell us about organization in the natural world? Journal of Bioeconomics 17, 207–216, (2015).
  • Sumpter, D. Collective animal behavior. Princeton, (2010).
  • Garnier, S., Murphy, T., Lutz, M., Hurme, E., Leblanc,S. & Couzin, I. Stability and Responsiveness in a Self-Organized Living Architecture. PLoS Computational Biology 9(3), (2013).
  • Ratzke, C. & Gore, J. Shaping the Crowd: The Social Life of Cells (Preview). Cell, 1(5), 310-312, (2015).
  • Bonabeau, E., Theraulaz, G., & Dorigo, M. Swarm Intelligence: From Natural to Artificial Systems. Springer, (1999).
  • Dorigo, M. & Blum, C. Ant Colony Optimization Theory: A Survey. Theo. Comp. Sci., 344 (2-3), 243-278, (2005).
  • Karaboga, D., & Basturk, B. A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm. Journal of global optimization, 39(3), 459-471, (2007).
  • Dressler, F., & Akan, O. B. A survey on bio-inspired networking. Computer Networks, 54(6), 881-900, (2010).
  • Hsieh, M. A., Halász, Á., Berman, S. & Kumar, V. Biologically inspired redistribution of a swarm of robots among multiple sites. Swarm Intelligence, 2(2), 121-141, (2008).
  • Yu, C.-H. & Nagpal, R. Biologically-Inspired Control for Multi-Agent Self-Adaptive Tasks. American Association for Artificial Intelligence (AAAI) Press, (2010).
  • Pfeifer, R., Lungarella, M. & Iida, F. Self-organization, embodiment, and biologically inspired robotics. Science 318, 1088–1093, (2007).
  • Jennings, N. R. An agent-based approach for building complex software systems. Communications of the ACM 44, 35–41, (2001).

KEYWORDS: autonomous systems, swarms, control theory, bio-inspired computing, emergent behavior, animal models, self-organizing systems, artificial intelligence

US Flag An Official Website of the United States Government