Continuous-time multi-agent pathfinding with connectivity constraints
Complex and Intelligent Systems, cilt.12, sa.11, 2026 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 12 Sayı: 11
- Basım Tarihi: 2026
- Doi Numarası: 10.1007/s40747-026-02327-y
- Dergi Adı: Complex and Intelligent Systems
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Aerospace Database, INSPEC, Directory of Open Access Journals, Technology Collection (ProQuest)
- Anahtar Kelimeler: Connectivity, Continuous-time, Heuristic-search, Multi-agent, Pathfinding
- Orta Doğu Teknik Üniversitesi Adresli: Evet
Özet
Multi-Agent Pathfinding in continuous time (MAPFR) is the problem of computing collision-free trajectories for multiple agents moving in continuous space and time without discretizing time into time steps and unit-duration actions. Unlike classical MAPF, which assumes uniform, discrete time steps and unit-duration actions, MAPFR models arbitrary action durations and continuous motion, making it better suited for complex, real-world and multi-agent robotic systems. However, many practical applications also require agents to maintain reliable communication throughout execution, imposing a global connectivity constraint on their movements. The current state of the literature reveals that prior approaches are either constrained to discrete-time models that are unsuitable for complex real-world scenarios, or they completely omit the requirement of maintaining global connectivity. In this paper, we formalize this extended problem as CMAPFR (MAPFR with connectivity constraints), where agents must plan continuous-time trajectories that avoid collisions with each other while ensuring that their communication graph remains a single connected component. In response to this challenging variant, we propose a novel planning framework, called Connectivity-Constrained Continuous-Time Conflict-Based Search (C3BS), that integrates Continuous-Time Conflict-Based Search (CCBS) with dynamic connectivity graph maintenance to generate global network connectivity-preserving trajectories for each agent. Our approach enforces connectivity constraints during path generation, ensuring that all agents remain within both the required communication range and maintain unobstructed line-of-sight throughout their trajectories. We evaluated the method on benchmark multi-agent scenarios with varying map structures, number of agents, communication ranges, connectivity types (including range-only, line-of-sight-only, and combined), and overall task complexity. The experiment results demonstrate that the framework achieves success rates exceeding 90% within feasible execution times even in large-scale multi-agent scenarios, depending on the specific constraint configurations. This means that our approach successfully produces feasible, collision-free, connectivity-preserving trajectories for even a large number of agents in cluttered environments with efficient computational performance. This capability enables robust and coordinated operation in domains requiring continuous communication, including complex and multi-agent systems such as robotic swarms, distributed surveillance networks, and disaster response missions.