Paper deep dive
Decentralized Ergodic Coverage Control in Unknown Time-Varying Environments
Maria G. Mendoza, Victoria Marie Tuck, Chinmay Maheshwari, Shankar Sastry
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/10/2026, 1:58:00 AM
Summary
The paper introduces a decentralized multi-agent coverage framework for Unmanned Aerial Vehicles (UAVs) operating in unknown, time-varying environments under partial observability. The approach utilizes Gaussian Processes for online belief updates of importance maps and Rapidly Ergodic Markov Chains (REMC) to generate adaptive policies that balance exploration and exploitation, ensuring long-term visitation frequencies match estimated importance distributions.
Entities (4)
Relation Signals (2)
UAV → implements → Rapidly Ergodic Markov Chain
confidence 95% · Each agent computes an adaptive ergodic policy, implemented via a Markov-chain transition model
UAV → uses → Gaussian Processes
confidence 95% · Gaussian Processes are used to perform those online belief updates.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:A key challenge in disaster response is maintaining situational awareness of an evolving landscape, which requires balancing exploration of unobserved regions with sustained monitoring of changing Regions of Interest (ROIs). Unmanned Aerial Vehicles (UAVs) have emerged as an effective response tool, particularly in applications like environmental monitoring and search-and-rescue, due to their ability to provide aerial coverage, withstand hazardous conditions, and navigate quickly and flexibly. However, efficient and adaptable multi-robot coverage with limited sensing in disaster settings and evolving time-varying information maps remains a significant challenge, necessitating better methods for UAVs to continuously adapt their trajectories in response to changes. In this paper, we propose a decentralized multi-agent coverage framework that serves as a high-level planning strategy for adaptive coverage in unknown, time-varying environments under partial observability. Each agent computes an adaptive ergodic policy, implemented via a Markov-chain transition model, that tracks a continuously updated belief over the underlying importance map. Gaussian Processes are used to perform those online belief updates. The resulting policy drives agents to spend time in ROIs proportional to their estimated importance, while preserving sufficient exploration to detect and adapt to time-varying environmental changes. Unlike existing approaches that assume known importance maps, require centralized coordination, or assume a static environment, our framework addresses the combined challenges of unknown, time-varying distributions in a more realistic decentralized and partially observable setting. We compare against alternative coverage strategies and analyze our method's response to simulated disaster evolution, highlighting its improved adaptability and transient performance in dynamic scenarios.
Tags
Links
- Source: https://arxiv.org/abs/2604.04280v1
- Canonical: https://arxiv.org/abs/2604.04280v1
Trouble viewing inline? Open PDF directly →
Full Text
49,199 characters extracted from source content.
Expand or collapse full text
Decentralized Ergodic Coverage Control in Unknown Time-Varying Environments Maria G. Mendoza University of California, Berkeley. maria_mendoza@berkeley.edu Victoria Marie Tuck University of Pennsylvania. vtuck@seas.upenn.edu Chinmay Maheshwari Johns Hopkins University. chinmay_maheshwari@jhu.edu Shankar Sastry University of California, Berkeley. sastry@coe.berkeley.edu Abstract A key challenge in disaster response is maintaining situational awareness of an evolving landscape, which requires balancing exploration of unobserved regions with sustained monitoring of changing Regions of Interest (ROIs). Unmanned Aerial Vehicles (UAVs) have emerged as an effective response tool, particularly in applications like environmental monitoring and search-and-rescue, due to their ability to provide aerial coverage, withstand hazardous conditions, and navigate quickly and flexibly. However, efficient and adaptable multi-robot coverage with limited sensing in disaster settings and evolving time-varying information maps remains a significant challenge, necessitating better methods for UAVs to continuously adapt their trajectories in response to changes. In this paper, we propose a decentralized multi-agent coverage framework that serves as a high-level planning strategy for adaptive coverage in unknown, time-varying environments under partial observability. Each agent computes an adaptive ergodic policy, implemented via a Markov-chain transition model, that tracks a continuously updated belief over the underlying importance map. Gaussian Processes are used to perform those online belief updates. The resulting policy drives agents to spend time in ROIs proportional to their estimated importance, while preserving sufficient exploration to detect and adapt to time-varying environmental changes. Unlike existing approaches that assume known importance maps, require centralized coordination, or assume a static environment, our framework addresses the combined challenges of unknown, time-varying distributions in a more realistic decentralized and partially observable setting. We compare against alternative coverage strategies and analyze our method’s response to simulated disaster evolution, highlighting its improved adaptability and transient performance in dynamic scenarios. Keywords— Multi-agent Coverage Control, Unknown Dynamic Environments, Ergodic Theory, Gaussian Processes, Autonomous Systems 1 Introduction Figure 1: Multi-agent decentralized ergodic coverage in a time-varying environment. UAVs initially explore the environment to build situational awareness, then spend more time in regions of interest such as evolving fire fronts and dense human populations, balancing exploration and exploitation over time. Improved situational awareness in disaster response requires continuously monitoring evolving hazards and victim locations to support timely rescue decisions and effective deployment of limited resources. Search and Rescue (SAR) operations in disasters and emergencies are complex due to the highly dynamic and unstructured environments, uncertainty in sensing and communication, and the unpredictable behavior of human victims. Rapidly evolving hazards, such as fire spread, structural collapse, and smoke, exacerbate partial observability and limit human access, thereby increasing operational risk and reducing response efficiency. Unmanned Aerial Vehicles (UAVs) have emerged as a promising tool for SAR due to their ability to rapidly provide aerial coverage and real-time situational awareness (Lyu et al., 2023). These capabilities have motivated adoption of the ”Drone as a First Responder (DFR)” (Hunter et al., ) programs by emergency response agencies in the United States, including fire departments, law enforcement, and disaster response units. However, most current deployments remain human-supervised, which limits scalability and takes resources away from other efforts. Enabling decentralized autonomy is therefore essential for large-scale disaster response. Despite extensive research on multi-robot SAR, existing approaches span a wide range of assumptions, objectives, and operational settings. Many formulations emphasize centralized coordination or assume reliable communication or static task structure, while others focus on reactive exploration or information gathering. Reactive strategies are effective at quickly exploiting high-information regions; however, because they typically optimize myopic objectives, they neglect other regions that later become critical. These design choices are often misaligned with disaster-response settings. In disaster response environments, hazards evolve, victims move, and communication may be unreliable; thus, maintaining sustained situational awareness across the entire environment is essential. Effective multi-UAV systems for disaster response require decentralized multi-robot autonomy that adapts to unknown, time-varying, partially observable environments, and with communication limitations (Drew, 2021). These demands motivate principled multi-robot planning frameworks that balance exploration and information gathering under realistic operational constraints. Many search tasks can be abstracted as multi-robot coverage problems, where coverage emphasizes the space swept by the robots’ sensors over time (Choset, 2001). Unlike classical coverage that seeks complete visitation, disaster response requires persistent and adaptive monitoring as hazards and priorities evolve. Motivated by this perspective, we study SAR as a decentralized multi-agent coverage control problem under uncertainty, where environments are unknown, sensing is local and noisy, and coordination must scale with team size. Rather than prescribing fixed trajectories or centralized assignments, we seek mechanisms that regulate how agents distribute sensing effort over space and time. To this end, we leverage ergodic theory for multi-agent coverage, shaping trajectories so that long-term visitation frequencies match a target information distribution (Moore, 2015). This naturally balances the exploration of uncertain regions with the monitoring of high-priority areas. In this work, we propose a decentralized multi-robot coverage framework for unknown and partially observable environments, where the information distribution is dynamic and inferred online from local noisy measurements. We treat search as a multi-agent coverage control problem and use an ergodic planner as a high-level guidance mechanism enabling scalable decentralized execution while balancing exploration and information-driven inspection. Our main contribution is a decentralized multi-agent coverage framework that enables adaptive, distribution-aware coverage in unknown and time-varying environments under partial observability. The framework integrates online spatial inference with ergodic visitation regulation to continuously track evolving importance distributions while maintaining efficient coordination over decentralized communication networks. 2 Related Works Learning-based methods approximate coordination policies through data-driven training. In (Tzes et al., 2023), graph neural networks learn distributed active information acquisition policies by aggregating neighboring state estimates and uncertainty through message passing. This method scales to large teams but assumes known system dynamics and optimizes uncertainty reduction under a fixed parametric model. In (Pan et al., 2024) and (Mendoza et al., 2025), reinforcement learning is used to address partially observable search-and-rescue tasks. While these approaches handle local observability, they assume perfect information sharing and rely on offline training, which may limit robustness under communication constraints and diverse environment structures. Probabilistic approaches explicitly model spatial reward structure. Gaussian Process-based methods (Zhang et al., 2024) estimate unknown reward densities online, but guide agents greedily toward high-value regions, prioritizing short-horizon exploitation. Task decomposition and MPC-based formulations (Zhou et al., 2023; Eberhard et al., 2025) partition the environment or assume structured density models to optimize assignment efficiency and coverage speed. These methods often rely on prior knowledge of the density function or structured dynamics to enable rapid convergence. Bandit-feedback submodular coordination (Xu et al., 2023) provides bounded regret guarantees under partial observability, optimizing cumulative reward relative to the offline optimum. However, it assumes a known submodular utility structure and focuses on maximizing instantaneous or cumulative reward rather than explicitly shaping long-run visitation behavior. Similarly, dynamic target allocation methods (Tihanyi et al., 2023) assume prior knowledge of environmental parameters such as the number and location of targets or hazards, which may not be available in evolving disaster scenarios. Across these formulations, coordination is framed as reward maximization or assignment optimization, without directly enforcing persistent coverage over time. Discrete Markov-chain models provide alternative mechanisms for shaping long-run visitation behavior through stochastic transition design. In (George et al., 2018), transition probabilities are constructed to achieve a prescribed stationary distribution while maximizing entropy rate, promoting randomized motion under static assumptions. In contrast, (Díaz-García et al., 2023) minimizes average hitting time to specified regions of interest, emphasizing transient responsiveness while maintaining fixed stationary constraints. These approaches emphasize short-term arrival metrics but do not explicitly minimize a mismatch between frequency of visitation proportional to a desired spatial distribution. Ergodic theory, by contrast, provides a principled framework for regulating time-averaged spatial statistics of agent motion (Moore, 2015; Frigg et al., 2025). Rather than maximizing instantaneous reward, ergodic formulations seek visitation patterns whose empirical distribution matches a target spatial distribution over long horizons. By enforcing irreducibility and recurrence in the induced dynamics, ergodic objectives naturally balance exploration of low-visit regions with repeated coverage of high-importance areas. Prior work has extended ergodic control to address practical challenges in robotic exploration, including multiple and dynamic objectives (Rao et al., 2023; Mavrommati et al., 2018; Ren et al., 2023a), multi-robot coordination (Gkouletsos et al., 2021), sensor constraints (Wittemyer et al., 2025; Coffin et al., 2022; Ren et al., 2023b), energy-aware planning (Naveed et al., 2025), and continuous-space trajectory optimization (Ren et al., 2023b). Many of these ergodic control formulations operate in continuous spaces and require point-to-point trajectory optimization, which can yield highly oscillatory motion, implicitly assume reversible navigation, and rely on fine-grained sensing models (Wong et al., 2025). These factors limit their practicality in dynamic, partially observable environments with constrained motion, such as no-fly zones, obstacles, and asymmetric accessibility. Within our framework, ergodicity is used to regulate long-run spatial visitation through a discrete transition model, rather than to generate continuous control trajectories directly. In this setting, ergodic planning directs UAVs toward informative regions while maintaining long-term coverage, without requiring continuous planning of full trajectories. In this work, we incorporate the Rapidly Ergodic Markov Chain (REMC) method (Wong et al., 2025) to construct transition matrices that converge rapidly to a desired stationary distribution. REMC solves a convex optimization problem minimizing the second-largest eigenvalue magnitude subject to stochasticity and graph connectivity constraints, thereby accelerating mixing while preserving feasibility over the workspace graph. While REMC addresses spectral convergence properties of ergodic transitions, our contribution extends beyond this component by integrating ergodic visitation regulation with online belief updates, partial observability, and decentralized coordination in dynamic environments. 3 System Model Our system model is comprised of three components: a graph-based representation of the environment; a team of M unmanned aerial vehicles (UAVs), which we will refer to as agents; and an accompanying time-varying information map to model the typical evolution of disaster-response scenarios. In this section, we formalize this graph-based environment representation (Sec. 3.1), the dynamics and sensing capabilities of the agents (Sec. 3.2), and the dynamics of the underlying information map (Sec. 3.3). To denote an indicator function, we use the notation (x):→0,1|| 1_X(x):X→\0,1\^|X| defined over an ordered set =x1,…,xNX=\x_1,…,x_N\ such that the iith element i(x) 1_X^i(x) is 1 if x=xix=x_i and 0 otherwise. We define the elements of a set X in a δ-ball around o as Ball(o,δ)=x∈|‖x−o‖2≤δBall_X(o,δ)=\x \ |\ \|x-o\|_2≤δ\ 3.1 Environment We represent the environment as an undirected graph =(ℛ,ℰ)G=(R,E) with an indexed set of R regions ℛR such that rir_i and rjr_j are connected iff (ri,rj)∈ℰ(r_i,r_j) . We define the neighbors of region rir_i as (ri)=r∈ℛ|(ri,rj)∈ℰN(r_i)=\r \ |\ (r_i,r_j) \. Each region ri∈ℛr_i is assigned a non-negative, possibly time-varying weight wk(ri)≥0w_k(r_i)≥ 0 representing its relative information content or priority. The time-varying weights in each region form the information map ϕk∗∈ℝ≥0|ℛ|φ^*_k ^|R|_≥ 0 st. ‖ϕk∗‖1>0\|φ^*_k\|_1>0 which evolves over time k=0,1,…,Kk=\0,1,…,K\. The information map ϕk⋆φ _k encodes mission-level sensing priorities at time k. In a search-and-rescue scenario, higher weights wk(ri)w_k(r_i) can be specified for regions where human presence is suspected, where fire is actively spreading, or where smoke intensity is elevated, thereby requiring UAVs to allocate more time collecting critical information in those areas. These weights reflect operational priorities and guide the autonomous UAV system to concentrate sensing effort on regions of greater importance. The normalized weighting below defines the (true) target spatial distribution: ρ¯k⋆=ϕk⋆Tϕk⋆ ρ _k= φ _k1^Tφ _k (1) 3.2 UAV Agents Consider a team of M unmanned aerial vehicles (UAVs), indexed by the set ℳ≜1,…,MM \1,…,M\. Each UAV operates autonomously, collecting noisy observations about the environment within a predefined sensing range RsenseR_sense and communicating with its neighbors according to a communication radius RcommR_comm. At time step k, each UAV m occupies a single region, which we denote with xkm∈ℛx^m_k . UAVs move according to the starting position x0mx^m_0. Agents move by traversing on edges in the graph such that xk+1m∈(xkm)x_k+1^m (x_k^m). We compute the long-term time-averaged visitation statistics of each UAV over ℛR, defining their empirical visitation distribution. The empirical visitation distribution of UAV m up to time k is defined as ρ^km=1k+1∑τ=0kℛ(xτm) ρ_k^m= 1k+1Σ _τ=0^k 1_R(x^m_τ) (2) The team empirical visitation distribution is ρ^k≜1M∑m=1Mρ^km ρ_k 1M _m=1^M ρ^m_k. At each time step k, agent m receives noisy information about the weight of the regions it can sense: Ykm(xkm)≜(x,(ϕk,r⋆)r=x+εkm)|x∈Ballℛ(xkm,Rsense)Y_k^m(x^m_k) \(x,(φ _k,r)_r=x+ ^m_k)\ |\ x _R(x^m_k,R_sense)\ (3) where εkm ^m_k determines the sensor noise from each UAV’s observations at a given time step. 3.3 Dynamic Information Map The initial information map ϕ0⋆φ _0 and its evolution are exogenous and unknown to the UAVs a priori. Let ⊂1,…,KK⊂\1,…,K\ denote the (unknown) set of environment change times. The information map evolves according to ϕk⋆=ϕk−1⋆,k∉,k(ϕk−1⋆),k∈,φ _k= casesφ _k-1,&k ,\\ U_k(φ _k-1),&k , cases (4) where k:ℝ≥0n→ℝ≥0nU_k:R^n_≥ 0 ^n_≥ 0 denotes an exogenous transformation applied to the map when an environmental change occurs. 4 Problem Statement We consider a team of M UAVs tasked with autonomously exploring an unknown, dynamic environment to discover and track regions of high information content, which we refer to as the regions of interest (ROI). The objective of the UAV team is to ensure that their empirical visitation distribution aligns with the unknown true distribution over time. We measure the team’s performance using time-averaged regret: Regret(K)=1K∑k=1K[‖ρk−ρ¯k⋆‖1] Regret(K)= 1K _k=1^KE[\| _k- ρ _k\|_1] (5) This regret captures the cumulative discrepancy between the empirical visitation distribution and the target spatial distribution. We desire that the regret satisfies a sublinear bound: Regret(K)≤(Kα+), Regret(K) (K^α+V), where α<0α<0 and ≥0V≥ 0 is such that limK→∞1K∑k=1K‖ρk⋆−ρk−1⋆‖≤. _K→∞ 1K _k=1^K\| _k - _k-1 \| . The factor V captures the long-run average cumulative change in target spatial distribution. In simpler terms, we desire that the team can closely track the desired distribution as long as it does not change too drastically. 5 Approach Our framework for multi-UAV decentralized coverage in an environment with unknown and time-varying information contains the following components: (i) local information acquisition and sharing (Sec. 5.1), (i) the construction of belief map to drive exploration planning (Sec. 5.2) (i) and policy generation to match visitation frequencies to the learned belief distribution (Sec. 5.3). We summarize the algorithm in Section 5.4. 5.1 Observation and Sharing of Information At each time step k, UAV m obtains a measurement of the information value of the region at that location, Ykm(xkm)Y^m_k(x_k^m) as described in Eq. (3). UAVs communicate locally with neighboring agents within a finite communication radius RcommR_comm. We define a UAV’s communication neighborhood at timestep k as km≜l∈ℳ∖m∣‖xkm−xkl‖2≤RcommN_k^m \l \m\ \ \|x^m_k-x^l_k\|_2≤ R_comm\. Note that the communication radius RcommR_comm is assumed to be homogeneous across the team such that neighbors are symmetric l∈km⇔m∈kll ^m_k m ^l_k. At each time step, UAV m shares its most recent observations with all neighbors l∈kml ^m_k. Each UAV maintains a local dataset of observations collected up to time k, allowing duplicates, which aggregates all past measurements obtained by UAV m via its sensing or as received from neighbors: km≜k−1m∪(⋃μ∈m∪kmYkμ)D^m_k ^m_k-1∪( _μ\ ∈\ \m\\ ∪\ N^m_kY^μ_k) where −1m=∅D^m_-1= . Using the aggregated dataset kmD^m_k, each UAV constructs its local belief map ρ¯km ρ^m_k and corresponding belief information map ϕ^k,rm φ^m_k,r as described in the next section. 5.2 Building a Belief Information Map The UAVs do not have access to the true target distribution ρ¯k⋆ ρ _k for planning and are not informed of the environment change times K or the evolution kU_k. They must therefore adapt online using only local observations and shared information. As described in Sec. 5.1, at each time step, each UAV updates its observation set with directly observed noisy measurements of the true information value of the region it occupies (and within its sensing range RsenseR_sense) and its neighbors’ observations. Each agent uses this information to build its best estimate of the true spatial distribution. We refer to this estimate as the agent’s belief distribution ρ¯km ρ^m_k. These observations provide partial and noisy information about ϕk⋆φ _k, motivating the use of a probabilistic model for belief. To represent uncertainty over the information map, each UAV models this belief over region values using a Gaussian process (GP) (Rasmussen and Williams, 2006). We place a GP prior over the latent information function, ϕ0(⋅)∼(μ0(⋅),κ0(⋅,⋅)), _0(·) \! ( _0(·), _0(·,·) ), where μ0:ℛ→ℝ _0:R denotes the prior mean function and κ0:ℛ×ℛ→ℝ _0:R×R is a covariance kernel encoding spatial correlations between regions. This prior captures initial uncertainty about the information content of the environment before any observations are collected. Given the collected dataset of noisy observations kmD^m_k, each UAV computes a GP posterior at a frequency τGP _GP, characterized by a posterior mean μkm(⋅) _k^m(·) and posterior standard deviation σkm(⋅) _k^m(·). To guide exploration under this inherent uncertainty, each UAV constructs a conservative estimate of regional importance using an Upper Confidence Bound (UCB) (Srinivas et al., 2010), ϕ¯km(r)≜μkm(r)+βσkm(r), φ_k^m(r) _k^m(r)+β\, _k^m(r), (6) where β>0β>0 is a design parameter that balances exploration of uncertain regions against exploitation of regions with high estimated importance. The resulting estimate ϕ^km φ_k^m is referred to as the belief information map and is normalized to form the belief target distribution ρ¯km ρ_k^m, which is used in the next section to determine each agent’s policy. 5.3 Rapidly Ergodic Markov Chain Policy A Markov chain is said to be ergodic with respect to a target static spatial distribution ρ¯ ρ at a given time k if the empirical visitation distribution ρ^k ρ_k converges to ρ¯ ρ in expectation, i.e., limk→∞[ρ^k]=ρ⋆ _k→∞E\! [ ρ_k ]=ρ for all initial distributions. We take inspiration from ergodic search to determine a policy for each agent to track its belief target distribution. We leverage specifically the Rapidly Ergodic Markov Chain (REMC) algorithm (Wong et al., 2025), which aims to rapidly converge to ergodicity. The REMC algorithm takes in a target distribution ρ¯ ρ and allowed transitions ℰE and provides a stochastic transition matrix P∈ℝ|ℛ|×|ℛ|P ^|R|×|R| over graph G, where each state corresponds to a region ri∈ℛr_i . The entry Pj,iP_j,i denotes the probability that a UAV transitions from region rir_i to region rjr_j in one time step, i.e., Pj,i=ℙ(xk+1=rj∣xk=ri)P_j,i=P(x_k+1=r_j x_k=r_i) The transition matrix is constrained by the graph structure, such that Pj,i>0P_j,i>0 only if (ri,rj)∈ℰ(r_i,r_j) . If the graph G is strongly connected and the transition matrix P is irreducible and stochastic, then the induced Markov chain admits a unique stationary distribution ρ¯ ρ. Under repeated sampling according to P, the long-term visitation frequency converges to this stationary distribution in expectation, ensuring asymptotic ergodic coverage. We leverage REMC at a set frequency τP _P. At this frequency, each agent calls the REMC algorithm on its current target distribution ρ¯km ρ_k^m with the static edge set ℰE to receive a stochastic transition matrix PkmP_k^m. We note that our underlying true distribution ρ¯k ρ_k is time-varying. Therefore, ergodic guarantees may not necessarily hold, which is why we aim to minimize regret under reasonable assumptions of ρk⋆ρ _k. Finally, after each time step k, each UAV transitions to a neighboring region xk+1mx^m_k+1 according to this local transition policy PkmP_k^m, induced from the Markov chain described. 5.4 Algorithm We integrate the components described above into a decentralized ergodic exploration framework, summarized in Algorithm 1. The algorithm operates as an iterative learning-and-planning loop in which each UAV independently gathers information, updates its belief over the spatial distribution, and recomputes a policy based on its current belief. At initialization, each UAV m begins with a uniform belief distribution over reachable regions and constructs an initial stochastic transition policy P0mP^m_0 using the REMC algorithm. Thereafter, the system evolves over discrete time steps, combining local sensing, neighbor communication, belief updates, and policy recomputation at specific time frequencies. We assume agent synchronicity. The overall procedure is structured as follows. 1. Information gathering [lines 4-5]: Each UAV collects noisy observations of the regions within its sensing range RsenseR_sense. 2. Information sharing [lines 6-9]: Observations are exchanged with neighboring UAVs within a communication radius RcommR_comm. 3. Belief map update [lines 10-14]: Every τGP _GP steps, each UAV updates its local belief map ρ¯km ρ^m_k by fitting a Gaussian Process (Algorithm 2) to its aggregated observations, determining a conservative estimate of the information map via an Upper Confidence Bound (UCB), and finally normalizing the information map. 4. Local policy update [lines 15-19]: Every τP _P steps, each UAV recomputes its transition policy PkmP^m_k via the REMC method using the updated target distribution ρ¯km ρ^m_k. 5. Exploration [line 20]: Each UAV moves through the environment by sampling its next transition from its local policy. 6. Repeat steps 1-5 until the final time horizon TfinalT_final Algorithm 1 Decentralized Ergodic Exploration 1:Input: TfinalT_final, τGP _GP, τP _P, RcommR_comm, RsenseR_sense, x1mx^m_1 2:Initialize: ρ¯0m←1n ρ^m_0← 1n1, 0m←∅D_0^m← , P0m←REMC(ρ0¯)P^m_0 ( _0) ⊳ See (Wong et al., 2025) 3:for k=1,…,Tfinal−1k=1,…,T_final-1 do 4: Ykm←ϕk⋆(xkm)+εkmY^m_k←φ _k(x^m_k)+ ^m_k ⊳ Observe Data 5: km←k−1m∪YkmD^m_k ^m_k-1∪ Y^m_k ⊳ Append Observed Data 6: km←l∈ℳ∖m|‖xkm−xkl‖2≤RcommN^m_k←\l \m\\ |\ \|x^m_k-x^l_k\|_2≤ R_comm\ 7: for each l∈kml ^m_k do 8: km←km∪YklD^m_k ^m_k∪ Y^l_k ⊳ Append Neighbors’ Data 9: end for 10: if mod(k,τGP)=0 (k, _GP)=0 then 11: ϕ¯km,ρ¯km←UCB(km) φ_k^m, ρ^m_k _UCB(D^m_k) ⊳ Update Belief Distribution 12: else 13: ρ¯km←ρ¯k−1m ρ^m_k← ρ^m_k-1 14: end if 15: if mod(k,τP)=0 (k, _P)=0 then 16: Pkm←REMC(ρ¯km)P^m_k ( ρ^m_k) ⊳ Update Policy 17: else 18: Pkm←Pk−1mP^m_k← P^m_k-1 19: end if 20: xk+1m←x∼Pkm(⋅∣xkm)x^m_k+1← x P^m_k(· x^m_k) ⊳ Sample Next Region 21:end for Algorithm 2 GP Belief Update UCB()GP_UCB(D) 1:Input: Dataset D, Exploration parameter β 2:Compute posterior mean μ and covariance κ st. ϕ|∼GP(μ,κ)φ\ |\ D GP(μ,κ) ⊳ Fit Gaussian Process to Data 3:ϕUCB←μ+βσ _UCB←μ+β\,σ, σr=κr,r∀r∈ℛ _r= _r,r\ \ ∀ r ⊳ Conservative Estimate 4:ρ←ϕUCBTϕUCBρ← _UCB1^T _UCB ⊳ Normalize ϕUCB _UCB to Obtain ρ 5:return ϕUCB,ρ _UCB,ρ 6 Experiments Figure 2: Ground-truth information map showing regions of interest (yellow to brown) and no-fly zones (black crosses). We evaluate the proposed decentralized ergodic coverage framework in simulated disaster-response environments. The environment is discretized into a finite grid of regions, which induces a graph-based abstraction of the workspace. Figure 2 illustrates this abstraction. The left panel shows an example spatial environment overlaid with a grid, where region colors indicate underlying information weights corresponding to regions of ROIs, such as areas with high human density or active hazards, while red cells denote no-fly zones. The right panel depicts the corresponding graph-level representation used by the planner, highlighting accessible regions, ROIs, and excluded no-fly zones. No-fly zones represent regions that are inaccessible to the UAVs, meaning for any region rir_i designated as a no-fly zone, we enforce (ri,rj)∉ℰand(rj,ri)∉ℰ,∀rj∈ℛ(r_i,r_j) \ and\ (r_j,r_i) ,\ ∀ r_j such that no UAV may enter or leave these regions. All simulations were implemented in Python and executed on a laptop equipped with a 12th-generation Intel Core i7-1200H CPU (14 cores, 20 threads) and 32 GB of DDR4 RAM, running Ubuntu 22.04. We evaluate the performance of our proposed method under a range of simulation conditions, varying: • Environment design: reward map structure, number and spatial distribution of ROIs and no-fly zones, and number of regions • Team size: number of UAVs, ranging from 1 to 10; • Communication: communication radius, from local (within one grid cell) to global communication; • Environmental dynamics: rate at which the underlying information map changes over time. More details in section 6.1 In addition to time-averaged regret (Eq. 5), we evaluate the quality of the learned belief and the ℓ1 _1-error between the empirical and target distribution. We define the team belief target distribution as ρ¯k≜1M∑m=1Mρ¯km ρ_k 1M _m=1^M ρ^m_k and the mismatch between the team’s belief and the true target distribution as ℒbelief,k=‖ρ¯k−ρ¯k⋆‖1L_belief,k= ρ_k- ρ _k _1 (7) and the deviation of the empirical from the true target distribution as Ek=‖ρ^k−ρ¯k⋆‖1E_k= ρ_k- ρ _k _1 (8) 6.1 Dynamic Environment We consider two representative types of environment evolution: (i) relocation of high-information regions, emulating changes in target density such as human populations evacuating at different times; and (i) expansion of high-information regions to neighboring regions, capturing spreading phenomena such as fire, smoke, or contamination. 6.2 Policy and Belief Map Updates (a) (b) Figure 3: Performance under different policy and belief update periods (τGP=τP _GP= _P). Each subplot shows the Regretk Regret_k (Eq. 5) (top), the deviation of empirical to true target distribution (middle), and belief error ℒbelief,kL_belief,k (bottom) under varying information map change intervals. We evaluate the effect of the policy update period τP _P and the belief map update period τGP _GP on performance. Both parameters are varied jointly across different time steps. In this study, we consider a single agent operating on a 10×1010× 10 grid under multiple environment layout designs and impose different rates of environment evolution. Figure 3 presents two scenarios, each consisting of three subplots. Each row corresponds to a different environment evolution schedule K, including periodic changes at uniform time and non-uniform change intervals. For each case, we report the regret Regretk Regret_k (Eq. 5) in the top plot, the ℓ1 _1-error deviation of empirical to true target distribution (Eq. 8) in the middle plot, and the belief error ℒbelief,kL_belief,k (Eq. 7) in the bottom plot. In the scenario with periodic changes at uniform times (Fig. 3a), we observe that across update frequencies τGP,τP _GP, _P ranging from 10 to 100 steps, the update period must remain a fraction of the environment change interval to maintain lower regret and performance. When the update frequency is moderately faster than the environment evolution, the agent adapts its belief and tracks the target distribution effectively, without requiring excessive replanning. Although more frequent updates improve belief accuracy, the marginal gains diminish beyond a certain point while computational cost increases. In contrast, when the update period becomes comparable to or larger than the environment change rate, both regret and belief error increase, as the agent reacts too slowly to shifts in the underlying distribution. A similar trend is observed in Fig. 3b under non-uniform environment changes. Maintaining a policy update frequency that remains a fraction of the environment’s change interval consistently reduces all three reported error metrics. However, when the environment stabilizes for extended periods, longer update intervals do not degrade performance. This suggests the potential for an adaptive update mechanism that adjusts τGP _GP and τP _P based on detected changes in the environment. From an application perspective, this result is encouraging. The system is not overly sensitive to precise tuning of τGP _GP and τP _P, provided that the update frequency is reasonable relative to the environment dynamics. As long as the update period is smaller than the characteristic time scale of environmental change, performance remains stable. In real deployments (e.g., disaster monitoring, fire spread tracking, search-and-rescue), planners do not need to fine-tune update frequencies precisely. A moderate update rate provides a robust trade-off between computational cost and responsiveness. Update planning can be programmed with the policy and belief update frequency to be roughly 5−10×5-10× faster than an observed environment change rate. 6.3 Communication Constraints Figure 4: Map Exploration Performance under varying communication radius and team size. Top: Time to first reach a region of interest (ROI). Bottom: Time to achieve full map coverage. Columns correspond to the number of UAVs. We analyze the effect of communication constraints on decentralized multi-UAV coverage. The communication radius varies from local (one neighboring grid cell) to fully connected (global communication). For each configuration, we perform multiple simulations varying initial conditions, map layouts, and team sizes (N=3,6,10)(N=3,6,10). Figure 4 reports the time required to discover the Regions of Interest (ROIs) and the time to achieve full map coverage. Across all team sizes, reducing the communication radius does not significantly degrade ROI discovery time. In this analysis, we maintain the environment static to isolate the analysis of communication impact. For N=3N=3 UAVs, performance remains comparable across communication settings. This indicates that global communication is not strictly necessary for efficient ROI localization. As the number of agents increases, spatial redundancy decreases naturally, and even locally constrained teams can rapidly discover high-value regions. As expected, full map coverage time decreases with increasing team size. For N=3N=3, communication constraints have a more noticeable effect, since fewer agents must coordinate exploration over the entire domain. However, even under local communication, the agents successfully explore the full map within the simulation horizon. Figure 5 plots the average KL divergence between each agent’s local belief and the team-averaged belief over time for different communication radii and team sizes. For all team sizes, increasing the communication radius accelerates convergence of beliefs. However, moderate communication (Rcomms=5R_comms=5) achieves near-zero divergence rapidly, particularly for larger teams. These results indicate that limited-range communication can be sufficient to achieve rapid belief alignment without requiring full global connectivity. Figure 5: KL divergence between each UAV’s beliefs and the network mean belief over time. 6.4 Comparison with MAC-DT We compare the performance of our approach against the Multi-Agent Coverage with Doubling Trick (MAC-DT) algorithm (Zhang et al., 2024), which also addresses coverage over unknown information maps. Similar to our framework, MAC-DT uses GPs to guide exploration in unknown environments. However, the planner in MAC-DT is based on a greedy strategy, whereas our method optimizes coverage through an ergodic objective considering long-term weighted visitation. In this simulation study, we evaluate: (i) time to first reach a region of interest (ROI), (i) time to achieve full-map coverage, (i) Regret (5), and (iv) the belief error ℒbelief,kL_belief,k. Experiments are conducted in both small and medium-sized environments while varying the number of agents and environmental configurations, including the spatial distribution of ROIs, no-fly zones, and initial agent positions. For the MAC-DT approach, we report performance under two different GP update frequencies, denoted by τGP _GP. This distinction is necessary because MAC-DT exhibits sensitivity to the belief-update rate, which implicitly biases the planner toward either aggressive exploration or exploitation. We observe that more frequent GP updates tend to favor rapid full-map coverage, while less frequent updates bias the planner toward quickly identifying high-information ROIs. Figure 6: Regretk Regret_k (Eq. 5) and belief error ℒbelief,kL_belief,k performance comparison between our Decentralized Ergodic Framework and MAC-DT for a static map Across all simulations, the sensing range is limited to a single grid cell, and the environment remains static to isolate coverage performance analysis. Table 1 summarizes the full-map coverage results. Our framework successfully explores the entire environment within 3000 steps compared to MAC-DT, regardless of environment size and number of agents. Table 2 reports ROI discovery times. While MAC-DT occasionally reaches one of the ROI faster due to its greedy nature, it fails to explore other regions, leading to slower discovery of additional ROIs. In contrast, our method maintains balanced exploration and finds the ROIs much faster. Figure 6 further illustrates long-term behavior on the smaller grid over 8000 steps. Over time, our ergodic approach steadily reduces regret, reflecting balanced coverage aligned with the target distribution. In contrast, MAC-DT exhibits increasing regret, as its greedy objective encourages prolonged visitation of high-reward regions at the expense of broader exploration. While such behavior can be advantageous in static environments with fixed priorities, it becomes problematic in dynamic settings where the spatial distribution evolves, potentially causing the system to miss newly emerging regions of importance. Table 1: Full Map Exploration Performance Grid Algorithm Success Rate Timestep 5×5 Ours 100% 65.0±25.565.0± 25.5 MAC-DT (τGP=100 _GP=100) 38% 438.3±60.3438.3± 60.3 MAC-DT (τGP=50 _GP=50) 13% 153.0153.0 10×10 Ours 100% 250.1±146.6250.1± 146.6 MAC-DT (τGP=100 _GP=100) 33% 470.3±115.8470.3± 115.8 MAC-DT (τGP=50 _GP=50) 22% 1430.5±1166.01430.5± 1166.0 Table 2: Regions of Interest Discovery Timestep Grid ROI Priority Ours MAC-DT 5×5 Low 15.5±8.2815.5± 8.28 67.5±105.367.5± 105.3 (τGP=100 _GP=100) 34.0±57.834.0± 57.8 (τGP=50 _GP=50) High 34.8±20.734.8± 20.7 179.5±219.2179.5± 219.2 (τGP=100 _GP=100) 24.9±25.124.9± 25.1 (τGP=50 _GP=50) High 14.3±19.214.3± 19.2 228.0±191.8228.0± 191.8 (τGP=100 _GP=100) 53.0±40.753.0± 40.7 (τGP=50 _GP=50) 10×10 All 36.8±41.936.8± 41.9 202.9±221.8202.9± 221.8 (τGP=100 _GP=100) 186.7±416.9186.7± 416.9 (τGP=50 _GP=50) 7 Conclusion This work presents a decentralized framework for multi-robot coverage in highly adversarial environments characterized by unknown and dynamically evolving information distributions, as well as limited sensing and communication ranges. The proposed approach integrates ergodic control with online belief updates to enable adaptive, information-driven exploration. Simulation results demonstrate the effectiveness of the framework across dynamic environments with varying numbers of agents, environment sizes, and spatial ROI distributions. Compared to MAC-DT, our results show that a strategic planner based on ergodic control adapts more effectively to environmental changes. By explicitly balancing exploration and exploitation, ergodic control naturally drives agents toward regions of interest while maintaining global coverage objectives. We also show that policies can be constructed online from observations without requiring frequent updates, demonstrating robustness to policy update frequency. Furthermore, the framework operates in a decentralized manner, allowing agents to achieve mission objectives using only local information and limited communication. Overall, this work highlights the advantages of ergodic control for scalable, adaptive, and decentralized multi-robot coverage in uncertain and evolving environments. Future work includes scalability analysis and comparison to benchmarks in a time-varying environment. References H. Choset (2001) Coverage for robotics – a survey of recent results. Annals of Mathematics and Artificial Intelligence 31 (1), p. 113–126. External Links: Document, ISSN 1573-7470, Link Cited by: §1. H. Coffin, I. Abraham, G. Sartoretti, T. Dillstrom, and H. Choset (2022) Multi-agent dynamic ergodic search with low-information sensors. In 2022 International Conference on Robotics and Automation (ICRA), Vol. , p. 11480–11486. External Links: Document Cited by: §2. G. Díaz-García, F. Bullo, and J. R. Marden (2023) Distributed markov chain-based strategies for multi-agent robotic surveillance. IEEE Control Systems Letters 7, p. 2527–2532. Cited by: §2. D. S. Drew (2021) Multi-agent systems for search and rescue applications. Current Robotics Reports 2 (2), p. 189–200. External Links: Document, ISSN 2662-4087 Cited by: §1. P. B. Eberhard, J. Köhler, O. Hüsser, M. N. Zeilinger, and A. Carron (2025) Time-varying coverage control: a distributed tracker-planner mpc framework. arXiv preprint arXiv:2507.01567. Cited by: §2. R. Frigg, J. Berkovitz, and F. Kronz (2025) The Ergodic Hierarchy. In The Stanford Encyclopedia of Philosophy, E. N. Zalta and U. Nodelman (Eds.), Note: https://plato.stanford.edu/archives/win2025/entries/ergodic-hierarchy/ Cited by: §2. M. George, S. Jafarpour, and F. Bullo (2018) Markov chains with maximum entropy for robotic surveillance. IEEE Transactions on Automatic Control 64 (4), p. 1566–1580. Cited by: §2. D. Gkouletsos, A. Iannelli, M. Hudoba de Badyn, and J. Lygeros (2021) Decentralized trajectory optimization for multi-agent ergodic exploration. IEEE Robotics and Automation Letters 6 (4), p. 6329–6336. External Links: Document Cited by: §2. [9] M. C. Hunter, C. (. Quach, and K. Smalling First responder uas use in post-disaster environments. In AIAA AVIATION FORUM AND ASCEND 2025, p. . External Links: Document, Link, https://arc.aiaa.org/doi/pdf/10.2514/6.2025-3355 Cited by: §1. M. Lyu, Y. Zhao, C. Huang, and H. Huang (2023) Unmanned aerial vehicles for search and rescue: a survey. Remote Sensing 15 (13). External Links: Link, ISSN 2072-4292, Document Cited by: §1. A. Mavrommati, E. Tzorakoleftherakis, I. Abraham, and T. D. Murphey (2018) Real-time area coverage and target localization using receding-horizon ergodic exploration. IEEE Transactions on Robotics 34 (1), p. 62–80. External Links: Document Cited by: §2. M. G. Mendoza, A. Kalanther, D. Bostwick, E. Stephan, C. Maheshwari, and S. Sastry (2025) Coordinated autonomous drones for human-centered fire evacuation in partially observable urban environments. In 2025 IEEE Global Humanitarian Technology Conference (GHTC), Vol. , p. 01–08. External Links: Document Cited by: §2. C. C. Moore (2015) Ergodic theorem, ergodic theory, and statistical mechanics. Proceedings of the National Academy of Sciences 112 (7), p. 1907–1911. External Links: Document, Link, https://w.pnas.org/doi/pdf/10.1073/pnas.1421798112 Cited by: §1, §2. K. B. Naveed, D. R. Agrawal, R. Kumar, and D. Panagou (2025) Adaptive ergodic search with energy-aware scheduling for persistent multi-robot missions. Autonomous Robots 49 (4), p. 27 (en). External Links: ISSN 1573-7527, Link, Document Cited by: §2. H. Pan, X. Duan, W. Yu, and J. He (2024) A deep reinforcement learning approach to multi-agent search and rescue in unknown environments. In Proceedings of 2023 7th Chinese Conference on Swarm Intelligence and Cooperative Control, J. Yu, Y. Liu, and Q. Li (Eds.), Singapore, p. 102–112. External Links: ISBN 978-981-97-3332-3 Cited by: §2. A. Rao, A. Breitfeld, A. Candela, B. Jensen, D. Wettergreen, and H. Choset (2023) Multi-objective ergodic search for dynamic information maps. In 2023 IEEE International Conference on Robotics and Automation (ICRA), p. 4560–4566. External Links: Document Cited by: §2. C. E. Rasmussen and C. K. I. Williams (2006) Gaussian processes for machine learning. MIT Press, Cambridge, MA. External Links: ISBN 9780262182539, Link Cited by: §5.2. Z. Ren, A. K. Srinivasan, B. Vundurthy, I. Abraham, and H. Choset (2023a) A pareto-optimal local optimization framework for multiobjective ergodic search. IEEE Transactions on Robotics 39 (5), p. 3452–3463. Cited by: §2. Z. Ren, A. K. Srinivasan, B. Vundurthy, I. Abraham, and H. Choset (2023b) A pareto-optimal local optimization framework for multiobjective ergodic search. IEEE Transactions on Robotics 39 (5), p. 3452–3463. External Links: Document Cited by: §2. N. Srinivas, A. Krause, S. Kakade, and M. Seeger (2010) Gaussian process optimization in the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML’10, Madison, WI, USA, p. 1015–1022. External Links: ISBN 9781605589077 Cited by: §5.2. D. Tihanyi, Y. Lu, O. Karaca, and M. Kamgarpour (2023) Multi-robot task allocation for safe planning against stochastic hazard dynamics. In 2023 European Control Conference (ECC), p. 1–6. Cited by: §2. M. Tzes, N. Bousias, E. Chatzipantazis, and G. J. Pappas (2023) Graph neural networks for multi-robot active information acquisition. In 2023 IEEE International Conference on Robotics and Automation (ICRA), Vol. , p. 3497–3503. External Links: Document Cited by: §2. E. Wittemyer, A. Rao, I. Abraham, and H. Choset (2025) Multi-agent ergodic exploration under smoke-based time-varying sensor visibility constraints. In 2025 IEEE International Conference on Robotics and Automation (ICRA), Vol. , p. 5452–5458. External Links: Document Cited by: §2. B. Wong, R. H. Lee, T. M. Paine, S. Devasia, and A. G. Banerjee (2025) Rapidly converging time-discounted ergodicity on graphs for active inspection of confined spaces. arXiv preprint arXiv:2503.10853. Cited by: §2, §2, §5.3, 2. Z. Xu, X. Lin, and V. Tzoumas (2023) Bandit submodular maximization for multi-robot coordination in unpredictable and partially observable environments. arXiv preprint arXiv:2305.12795. External Links: Link Cited by: §2. R. Zhang, H. Ma, and N. Li (2024) Multi-agent coverage control with transient behavior consideration. In Conference on Learning for Dynamics & Control, External Links: Link Cited by: §2, §6.4. B. Zhou, H. Xu, and S. Shen (2023) Racer: rapid collaborative exploration with a decentralized multi-uav system. IEEE Transactions on Robotics 39 (3), p. 1816–1835. Cited by: §2.