Real-Time Decision Making in Swarm Situations Using Belief Networks

Gerald Friedland | 17-ERD-096

Overview

A significant challenge in the field of data science is determining how to prioritize inputs of information coming from various sources. How does one make the best possible decisions that will lead to optimizing the information? Belief propagation in graphical Bayesian models (probabilistic neural networks) is a powerful statistical tool that enables self-healing in the presence of noisy or corrupted data, adaptive reconfiguration when new data are presented, and the ability to reconfigure when confronted with unknown scenarios. In this project, we contributed new theoretical foundations to improve the computational complexity of belief propagation and to create models that address realistic swarm scenarios in a self-organizing way.

Background and Research Objectives

Given intelligence gathered from diverse sources, including in a swarm situation of many autonomous gathering entities, one naturally asks the question, "How do we best exploit and combine the available information to maximize benefit?" A principled approach is to capture the sources and their statistical dependencies using graphical models, with the goal of doing inference over the graph through inter-node communication involving exchange of probability estimates between the nodes in the graph. These generative graphical models are usually known as belief networks, Bayes(ian) networks, or Bayes(ian) graphical models that represent a set of random variables and their conditional dependencies via a directed acyclic graph. For example, a Bayesian network could represent the probabilistic relationships between diseases and symptoms. Given symptoms, the network can be used to compute the probabilities of the presence of various diseases. Alternatively, when mapped to a swarm intelligence-gathering scenario as we consider here, it could represent the values or states of (possibly multi-dimensional) sensor measurements related to the environment being sensed or surveilled. While graphics processing units (GPUs) could be used to improve the speed of belief networks, a host of relevant swarm applications (such as those that form the motivation for this proposal) involve small-footprint and low-power devices that cannot be fitted with power-hungry GPUs. For example, in autonomous vehicles or drone applications, battery power is a major concern.

Our goal was to develop a prototype and evaluate real-time, swarm decision making by posing representative challenges in a Bayesian graphical model framework optimized for modeling, analysis, interpretability, and formulation of provably efficient, probabilistic inference algorithms. We explored both specialized hardware that can run these algorithms in a power-efficient platform and the structure of efficient swarm architectures that enable real-time collaboration and re-configurability based on detected changes in the sensing environment. While there has been significant work in swarm intelligence over the last few decades, hardware-accelerated belief networks have not been explored and represent a unique capability at Lawrence Livermore National Laboratory.

Impact on Mission

This study applies to a variety of Laboratory and national programs that employ distributed intelligence sensor readings or combine the outputs of machine learning. In so doing, our research advances the science, technology, and engineering competencies that are the foundation of the NNSA mission. The project advances the state of the art in collaborative autonomy relevant to nuclear nonproliferation and defense-related situational awareness and response needs, all of which support of the Laboratory’s R&D challenges in cyber security and space security. By creating models for swarm-situation intelligence gathering, this study supports the Laboratory’s core competencies in high-performance computing, simulation, and data science.

Conclusion

Our goal was to create an understanding of the bottlenecks of swarm decision making using belief networks and to create a demonstrator that simulates methods to address them with algorithmic or hardware approaches. Specifically, we completed a demonstrator of a belief network for swarm decision making in search and recovery simulations. We also showed that the intellectual capacity of swarms grows additively if the drones are fully connected. Our research resulted in advances in the fields of machine learning, information theory, scientific computing, and others.

Publications and Presentations

Friedland, G. and M. Krell. 2017. "Capacity Scaling Law for Artificial Neural Networks." arXiv . August 2017. LLNL-TR-736950.

Friedland, G. and A. Metere. 2017. "An Isomorphism Between Lyapunov Exponents and Shannon's Channel Capacity." arXiv . June 2017. LLNL-TR-733786.