Keeping Robot Teams Connected: A New Approach to Multi-Agent Pathfinding

Imagine a team of rescue robots navigating through a disaster zone, or a fleet of autonomous vehicles coordinating deliveries in a dense urban environment. In these scenarios, maintaining constant communication between all team members isn’t just helpful—it’s essential for mission success and safety. But how do you plan paths for multiple agents that need to stay connected while navigating complex environments with obstacles (Multi-Agent Pathfinding under Team-Connected Communication Constraints-MAT3C)?

We introduce APEDL (Adaptive Path Expansion and Dynamic Leading), a framework that tackles this challenging problem head-on.

The Challenge: Pathfinding with Team-Connected Communication Constraints

Traditional multi-agent pathfinding focuses on getting robots from start A to goal B without collisions. But many real-world applications require something more: maintaining a communication network throughout the entire journey. This means agents must form a “spanning tree” of connections—think of it as ensuring there’s always a chain of communication linking every robot to every other robot.

This constraint creates significant complications:

• Changing neighborhoods: Agents that can communicate at the start might need to separate to reach different goals
• Fixed leader problems: If one robot leads and gets stuck or reaches its goal early, followers can become stranded
• Planning complexity: Standard approaches that compute entire paths in one shot often fail when agents need to coordinate dynamically

The APEDL Solution: Two Key Innovations

We developed two complementary techniques to address these challenges:

1. Adaptive Path Expansion (APE)

Instead of planning complete paths from start to finish in one go, APE allows agents to build their routes incrementally across multiple stages. When an agent gets stuck following a leader who’s heading in a different direction, it doesn’t fail entirely—it can resume planning in the next expansion phase.

Think of it like GPS navigation that recalculates your route when you miss a turn, rather than giving up entirely.

2. Dynamic Leading (DL)

Rather than designating a fixed leader for the entire mission, DL allows leadership to transfer dynamically to whichever agent has made the most progress at any given time. This prevents the team from getting stuck when the original leader reaches its goal first or moves in an unhelpful direction.

The framework also includes a “Team Communication Tree” that manages the overall planning process and ensures communication constraints are never violated.

Real-World Performance

We tested APEDL across five different environment types—from random obstacle fields to office buildings with narrow hallways. The results are compelling:

• Successfully handles up to 25 agents under limited communication range constraints
• Achieves over 90% success rates where existing approaches routinely fail
• Significantly outperforms state-of-the-art methods like priority-based search and traditional platooning approaches

The framework works with two types of communication constraints: limited range (agents must stay within a certain distance) and line-of-sight (agents must have visual contact). While performance is stronger under range constraints, APEDL still outperforms baselines even in the more challenging line-of-sight scenarios.

Limitations and Future Work

APEDL is not theoretically complete—there are scenarios where a solution exists but the algorithm might not find it due to its greedy approach to single-agent planning. However, for practical applications, the significant performance improvements over existing methods make it a valuable contribution.

The performance of APEDL degrades under line-of-sight constraints, particularly in environments with many obstacles. Future work could focus on developing better heuristics for the communication tree and extending the framework to achieve theoretical completeness.

Why This Matters

This research addresses a gap between theoretical multi-agent pathfinding and real-world applications where maintaining team connectivity is crucial. Applications span from:

• Disaster response: Search and rescue robots that must stay coordinated
• Military operations: Autonomous vehicles operating in contested environments
• Industrial automation: Robot teams working in warehouses or manufacturing facilities
• Environmental monitoring: Sensor networks that need to maintain data connectivity

The Bottom Line

APEDL represents a meaningful step forward in multi-agent pathfinding for communication-constrained environments. While not perfect, it demonstrates that thoughtful algorithmic design can dramatically improve performance on practically important problems. The framework’s ability to handle dynamic leadership changes and incremental path planning offers a more robust approach than previous methods.

For robotics researchers and practitioners working on multi-agent systems, this work provides both concrete algorithmic improvements and valuable insights into the challenges of maintaining connectivity during coordinated navigation. As autonomous systems become more prevalent in complex, real-world environments, solutions like APEDL will become increasingly important for ensuring reliable team coordination.

*The full paper, “Multi-Agent Pathfinding Under Team-Connected Communication Constraint via Adaptive Path Expansion and Dynamic Leading,” is being reviewed in the Journal of Artificial Intelligence Research in 2025. The algorithm detail can be seen in this link . *