Probabilistic Guidance for Swarms of Autonomous Agents
- Created on Saturday, 01 March 2014
- NASA’s Jet Propulsion Laboratory, Pasadena, California
A probabilistic approach is simpler to implement as the number of agents becomes large.
Available guidance approaches for large numbers (i.e., swarms) of artificial agents are currently very limited. Swarms in nature (e.g., bees, birds, ants) typically contain hundreds to thousands of agents. The problem is how to mimic nature, and develop guidance laws for artificial (manmade) swarms containing hundreds to thousands of artificial agents.
A new guidance solution lets go of conventional deterministic approaches and instead looks at statistical approaches. Because swarms contain a statistically meaningful number of agents, a probabilistic approach is more relevant to the problem. In particular, a probabilistic guidance approach (PGA) has been developed that controls the statistical ensemble (i.e., the desired probability density across a swarm of agents), rather than any single individual agent’s trajectory. Because the PGA works with a statistically large ensemble of agents, the “law of large numbers” kicks in, and the PGA approach actually becomes more accurate and simpler to implement as the number of agents becomes large. This is in sharp contrast to deterministic approaches to swarm guidance that become more complex and unwieldy as the number of agents becomes large.
The main idea is to have each agent follow an independent realization of a Markov chain. The desired distribution emerges as the ensemble of agents in the swarm maneuvers about, asymptotically achieving a desired statistical steady-state condition, and eliciting a clear emergent behavior from the swarm. The implementation of the probabilistic guidance law is completely decentralized, and leads to an important swarm behavior that exhibits autonomous self-repair and maintenance capabilities.
The development area relies heavily on the theory of Markov processes, Monte-Carlo-Markov-Chain sampling methods, graph theory, and Lyapunov stability analysis. The development is aided by recent research in designing fast mixing Markov chains that converge to desired distributions and incorporate constraints on transition probabilities, and many classical results on convergence of Markov chains.
The main novel feature is that the PGA guidance law is probabilistic in nature, and specifies the desired spatial probability density distribution for the swarm rather than the exact desired paths of the individual agents. Consequently, PGA is a more natural and useful guidance statement when dealing with swarms comprised of a statistically large number of agents, compared to deterministic methods that become unwieldy as the number of agents becomes large.