Probabilistic Backward and Forward Reasoning in Stochastic Relational Worlds

Tobias Lang, Marc ToussaintICML 2010

Planning for a robot in the real world is messy. Actions are rarely deterministic—if a robot tries to pick up a block, it might slip, or the whole tower might topple. Furthermore, the number of possible things a robot could do at any moment is astronomical.

In their 2010 paper, "Probabilistic Backward and Forward Reasoning in Stochastic Relational Worlds," Tobias Lang and Marc Toussaint propose a way to make this planning more efficient by reasoning from both ends: starting from where the robot is (forward) and where it wants to be (backward).

TL;DR

The authors present a bidirectional probabilistic planning framework that combines forward and backward reasoning using learned relational rules. By "meeting in the middle," the algorithm significantly prunes the search space, allowing robots to plan more accurately and quickly in complex, noisy 3D environments.

What Problem Does This Paper Address?

Most automated planning falls into one of two camps:

  1. Forward Planning: You start at the current state and explore possible future actions. The problem? The "search tree" grows exponentially. If you have 10 possible actions and need a 10-step plan, you're looking at $10^{10}$ possibilities.
  2. Backward Planning: You start at the goal and work backward to the current state. This is often more efficient because fewer actions typically lead to a specific goal than lead away from a starting state.

However, in stochastic relational worlds (where actions have random outcomes and involve relationships between many objects), backward planning is notoriously difficult. Most existing probabilistic planners only look forward because "inverting" a random outcome is mathematically complex. This paper tackles the challenge of creating a robust, probabilistic backward reasoning component that can be integrated with forward search.

Methods

The authors build upon a framework called PRADA, which uses Noisy Indeterministic Deictic (NID) rules. These rules describe how actions change the world (e.g., "If I drop X on Y, there is a 60% chance X ends up on Y, and a 10% chance it's just 'noise' or a failure").

1. Learning the "Reverse" World

Instead of trying to mathematically invert complex forward rules, the authors take a clever, data-driven approach: they learn a backward model directly from experience. By taking "triples" of data (State A $\xrightarrow{Action}$ State B) and simply reversing them (State B $\xrightarrow{Action}$ State A), they train a model that predicts which previous states likely led to the current one.

2. The Two-Filter Approach

They implement a "two-filter" smoothing method:

  • Forward Filter: Estimates which states are reachable from the start.
  • Backward Filter: Estimates which states are likely to lead to the goal.
  • The Integration: The planner looks for an action sequence where the forward-reachable states overlap strongly with the backward-reachable states.

3. Goal Mixture Models

A common pitfall in backward planning is "partial goals" (e.g., "I want a tower of three blocks, I don't care which ones"). If you treat this as a single average state, you lose the specific relationships (correlations) between blocks. The authors use a mixture model to represent the goal, effectively allowing the planner to consider multiple specific ways the goal could be achieved simultaneously.

Datasets and Environment

The researchers evaluated their approach in a 3D simulated desktop environment powered by the Open Dynamics Engine (ODE).

3D simulated desktop environment with a robot arm and various objects.
  • The Setup: A robot arm interacts with cubes, balls, and boxes of different sizes.
  • Training: The models were trained on 500 "experience triples" generated by performing random actions in the simulator.
  • The Challenge: Unlike "grid world" toy problems, this simulation includes realistic physics—piles can topple, and objects can fall off the table and become lost forever.

Key Insights and Ideas

  • Pruning via Directionality: Backward reasoning acts as a powerful filter. In a "Box Tower" task, many actions are possible at the start (opening any box, picking up any block), but very few actions lead directly to the final goal state. Starting from the goal narrows the search space immediately.
  • Learning is Easier than Inverting: The "aha moment" here is that you don't need a perfect symbolic inversion of a forward rule. If you have enough data, you can simply learn the backward dynamics as a separate model.
  • Relational Strength: Because the rules are "relational" (reasoning about "any block X on any block Y"), the knowledge learned in a small world with a few objects can be directly applied to much larger, more complex worlds without retraining.

Key Results

The bidirectional approach (PRADA$\leftrightarrows$) was compared against pure forward planning (PRADA$\rightarrow$) and UCT (a popular Monte Carlo Tree Search algorithm).

Experimental results comparing UCT, forward PRADA, and bidirectional PRADA across different object counts.
  • Efficiency: In tasks like reversing a stack of cubes, the bidirectional approach was roughly 35% faster than pure forward planning while maintaining a higher success rate.
  • Scalability: In tasks with 10 objects (a massive state space), the bidirectional planner achieved a significantly higher discounted reward (~111.34) compared to the forward-only version (~97.25) and UCT (~32.15).
  • Accuracy: The bidirectional search was less likely to get "distracted" by irrelevant actions that looked good in the short term but didn't lead to the goal.

Limitations and Future Work

  • Deictic Resolution: The authors noted that learning backward models is slightly harder than forward ones because "deictic references" (referring to objects not directly involved in the action, like the table a block was taken from) are harder to resolve in reverse.
  • Grounded vs. Lifted: While the rules are abstract, the planning still happens in a "grounded" domain (specific objects). The authors suggest that moving toward "lifted" backward reasoning—reasoning about classes of objects without ever picking specific ones—is the next major frontier.
  • Goal Descriptions: Finding the right mixture model to approximate complex goal beliefs remains a manual task; automating this from natural language or high-level rewards is a suggested future direction.

Summary updated

BibTeX
@inproceedings{lang2010probabilistic,
  author = {Tobias Lang and Marc Toussaint},
  title = {{Probabilistic Backward and Forward Reasoning in Stochastic Relational Worlds}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
}
Figure