Real-Time Robotic Search using Structural Spatial Point Processes

Olov Andersson, Per Sidén, Johan Dahlin, Patrick Doherty, Mattias VillaniUAI 2019 · OpenReview

Abstract

Aerial robots hold great potential for aiding Search and Rescue (SAR) efforts over large areas, such as during natural disasters. Traditional approaches typically search an area exhaustively, which is often inefficient given that victims are not distributed randomly. This paper introduces a probabilistic framework for SAR that allows aerial robots to move beyond exhaustive "lawnmower" search patterns. By combining fast Bayesian inference (INLA) with a novel Monte Carlo Tree Search (MCTS) variant, the system learns victim distributions in real-time, significantly reducing the time required to find injured individuals in disaster zones.

Introduction

In the wake of a natural disaster or a terrorist attack, every minute counts. Traditional robotic search strategies often rely on exhaustive coverage—systematically flying over every square meter of a grid. This is inefficient because it ignores a fundamental truth: victims aren't distributed randomly. They cluster near buildings, roads, or specific incident sites. The challenge is that while we might have some prior knowledge (like GIS maps or cell phone traffic), it is often incomplete or inaccurate. A robot needs to be able to integrate prior knowledge, update its beliefs instantly as it observes victims, and plan a path that balances exploration with physical constraints like flight time.

Methodology

The authors propose a "Structural Spatial Point Process" model composed of three interacting spatial fields: Population Intensity (where people are likely to be), Detection Probability (sensor effectiveness), and Injury Probability (likelihood of injury given presence).

Integration of GIS data with the spatial point process model.

To make this work in a "real-time" robotic context, the paper employs two algorithmic techniques:

  1. Integrated Nested Laplace Approximation (INLA): Instead of using slow, traditional sampling methods like MCMC to update the robot's "map" of victims, the authors use INLA. This provides a fast, deterministic approximation for latent Gaussian processes, allowing the robot to update its entire belief state in seconds.
  2. MCTSJump: Standard path planning (moving to adjacent cells) is too slow for large areas. The authors modified Monte Carlo Tree Search to include "action abstractions" or "jumps." This allows the planner to consider flying directly to high-value, distant areas of the map if the expected payoff outweighs the travel time.

Experimental Setup

The researchers used real-world Geographic Information System (GIS) data from the Swedish government (Lantmäteriet) for a 4.0 x 2.7 km area around Gamleby, Sweden. The data included layers for buildings, forests, roads, fields, and water. Victim patterns were simulated based on these layers to create four distinct scenarios (ranging from "No Prior Information" to "Terrorist Attack with Unknown Sites") to test the model's adaptability.

Results and Discussion

The framework was evaluated on the time taken to find 50% of the injured victims. The most significant finding is that even a little bit of real-time learning drastically outperforms a perfect exhaustive search. By updating the "injury model" on the fly, the robot can "stumble" upon a victim and immediately realize it should focus its search in that vicinity.

Comparison of search times (minutes) to find 50% of victims across different scenarios.

In Scenario A (no prior info), the MCTSJump (learning) approach found half the victims in 241 minutes, compared to 835 minutes for the standard lawnmower pattern—a nearly 3.5x speedup. Even compared to "globally greedy" strategies, MCTSJump was faster because it accounts for the long-term cost of travel and the value of future information. The entire inference and planning loop took approximately 5 seconds on a standard Core i7 CPU, making it viable for deployment on actual UAV hardware.

Conclusion

The proposed framework demonstrates that learning trumps exhaustion in large-scale SAR. The "Jump" abstraction in MCTS allows the robot to act more like a human strategist—scouting a high-population area, then leaping across the map to check a remote road or building. Future work will address limitations such as static victim assumptions, single-robot constraints, and the need for dynamic mortality modeling where the urgency of finding a victim changes over time.

Summary updated

Abstract

Aerial robots hold great potential for aiding Search and Rescue (SAR) efforts over large areas, such as during natural disasters. Traditional approaches typically search an area exhaustively, there...
BibTeX
@inproceedings{andersson2019real,
  author = {Olov Andersson and Per Sidén and Johan Dahlin and Patrick Doherty and Mattias Villani},
  title = {{Real-Time Robotic Search using Structural Spatial Point Processes}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=nFaTBqwHR50},
}
Figure