Source-linked AI summary
Online Replanning in Belief Space for Partially Observable Task and Motion Problems
Caelan Reed Garrett, Chris Paxton, Tomás Lozano-Pérez, Leslie Pack Kaelbling, Dieter Fox
TL;DR
Partially observable manipulation requires robots to observe their surroundings, update beliefs, and adapt plans as actions have stochastic effects. The paper combines cost-sensitive planning over hybrid beliefs with plan-structure reuse and deferred computation; experiments report higher success and generally lower planning time when both techniques are applied.
Problem
Robots performing multi-step manipulation must act under stochastic effects and partial observability, selecting observations and updating beliefs before planning further actions.
Source: §I · p. 1Method
The system plans online over hybrid belief states, modeling observation and visibility, while reusing prior plan structure and deferring selected expensive computations.
Source: §I · p. 1, A. Modeling Observations · p. 3Results
Applying both plan constraints and deferred streams yields a large improvement in success rate and generally reduces total planning time during policy execution.
Source: §VIII · p. 6Takeaways & Limitations
The system solves partially observable problems in simulation and demonstrates kitchen manipulation tasks with a real robot.
Source: §I · p. 2, §VIII · p. 6, §IX · p. 6
Abstract
from arXiv · showhide
To solve multi-step manipulation tasks in the real world, an autonomous robot must take actions to observe its environment and react to unexpected observations. This may require opening a drawer to observe its contents or moving an object out of the way to examine the space behind it. Upon receiving a new observation, the robot must update its belief about the world and compute a new plan of action. In this work, we present an online planning and execution system for robots faced with these challenges. We perform deterministic cost-sensitive planning in the space of hybrid belief states to select likely-to-succeed observation actions and continuous control actions. After execution and observation, we replan using our new state estimate. We initially enforce that planner reuses the structure of the unexecuted tail of the last plan. This both improves planning efficiency and ensures that the overall policy does not undo its progress towards achieving the goal. Our approach is able to efficiently solve partially observable problems both in simulation and in a real-world kitchen.
I. INTRODUCTION
Autonomous manipulation combines discrete and continuous planning with stochastic actions and partial observability. The paper plans directly over hybrid beliefs, replans online, and constrains successive plans to preserve progress while reducing search.
I. INTRODUCTION
- Robots must jointly choose objects and motions while coping with stochastic action effects and occlusions that limit observation.These challenges motivate maintaining beliefs and choosing actions that reduce uncertainty.Source: §I · p. 1
- Online replanning approximates an intractable belief-space policy problem by repeatedly solving determinized versions with a TAMP planner.Belief-space actions operate on distributions over states rather than individual states.Source: §I · p. 1
- Hybrid belief distributions let the planner represent multimodal object-pose uncertainty and reason about how occlusion affects detection.It approximates detection probability through conditions on individual objects, exposing sparse interactions for efficient occlusion reasoning.Source: §I · p. 1
- Constraining new plans to retain the structure of the prior plan preserves goal progress while reducing search and speeding successive replanning.Some parameter values can still change in response to stochastic execution or new observations.Source: §I · p. 1
- The system defers expensive parameter computations when they occur later in the plan and are likely to admit satisfying values.The strategy seeks only the computation needed to obtain the next action and certify progress; the system is evaluated in simulation and a real kitchen.Source: §I · pp. 1–2
II. RELATED WORK
- Prior online methods include Monte Carlo action sampling and determinization, but uninformed sampling struggles with the hybrid action space and most-likely observation can miss needed outcomes.Earlier belief representations also use discrete or fluent-based abstractions rather than operating directly on distributions.Source: §II · p. 2
III. PROBLEM DEFINITION
The paper formulates hybrid belief-state stochastic shortest-path problems and solves them online by determinizing action outcomes. Its PDDLStream formulation represents robot actions and continuous computations, with particle beliefs for uncertain object poses.
III. PROBLEM DEFINITION
- The robot seeks a minimum-cost policy from a prior belief to a goal set of beliefs, evaluated online through repeated replanning on determinized problems.The addressed belief-state SSPPs have strictly positive action costs.Source: §III · p. 2
- The kitchen state includes robot and drawer configurations, object attachments, and object poses, with particle filtering used for partially observed object poses.The maintained belief is factored across variables; configuration and joint-angle estimates are point estimates.Source: §III · p. 2
IV. PDDLSTREAM FORMULATION
- Action schemas specify parameters, preconditions, and effects, while move and pick update robot configuration and object attachment facts.The domain also defines actions such as place, pushing or pulling doors, pouring, and pressing buttons.Source: §IV · pp. 2–3
- PDDLStream represents continuous planning computations as streams that generate values and certify facts for their inputs and outputs.Examples include inverse kinematics for arm configurations and motion planning for trajectories.Source: §IV · p. 3
A. Modeling Observations
Observation actions are represented as belief updates conditioned on hypothesized observations, while sampling and visibility procedures let the planner account for occlusion. Visibility is estimated from sampled poses using ray-casting.
A. Modeling Observations
- The detect action replaces an object's prior pose belief with its Bayesian posterior when the observation is not occluded.The update-belief stream computes that posterior from the prior belief and hypothesized observation; given an observation, the update is deterministic.Source: A. Modeling Observations · p. 3
- Sampling and inference streams operate on pose distributions to model observations and visibility, with occlusion probability estimated by ray-casting sampled poses.The planner uses this representation to reason about occlusion interactions.Source: A. Modeling Observations · p. 3
- The derived BOccluded predicate marks an observation as blocked when another object's pose belief prevents its receipt with probability exceeding ϵ.Visibility testing checks whether the probability of prevention is below ϵ.Source: A. Modeling Observations · p. 3
V. DETERMINIZED OBSERVATION COSTS
The section assigns observation actions costs so a deterministic planner can reason approximately about probabilistic success. It bounds observation likelihood using object visibility and detection assumptions, while choosing local observation regions to keep the bound tractable.
V. DETERMINIZED OBSERVATION COSTS
- The planner minimizes observation cost, ObsCost, as a function of the prior pose belief and candidate observation.The same analysis can apply to other probabilistic conditions, such as collision checks.Source: §V · p. 3
A. Self-Loop Determinization
- Self-loop determinization combines action cost, success probability, and failed-transition recovery cost into a transformed deterministic action cost.The domain supplies an upper bound on successful-outcome cost and recovery cost, plus a lower bound on success probability.Source: A. Self-Loop Determinization · pp. 3–4
B. Computing the Likelihood of an Observation.
- Observation likelihood uses visibility and detection variables, with detection modeled using a false-negative probability and pose observations using Gaussian noise.The false-positive probability is conservatively bounded below by zero.Source: B. Computing the Likelihood of an… · p. 4
- A lower bound on visibility probability removes dependence on all other objects’ beliefs at once, avoiding an unfactored cost parameterization as object count grows.The method takes a worst-case visibility probability over a subset of target poses for each potentially occluding object.Source: B. Computing the Likelihood of an… · p. 4
- The planner samples candidate observations and selects a pose region and occlusion threshold, trading higher prior probability against lower visibility bounds.In practice, the target region is a δ-neighborhood around a sampled pose; detect is allowed only when each other object meets the visibility threshold.Source: B. Computing the Likelihood of an… · p. 4
C. Observation Example
The example illustrates how the chosen target-pose region affects which objects the visibility bound treats as occluders. Restricting the region locally can reduce the number of objects that must be moved before detection.
C. Observation Example
- With the target equally believed at two poses and A, B, and C otherwise known, each object blocks one possible target pose.For the full region containing all three target poses, the bound requires moving all three objects before detect.Source: C. Observation Example · p. 4
- A smaller target-pose region makes B unnecessary to move, while a still more local region leaves only A to move.The example uses the local region to make the visibility bound sparse with respect to which objects affect the observation.Source: C. Observation Example · p. 4
VI. ONLINE REPLANNING
Replanning after each action can produce a policy that repeatedly revisits earlier actions instead of reaching the goal. Yet executing a complete plan open loop is unreliable when actions are stochastic, motivating replanning that retains progress.
VI. ONLINE REPLANNING
- Naive replanning can repeatedly choose another base move after the robot has already moved, so the induced policy may never reach the goal.This can happen even when every replanning call finds a plan.Source: §VI · pp. 4–5
- Executing the whole plan open loop is unsuitable when stochastic base movements make the intended configuration unreliable.Replanning instead uses the base pose actually reached rather than the intended pose.Source: §VI · p. 5
- Requiring each future plan to have fewer actions can ensure goal achievement with probability 1 when actions have positive success probability, but replanning from scratch wastes search effort.The stated condition includes domains that are dead-end free.Source: §VI · p. 5
A. Reuse-Enforced Replanning
Reuse-enforced replanning constrains a new plan to retain the previous plan’s structure while allowing observation-dependent values to change. The planner carries forward suitable facts and the unexecuted tail, then relaxes the constraints if constrained planning times out.
A. Reuse-Enforced Replanning
- The method preserves constants such as object names and grasps, while replacing pose-, configuration-, and trajectory-dependent arguments with free variables.The prior plan’s action structure can therefore persist as values are adapted to new observations.Source: A. Reuse-Enforced Replanning · p. 5
- Reusing the plan structure fixes the action sequence, objects, and grasps while allowing some parameter values to change.The example’s constrained tail contains the remaining arm move and pick actions with free-variable arguments.Source: A. Reuse-Enforced Replanning · p. 5
- After determinizing the current belief, the policy tries constrained planning and removes the constraints for a retry if the planner times out.A successful plan returns certified facts; after executing its first action and updating the belief, the policy retains constant facts and the unexecuted plan tail.Source: A. Reuse-Enforced Replanning · p. 5
- The constraint transformation preserves action order and fixed argument values while allowing free variables to remain unbound or take assigned values.Applied facts encode ordering; Bound and Assigned facts track whether a free variable has been bound to a value.Source: A. Reuse-Enforced Replanning · p. 5
VII. DEFERRED STREAM EVALUATION
The system delays expensive stream evaluations until they are needed to execute the next action, reducing work on plans that will not be executed. It also identifies cases where early evaluation is preferable.
VII. DEFERRED STREAM EVALUATION
- Streams needed for the first action are queried, while other expensive streams are deferred until a later replanning invocation.The procedure recursively identifies streams required by those needed for the first action; in the example, inverse kinematics and arm-motion streams are deferred.Source: §VII · p. 6
- Deferral is not always cheaper: if the initial pose, grasp, and base configuration may lack a kinematic solution, infer this before moving and sample new values.The paper contrasts early inference with moving to the base configuration before discovering the missing solution.Source: §VII · p. 6
- In this domain, only the motion stream is deferred because it almost always succeeds when the initial and final configurations are collision-free.Source: §VII · p. 6
VIII. EXPERIMENTS
The experiments evaluate plan constraints and deferred streams in simulation and demonstrate kitchen manipulation on a real robot. Using both techniques improves success rates and generally reduces planning time during policy execution.
VIII. EXPERIMENTS
- The simulated evaluation tested four system variants across 25 randomly generated problems in four domains, with each policy limited to 10 minutes of planning time.Source: §VIII · p. 6
- Using both plan constraints and deferred streams yields a large success-rate improvement and generally reduces total planning time while executing the policy.Table I reports success rate and mean total planning time for successful trials over 25 generated problems per task.Source: Table I · p. 6, §VIII · p. 6
- A Franka Emika Panda robot performed Inspect Drawer, Swap Drawers, and Cook Spam tasks in a real-world kitchen.Source: §VIII · p. 6
IX. CONCLUSIONS
The conclusion presents a replanning system for partially observable domains that plans directly on beliefs, constrains plan structure, and defers expensive stream evaluations.
IX. CONCLUSIONS
- Planning directly on beliefs lets the planner approximately compute detection likelihood from movable-object pose beliefs.Source: §IX · p. 6
- Constraints on plan structure ensure that the replanning policy continues making progress toward the goal.Source: §IX · p. 6
- Deferring expensive stream evaluations enables replanning to be performed efficiently.Source: §IX · p. 6
APPENDIX
The appendix lists simulated tasks by their goal conditions, prior beliefs, latent initial states, and successful execution traces. The examples include drawer inspection and stowing, as well as cooking a block after uncovering it.
APPENDIX
- For each simulated experiment, the appendix lists the goal condition, prior belief, latent initial state, and a successful execution trace.Source: APPENDIX · p. 7
1) Inspect:
- In Inspect, the block is already in the target drawer, but the robot opens it to localize the block before closing it again.The prior is uniform over both drawers, and the initial state places the block in the bottom drawer.Source: 1) Inspect · p. 7
2) Stow:
- In Stow, the robot removes the sugar box so the drawer can close, places the block inside, and closes the drawer.The sugar box's height would otherwise cause a collision with the cabinet.Source: 2) Stow · p. 7
- In the other drawer task, failing to detect the block in the first drawer leads the robot to investigate the other drawer before stowing it in the target drawer.The policy temporarily places the block on the counter while switching drawers.Source: 3) Swap · p. 7
4) Cook:
- In Cook, the robot moves one or both occluding boxes, detects the block, places it on the stove, and turns the stove on and off.Which objects it must inspect behind depends on the block's initial pose and the first manipulation action.Source: 4) Cook · p. 7