Global/Local Dynamic Models

Avi Pfeffer, Subrata Das, David Lawless, Brenda NgIJCAI 2007

Abstract

Tracking the states of numerous interacting entities, such as units in a battlefield or agents in a market, presents a significant computational challenge due to the exponential growth of the state space. This paper introduces Global/Local Dynamic Models (GLDMs) and the Global/Local Particle Filtering (GLPF) algorithm. By decomposing the system state into globally influenced interaction components and locally influenced individual components, GLPF enables efficient and scalable tracking. Experimental results in simulated urban warfare scenarios demonstrate that GLPF significantly outperforms standard and factored particle filters in both precision and recall, particularly as system complexity increases.

Introduction

The problem of tracking multiple interacting entities—like companies in a market, people in an epidemic, or units on a battlefield—is a computational nightmare. Standard tools like Particle Filtering (PF) represent the entire system's state as a single high-dimensional point. As the number of entities grows, the "state space" explodes, and PF requires an astronomical number of particles to remain accurate.

Existing "Factored" Particle Filters try to break the state into smaller pieces (factors), but they typically still perform dynamics propagation and observation conditioning globally. This often leads to a "washout" effect: if one entity's state is slightly off in a global particle, the entire particle might be rejected by an observation, even if the states of all other entities were perfectly accurate. The authors seek a way to exploit local independence to make inference scalable without losing the ability to model global interactions.

The Global/Local Dynamic Model (GLDM)

The authors propose a modeling framework that exploits local independence without sacrificing the ability to model global interactions. In a GLDM, an entity’s state is partitioned into two distinct components:

  1. Locally influenced state ($U$): This component depends solely on the entity’s own previous state, representing individual behavior.
  2. Globally influenced state ($V$): This component captures interactions and depends on the states of all entities in the system, representing shared context or team goals.

Crucially, observations ($O$) are restricted to depend only on the state of an individual entity. This structure allows the model to decouple individual movements from collective behavior during the observation step.

Graphical representation of a Global/Local Dynamic Model (GLDM).

Global/Local Particle Filtering (GLPF)

To perform inference on GLDMs, the authors introduce the GLPF algorithm. The core principle is to "reason globally about global dynamics, and locally about local dynamics."

Instead of a monolithic update, GLPF follows a multi-step process:

  • Global Propagation: It propagates the global interaction variables ($V$) across the whole system.
  • Local Projection and Update: It "projects" that global information down to individual entities, allowing each entity to update its local state ($U$) and incorporate its own observations independently.
  • Local Resampling: Finally, it resamples particles locally. This prevents a bad guess about one entity from ruining the tracking of another, effectively solving the "washout" problem.

To handle observations that aren't local (like two units communicating), the authors employ evidence reversal, treating the observation as a constraint on the transition model rather than a separate sensor update.

Experimental Evaluation

The GLPF algorithm was evaluated using simulated urban warfare data. The scenario involved small, mobile enemy units moving through a city map, occasionally communicating to form "teams" and attack specific targets. The goal was to detect "threats"—defined as four units sharing a common goal—within 12 time steps of team formation. Experiments were conducted with 10 to 20 units and 6 to 20 potential target locations.

Key Results

GLPF was compared against ordinary PF, Factored PF, and a "completely local" baseline across several scenarios:

  • Superior Performance: In a 10-unit/6-target scenario, GLPF achieved 56% precision with 87% recall, significantly outperforming both ordinary and factored PF.
  • Robust Scaling: When the complexity increased to 20 units, GLPF maintained strong performance (57% precision / 76% recall), while the other methods degraded significantly.
  • Importance of Global Reasoning: The "all local" method (which ignored interactions entirely) performed poorly, proving that while local conditioning is good, the global model is essential for understanding how teams form.
Precision-Recall curves comparing GLPF against standard and factored particle filters across three scenarios.

Discussion

GLPF makes a deliberate trade-off: by conditioning on observations locally, it loses the ability to reason that "Unit A is moving toward Target X, so its teammate Unit B is likely also moving toward Target X." However, the authors prove that the gain in local accuracy and scalability far outweighs this loss in cross-entity reasoning.

The success of the method depends on the "strength" of the global vs. local interactions; in systems where entities are extremely tightly coupled, the local conditioning might lose too much information. Future work may address current limitations, such as the requirement for local observations and the assumption of a fixed entity count, by exploring methods for "splitting and merging" entities.

Summary updated

BibTeX
@inproceedings{pfeffer2007global,
  author = {Avi Pfeffer and Subrata Das and David Lawless and Brenda Ng},
  title = {{Global/Local Dynamic Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure