A Lightweight Traffic Map for Efficient Anytime LaCAM*

This paper proposes a new approach that leverages LaCAM*'s ability to construct a dynamic, lightweight traffic map during search, overcoming the computational overhead and static limitations of existing Frank-Wolfe-based guidance path methods to achieve higher solution quality in Multi-Agent Path Finding.

The Gist

Imagine a massive, bustling warehouse filled with hundreds of tiny robots. Their job is simple: pick up packages and deliver them to specific spots. But here's the catch: they all share the same floor, and if two robots try to occupy the same square at the same time, they crash.

This is the Multi-Agent Path Finding (MAPF) problem. It's like trying to get 1,000 people to leave a stadium at once without anyone tripping over each other.

The Old Way: The "Blind Rush"

For a long time, the best way to solve this was to tell every robot: "Go straight to your destination using the shortest path!"

This works fine when there are only a few robots. But when the warehouse gets crowded, everyone rushes for the same narrow hallway. It creates a massive traffic jam. The robots get stuck, the system slows down, and the "solution" (getting everyone to their goal) takes forever.

Some researchers tried to fix this by drawing a static map before the robots even started moving. They'd say, "Okay, let's calculate the perfect routes for everyone so no one gets stuck."

• The Problem: This calculation takes a long time (like spending an hour planning a party before you even invite anyone). Also, once the plan is made, it's rigid. If a robot gets delayed or the traffic changes, the old plan is useless.

The New Idea: The "Lightweight Traffic Map" (LTM)

The authors of this paper, Bojie Shen and his team, came up with a smarter, more flexible approach called LaCAM + LTM*.

Instead of spending hours planning the perfect route beforehand, they let the robots start moving and learn from the traffic jams as they happen.

Here is how it works, using a simple analogy:

1. The "Live Traffic App"

Imagine the robots are using a navigation app (like Waze or Google Maps), but instead of relying on pre-recorded data, the app updates in real-time based on what the robots are actually doing right now.

• The Search: The system runs a quick search to find a path.
• The Observation: As the robots move, the system watches where they get stuck. If 50 robots try to squeeze through the same narrow door, the system marks that door as "Heavy Traffic."
• The Update: The system instantly updates a Lightweight Traffic Map (LTM). It puts a "price tag" on that crowded door. Now, when the system plans the next move, it sees that door is expensive and tries to find a different, less crowded route.

2. The "Do-Over" Strategy

The old methods would plan once and stick to it. The new method is like a coach who says, "Okay, we tried that route, and it was a mess. Let's restart from where we are right now, look at the new traffic map, and try a different path."

They do this over and over again in a split second. Every time they restart, they have a better "map" of where the traffic is, so they guide the robots away from the jams more effectively.

Why is this better?

• No Waiting: You don't need to spend hours calculating the perfect plan before starting. The robots can start moving immediately.
• Adaptable: If a robot breaks down or a new obstacle appears, the map updates instantly. It's not a rigid plan; it's a living guide.
• Smarter: By constantly learning from the "traffic," the system naturally spreads the robots out, avoiding the bottlenecks that cause the worst delays.

The Result

In their experiments, this new method was like a master traffic controller.

• In a "One-Shot" test (finding the best plan for a warehouse all at once), it found better solutions faster than the old methods.
• In a "Live" test (where robots have to move while the plan is being made), it kept the robots flowing smoothly even when the warehouse was packed tight, whereas other methods got stuck in gridlock.

In short: Instead of trying to predict the future perfectly, this method watches the present, learns where the traffic is, and constantly reroutes the robots to keep the warehouse moving. It's the difference between a rigid, pre-printed map and a smart, live GPS that knows exactly where the traffic is right now.

Technical Summary

1. Problem Definition

The paper addresses the Multi-Agent Path Finding (MAPF) problem, which involves computing collision-free paths for a team of agents navigating a shared environment to minimize the Sum-of-Loss (SoL) objective. SoL measures the total number of agents not yet at their goals at each time step, rewarding solutions that bring agents to goals earlier rather than just minimizing the makespan (last arrival time).

The Core Challenge:
While state-of-the-art solvers like LaCAM* (Lazy Constraint Addition MAPF) and PIBT (Priority Inheritance with Backtracking) are efficient, they often rely on "myopic" heuristics (individual shortest paths). This causes agents to converge on the same routes, leading to severe congestion and poor solution quality in dense scenarios.

Limitations of Existing Solutions:
Recent attempts to fix this use guidance paths (e.g., Traffic Flow Optimization, Space Utilization Optimization). However, these methods suffer from two major drawbacks:

1. High Computational Overhead: They require expensive offline pre-computation (e.g., Frank-Wolfe optimization or iterative replanning) to reach a traffic equilibrium before the search begins, delaying the first solution.
2. Static Nature: The guidance paths are fixed. Once the search begins, they cannot adapt to dynamic congestion patterns discovered during the search, leading to diminishing returns in later iterations.

2. Methodology: Lightweight Traffic Map (LTM)

The authors propose LaCAM + LTM, a novel online mechanism that integrates a dynamic, lightweight traffic map directly into the LaCAM search process.

Key Components:

• Dynamic Traffic Mapping: Instead of pre-computing paths, LTM constructs a directed weighted graph ($G_{LTM}$) where edge weights represent real-time traffic congestion.
• Data Collection from PIBT: During the search, the algorithm records two types of data from the low-level PIBT generator:
  1. Committed Actions: Actual moves chosen by PIBT.
  2. Blocked Actions: High-priority moves that were rejected due to conflicts with other agents.
• Weight Update Mechanism:
  • Edge costs are incremented based on observed actions and blocked attempts.
  • Propagation: If a vertex is congested (or an agent waits), the cost is propagated to all outgoing edges from that vertex.
  • Normalization: Weights are bounded within a fixed range $[w_{LB}, w_{UP}]$ (e.g., 0 to 10) to prevent edges from becoming prohibitively expensive, ensuring graph connectivity.
  • Goal Handling: Once an agent reaches its goal, waiting actions there are ignored to prevent artificial penalization of goal nodes.
• Integration with LaCAM:*
  • Modified Heuristics: The evaluation function $f(v)$ in PIBT is changed from a standard distance metric to a shortest-path distance computed on the weighted LTM. This biases agents away from congested areas.
  • Frequent Restarts: The algorithm modifies LaCAM*'s anytime behavior. Instead of a single deep depth-first search, it performs bounded iterations. After each iteration, it updates the LTM and restarts the search from a selected configuration (often a node closer to the goal or a random node in the search tree) to explore new regions with the updated guidance.

Algorithm Flow (Algorithm 1):

1. Initialize LTM with uniform costs.
2. Run a bounded LaCAM* search guided by the current LTM.
3. Record the PIBT execution history (actions and conflicts).
4. Update the LTM weights based on the history.
5. Select a new restart node and repeat until the time budget is exhausted.

3. Key Contributions

1. Elimination of Offline Overhead: The method removes the need for expensive pre-computation (Frank-Wolfe or SUO), allowing the solver to start immediately and adapt in real-time.
2. Self-Adaptive Guidance: Unlike static guidance paths, the LTM evolves continuously during the search, capturing dynamic congestion patterns and steering agents away from bottlenecks as they emerge.
3. Efficient Implementation: The LTM is computationally lightweight, using simple additive updates and bounded normalization, making it suitable for large-scale, real-time applications.
4. Dual-Setting Adaptability: The framework is successfully adapted for both:
   • One-shot MAPF: Finding the best solution within a fixed time limit.
   • Planning-and-Execution MAPF: Where agents must commit to actions while planning continues (handling dynamic execution windows).

4. Experimental Results

The authors evaluated LaCAM*+LTM on standard MAPF benchmarks (grid maps) with up to 2,000 agents.

• One-Shot Setting:

  • Performance: LaCAM*+LTM consistently achieved lower Sum-of-Loss ratios compared to baselines (LaCAM*, LaCAM*+TO, LaCAM*+SUO).
  • Scalability: The performance gap widened as agent density increased. While baselines degraded due to static guidance, LTM maintained high solution quality by adapting to congestion.
  • Convergence: It demonstrated faster convergence and returned more solutions over time compared to competitors.

• Planning-and-Execution Setting:

  • Comparison: Outperformed PIE (a state-of-the-art hybrid solver combining LaCAM* and Large Neighborhood Search).
  • Robustness: In dense scenarios, PIE's performance degraded significantly because its LNS component relies on expensive Space-Time A* repairs and struggles with global congestion. LaCAM*+LTM maintained robustness by continuously updating global traffic guidance.

5. Significance

This work represents a significant shift in how traffic congestion is handled in MAPF. By moving from offline, static optimization to online, dynamic adaptation, the authors demonstrate that high-quality solutions can be found without the heavy computational cost of pre-computation.

The Lightweight Traffic Map effectively turns the search process itself into a learning mechanism, where the "history" of the search informs future decisions. This makes the approach highly suitable for real-world robotics applications (e.g., warehouse automation, autonomous driving) where environments are dynamic, agent counts are high, and real-time responsiveness is critical.