Stochastic Surveillance and Distributed Coordination

Designing fast and unpredictable motion strategies for robotic surveillance agents in complex environments using Markov chain modeling and optimization methods.

This research focused on robotic surveillance in complex environments via autonomous vehicles. The chief aim was to design fast and unpredictable motion strategies for surveillance agents. The technical approach focused on Markov chain modeling and optimization methods.

For the setting of faults or randomly appearing intruders, quickest detection algorithms were proposed and the so-called hitting time of both a single and multiple Markov chains were computed and optimized. For example, the meeting time between a pursuer and evader performing random walks was analyzed on digraphs. The closed-form expression for the expected meeting time was obtained and the minimization problem for the expected capture time for a pursuer/evader pair was set up and studied.

On the topic of unpredictable strategies, two notions of entropy for robotic motion were proposed. First, the problem of maximizing the entropy rate generated by a random walk was studied. That showed the equivalence to a semidefinite program for reversible chains. Next came the introduction of a novel concept of unpredictability based on the average entropy of the return time variables at the environment locations. This optimization problem was formally studied and validated the performance of projected gradient algorithms for this problem. The algorithms were validated on basic and random graphs and on a publicly available dataset describing crime statistics in San Francisco.

The Matlab and Julia implementations of the proposed algorithms were distributed in an open source "RoboSurv” library available on GitHub. The research also provided partial support for work by the PI on a network systems book and a few related topics, including synchronization in pulse-coupled oscillators, graph-theoretic small gain theorems for positive and monotone systems, capture strategies for 3D reach-avoid games, and collective cell migration.

In designing efficient surveillance, information gathering, and coordination strategies for robotic networks in dynamic environments and applying them to DoD scenarios, it could be argued that sensor scheduling, motion planning and coordination algorithms for surveillance and anomaly detection is a crucial objective. The key technological challenge is how to search an area in a persistent manner, with minimal average time to detection, with unpredictable trajectories and with optimally partitioned workload among multiple assets.

The key scientific subject is the study of optimization criteria, convexity properties, relaxations and coordination strategies defined via the theory of Markov chains and random walks. This technical approach is based on a combination of tools from the study of Markov chains, convex optimization, dynamical systems, distributed algorithms, robotic coordination, and network systems. The research effort on stochastic surveillance can be articulated via the following tasks:

  1. Characterizing optimal stationary distributions, i.e., deciding where to focus the search efforts;
  2. Computing optimal reversible Markov chains via convex optimization;
  3. Computing optimal non-reversible Markov chains on lifted spaces;
  4. Computing optimal Markov chains with entropy-rate constrains, i.e., designing unpredictable fast searchers;
  5. Designing and characterizing search strategies for randomly moving evaders; and
  6. Defining, analyzing and optimizing an appropriate notion of group Kemeny constant (i.e., a mean first passage time for multiple walkers), thereby designing multivehicle surveillance policies.

This work was done by Francesco Bullo of the University of California, Santa Barbara for the Air Force Research Laboratory. For more information, download the Technical Support Package (free white paper) below. AFRL-0304

This Brief includes a Technical Support Package (TSP).
Stochastic Surveillance and Distributed Coordination

(reference AFRL-0304) is currently available for download from the TSP library.

Don't have an account? Sign up here.