Abstract
Traditional plan recognition systems often rely on discrete state spaces or predefined action libraries, which can lead to significant information loss in continuous physical environments. This paper introduces Mirroring, a framework that leverages off-the-shelf motion planners to infer an agent's goals directly in continuous domains. By avoiding early discretization, Mirroring achieves higher accuracy and faster convergence while remaining compatible with classical discrete planning tasks.
Introduction
Plan, Activity, and Intent Recognition (PAIR) is the task of inferring an agent's hidden goals from a partial sequence of observed actions. This capability is essential for autonomous systems, such as robot assistants or self-driving cars, to interact safely and effectively with humans. Historically, continuous domains have been handled by "discretizing" the environment into a grid. However, this approach introduces a fundamental trade-off: coarse grids lose critical directional information, while fine grids become computationally prohibitive.
The Problem with Discretization
The authors demonstrate that early commitment to discretization leads to inherent bottlenecks. If a grid is too coarse, a recognizer may fail to distinguish between goals until the agent is nearly at its destination.
The paper provides formal proofs (Theorems 1 and 2) showing that for any fixed discretization, there exist scenarios where a continuous-space recognizer succeeds while a discrete one fails.
The Mirroring Framework
Mirroring re-frames plan recognition as a planning problem solvable by unmodified, off-the-shelf (OTS) planners, such as RRT* for motion or PDDL planners for logic. The process involves:
- Observation Skeleton: Treating observed positions as a "skeleton" path.
- The Mirrored Plan: Using a planner to find the most efficient path constrained to pass through these observations to reach a potential goal $g$.
- The Optimal Plan: Calculating the unconstrained optimal path to goal $g$ from the start point.
- Rationality Ratio: Comparing the costs of the mirrored and optimal plans. A high ratio suggests the goal is likely, assuming the agent acts rationally.
This approach ensures zero matching error between observations and hypothesized plans, focusing the inference entirely on the principle of rationality to rank potential goals.
Experimental Evaluation
The framework was evaluated across over 1,000 problems, including 3D navigation in cubicle environments, robot soccer simulations, and shape recognition of hand-drawn polygons. Additionally, 450 classical discrete planning problems were tested to ensure the method generalizes beyond continuous tasks.
Key Results and Insights
The continuous Mirroring approach consistently outperformed discretized versions. In the robot soccer domain, the continuous model achieved higher convergence scores across various initial locations and goal configurations.
Key takeaways include:
- Planner Selection: Asymptotically optimal planners like RRT* or TRRT are crucial. TRRT, in particular, offered an excellent balance of high accuracy and low computational overhead.
- Unified Theory: Mirroring generalizes "Plan Recognition as Planning" (PRP), working seamlessly for both discrete logic and 3D motion.
- Discrete Parity: In discrete benchmarks, Mirroring matched state-of-the-art methods in 99.5% of cases, proving that a continuous formulation does not compromise performance on classical tasks.
Conclusion
Mirroring provides a robust solution for plan recognition in the messy reality of the physical world. While the current "shortcut" method is sensitive to noisy observations, it sets a new standard for accuracy in continuous domains. Future work will focus on handling sensor noise and extending the framework to multi-agent and hybrid (continuous-discrete) domains.
Summary updated