ICLR 2023

Implicit Differentiable Planning

Scaling up and Stabilizing Differentiable Planning with Implicit Differentiation

Linfeng Zhao, Huazhe Xu, Lawson L.S. Wong

Motivation

  • VIN-based planners are trained end to end by differentiating through the planning process.
  • Algorithmic differentiation couples the backward pass to every forward planning iteration.
  • Longer planning horizons increase backward runtime and memory use, and deep unrolls can become unstable.
Comparison of explicit and implicit gradients through a differentiable value-iteration planner
Algorithmic differentiation follows the full unrolled computation graph; implicit differentiation computes gradients at an estimated Bellman fixed point.

Implicit Differentiation

  • Repeated application of the Bellman operator produces an estimated fixed point, v*.
  • Differentiate through the fixed-point equation instead of the forward iteration layers.
  • The forward and backward passes use separate iteration budgets.
  • The forward pass must still solve the equilibrium accurately; with too few iterations, algorithmic differentiation can be preferable.
v* = f(v*, r, theta)
dv*/dx = (I - df/dv*)^-1 df/dx

Evaluation Environments

  • 2D maze navigation with a given grid map
  • Visual maze navigation with a learned map
  • 2-DOF manipulation in configuration space
  • 2-DOF manipulation in workspace with a learned map
Examples of navigation, visual navigation, and manipulation planning tasks
Four navigation and manipulation environments used to evaluate implicit differentiable planners.

Runtime and Memory

  • Algorithmic differentiable planners have backward runtime and memory use that grow with the number of unrolled layers.
  • Implicit differentiable planners have backward runtime independent of the number of forward iterations.
  • Forward runtime remains comparable, while memory use is lower and larger models continue to run when explicit planners exceed the 11 GB limit.
  • On 2D navigation, implicit planners converge stably at iteration counts where some algorithmic planners fail.
Backward runtime of explicitly differentiated planners as layer count and task size increase
Algorithmic differentiable planners: backward runtime grows with the number of layers; missing points indicate out-of-memory runs.
Backward runtime of implicitly differentiated planners across forward iteration counts and task sizes
Implicit differentiable planners: backward runtime remains constant as the number of forward iterations increases.

Generalization to Larger Maps

  • Models are trained on 15 x 15 maps and evaluated on unseen maps up to 99 x 99.
  • ID-SymVIN outperforms SymVIN; VIN and ID-VIN perform similarly; ID-ConvGPPN trails ConvGPPN.
  • The main benefit is training scalability and convergence stability, not a universal improvement in forward generalization.
Generalization success from 15 x 15 training maps to increasingly large unseen maps
Success rates on six map sizes, averaged over five model seeds and 1,000 unseen maps per size.

Publication

Linfeng Zhao, Huazhe Xu, and Lawson L.S. Wong. International Conference on Learning Representations, 2023.