🌀 nonlinear sciences

On dynamic multi-agent pathfinding methods: review, simulations and modifications

This paper presents a systematic evaluation of six pathfinding algorithms for Dynamic Multi-Agent Pathfinding (D-MAPF) within a unified simulation framework, introducing a novel template-based method called A** that decouples offline geometric path generation from online temporal adaptation to improve solution quality in environments with dynamic obstacles and partial observability.

Original authors: Gabriel Fejziaj, Salama Hassona, Wieslaw Marszalek

Published 2026-06-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gabriel Fejziaj, Salama Hassona, Wieslaw Marszalek

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 a busy warehouse filled with dozens of delivery robots. Their job is simple: get from Point A to Point B without bumping into shelves, walls, or each other. But here's the twist: the warehouse isn't static. Doors randomly open and close, forklifts block aisles unexpectedly, and the robots can only see what's right in front of them, not the whole map.

This paper is a report card on how well different "navigation brains" handle this chaotic scenario. The researchers tested six different strategies to see which one gets the most robots to their goals quickly and safely.

The Problem: The "Blindfolded Dance"

In the real world, robots can't see the future. They might plan a path, only to find a wall has suddenly appeared. If they have to stop, look around, and draw a brand new map from scratch every time, they waste precious time.

The researchers wanted to find the best way to handle this "dynamic" chaos where:

Obstacles move: Walls appear and disappear on a schedule.
Vision is limited: Robots only see a few steps ahead.
Crowds exist: Many robots are trying to move at once, so they have to avoid crashing into each other.

The Six Contenders

The team tested six different "brains" (algorithms):

Dijkstra: The "Old School Calculator." It's very thorough but slow. Every time the map changes, it redraws the entire path from scratch, ignoring shortcuts. It's like re-reading a whole book just because one page changed.
D Lite:* The "Fixer-Upper." Instead of redrawing the whole map, it only fixes the broken parts. It's faster and smarter than Dijkstra for changing environments.
Space-Time A (STA):** The "Time Traveler." It doesn't just look at where to go, but when. It plans paths that account for time, ensuring you don't arrive at a spot exactly when another robot is there.
WHCA:* The "Window Planner." It only looks a few steps ahead (a small time window) and plans in chunks. It's fast but might miss the big picture.
M:* The "Diplomat." It lets robots plan their own paths first. If they are about to crash, then it steps in to negotiate a detour just for those two.
A (The New Star):** The "Travel Agent with Backup Plans." This is the new method the authors created.

The Star Player: A** (The Travel Agent)

The authors designed A specifically for this messy, unpredictable world. Here is how it works, using a simple analogy:

Imagine you are traveling to a city. Instead of just picking one route, you ask a travel agent to give you five different route options (templates) before you even leave your house.

Route A goes through the park.
Route B goes along the coast.
Route C goes through the mountains.

The agent makes sure these routes are very different from each other so you have choices.

Now, imagine you are driving. Suddenly, a roadblock appears on Route A.

Old methods might panic and try to calculate a whole new route from your current spot, which takes time.
A says, "No problem! I already have Route B and C ready." It quickly checks if you can merge onto Route B or C from where you are right now. If you can, it snaps you onto that new path instantly. If not, it quickly generates a few new backup routes.

Why is this cool?
It separates the "big picture" (finding different roads) from the "immediate action" (merging onto the road). This lets the robot keep moving even when the world changes, because it's never starting from zero.

The Results: Who Won?

The researchers ran thousands of simulations with different numbers of robots and different map layouts.

The Winner (Efficiency): A was the best at getting all robots to their goals with the least amount of total waiting and driving time. It was the most efficient "team player."
The Trade-off: A** is a bit "heavy" on the computer. Because it calculates all those backup routes, it takes longer to think than the simpler methods. However, the time it saves by not getting stuck or taking bad detours makes up for it.
The Losers:
- Dijkstra was too slow and inefficient in a changing world.
- D Lite* and M* were okay, but they got stuck more often or took longer routes than A**.
- WHCA* and STA* were very reliable (they rarely crashed), but they weren't as efficient at minimizing total travel time.

The Bottom Line

The paper concludes that for environments that are crowded, changing, and hard to see, the A method is the superior choice. It acts like a smart traveler who always has a Plan B, C, and D ready, allowing the whole fleet of robots to move smoothly even when the world throws them a curveball.

Note: The paper focuses strictly on these computer simulations. It does not claim these results apply to real-world medical uses, self-driving cars on highways, or other specific industries yet; it simply proves the math works better in the test environment.

Technical Summary: Review, Simulations, and Modifications on Dynamic Multi-Agent Pathfinding Methods

1. Problem Definition

This paper addresses Dynamic Multi-Agent Pathfinding (D-MAPF), a complex planning problem situated at the intersection of dynamic environments, partial observability, and inter-agent coordination. Unlike static Multi-Agent Pathfinding (MAPF), where the map is fixed, D-MAPF involves environments where obstacles appear and disappear on unknown schedules. Furthermore, agents operate under partial observability, meaning they only detect obstacles when they enter their specific vision range (via ray-casting), rather than possessing global knowledge of the environment.

The study focuses on a grid-based setting with four-connected movement, where multiple agents must reach individual goals simultaneously. The problem is constrained by:

Dynamic Obstacles: Obstacles follow deterministic or randomized schedules (appearance/disappearance times) unknown to agents until detected.
Prioritized Planning: To manage combinatorial complexity, the system uses a decoupled approach where agents plan sequentially based on a fixed priority order, treating previously planned agents as moving obstacles in a shared reservation table.
Exclusion of Optimal Coupled Solvers: Algorithms like Conflict-Based Search (CBS) are excluded due to their computational infeasibility in reactive, real-time replanning scenarios with frequent environmental changes and partial observability.

2. Methodology

The authors evaluated six representative algorithms within a unified simulation framework. All algorithms share the same map, obstacle schedules, agent parameters, and reservation systems to ensure fair comparison.

2.1 Evaluated Algorithms

Dijkstra: Serves as a baseline static planner. It performs full uniform-cost searches at each replanning step without heuristic guidance or time-awareness, treating reservations as static blocks.
D Lite:* An incremental heuristic search designed for dynamic environments. It repairs existing paths by propagating cost corrections only to affected graph portions rather than recomputing from scratch.
Space-Time A (STA):** Extends A* by incorporating time into the state representation (position + timestep), allowing for collision avoidance via reservation tables.
WHCA (Windowed Hierarchical Cooperative A):** A cooperative algorithm that restricts planning to a fixed time window (e.g., 16 steps), planning toward waypoints iteratively.
M (M-Star):* A multi-agent algorithm that plans paths independently and only expands the search space to joint configurations when collisions are detected.
A (Proposed):** A novel method introduced as the primary contribution.

2.2 The Proposed A** Algorithm

A** is designed specifically for reactive planning in dynamic, partially observable settings. Its core innovation is the decoupling of offline geometric path generation from online temporal adaptation using a template-based approach:

Template Generation (Offline/Pre-computation): Upon initialization or when an agent's known obstacle set changes, the algorithm generates $k$ $k$ candidate paths (templates) using a penalized 2D A* search.
- After finding a path, a fixed penalty is added to the traversal cost of every cell in that path.
- This forces subsequent searches to find geometrically distinct routes, creating a diverse set of candidate paths.
- Known active dynamic obstacles receive additional penalties to bias templates away from hazardous regions.
Online Reconnection (Temporal Adaptation): When a replan is triggered (e.g., an obstacle blocks the current path), A** does not search the entire space. Instead, it attempts to reconnect the agent's current position to any accessible point along the stored templates.
- It computes a "bridge" using Space-Time A* from the current position to a specific point on a template.
- It validates the "tail" (the remainder of the template) against the expected absolute time to ensure no dynamic obstacles activate along the route.
- The combination of bridge and tail that minimizes total path length is selected.
Fallback: If reconnection to all existing templates fails, new templates are generated from the current state, and the process repeats.

3. Key Contributions

The paper makes five specific contributions:

Formalization and Framework: The authors formalize D-MAPF as a reactive, partially observable problem on a grid with time-scheduled dynamic obstacles and per-agent vision ranges. They provide a simulation framework to instantiate this setting for benchmarking.
Algorithmic Integration: Six diverse algorithms (Dijkstra, D* Lite, STA*, WHCA*, M*, and A**) are integrated into a common framework, enabling systematic benchmarking and direct performance comparison.
Vision-Based Obstacle Filter: A transparent filter is introduced that enforces partial observability across all planners without modifying their core search logic, ensuring agents only react to observed obstacles.
Empirical Evaluation: A comprehensive evaluation is conducted across 8 benchmark maps, 10 agent-count configurations (1–10 agents), and 100 repetitions per combination. Metrics include Sum of Costs (SoC), Makespan, failure rates, and computational time.
Characterization of A:** The paper introduces and evaluates A**, demonstrating that its template-based approach effectively balances solution quality and replanning efficiency in dynamic environments.

4. Experimental Results

The experiments were conducted on 8 maps (including empty, maze, random, and room configurations) with dynamic obstacles appearing and disappearing within random intervals.

Solution Quality (Sum of Costs - SoC):
- A consistently achieved the lowest SoC for agent counts from 1 to 9.
- The template mechanism allows A** to bypass temporarily blocked regions by switching to pre-computed geometrically distinct routes, reducing the need for costly online detours.
- For 10 agents, M* yielded a slightly lower SoC than A**, though A** remained competitive.
- Dijkstra exhibited the highest SoC (except for 1 agent) due to its lack of time-awareness, forcing agents to wait or take longer detours.
Computational Efficiency:
- Dijkstra and D Lite* were the fastest, with average total computation times below 6 ms, due to their simplicity and incremental nature.
- A exhibited significantly higher computation times (ranging from hundreds to thousands of milliseconds). The overhead stems from generating $k$ templates (requiring $k$ penalized 2D A* runs) and evaluating bridges (requiring multiple STA* searches).
- Replanning Frequency: While A** replans less frequently than WHCA* or Dijkstra (because templates anticipate future conflicts), the cost per replan is high. Consequently, the total computational time for A** is the highest among all methods.
Robustness (Failure Rate):
- STA* and WHCA* demonstrated the lowest failure rates (below 11%), attributed to their exhaustive time-expanded search which is more likely to find a solution within the planning horizon.
- A had a higher failure rate (averaging 21%), which the authors attribute to the complexity of the replanning logic and the specific constraints of the dynamic environment.
- D Lite* and M* also showed higher failure rates (20%), particularly in dense agent configurations.

5. Significance and Claims

The paper claims that A represents a significant advancement in handling D-MAPF with partial observability. By decoupling geometric diversity generation from temporal feasibility verification, A** achieves superior solution quality (lowest SoC) in most configurations, effectively navigating environments with frequent changes and limited sensing.

The authors acknowledge the trade-off: A** achieves better paths at the cost of higher computational overhead. However, they argue that in scenarios where solution quality (minimizing total travel time/cost) is prioritized over raw replanning speed, the template-based approach offers a robust alternative to traditional incremental or windowed planners. The study concludes that while no single algorithm dominates all metrics, A** is particularly effective for minimizing the Sum of Costs in dynamic, partially observable multi-agent systems.