Symmetry Breaking in Planning and Multi Agent Pathfinding

This direction is merged into another direction: symmetry-induced search redundancy. Its last version stays readable and citable here.

Version 1 of 124 papers33 conceptsfrozen 2026-10-04

In automated planning and pathfinding, the greatest enemy of efficiency is not the size of the environment, but the presence of symmetry. Symmetry occurs when a search algorithm treats functionally identical states or paths as distinct, forcing it to redundantly explore thousands of permutations that lead to the same outcome.

Without mechanisms to "break" these symmetries, solvers fall into an exponential trap, exhaustively proving that every slight variation of a failing plan still fails. Modern research has moved from simple object-based pruning to sophisticated geometric and logical constraints that resolve entire families of redundant conflicts in a single step.

The Permutation Trap in Classical Planning

The intuition for symmetry breaking begins with objects. In a logistics problem, if you have two identical trucks at the same location, a standard planner might try moving Truck A then Truck B, and then separately try moving Truck B then Truck A. To the algorithm, these are different branches; to the user, they are identical.

Maria Fox and Derek Long addressed this in their work on the STAN planner. By automatically detecting functionally interchangeable objects, they allowed the planner to treat them as a single group. This prevents the "exponential explosion" of searching redundant permutations, turning intractable combinatorial problems into manageable ones.

Path Symmetry and Canonical Orderings

In grid-based navigation, symmetry manifests as "path redundancy." If an agent needs to move two steps right and two steps up in an open field, there are six different shortest paths (e.g., Right-Right-Up-Up, Right-Up-Right-Up, etc.). A standard A* search might evaluate all of them.

Nathan R. Sturtevant and Steve Rabin deconstructed this problem in Canonical Orderings on Grids. They showed that the success of algorithms like Jump Point Search (JPS) stems from enforcing a canonical ordering—a rule that says "if you can reach a point via multiple equivalent paths, only consider the one that follows a specific sequence (like Horizontal-then-Vertical)."

By pruning all non-canonical paths, the search space collapses. Daniel Harabor and Peter J. Stuckey further generalized this by treating JPS as a graph abstraction, allowing these symmetry-breaking rules to be integrated with other speedup techniques like Contraction Hierarchies.

Conflict Symmetry in Multi Agent Coordination

The most complex form of symmetry arises in Multi-Agent Path Finding (MAPF). When two agents' paths intersect, they create a "conflict." In open spaces, there might be millions of ways for two agents to collide within a certain area (a "rectangle conflict").

Jiaoyang Li and her collaborators identified that standard Conflict-Based Search (CBS) fails here because it tries to resolve each individual collision point one by one. In Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding, they introduced barrier constraints. Instead of saying "Agent 1 cannot be at cell (X,Y) at time T," a barrier constraint says "Agent 1 must stay on one side of this entire boundary," effectively resolving thousands of potential symmetric collisions in a single branch of the search tree.

This logic extends to other spatial configurations:

  • Corridor Symmetries: In narrow passages, agents may have many ways to delay or move that all result in the same deadlock. Li et al. developed constraints to force one agent to wait or detour entirely.
  • Target Symmetries: When an agent reaches its goal but blocks others, the search can stall. Specialized constraints now recognize when a target is "occupied" in a way that creates redundant failures.

Logic Based Pruning and Mutex Propagation

While geometric constraints work well for grids, more general planning problems require logical symmetry breaking. Han Zhang and T. K. Satish Kumar adapted mutex (mutual exclusion) propagation from classical planning to MAPF.

In Multi-Agent Path Finding with Mutex Propagation, they demonstrated how to propagate constraints through time to identify pairs of (agent, location, time) that are physically impossible to satisfy simultaneously. This acts as a generalized symmetry breaker, automatically discovering constraints that human researchers might otherwise have to code manually for every new environment type, such as those involving large agents or continuous time.

Learning to Break Symmetry

The latest frontier involves using machine learning to identify these redundancies. Taoan Huang and Sven Koenig have explored learning-based conflict resolution, where a model learns to prioritize which symmetries to break first.

More recently, Y. H. Bai and Felipe Trevizan introduced Distincter, which uses Graph Neural Networks (GNNs) to exploit the inherent permutation invariance of symmetric objects. By embedding symmetry breaking directly into the neural architecture, these planners can outperform long-standing state-of-the-art systems by refusing to even "see" the redundant permutations that once crippled search algorithms.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_symmetry_breaking_in_planning_and_multi__4f36cfc3,
  title = {Symmetry Breaking in Planning and Multi Agent Pathfinding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/symmetry-breaking-in-planning-and-multi-agent-pathfinding/rdr_4f36cfc37ebf4a25aa6b23c558861c56},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_symmetry_breaking_in_planning_and_multi__4f36cfc3_v1,
  title = {Symmetry Breaking in Planning and Multi Agent Pathfinding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/symmetry-breaking-in-planning-and-multi-agent-pathfinding/rdr_4f36cfc37ebf4a25aa6b23c558861c56/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}