This paper proposes a novel planning framework for solving the multi-agent pathfinding problem under team-connected communication constraints. Every agent must maintain a communication channel with the rest of the team while moving. Existing multi-agent pathfinding methods (e.g., priority-based search) have potential in this domain, but they may fail when the neighboring configurations at the starting and target points are different. A single-extension approach (compute each agent's path from the starting point to the target point as a single extension) cannot reliably handle planning under communication constraints when the neighbors change while the agent is moving. Similarly, a leader-follower approach (e.g., platoning) is effective in maintaining team communication, but its practicality is limited because fixing the leader in the early stage of the planning may cause planning failure in dense environments. To overcome these limitations, this paper proposes a novel two-stage multi-agent pathfinding framework that integrates two techniques. The first technique is an adaptive path extension technique that extends the agent's path to the target point in multiple steps, and the second technique is a dynamic leader technique that reselects the leading agent during each agent's path extension whenever progress is impossible. Simulation experiments show that the proposed technique can handle up to 25 agents in five types of environments under limited communication range constraints, up to 11 to 12 agents in three types of environments under line-of-sight communication constraints, and achieves a success rate of over 90% even when existing methods fail.
