MOBILITY ENGINEERING Produced by SAE Media Group
MOBILITY ENGINEERING
Magazines
Magazine cover

Current Issue

Archives

Magazine cover

Current Issue

Archives

Magazine cover

Current Issue

Archives

Magazine cover

Current Issue

Archives

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

Topics:
Aerospace Automation Automation Autonomous vehicles Command, Control, and Navigation Systems Data acquisition and handling Imaging Motion Control Optimization Positioning Equipment Research and development Robotics Robotics Simulation and modeling Surveillance Surveillance and Security Surveillance and Security Vehicles
This Brief includes a Technical Support Package (TSP).
Document cover
Stochastic Surveillance and Distributed Coordination

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

Don't have an account?

More From SAE Media Group

    Magazine cover
    Aerospace & Defense Technology Magazine

    This article first appeared in the June, 2021 issue of Aerospace & Defense Technology Magazine (Vol. 6 No. 4).

    Read more articles from this issue here.

    Read more articles from the archives here.

    Overview

    The document is a final performance report detailing a research project focused on "Stochastic Surveillance and Distributed Coordination," conducted by Francesco Bullo at the University of California, Santa Barbara, from June 1, 2015, to May 31, 2020. The primary objective of the project was to design efficient and unpredictable motion strategies for autonomous vehicles used in robotic surveillance within complex environments.

    The research emphasized the application of Markov chain modeling and optimization methods to enhance surveillance capabilities. Key achievements included the development of quickest detection algorithms tailored for scenarios involving faults or randomly appearing intruders. The project explored the concept of hitting time in single and multiple Markov chains, which is crucial for understanding the dynamics of pursuit and evasion in surveillance contexts.

    A significant focus was placed on analyzing the expected meeting time between pursuers and evaders engaged in random walks on directed graphs (digraphs). The researchers derived closed-form expressions for the expected meeting time, which is vital for optimizing capture strategies in surveillance operations. Additionally, the project addressed the minimization problem for expected capture time, providing insights into effective coordination strategies for multiple agents.

    The report also highlights the development of a textbook titled "Lectures on Network Systems," which serves as a comprehensive resource for graduate students interested in network systems, distributed algorithms, and cooperative control. The textbook is organized into three main parts: Linear Systems, Topics in Averaging Systems, and Nonlinear Systems, covering essential concepts in matrix and graph theory, dynamical models, and control problems.

    The textbook has gained international recognition, being adopted by approximately 35 instructors across 16 countries, and has been downloaded over 4,700 times since its initial release. It includes numerous examples from various fields, such as ecology, epidemiology, and robotics, making it a valuable educational tool.

    Overall, the document encapsulates significant advancements in the field of robotic surveillance, emphasizing the integration of theoretical models with practical applications. The research outcomes contribute to the understanding of distributed control and coordination in complex environments, paving the way for future innovations in autonomous systems.

    Top Stories

    INSIDERRF & Microwave Electronics

    Feature Image FAA to Replace Aging Network of Ground-Based Radars

    PodcastsDefense

    Feature Image A New Additive Manufacturing Accelerator for the U.S. Navy in Guam

    NewsSoftware

    Feature Image Rewriting the Engineer’s Playbook: What OEMs Must Do to Spin the AI Flywheel

    Road ReadyPower

    Feature Image 2026 Toyota RAV4 Review: All Hybrid, All the Time

    INSIDERDefense

    Feature Image F-22 Pilot Controls Drone With Tablet

    INSIDERRF & Microwave Electronics

    Feature Image L3Harris Starts Low Rate Production Of New F-16 Viper Shield

    Webcasts