Abstract
As autonomous agents become more ubiquitous, they will eventually have to reason about the plans of other agents, which is known as theory of mind reasoning. We develop a planning-as-inference framework in which agents perform nested simulation to reason about the behavior of other agents in an online manner. As a concrete application of this framework, we use probabilistic programs to model a high-uncertainty variant of pursuit-evasion games in which an agent must make inferences about the other agents' plans to craft counter-plans. Our probabilistic programs incorporate a variety of complex primitives such as field-of-view calculations and path planners, which enable us to model quasi-realistic scenarios in a computationally tractable manner. We perform extensive experimental evaluations which establish a variety of rational behaviors and quantify how allocating computation across levels of nesting affects the variance of our estimators.
Introduction
The deployment of autonomous agents in real-world environments necessitates the ability to reason about the internal states and intentions of other actors—a cognitive capability known as Theory of Mind (ToM). Traditional pursuit-evasion models often rely on "minimax" strategies within fully observable, discretized grid worlds. However, real-world scenarios are characterized by continuous spaces, complex obstacles, and significant uncertainty.
Implementing recursive reasoning ("I think that you think...") in these continuous environments is computationally demanding. This research addresses the gap between high-level cognitive modeling and low-level physical simulation. By treating planning as a statistical inference problem, we enable agents to reason about complex primitives, such as line-of-sight and path planning, in real-time.
Methods and Environment
Our framework utilizes a planning-as-inference approach. Instead of traditional optimization, we define a "desirability" distribution over possible trajectories and use probabilistic inference to identify the most likely successful plan.
Simulation Primitives and Data
To move beyond simplistic grid worlds, we utilize a coarse polygonal city map of Bremen, Germany, derived from 3D point cloud data. This provides a quasi-realistic environment with intricate obstacles and alleyways. Within this environment, we employ two key primitives:
- Rapidly-Exploring Random Trees (RRTs): Used for continuous path planning.
- Isovists: Polygonal field-of-view calculations used to determine visibility between agents.
Nested Importance Sampling (NIS)
The core of our approach is Nested Importance Sampling, structured across four levels:
- Episode Model: Manages the overall sequence of moves.
- Outermost Model (Chaser): Samples potential chaser paths, evaluating them against imagined runner paths.
- Middlemost Model (Runner): Simulates the runner's reactions to avoid a "naive" chaser.
- Innermost Model (Naive Chaser): A simplified model used by the runner to predict the chaser's future position.
Results
We evaluated the framework across four scenarios varying in agent intelligence levels. Key findings include:
- The Value of Nested Reasoning: A "Smartest Chaser" using nested reasoning achieved a 98% detection rate against a naive runner. Crucially, when facing a "Smarter Runner" (one that attempts to hide), the Smartest Chaser maintained a 56% detection rate, significantly outperforming a "Smart Chaser" (36% detection rate) that assumes random runner movement.
- Computational Trade-offs: With a fixed budget, agents must balance "thinking deep" (sampling opponent reactions, $L$) versus "thinking broad" (sampling own plans, $K$). Increasing inner-loop samples ($L$) reduces utility estimate variance, leading to more robust decisions, provided sufficient outer samples ($K$) are available to explore the plan space.
Conclusion and Future Work
While effective, the current model is computationally intensive, requiring millions of RRT planner calls. Future work will focus on optimizing inference for real-time hardware deployment. Additionally, we aim to relax the assumption of perfect map knowledge, allowing agents to build maps dynamically. Beyond pursuit-evasion, this framework holds promise for collaborative tasks where agents must infer the needs and hidden observations of their partners.
Summary updated