Source-linked AI summary
Online Bayesian Goal Inference for Boundedly-Rational Planning Agents
Tan Zhi-Xuan, Jordyn L. Mann, Tom Silver, Joshua B. Tenenbaum, Vikash K. Mansinghka
TL;DR
The paper asks how machines can infer goals from actions produced by agents whose planning is bounded, sub-optimal, or unsuccessful. It models such agents as replanning probabilistic programs and introduces SIPS for online Bayesian inference, achieving accurate inference across optimal and non-optimal trajectories while often using far less computation than Bayesian IRL baselines.
Problem
Existing goal-inference approaches often assume optimal behavior or simplified action noise, rather than the planning difficulties that produce sub-optimal or failed trajectories.
Method
The architecture models agents as boundedly rational planners that interleave resource-limited search with execution, while SIPS incrementally infers partial plans and goals using sequential Monte Carlo.
Results
The approach accurately infers goals from optimal and non-optimal trajectories involving backtracking and failure, and often uses orders of magnitude less computation than Bayesian IRL baselines across planning domains.
Takeaways & Limitations
Online modeling of partial plans enables goal inference that remains effective when agents act sub-optimally or fail, while supporting efficient inference across compositional domains with sparse rewards.
Takeaways & Limitations
The study considers finite sets of final goals and environments unlike many real settings that have hierarchical goals, stochastic dynamics, or infinite action spaces.
Abstract
from arXiv · showhide
People routinely infer the goals of others by observing their actions over time. Remarkably, we can do so even when those actions lead to failure, enabling us to assist others when we detect that they might not achieve their goals. How might we endow machines with similar capabilities? Here we present an architecture capable of inferring an agent's goals online from both optimal and non-optimal sequences of actions. Our architecture models agents as boundedly-rational planners that interleave search with execution by replanning, thereby accounting for sub-optimal behavior. These models are specified as probabilistic programs, allowing us to represent and perform efficient Bayesian inference over an agent's goals and internal planning processes. To perform such inference, we develop Sequential Inverse Plan Search (SIPS), a sequential Monte Carlo algorithm that exploits the online replanning assumption of these models, limiting computation by incrementally extending inferred plans as new actions are observed. We present experiments showing that this modeling and inference architecture outperforms Bayesian inverse reinforcement learning baselines, accurately inferring goals from both optimal and non-optimal trajectories involving failure and back-tracking, while generalizing across domains with compositional structure and sparse rewards.
1 Introduction
The paper addresses the difficulty of inferring goals when agents plan and act sub-optimally, including backtracking and failure. It proposes a unified architecture combining boundedly-rational planning, probabilistic programs, symbolic environments, and online Sequential Inverse Plan Search.
- Motivation: Prior goal-inference approaches commonly assume optimal behavior or simplified noise, failing to model the difficulty of planning that produces sub-optimal or failed plans.These assumptions also impose a cognitively implausible burden on observers.
- Illustrative behavior: Figure 1 illustrates inference from both a sub-optimal backtracking trajectory and a failed trajectory that myopically consumes a key.In both cases, the method eventually infers the correct goal and shows sharp inference shifts at behaviorally informative points.
- Contribution: The architecture models agents as boundedly rational planners that interleave resource-limited plan search with execution and replanning.This supports online Bayesian inference from trajectories involving backtracking or irreversible failure.
- Contribution: SIPS performs sequential Monte Carlo inference by incrementally extending hypothesized partial plans as new observations arrive, limiting computation through online replanning.The architecture combines probabilistic programs, a PDDL environment model, and SIPS.
- Evaluation: The method achieves high accuracy across compositional planning domains with sparse rewards, often using orders of magnitude less computation than Bayesian inverse reinforcement learning baselines.The evaluation compares against a Bayesian inverse reinforcement learning baseline across a wide variety of planning domains.
2 Related Work
Related work has modeled goal inference through inverse reinforcement learning, Bayesian theory of mind, and plan recognition, but often assumes optimality, achievable goals, or costly offline computation. This paper instead models resource-limited online planning and incrementally infers partial plans.
- Inverse reinforcement learning: Inverse reinforcement learning often requires solving an underlying MDP for each candidate goal or reward function and possible initial state, making complex online inference costly.The paper’s online model-based planning assumption is intended to reduce computation time.
- Bayesian theory of mind: Bayesian theory-of-mind models predict human inferences but have largely relied on MDP-based formalisms; this work explicitly represents partial plans or intentions.The paper positions partial-plan inference as an extension of that line of work.
- Plan recognition as planning: Plan-recognition methods commonly use heuristic likelihoods that assume goals are achievable, preventing reliable inference when agents encounter irreversible failures.The paper models online planners that may execute partial plans leading to dead ends.
- Online goal inference: Recent online goal-inference approaches either target restricted one-dimensional settings or rely on expensive value iteration, whereas this work uses sequential Monte Carlo for incremental plan inference.SIPS exploits the online structure of the agent model to limit computation cost.
- Sub-optimal behavior: The paper extends bounded-suboptimality models by treating sub-optimal planning as resource-limited search while preserving instrumental subgoals and sparse rewards.This differs from myopic models that assign zero reward beyond a fixed time horizon.
3 Boundedly-Rational Planning Agents
The agent model represents bounded rationality as limited-horizon, stochastic planning interleaved with execution and replanning. Probabilistic programs and PDDL jointly encode goals, plans, actions, observations, and environment dynamics.
- Generative agent model: The generative process samples a goal, updates an internal plan, selects an action, transitions the environment, and produces a potentially noisy observation.The plan and plan-update variables extend standard MDP agent models with explicit internal planning.
- Environment representation: PDDL represents states and goals with predicate facts, relations, and numeric expressions, while transition operators specify action preconditions and effects.The architecture focuses on deterministic transitions here but supports stochastic transitions through Probabilistic PDDL.
- Boundedly-rational planning: Agents search only up to a sampled budget η, execute a partial plan toward a promising intermediate state, and then replan from the resulting state.This models full-horizon planning as costly or intractable while allowing agents to continue pursuing goals.
- Search budget: The search budget follows a negative-binomial distribution whose parameters model planner persistence and favor intermediate plan lengths when r > 1.Very long plans are costly, while very short plans are unhelpful.
- Stochastic search: Stochastic A* expands successor states with probability proportional to exp(−f(s, g)/γ), where f combines path cost and heuristic distance and γ controls search randomness.Low noise and informative heuristics favor successors with low estimated total plan cost.
- Execution and replanning: The UPDATE-PLAN and SELECT-ACTION programs extend plans when they end or fail to anticipate the current state, otherwise continuing execution without additional planning.This explicitly interleaves search and execution.
4 Online Bayesian Goal Inference
Online Bayesian goal inference treats goals, states, actions, plans, and observations as latent or noisy variables and approximates their posterior with SIPS. SIPS updates weighted particles incrementally, extending only hypotheses whose plans no longer reach the current observation.
- Inference problem: The inference target is the posterior probability of each possible goal given a sequence of potentially noisy state observations.Exact computation is intractable because it must marginalize over latent states, actions, and plans.
- SIPS: SIPS uses sequential Monte Carlo to infer likely partial plans and goals online from the posterior at the previous timestep.Each particle represents a goal and plan hypothesis, and new observations update its weight.
- Particle updates: As observations arrive, SIPS extends particles to the new timestep and reweights them according to their likelihood of producing the observation.The weighted particles approximate the posterior over the model’s unobserved plans and goals.
- Online extension: SIPS is online because each hypothesized plan is extended only when it lacks a planned action for the current time and state, limiting expensive planning calls.The agent’s online-planning assumption lets the observer defer computation until a hypothesis needs extension.
- Particle diversity: Resampling prunes low-weight hypotheses when effective sample size falls below a threshold, while rejuvenation uses data-driven Metropolis-Hastings proposals to restore particle diversity.One proposal reintroduces goals near the latest observation in heuristic distance.
5 Experiments
Experiments evaluate SIPS for human-like inference from failed and sub-optimal plans, then compare its accuracy, speed, and robustness across structured planning domains. SIPS tracks human inference patterns, outperforms unbiased BIRL, and remains relatively robust to mismatched agents and human data.
- Accuracy, Speed and Robustness of Inference: Across domains with compositional structure and sparse rewards, SIPS is evaluated against BIRL on varying state-space and goal-space complexity.The domains range from Taxi with |S| = 125 to Intrusion Detection with |S| ∼10^30 and 20 possible goals.
- Human-Like Goal Inference from Sub-optimal and Failed Plans: SIPS infers goals through backtracking and irreversible failure, shifting posterior mass as observations rule out or support candidate gems.In one trajectory it shifts from yellow to blue after backtracking; in another it discards red after the agent passes a door and converges on blue after unlocking the relevant door.
- Human-Like Goal Inference from Sub-optimal and Failed Plans: SIPS matches human inference trends more closely than oracle BIRL, correlating at r=0.99 versus r=0.80 on the illustrative trajectory.Across all trajectories, SIPS correlates with mean human inferences at r=0.89, compared with r=0.51 for BIRL.
- Accuracy, Speed and Robustness of Inference: SIPS greatly outperforms unbiased BIRL in accuracy and speed in three of four domains, with average runtime often several orders of magnitude smaller.It achieves comparable accuracy and speed to oracle BIRL, sometimes with less computation, while producing higher estimates of P(g_true|o).
- Accuracy, Speed and Robustness of Inference: SIPS remains relatively robust under mismatched parameters, heuristics, Boltzmann-rational agents, optimal agents, and human-generated trajectories.Performance can degrade for highly random behavior, improve when mismatched parameters are more optimal, and remains strong on human data.
6 Limitations and Future Work
The paper identifies important boundaries for its current architecture and proposes extensions to represent richer goals and environments.
- Limitations and Future Work: The architecture currently assumes finite sets of final goals, whereas human motives may be infinite, hierarchical, and instrumental.The authors propose probabilistic grammars or programs to represent structured hierarchies of goals and plans.
- Limitations and Future Work: The evaluated domains omit stochastic dynamics and infinite action spaces, motivating integration with Monte Carlo Tree Search or sample-based motion planners.The proposed extensions could use learned heuristics as modeling components.
7 Broader Impact
The paper presents goal inference as potentially useful for assistance but warns that mature versions could also enable manipulation, offense, or surveillance. It therefore urges evaluation of institutional use and social consequences.
- Broader Impact: Online inference despite human failure could support smart interfaces, personal assistants, and collaborative robots that offer help during sub-optimal plans.These assistive applications also carry risks of reducing human autonomy.
- Broader Impact: Mature versions of goal-inference technology could be abused for manipulative, offensive, or surveillance purposes, especially in contexts of over-policing marginalized groups.The authors urge future research to examine who deploys such systems and whether their uses produce just and beneficial outcomes.
Supplemental Material
The supplemental material is identified by the paper’s authorship and arXiv metadata.
- Supplemental Material: The paper lists Tan Zhi-Xuan, Jordyn L. Mann, Tom Silver, Joshua B. Tenenbaum, Vikash K. Mansinghka, and their MIT affiliation.
- Supplemental Material: The manuscript is identified as arXiv:2006.07532v2, dated 25 Oct 2020.
A Experimental Details
The experiments compare SIPS with BIRL and PRP, detailing their inference procedures, computational trade-offs, and qualitative evaluations on sub-optimal trajectories.
- Experimental Methods: Rejuvenation improves SIPS on highly sub-optimal and failed plans but is difficult to tune and can increase runtime, so quantitative experiments omit it.The qualitative results in Figure 1 require rejuvenation, whereas the quantitative experiments use SIPS without rejuvenation.
- Experimental Methods: SIPS uses sequential particle inference, while BIRL computes value functions with value iteration and PRP constructs optimal partial plans for each goal at every timestep.SIPS extends partial plans incrementally from previous timesteps; PRP incurs substantially more runtime and assumes a feasible plan exists from each current state to every goal.
- Experimental Methods: PRP cannot account for irreversible failures because it assumes a plan always exists from the current observed state to every goal.Its per-goal, per-timestep planning also scales poorly as trajectories move farther from candidate goals.
- Experimental Methods: PRP achieves high accuracy on many sub-optimal trajectories but can require up to 30 times more runtime than SIPS.This makes PRP a useful offline accuracy benchmark despite its computational cost.
- Qualitative Comparisons: Qualitative comparisons in Doors, Keys & Gems examine two sub-optimal and two irreversibly failed trajectories, omitting BIRL-U because it produces a uniform posterior after failing to solve the underlying MDP.Figures S1 and S2 report sub-optimal-plan inferences; the supplied figure passages specify SIPS, BIRL-O, and PRP settings.
B.1.1 Sub-Optimal Plans
On sub-optimal trajectories, SIPS produces more human-like goal inferences than BIRL and PRP, especially when observations reveal backtracking and changing intended goals.
- Sub-Optimal Plans: SIPS initially remains uncertain, shifts toward the yellow gem after the first key and door, then switches to the blue gem when the agent backtracks.These changes occur at the key timepoints described for Figure S1 and are reported as more human-like than the baselines.
- Sub-Optimal Plans: BIRL changes more gradually because it models noise in action selection rather than in planning, producing artifacts such as increased red-gem probability before timestep 9.Its action-noise model makes actions leading toward farther goals less likely under the corresponding goal.
- Sub-Optimal Plans: PRP overcommits to the yellow gem and recovers slowly toward the blue gem because it exponentially penalizes plans whose costs exceed the optimal plan.Between timesteps 10 and 20, plans consistent with the blue gem are much longer than the optimal blue-gem plan, so PRP assigns them very low probability.
- Sub-Optimal Plans: PRP remains slow to recover after backtracking from timesteps 17 to 24, indicating inadequate modeling assumptions for trajectories with substantial backtracking.The same qualitative issues appear in the second sub-optimal trajectory, where BIRL maintains high yellow-gem probability while the agent collects the second key.
B.1.2 Failed Plans
SIPS infers goals from trajectories involving irreversible failure, whereas BIRL and PRP fail in distinct ways. Across broader accuracy and runtime evaluations, SIPS offers the best speed–accuracy balance, although PRP often leads on accuracy alone.
- Failed Plans: SIPS correctly infers the blue gem as the goal despite ignored keys and irreversible key use, because partial-plan search favors promising intermediate states.The inference remains stable after the agent uses its only key at t = 21.
- Failed Plans: BIRL favors the red gem and PRP fails to increase blue-gem probability, with PRP eventually reverting to a uniform distribution after failure.BIRL’s posterior stops changing once no goal remains reachable, while PRP cannot model failed plans.
- Failed Plans: SIPS again identifies the blue gem slightly before failure, while BIRL selects red and PRP selects the only remaining acquirable yellow gem.
- Accuracy: PRP generally achieves the highest accuracy metrics, while SIPS and BIRL-O perform comparably; these metrics do not capture calibrated temporal inferences or failed-plan capability.Most evaluated domains lack irreversible failures, limiting what Table S2 reveals about SIPS’s distinctive strength.
- Runtime: SIPS achieves the best speed–accuracy balance through incremental computation, while PRP requires up to 30 times more computation per timestep.BIRL-U requires orders of magnitude more initial computation, and BIRL-O is slower than SIPS on Doors, Keys & Gems in average runtime.
B.3 Robustness to Parameter Mismatch
Robustness experiments test SIPS under mismatched planning parameters across Doors, Keys, Gems and Blocks World. Performance generally degrades with mismatch, while highly random behavior from an uninformative heuristic produces especially poor inferences.
- Robustness: SIPS remains reasonably robust to mismatched parameters, although degradation reflects both mismatch and increased randomness from less optimal data-generating agents.
- Robustness: Agents generated with the uninformative goal-count heuristic yield highly random behavior and poor inference, with Top-1 at Q3 = 0.37 even under the matching heuristic.
- Evaluation Setup: The robustness evaluations report Top-1 accuracy at the third trajectory quartile for Doors, Keys, Gems and Blocks World under parameter mismatch.The tables vary assumed persistence, continuation probability, and heuristic settings.
- Human Studies: The experiments include human pilot data collection in the Doors, Keys & Gems and Blocks World domains using interactive action-selection interfaces.The pilot studies involved N=5 subjects and collected judgments or human-generated plans for robustness analyses.