Symmetry in path planning: The same path can be transformed through rotations and reflections while preserving optimality.
The D4 group of symmetries includes 4 rotations and 2 reflections, which preserve the grid structure of the planning problem.
Our SymVIN architecture uses steerable convolutions to maintain symmetry equivariance throughout the planning process.
In this paper, we study a principled approach on incorporating group symmetry into end-to-end differentiable planning algorithms and explore the benefits of symmetry in planning. To achieve this, we draw inspiration from equivariant convolution networks and model the path planning problem as a set of signals over grids. We demonstrate that value iteration can be treated as a linear equivariant operator, which is effectively a steerable convolution. Building upon Value Iteration Networks (VIN), we propose a new Symmetric Planning (SymPlan) framework that incorporates rotation and reflection symmetry using steerable convolution networks. We evaluate our approach on four tasks: 2D navigation, visual navigation, 2 degrees of freedom (2-DOF) configuration space manipulation, and 2-DOF workspace manipulation. Our experimental results show that our symmetric planning algorithms significantly improve training efficiency and generalization performance compared to non-equivariant baselines, including VINs and GPPN.
Model-based planning algorithms can struggle to find solutions for complex problems, and one solution is to apply planning in a more structured and reduced space. When a task exhibits symmetry, this structure can be used to effectively reduce the search space for planning.
Figure 1: Symmetry in path planning. Given a map \(M\) (top row), the objective is to find optimal actions \(A = \text{SymPlan}(M)\) to a given position (red dots). If we rotate the map \(g.M\), its solution \(g.A\) is also connected by a rotation with the original solution \(A\).
As shown in Figure 1, if we find the optimal solution to a map, it automatically generalizes the solution to all 8 transformed maps (4 rotations times 2 reflections, including identity transformation). This can be characterized by equivariance of a planning algorithm Plan: \(g.\text{Plan}(M) = \text{Plan}(g.M)\), where \(M\) is a maze map, and \(g\) is the symmetry group \(D_4\) under which 2D grids are invariant.
Figure 2: The \(D_4\) group of symmetries includes 4 rotations and 2 reflections, which preserve the grid structure. This reduces the search space by \(|C_4| = 4\) (or \(|D_4| = 8\)) times.
We present an algorithmic framework that can provably leverage the inherent symmetry of the path-planning problem in a differentiable manner. To make our approach more accessible, we first introduce Value Iteration Networks (VINs) as the foundation for our algorithm: Symmetric VIN.
Figure 3: The commutative diagram of Symmetric Value Iteration Network (SymVIN). Every row is a full computation graph of VIN. Every column rotates the field by \(\circlearrowleft 90°\). The network maintains equivariance through steerable convolutions at each step.
Beyond translation, we are more interested in rotation and reflection symmetries. Intuitively, as shown in Figure 1, if we find the optimal solution to a map, it automatically generalizes the solution to all transformed maps. This can be characterized by equivariance of a planning algorithm Plan: \(g.\text{Plan}(M) = \text{Plan}(g.M)\), where \(M\) is a maze map, and \(g\) is the symmetry group \(D_4\) under which 2D grids are invariant.
We demonstrate the benefits of our symmetry-aware approach through extensive experiments:
Figure 4: Generalization performance under varying numbers of value iterations. Our SymVIN and SymGPPN methods show consistent improvement over non-equivariant baselines across different iteration counts.
Figure 5: Visualization of equivariance error across different planners. Our method better preserves symmetries compared to baseline approaches, leading to more consistent planning behavior under transformations.
@inproceedings{zhao2023symplan,
title={Integrating Symmetry into Differentiable Planning with Steerable Convolutions},
author={Zhao, Linfeng and Zhu, Xupeng and Kong, Lingzhi and Walters, Robin and Wong, Lawson LS},
booktitle={International Conference on Learning Representations (ICLR)},
year={2023}
}