Online Competitive Information Gathering for Partially Observable Trajectory Games

Mel Krusniak, Hang Xu, Parker Palermo, Forrest LainearXiv 2025 · DOI · arXiv

Abstract

This paper presents an online planning framework for robots operating in continuous, competitive environments with imperfect information. Modeled as Partially Observable Stochastic Games (POSGs), these scenarios are typically computationally prohibitive in continuous trajectory space. The proposed method combines particle-based joint state estimation with stochastic gradient play to enable agents to strategically gather information. By maintaining a distribution of possible world states and performing Monte Carlo sampling to refine strategies, agents exhibit emergent active information-seeking behaviors. Experimental results across various multi-agent drone simulations demonstrate significant performance improvements over passive planning baselines, with computational speeds approaching real-time requirements.

Introduction

In real-world robotics, agents often operate with imperfect information. For instance, in a pursuit-evasion game, a pursuer may have a limited field of view, while the evader strategically hides. These scenarios are mathematically modeled as Partially Observable Stochastic Games (POSGs). While discrete versions (e.g., Poker) are well-studied, solving them in continuous trajectory space is challenging due to the "infinite hierarchy of beliefs" and the computational cost of online planning. Most existing solutions rely on extensive offline pre-training or simplify the agents' belief structures. This work addresses the challenge of online planning, enabling robots to compute trajectories that strategically gather information to gain a competitive advantage without prior environment-specific training.

Methodology

The authors introduce a variant of Model Predictive Game Play (MPGP) tailored for imperfect information. The approach relies on three core components:

  1. Policy Mapping: Instead of planning a single deterministic path, agents learn a policy $\pi$ that maps observation histories to future actions. This allows for contingency planning based on whether an opponent is detected.
  2. Particle-Based Joint Distribution: To manage complex beliefs, the solver maintains a set of "particles" representing joint states of the world and the observation histories of all players. This avoids the computational explosion of nested belief modeling.
  3. Stochastic Gradient Play: Agents approximate a Nash equilibrium by performing gradient descent on expected costs. Strategies are refined through Monte Carlo sampling across the particle set.
  4. The $\gamma$ Update Rule: A specific parameter $\gamma$ balances following the theoretical equilibrium with reacting to actual real-time observations, ensuring robustness in dynamic environments.

Experimental Setup

The method was evaluated in four distinct continuous simulation environments designed to test different aspects of competitive information gathering:

  • UAV Tag: A 1v1 pursuit-evasion game with limited fields of view.
  • Tag Chain: A four-player extension where agents are simultaneously pursuers and evaders.
  • Hide and Seek: A complex environment with circular obstacles that block both vision and movement.
  • Warehouse Pickup: A competitive but non-adversarial scenario where robots must infer opponent locations from noisy broadcasts to avoid collisions.
The simulation environments used for evaluation: UAV Tag (left), Tag Chain (center), and Hide and Seek (right).

Key Insights and Results

Active vs. Passive Information Gathering

A central finding is the emergence of "active" information gathering. Unlike passive agents that move based on initial guesses, active agents intentionally deviate from the shortest path to check blind spots or corners. This behavior is not hard-coded but emerges naturally as the agents seek to minimize their long-term costs.

Comparison between passive and active information gathering. In active mode, agents strategically move to reduce uncertainty about the opponent's position.

Performance Metrics

  • Cost Efficiency: The "Active" solver consistently outperformed the "Passive" baseline. In the UAV Tag scenario, the active pursuer reduced its mean cost from ~12.58 to ~9.97, a statistically significant improvement ($p < 0.05$).
  • Computational Performance: Optimization times per gradient step ranged from 0.06s to 0.22s. While not yet reaching the 30Hz threshold for high-speed flight, the results suggest that GPU acceleration could enable real-time deployment.
  • Equilibrium Selection: The authors found that maintaining multiple candidate policies ($N_{eq}$) allows agents to recover more effectively when their initial model of an opponent's strategy is incorrect.

Conclusion and Future Work

While the proposed method shows strong results in most scenarios, it faces challenges in highly complex environments like "Hide and Seek," where short planning horizons (e.g., 6 steps) are insufficient to capture deep strategic maneuvers around multiple obstacles. Furthermore, the current model assumes deterministic "pure" strategies; future work will explore mixed strategies to incorporate deceptive behaviors. Scaling the computational efficiency for longer planning horizons remains a primary objective for future iterations of the architecture.

Summary updated

Abstract

Game-theoretic agents must make plans that optimally gather information about their opponents. These problems are modeled by partially observable stochastic games (POSGs), but planning in fully continuous POSGs is intractable without heavy offline computation or assumptions on the order of belief maintained by each player. We formulate a finite history/horizon refinement of POSGs which admits competitive information gathering behavior in trajectory space, and through a series of approximations, we present an online method for computing rational trajectory plans in these games which leverages particle-based estimations of the joint state space and performs stochastic gradient play. We also provide the necessary adjustments required to deploy this method on individual agents. The method is tested in continuous pursuit-evasion and warehouse-pickup scenarios (alongside extensions to $N > 2$ players and to more complex environments with visual and physical obstacles), demonstrating evidence of active information gathering and outperforming passive competitors.
BibTeX
@misc{krusniak2025online,
  author = {Mel Krusniak and Hang Xu and Parker Palermo and Forrest Laine},
  title = {{Online Competitive Information Gathering for Partially Observable Trajectory Games}},
  year = {2025},
  eprint = {2506.01927},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.01927},
}
Figure