Estimating Activity at Multiple Scales using Spatial Abstractions

Majd Hawasly, Florian T. Pokorny, Subramanian RamamoorthyarXiv 2016 · arXiv

Introduction

Autonomous agents operating in dynamic environments, such as self-driving cars or maritime vessels, must predict the future actions of surrounding entities to ensure safety and efficiency. While traditional state estimation techniques like particle filters are adept at tracking precise coordinates, they often struggle to incorporate "coarse" or qualitative information—such as a human observer noting that a vehicle is "heading toward the exit." Furthermore, intent is inherently hierarchical; a ship follows a specific lane within a broader navigation plan.

This paper introduces the Multiscale Hierarchy of Particle Filters (MHPF), a framework designed to bridge the gap between low-level sensor data and high-level behavioral abstractions. By integrating hierarchical trajectory clustering with a synchronized stack of particle filters, MHPF enables robots to track and predict activities across multiple resolutions simultaneously.

Methodology

The MHPF framework operates through a two-stage process: hierarchical abstraction followed by multiscale filtering.

Hierarchical Abstraction of Trajectories

The system first builds a library of movement patterns from historical data. Using agglomerative clustering based on the discrete Fréchet distance, the framework generates a "filtration" of trajectory abstractions. This results in a tree structure where leaf nodes represent specific, high-resolution paths, and higher-level nodes represent broader, more generalized movement classes.

Figure 1: Visualization of trajectory clusters at different levels of abstraction. Colored lines represent specific clusters within the broader set of historical trajectories (grey).

Multiscale Hierarchy of Particle Filters (MHPF)

The core of the system is a "stack" of particle filters, where each filter corresponds to a node in the abstraction tree. A key innovation is the implementation of update rules that maintain probabilistic consistency across the hierarchy. When a specific path (leaf) becomes more likely based on sensor data, its parent nodes (general behaviors) are updated accordingly. This structure allows the system to process both "fine" observations (e.g., Euclidean distance to a point) and "coarse" observations (e.g., categorical intent) seamlessly.

Figure 2: The MHPF pipeline, showing the transition from raw trajectories to a hierarchical class tree and the resulting multiscale particle filter stack.

Experimental Evaluation

The researchers evaluated the MHPF framework using three distinct datasets:

  1. Synthetic 2D Configuration Space: 33 trajectories navigating around obstacles.
  2. Synthetic Y-Junction: 13 trajectories designed to test decision-making speed at branching points.
  3. Real-World AIS Tanker Data: 194 trajectories from Automatic Identification System (AIS) tracking of tankers in the Gulf of Mexico.

The performance was benchmarked against two baselines: BL1 (a standard filter tracking individual trajectories) and BL2 (a filter using non-hierarchical, combined dynamics).

Results and Discussion

The MHPF framework demonstrated significant improvements in both accuracy and convergence speed. In synthetic tests, MHPF achieved a Mean Squared Error (MSE) of 0.27, outperforming BL1 (0.38) and BL2 (0.53).

Key findings include:

  • Faster Convergence: MHPF identified the "true" trajectory class significantly faster than baselines, particularly when coarse observations were provided stochastically.
  • Robustness to Noise: In high-noise environments where "fine" filters often fail, the higher levels of the MHPF remained stable, providing reliable high-level intent predictions.
  • Qualitative Integration: The framework successfully prunes the hypothesis space by incorporating linguistic-style information (e.g., "the agent is in the north channel"), effectively bridging the gap between qualitative and quantitative data.

Conclusion

The Multiscale Hierarchy of Particle Filters provides a robust mathematical foundation for tracking agents across varying levels of detail. While the current implementation relies on a static hierarchy learned offline, it sets the stage for more advanced reactive planning. Future work will explore dynamic hierarchy updates and the direct integration of multiscale beliefs into robot motion planning, allowing for more nuanced responses to predicted agent behaviors.

Summary updated

Abstract

Autonomous robots operating in dynamic environments must maintain beliefs over a hypothesis space that is rich enough to represent the activities of interest at different scales. This is important both in order to accommodate the availability of evidence at varying degrees of coarseness, such as when interpreting and assimilating natural instructions, but also in order to make subsequent reactive planning more efficient. We present an algorithm that combines a topology-based trajectory clustering procedure that generates hierarchically-structured spatial abstractions with a bank of particle filters at each of these abstraction levels so as to produce probability estimates over an agent's navigation activity that is kept consistent across the hierarchy. We study the performance of the proposed method using a synthetic trajectory dataset in 2D, as well as a dataset taken from AIS-based tracking of ships in an extended harbour area. We show that, in comparison to a baseline which is a particle filter that estimates activity without exploiting such structure, our method achieves a better normalised error in predicting the trajectory as well as better time to convergence to a true class when compared against ground truth.
BibTeX
@misc{hawasly2016estimating,
  author = {Majd Hawasly and Florian T. Pokorny and Subramanian Ramamoorthy},
  title = {{Estimating Activity at Multiple Scales using Spatial Abstractions}},
  year = {2016},
  eprint = {1607.07311},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1607.07311},
}
Figure