💻 computer science

Homotopy-Aware Multi-Agent Path Planning on Plane

This paper presents an efficient, homotopy-aware multi-agent path planning framework for planar domains that leverages Dynnikov coordinates and revised prioritized planning to generate diverse, complete solutions while significantly outperforming non-homotopy-aware methods in speed and avoiding local optima.

Original authors: Kazumi Kasaura

Published 2026-02-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kazumi Kasaura

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the director of a massive, chaotic dance floor where hundreds of robots (agents) need to move from their starting spots to specific destinations. The floor is cluttered with pillars (obstacles), and the robots are large enough that they can't bump into each other.

Your goal isn't just to get them there; you want the smoothest, most energy-efficient dance possible.

Here is the problem: If you just tell the robots "go straight to your goal," they might get stuck in a local trap. They might find a path that looks good at first glance but forces them to take a huge detour later, or they might get stuck in a deadlock where they can't pass each other.

This paper proposes a clever new way to solve this: Homotopy-Aware Multi-Agent Path Planning.

Let's break down the jargon into simple concepts using some creative analogies.

1. The "String" Analogy: What is Homotopy?

Imagine you tie a piece of string from a robot's start point to its goal point.

Scenario A: The string goes over a pillar.
Scenario B: The string goes under the same pillar.

Even if you wiggle the string around, you can never turn Scenario A into Scenario B without cutting the string or lifting it off the floor. In math, these are called different homotopy classes. They are topologically distinct paths.

Why does this matter?
If you only look for one path, you might pick the "over" path. But maybe the "under" path is actually shorter or smoother once you optimize it. If you only look for many paths that all go "over" the pillar, you are just wasting time finding the same solution ten times. You need to find one path that goes over and one path that goes under.

2. The "Braided Hair" Problem

Now, imagine you have 100 robots. As they move, they weave around each other.

Robot A passes to the left of Robot B.
Later, Robot C passes to the right of Robot D.

The pattern of their movements creates a braid. In mathematics, this is called a "Braid Group."
The problem is that calculating these braids is incredibly hard. It's like trying to untangle a knot in a pair of headphones while blindfolded. Traditional methods try to write down the "word" for the knot (e.g., "left, right, left, left..."), but checking if two long words mean the same knot is a computational nightmare.

3. The Magic Tool: Dynnikov Coordinates

This is the paper's secret sauce. The authors use a mathematical trick called Dynnikov coordinates.

The Analogy:
Instead of trying to describe the knot by writing a long, confusing sentence (the "word"), imagine you have a special ruler with numbers on it. You slide the ruler over the knot, and it instantly spits out a simple list of numbers (a tuple of integers).

Old Way: "The string went around the pillar, then crossed the other string, then went back..." (Hard to compare).
New Way (Dynnikov): "The knot is represented by the numbers: [2, -1, 5, 0]." (Easy to compare!).

If two different-looking paths result in the same list of numbers, they are the same path. If the numbers are different, they are topologically unique. This allows the computer to check for "duplicate" paths instantly and efficiently.

4. The Strategy: "Revised Prioritized Planning"

The authors combine their "Magic Ruler" (Dynnikov) with a strategy called Revised Prioritized Planning (RPP).

Think of this like organizing a parade:

The Old Way: You tell Robot 1 to go. Then Robot 2. Then Robot 3. If Robot 2 gets stuck because Robot 1 is in the way, you have to start over.
The New Way: You tell Robot 1 to go, but you keep multiple versions of Robot 1's path in your head (one going left, one going right).
When you plan for Robot 2, you try to fit it into all of Robot 1's different versions.
You use the "Magic Ruler" to make sure you aren't wasting time planning paths that are topologically identical.

5. The Results: Why is this better?

The authors ran two main tests:

Speed Test: They compared their method against older methods.
- The Result: Their method was much faster. As they added more robots, the old method slowed down dramatically (like a traffic jam getting worse). Their method scaled up smoothly. It's like switching from a single-lane dirt road to a multi-lane highway.
Quality Test: They took the paths they found and tried to smooth them out to save energy (optimization).
- The Result: Because they found a wider variety of truly different starting paths (thanks to the Magic Ruler), they were able to find the globally best solution. The old methods often got stuck in "local optima"—good solutions that weren't the best possible ones.

Summary

Imagine you are trying to find the best route for a swarm of bees to get to a flower garden.

Without this paper: You might send the bees down one path, realize it's clogged, and try another path that looks exactly the same as the first one, wasting time.
With this paper: You use a "magic map" (Dynnikov coordinates) that instantly tells you which paths are truly different (going left vs. right of a tree). You explore all the unique options quickly, ensuring that when you finally smooth out the flight path, you find the absolute most efficient route for the whole swarm.

In short: This paper gives robots a "topological GPS" that helps them avoid getting stuck in bad loops and ensures they find the smoothest, most efficient way to move together, even in crowded, obstacle-filled environments.

1. Problem Definition

The paper addresses the Multi-Agent Path Planning (MAPP) problem in planar domains containing obstacles. The core objective is not merely to find a collision-free path for $N$ agents, but to generate $K$ mutually non-homotopic solutions (paths that cannot be continuously deformed into one another without crossing obstacles or other agents).

Motivation: In trajectory optimization, local optimization of a single initial path often leads to local minima. Different topological paths (homotopy classes) may converge to vastly different global optima after smoothing. Therefore, generating diverse initial solutions across different homotopy classes is crucial for finding globally optimal trajectories.
Challenge: Calculating homotopy classes for multiple agents is computationally difficult because the fundamental group of the configuration space is the Pure Braid Group, which is non-abelian. Solving the "word problem" (determining if two path representations are equivalent) in general braid groups is notoriously hard.
Goal: Develop a scalable, complete framework to generate multiple homotopically distinct solutions efficiently, enabling better downstream trajectory optimization.

2. Methodology

The authors propose a framework combining Revised Prioritized Planning (RPP) with Dynnikov coordinates to manage braid group elements efficiently.

A. Theoretical Framework

Reduction to Unlabeled Case:
- The problem is mapped from the labeled configuration space $C_n(D)$ to the unlabeled configuration space $UC_n(D)$ .
- Instead of tracking specific agent-goal permutations, the method treats agents as indistinguishable during homotopy calculation. This allows the use of the Braid Group ( $B_n$ ) rather than the more complex Pure Braid Group ( $P_n$ ) for labeling.
- Obstacles are treated as "virtual agents" that remain stationary, reducing the domain $D$ (with obstacles) to $\mathbb{R}^2$ minus $N+R$ points.
Word Construction:
- Homotopy classes are represented as "words" formed by generators $\sigma_i$ (representing the counter-clockwise swap of agents $i$ and $i+1$ based on x-coordinates).
- As agents move along a roadmap, the algorithm detects swaps in agent ordering to append generators to the braid word.
Dynnikov Coordinates (The Core Innovation):
- To avoid the computational bottleneck of solving the word problem using traditional methods (like Dehornoy order), the authors use Dynnikov coordinates.
- These coordinates represent braid group elements as tuples of integers $(a_1, \dots, a_{n-1}, b_1, \dots, b_{n-1})$ .
- Advantage: The group action and comparison of braids can be performed using simple arithmetic operations (addition, subtraction, max, min) on these integers. This allows for efficient storage and comparison of homotopy classes using standard data structures (e.g., self-balancing binary search trees).

B. Algorithm: Homotopy-Aware Revised Prioritized Planning (RPP)

The algorithm modifies the standard RPP approach:

Iterative Planning: Agents are planned one by one according to a priority order.
Homotopy-Augmented Graph: For the $i$ -th agent, the search is performed on a graph where vertices are pairs $(v, w)$ , consisting of a grid vertex $v$ and a braid word $w$ (represented by Dynnikov coordinates).
Parallel Expansion: Unlike standard RPP which finds a single path, this method maintains a set of plans for higher-priority agents, each belonging to a different homotopy class.
Search: An A*-like search is performed on the homotopy-augmented graph to find paths for the current agent that avoid collisions with previously planned agents while exploring different braid classes.
Completeness: The authors prove that under specific geometric assumptions (sufficient separation between starts, goals, and obstacles), the algorithm is complete: it can generate a solution for any valid homotopy class given a sufficiently large $K$ .

3. Key Contributions

First Sound Framework: This is the first known framework for homotopy-aware multi-agent path planning on a plane that is both theoretically sound and practically scalable.
Efficient Braid Management: The integration of Dynnikov coordinates allows for efficient handling of the non-abelian braid group, avoiding the high computational cost associated with Dehornoy orders.
Completeness Proof: The paper provides a theoretical proof that the method can generate solutions for all homotopy classes under specific density and separation assumptions.
Scalability: The method scales significantly better than previous approaches, making it viable for swarms of hundreds of agents.

4. Experimental Results

The authors conducted two main experiments:

A. Runtime and Scalability

Comparison: Compared their method (Dyn) against a baseline using Dehornoy order and handle reduction (HR).
Agent Scaling:
- Dyn: Runtime increased roughly quadratically ( $\Theta(n^2)$ ) with the number of agents.
- HR: Runtime increased roughly quintically ( $\Theta(n^5)$ ).
Solution Count ( $K$ ) Scaling:
- Dyn: Runtime increased linearly with $K$ .
- HR: Runtime increased slightly faster than linearly.
Conclusion: Dynnikov coordinates are the superior choice for managing braid classes in MAPP, especially as the number of agents grows.

B. Trajectory Optimization

Setup: Generated initial discrete paths using the proposed method (100 homotopically distinct solutions) and optimized them continuously using an acceleration-based cost function (minimizing jerk/energy).
Baselines: Compared against:
- OO: A single optimal grid path.
- PPvP: 100 paths generated by RPP with random priority orders (no homotopy awareness).
Findings:
- The homotopy-aware method (Ours) consistently found lower-cost trajectories than both baselines.
- PPvP failed to generate diverse homotopies (especially in empty maps), leading to many redundant initial paths that converged to the same local optima.
- Significance: Explicitly generating homotopically distinct solutions is critical for escaping local optima in continuous trajectory optimization.

5. Significance and Limitations

Significance: The paper bridges the gap between topological path planning and multi-agent systems. It demonstrates that topological diversity is not just a theoretical concept but a practical necessity for finding high-quality, low-cost trajectories in continuous environments. The use of Dynnikov coordinates solves a long-standing computational bottleneck in braid group manipulation.
Limitations:
- Agent Size: The current homotopy model treats agents as points. It does not account for homotopy classes that only emerge when considering the physical size of agents (e.g., agents passing through a narrow corridor in a specific order).
- Optimality: The method uses prioritized planning, which is not globally optimal in terms of path cost, though it is sufficient for generating diverse initial seeds.
- Future Work: The authors suggest combining this framework with optimal search algorithms (like Increasing Cost Tree Search) and exploring decentralized control strategies where agents communicate only their braid classes.

In summary, this paper presents a breakthrough in multi-agent planning by providing a computationally efficient method to explore the topological landscape of path solutions, directly leading to improved performance in continuous trajectory optimization tasks.