Simultaneous Team Assignment and Behavior Recognition from Spatio-Temporal Agent Traces

Gita Sukthankar, Katia P. SycaraAAAI 2006 · OpenReview

Abstract

This paper addresses the problem of activity recognition for physically-embodied agent teams. We define team activity recognition as the process of identifying team behaviors from traces of agent positions over time; for many physical domains, military or athletic, coordinated team behaviors create distinctive spatio-temporal patterns that can be used to identify low-level action sequences. This paper focuses on the novel problem of recovering agent-to-team assignments for complex team tasks where team composition, the mapping of agents into teams, changes over time. Without a priori knowledge of current team assignments, the behavior recognition problem is challenging since behaviors are characterized by the aggregate motion of the entire team and cannot generally be determined by observing the movements of a single agent in isolation. To handle this problem, we introduce a new algorithm, Simultaneous Team Assignment and Behavior Recognition (STABR), that generates behavior annotations from spatio-temporal agent traces. The proposed approach is able to perform accurate team behavior recognition without an exhaustive search over the combinatorial space of potential team assignments, as demonstrated on several scenarios of simulated military maneuvers.

Introduction

In domains such as military reconnaissance or sports analytics, understanding team behavior from raw agent traces—2D coordinates over time—is a critical but difficult task. While individual activity recognition is well-established, team-level recognition faces a "chicken-and-egg" dilemma: identifying a team's behavior requires knowing its composition, yet team composition is often only identifiable through coordinated behavior.

Spatio-temporal agent traces at different time steps showing dynamic team formations.

This challenge is compounded when team assignments are dynamic, with agents splitting, merging, or interleaving during complex maneuvers. For a group of just 16 agents, the number of possible partitions (the Bell number) exceeds 10 billion, making exhaustive search computationally impossible. Traditional proximity-based clustering often fails in these scenarios because agents from different teams may pass close to one another while maintaining distinct group identities.

Methodology: The STABR Algorithm

The Simultaneous Team Assignment and Behavior Recognition (STABR) algorithm addresses this by integrating geometric matching with temporal consistency. The approach consists of three main stages:

  1. Static Formation Matching (RANSAC): Instead of relying on proximity, STABR uses RANSAC to match agent positions against pre-defined geometric templates (e.g., wedges, squares). RANSAC is robust to "outliers"—agents from other teams or unaffiliated "singletons"—allowing it to identify structured formations even in crowded environments.
  2. Spatio-Temporal Pruning: To filter out coincidental geometric alignments, STABR validates hypothesized teams against parameterized behavior models (e.g., "advance," "wheel," or "pivot"). If a group’s motion over a short window does not fit a known behavior, the hypothesis is discarded, significantly reducing the search space.
  3. Global Optimization: The algorithm uses dynamic programming to find the most parsimonious explanation for the entire sequence. By penalizing frequent changes in team membership, it ensures stable and logical assignments over time.

Experimental Evaluation

The algorithm was tested on simulated military maneuvers involving 16 agents. These scenarios included complex transitions where teams converged, disbanded, and regrouped into new formations. The traces were corrupted with Gaussian noise to simulate real-world sensor inaccuracies.

Comparison of team assignment accuracy between the RANSAC-based STABR approach and traditional clustering.

As shown in the evaluation, STABR (utilizing RANSAC-based matching) maintains high accuracy even when teams interleave. In complex scenarios, STABR achieved up to 98.5% accuracy, whereas traditional proximity-based clustering plummeted to 18.3%. The pruning stage proved highly effective, reducing tens of thousands of potential hypotheses to a manageable set for global optimization. Furthermore, the algorithm successfully identified "singletons," preventing them from degrading the recognition of actual teams.

Conclusion and Future Work

STABR demonstrates that geometric template matching and behavior-based filtering are powerful tools for recovering dynamic team structures from noisy spatial data. While currently dependent on pre-defined templates and motion models, future work aims to enable the discovery of novel formations and integrate higher-level symbolic plan recognition for more complex hierarchical tasks.

Summary updated

Abstract

This paper addresses the problem of activity recognition for physically-embodied agent teams. We define team activity recognition as the process of identifying team behaviors from traces of agent positions over time; for many physical domains, military or athletic, coordinated team behaviors create distinctive spatio-temporal patterns that can be used to identify low-level action sequences. This paper focuses on the novel problem of recovering agent-to-team assignments for complex team tasks where team composition, the mapping of agents into teams, changes over time. Without a priori knowledge of current team assignments, the behavior recognition problem is challenging since behaviors are characterized by the aggregate motion of the entire team and cannot generally be determined by observing the movements of a single agent in isolation. To handle this problem, we introduce a new algorithm, Simultaneous Team Assignment and Behavior Recognition (STABR), that generates behavior annotations from spatio-temporal agent traces. The proposed approach is able to perform accurate team behavior recognition without an exhaustive search over the combinatorial space of potential team assignments, as demonstrated on several scenarios of simulated military maneuvers.
BibTeX
@inproceedings{sukthankar2006simultaneous,
  author = {Gita Sukthankar and Katia P. Sycara},
  title = {{Simultaneous Team Assignment and Behavior Recognition from Spatio-Temporal Agent Traces}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=rJ-6L1-OZr},
}
Figure