1 Department of Computer Science, University of Illinois Chicago Email: {hliu232,yzhan361,wenhao}@uic.edu 2 Department of Computer Science, University of North Carolina at Charlotte Email: yyang52@charlotte.edu 3 Department of Computer Science and Engineering, Texas A&M University Email: yiweilyu@tamu.edu
*This work was supported in part by the U.S. National Science Foundation under Grant CMMI-2528997.
Fig. 1. Illustration of proposed time-aggregated connectivity, where robots may temporarily disconnect while
achieving global connectivity through union of graph formed by selected reconnected edges over task-prescribed
time window \(T_{\mathrm{w}}\).
Abstract
Traditionally, connectivity maintenance for mobile robot teams enforces persistent global connectivity at every instant to guarantee information flow. While effective, this requirement can be overly restrictive when communication ranges are limited and robots must spread out to simultaneously perform different mobility tasks. In many scenarios, robots do not need to remain continuously connected at all times. Instead, they may temporarily disconnect as long as the required communication links are re-established within prescribed time windows, allowing team-wide information to propagate over time.
Motivated by this, we introduce a time-aggregated connectivity maintenance framework, which allows temporary disconnections while preserving team-wide information exchange over each time window, as shown in Fig. 1. The proposed framework combines a time-window aggregated minimum spanning tree (TWA-MST) to select low-effort reconnection edges and adaptive prescribed-time control barrier functions (adaptive PT-CBFs) to guarantee timely pairwise reconnection. Simulation examples with two-robot and multi-robot teams demonstrate that the proposed method enables robots to separate for task execution and subsequently re-establish the required communication links within task-prescribed time windows.
Method Overview
The approach is implemented as a coordination layer on top of robots' nominal trajectories, e.g., those generated by multi-agent path finding algorithms (MAPF) for some primary tasks. It intervenes by selectively reconfiguring corresponding robots' motions only when reconnection is needed, so robots can follow their task plans with low additional effort.
TWA-MST scheduler: for each candidate robot pair, aggregate predicted edge reconnection cost over a finite window given nominal trajectories, then choose a sparse set of reconnection edges and timing for low total control effort.
Adaptive PT-CBF controller: once an edge is triggered, adapt the prescribed-time barrier parameters online
so reconnection remains feasible and timely while reducing unnecessary control deviation.
Examples
In all videos, circle markers (●) indicate robot positions,
star markers (★) indicate assigned goals,
colored curves show trajectories, and labels (0-7) denote robot IDs.
Two-Robot Reconnection Comparison
Scenario: Two robots move from their initial positions to assigned goals under a short-range communication radius (\(R_{\mathrm{c}} = 3~\mathrm{m}\)). A reconnection event is triggered at the beginning of the trial, meaning that the required pairwise communication link must be re-established during motion. We compare our adaptive prescribed-time control barrier function (Adaptive PT-CBF), against prescribed-time control barrier function (PT-CBF with \(T_{\mathrm{p}} = 3~\mathrm{s}\) and \(T_{\mathrm{p}} = 15~\mathrm{s}\)), and a finite-time control barrier function (FT-CBF) under the same trigger schedule and communication radius. Here, \(T_{\mathrm{p}}\) denotes the pre-defined reconnection deadline (required parameter for PT-CBF)
Results:Our Adaptive PT-CBF reaches both goals with successful reconnection in a shorter run
(\(t \approx 28.57~\mathrm{s}\)) without manual \(T_{\mathrm{p}}\) tuning beforehand.
(a) Adaptive PT-CBF (end time \(t = 28.57~\mathrm{s}\))
(b) PT-CBF (\(T_{\mathrm{p}} = 3~\mathrm{s}\), end time \(t = 49.90~\mathrm{s}\))
(c) PT-CBF (\(T_{\mathrm{p}} = 15~\mathrm{s}\), end time \(t = 30.72~\mathrm{s}\))
(d) FT-CBF (end time \(t = 35.07~\mathrm{s}\))
Multi-Robot Navigation with Enforced Time-Aggregated Connectivity
Scenario: We demonstrate our proposed framework on a large-scale multi-robot navigation task in a cluttered indoor environment. Eight robots navigate through narrow corridors toward their assigned goals using trajectories generated by a multi-agent path finding (MAPF) planner as the nominal task plans. While following these nominal trajectories, robots may become disconnected and are expected to re-establish communication with different teammates over a task-prescribed time window of \(48.30\,\mathrm{s}\) to satisfy the time-aggregated connectivity requirement. We compare our approach against several baselines, including minimum connectivity constraint spanning tree (MCCST), time-sub-interval minimum spanning tree (TSMST), and a random spanning tree strategy.
Results:Our method reaches the assigned goals with a shorter completion horizon than MCCST-, TSMST-, and Random spanning tree-based baselines while
avoiding overly rigid always-connected motion.
(a) MAPF nominal plan, reference without reconnection control (end time \(t = 48.30~\mathrm{s}\))
(b) Ours, which selects edges from different times within the look-ahead window and only requires their union graph to be connected (completion time \(t = 50.16~\mathrm{s}\))
(c) MCCST, which maintains persistent global connectivity through minimum connectivity constraint spanning tree (failing to reach the goal)
(d) TSMST, which selects the lowest-cost spanning tree appearing at a future instant within the look-ahead window and enforces its missing edges (completion time \(t = 55.61~\mathrm{s}\))
(e) Random spanning tree, which uses a randomly selected spanning tree topology and chooses its minimum cost instant (completion time \(t = 68.96~\mathrm{s}\))
More Research
Explore more papers from our lab through the following research pages.
Spatio-Temporal Reconnection for Multi-Robot Networks using Adaptive Prescribed-Time CBFs
@inproceedings{liu2026timeaggregated,
title={Time-Aggregated Connectivity Maintenance for Multi-Robot Networks},
author={Liu, Hao and Yang, Yupeng and Zhang, Yanze and Lyu, Yiwei and Luo, Wenhao},
booktitle={Robotics: Science and Systems (RSS)},
year={2026}
}
