Dynamic multi-robot coverage framework via A*-optimized region patrolling and localized re-planning

Abstract

Efficient multi-robot coverage in dynamic environments remains a critical challenge for applications such as warehouse automation, environmental monitoring, inspection in large spaces, SAR, other innovative applications in Industrial Inspections. Traditional methods, such as spanning tree coverage and area-region-based partitioning, as well as market-based approaches such as divide area-based region partition (DARP), are effective under static conditions but suffer from rigidity in handling dynamic obstacles and poor adaptability to real-time changes. This paper introduces a hybrid framework, Robust DARP and A*, which integrates dynamic, region-based partitioning algorithm (DARP) with A* path planning from point-to-point navigation to coverage, with region constraints that enable complete and efficient coverage and path planning in non-stationary environments. Key innovations include: Localized region repair mechanism; a three-tier repair hierarchy (local–regional–global); incremental region repair instead of complete recomputation to minimize computational overhead during dynamic obstacle insertion; workload-balanced partitioning strategy that ensures equitable task allocation; and a turn-minimizing path planner that enhances energy efficiency. Fair task distribution among multiple robots without centralized coordination, extensive simulation trials across diverse terrains and scales (2 to 20 robots) demonstrates that our method achieves: coverage $\ge$ 97.3% under significant dynamic obstacles. Near-optimal path efficiency (max/min ratio $\le 1.15$ ), and sub-second runtime for large teams. This work presents a robust, scalable solution that provides an algorithmic foundation for real-world autonomous deployment. Evaluation is performed entirely in simulation using Python and Pygame environments; future work will extend the framework to support robots with varying capabilities for real-world deployment and optimization.

Introduction

The problem of complete coverage path planning (CPP) for multi-robot systems (MRSs) has emerged as a fundamental challenge in autonomous robotics, with critical applications ranging from precision agriculture to disaster response, with broad applications including environmental monitoring, surveillance, agriculture, and autonomous cleaning. While single-robot coverage solutions have been extensively studied, ¹ real-world applications demand coordinated approaches that can:

Efficiently partition workspaces

Optimize individual robot paths

Dynamically adapt to environmental changes

CPP focuses on designing paths that enable robots to systematically visit all accessible areas, aiming to maximize coverage with minimal overlap and resource use. Traditional single-robot algorithms, while foundational, often fail to scale effectively as environments expand and as demands for time efficiency and fault tolerance increase. Thus, deploying multiple cooperative robots is essential to improve coverage speed and robustness.

Traditional approaches such as spanning tree coverage (STC) ² guarantee completeness but enforce rigid motion patterns that prove inefficient in cluttered environments. Similarly, while decomposition and allocation of regions for partition-based coverage (divide area-based region partition (DARP)) ³ provides effective workload balancing, it assumes static environments.

A fundamental problem in multi-robot coverage is decomposing the environment into equitable and connected partitions, which facilitates parallel area exploration while avoiding inter-robot conflicts and collisions. The decomposition and allocation of regions for partition-based coverage (DARP) methodology is a prominent approach that partitions the workspace into connected regions assigned to individual robots.^3,4 When coupled with STC algorithms, each robot can systematically traverse its assigned region, guaranteeing complete coverage with low redundancy and bounded turning costs. ²

However, coverage in real-world environments is compounded by the presence of dynamic obstacles and changes in terrain, which necessitate adaptive, online algorithms capable of fast re-planning and robust operation without global recomputation. Moreover, minimizing the complexity of the path, such as the number of turns and revisits, has a critical impact on the energy consumption and operational efficiency of robots.^5,6 Our research addresses these limitations through three key innovations.

Dynamic Region Partitioning: Extending DARP’s flood-fill approach with localized repair mechanisms that maintain region connectivity during dynamic obstacle avoidance

A*-Optimized Coverage Paths: Replacing STC’s spanning tree traversal with heuristic search between systematically ordered cells

Real-Time Obstacle Reactivity: Achieving sub-0.1s replanning through combined global decomposition and local path repairs

In this context, the present research offers an optimized DARP-based multi-robot coverage framework that integrates dynamic obstacle handling and obstacle-aware path planning via A*, ensuring robust coverage with minimal turns and overlaps. This paper also presents extensive benchmarking and advanced visualization for performance assessment and interpretability. Our method addresses several notable gaps in the existing literature, including the limited handling of dynamic obstacles in DARP frameworks, the insufficient use of path-smoothing methods in multi-agent coverage, and the lack of scalable benchmarking across varied scenarios.

The primary innovation of this work is a modular hybrid framework that combines DARP-based dynamic region partitioning and replanning for multi-robot coverage in the presence of dynamic obstacles. Unlike prior DARP variants, most DARP-based coverage approaches assume static environments; the approach enables localized, real-time region repair and obstacle-reactive paths without full global re-computation, significantly improving scalability and responsiveness in non-stationary environments. Unlike distributed region repair methods, ⁷ which require explicit message passing among agents, our framework enables localized partition repair via a central planner, allowing adjustments. Furthermore, unlike online repartitioning approaches ⁸ that can trigger global recomputation, our method modifies only the regions directly affected, minimizing computational overhead and global disruption.

Thus, the main contribution of this work is a hybrid framework that uniquely combines DARP-based partitioning with A* path planning through a localized repair mechanism. This mechanism enables real-time adaptation to dynamic obstacles by recomputing only the affected regions and paths, avoiding the computational overhead of global re-planning.

While current validation is simulation-based—assuming perfect localization and obstacle detection for algorithmic focus—the framework’s localized repair mechanism and grid-independent partitioning are explicitly modular to accommodate real-world sensor noise and execution uncertainty.

The remainder of this paper is organized as follows: Section “Related work” reviews related work; Section “Problem formulation and environment description and modeling” provides the details of the proposed approach DARP-A* framework; Sections “Methodology and algorithm working” to “Scalability and performance” describe the methodology and implementation of algorithm working; Section “Computational complexity analysis” provides simulation and result discussion; Sections “Discussion and limitations” and “Conclusions” discuss the complexity, conclusion, and future direction with limitation.

Related work

In recent years, CPP has become a cornerstone of autonomous robotics, particularly for operations that require complete spatial coverage—ranging from agricultural field mapping and industrial floor cleaning to warehouse logistics and post-disaster search-and-rescue missions.^1,9

Foundations of CPP: The theoretical foundations were established by Choset, ¹ who formalized completeness guarantees for single-robot systems. Early work focused on decomposition strategies such as boustrophedon cells ¹⁰ and turn-optimized tours. ⁴

The fundamental goal of CPP is to generate an efficient, obstacle-free path that enables a robot to visit every accessible part of a designated area while minimizing redundancy, execution time, and energy usage. Early CPP research focused on single-agent strategies, utilizing techniques such as cellular decomposition, Voronoi partitioning, and graph traversal. The STC algorithm, as described by Gabriely and Rimon, ² was a notable advancement that provided a structured, non-redundant path over grid-based terrain using a spanning tree representation. However, these single-agent methods become impractical for large or time-sensitive missions due to their inherent scalability limitations.

Thus, the transition to MRSs has gained momentum. These systems promise parallelism and fault tolerance but demand more sophisticated coordination mechanisms. Early attempts to implement MRS for CPP often led to inefficiencies, such as overlapping paths or bottlenecks, due to simplistic task distribution. ¹¹ The evolution from single to multi-robot coverage introduced new technical challenges in task allocation ¹² and collision avoidance. ¹³

Structured area allocation: The DARP contribution to effective workspace partitioning is critical for multi-robot coverage. A breakthrough came with the DARP (divide areas for robotic planning) algorithm,^3,14 which formalized area partitioning among multiple robots based on their starting locations. DARP introduced the flood-fill approach for equitable region allocation. By iteratively balancing the number of assigned grid cells and ensuring area connectivity, DARP enabled robots to perform coverage with reduced overlap and better load balancing.

Subsequent efforts have expanded DARP’s capabilities. Gao et al. ¹⁵ introduced ideal-shaped spanning trees for subregion traversal, improving energy efficiency. In rugged terrains, Idir and Renzaglia ¹⁶ modified DARP to include terrain weights, although at the cost of slower convergence. Huang et al. ¹⁷ addressed outdoor environments by incorporating land-type-aware partitioning through quadtree structures, thereby adapting robot behavior based on terrain classification. Furthermore, online re-partitioning methods have been developed. ⁸ However, a key limitation persists: most DARP-based systems assume static maps and pre-configured plans, making them fragile in dynamic settings. When conditions change—such as a new obstacle appearing or a robot failing—manual intervention or complete global re-planning is often required. Benchmarking against static coverage baselines, we compare our approach with canonical static-coverage algorithms, which represent common alternatives. Multi-robot forest coverage (MFC) ¹³ extends spanning-tree methods to multiple robots; however, it uses naive area splitting, which can lead to unbalanced workloads. Multi-robot STC (minimum STC (MSTC)) ⁶ optimizes for a global minimum spanning tree before partitioning, often yielding shorter paths but at the cost of higher computational complexity and rigidity. Crucially, both MFC and MSTC, such as standard DARP + STC, are designed for static environments and lack mechanisms for dynamic obstacle response, requiring complete global replanning when changes occur—a key limitation our framework addresses.

Challenges in real-world dynamic setting: Unlike simulation settings, real-world environments are dynamic and unpredictable. Moving obstacles, signal latency, and sensor uncertainty all affect robot performance. Classical DARP or STC frameworks do not inherently support online adaptability. Reactive approaches, such as the dynamic window approach and velocity obstacles, ¹⁸ have been used for local collision avoidance but are insufficient for achieving global coverage objectives.

While modern alternatives, such as deep reinforcement learning (DRL), have shown potential in handling dynamic multi-agent environments, ¹⁹ they require significant training time and tend to generalize poorly across different scenarios. Furthermore, DRL models are often sensitive to sparse rewards and have high computational overhead. Recent advances focus on scalability and dynamic adaptability, ²⁰ but few unify partitioning, path planning, and obstacle handling. Also, while D* Lite ²¹ enables efficient re-planning, ²² most MRSs rely on global recomputation. Localized repair ⁷ and reinforcement learning ²³ are promising but computationally expensive. Other methods, such as A*-enhanced navigation or turn-optimized planning, ²⁴ also struggle with integrated dynamic response.

Prioritizing multi-objective tradeoffs: A significant shortcoming of many CPP approaches is the focus on a single optimization criterion, usually coverage completeness or minimal path length. However, real missions often involve multiple objectives: minimizing energy consumption, reducing communication overhead, and balancing task duration.

A significant shortcoming of many CPP approaches is the focus on a single optimization criterion, usually coverage completeness or minimal path length. However, real missions often involve multiple objectives: minimizing energy consumption, reducing communication overhead, and balancing task duration.^25,26 This survey reveals a clear gap in the existing approaches. In summary, while the foundational work in STC and DARP provides solutions for static, structured coverage, modern DRL or reactive approaches handle local dynamics, leaving a significant gap. There is a lack of a unified framework that combines load-balanced partitioning, globally optimized coverage paths, and lightweight localized adaptation to dynamic obstacles.

Bridging simulation and real-world execution: Another important consideration is the gap between algorithmic design and real-world implementation. Although simulation results are valuable for validating logic, they often fail to capture the challenges posed by sensor noise, hardware constraints, and environmental variability. Most CPP frameworks, including DARP variants, are validated only in static, virtual environments. To facilitate a future transition from simulation to real-world execution, the proposed hybrid DARP with A* is designed with modularity in mind. Our method computes lexicographically sorted coverage cells, effectively handling static and dynamic obstacles without resorting to full global re-planning. This offers a hybrid approach between proactive and reactive planning that could be integrated with a real-world robot’s local planner. Additionally, scalability in MRSs remains a pressing concern. mainly in static and rigid decomposition, inflexible coverage paths, heuristic-blind and global recomputation overhead re-planning.

Although the literature presents a diverse range of methods—from modular partitioning (DARP) to efficient traversal and adaptive planning (terrain-based or DRL-based), few integrate these components into a cohesive, dynamic, and scalable system. The proposed hybrid framework bridges these gaps by integrating DARP for initial load-balanced partitioning, A* for obstacle-aware path optimization, and dynamic region repair that updates only affected areas, also offering real-time adaptability, multi-objective tuning, and decentralized coordination within a unified coverage strategy.

A detailed examination of the relevant literature reveals opportunities for further contributions to maximize the capabilities of MRSs without compromising key aspects of existing solutions. In response to this need, this study suggests a hybrid A*-DARP framework for complete coverage while dynamically avoiding obstacles for multi-agent path formation within familiar terrains. The following stages define the specific paths within their assigned regions in a decentralized manner. The proposed algorithm is a computationally efficient approximation method for the multi-robot CPP (mCPP) problem.

Problem formulation and environment description and modeling

Path planning objective function: In a warehouse or industrial system with multiple autonomous robots, area coverage is achieved by having numerous robots navigate to cover a desired area, such as a warehouse, an agricultural plantation, or a search and rescue (SAR) mission, for critical tasks. The agents need to navigate back to the designated charging station to replenish their cell energy when it becomes insufficient. At this point, two key factors need to be considered: first, whether the remaining power will be sufficient for the robot to reach the charging point; second, whether abandoning ongoing tasks is necessary and what tradeoffs are involved for urgent tasks. Thus, careful consideration of the autonomous mobile robot’s (AMR’s) remaining power needs to encompass various complex scenarios. When planning paths for extended distances, it is crucial to ensure that the AMR can navigate back to its charging station while avoiding blockades at remote target points. At the present moment, the cost function distance can be calculated using Manhattan distance or Euclidean distance, as shown in Figures 1 and 2(b). In the context of coverage route planning, the primary objective is to arrange the area of interest and select an appropriate approach that aligns with the robot’s abilities. Typically, the vision camera & sensor, and the footprint of a robot are in the shape of a trapezium. For simplicity, we assume that the robot’s speed and altitude relative to ground level are stable, and that the robot’s projected ot’s position is in the middle. A square-shaped section with sides measuring $\ell$ . To facilitate comprehension, the entire operational area ( $A_i$ ), inclusive of obstacles ( $O_i$ ), is partitioned into equally sized cells according to the discretization parameter $\ell$ . In addition, it is assumed that the area of interest is a rectangular region in the x,y coordinate system. The entire area that needs to be covered can be achieved as follows.

Figure 1.

Core execution hybrid flowchart.

Figure 2.

(a) Illustrative diagram of grid procedure and (b) path generated by different distance functions.

Mathematical modeling of robust multi-robot coverage planning

Environment modeling: The method involves considering a grid world, dividing the map area into grids, with every single grid representing the data for its specific location. The modeling process proceeds as follows ²⁷ :

Dividing the entire area into a grid of grids.

Associating each discrete spatial unit with its corresponding position in the real-world environment.

Characterize the traversability status of each grid element to differentiate between accessible and inaccessible areas.

The coverage planning system optimizes the trajectories of $k$ robots in a grid environment $\mathcal{G}$ with static and dynamic obstacles. The core components are:

• Environment representation and initialization

• DARP-based region partitioning

• A*-optimized path planning

• Dynamic obstacle handling

• Performance benchmarking

We represent the environment as a 2D given below:

$$\begin{array}{rl}\mathcal{G}& =\{(i,j)\mid 0\le i<n_x,0\le j<n_y\}\\ s_{ij}& =\{\begin{array}{cc}0& \text{free cell}\\ 1& \text{static obstacle}\\ 2& \text{dynamic obstacle}\end{array}\\ {\mathcal{C}}_{ij}& \in \{-1,0,1,\dots ,k-1\}\text{( robot ownership) }\\ {\mathcal{V}}_{ij}& \in \{0,1\}\text{( coverage status) }\end{array}$$

The coverage state is represented by: ${\mathcal{C}}_{ij}\in -1,0,1,\dots ,k-1$ : Robot ownership ( $-1$  = unassigned) ${\mathcal{V}}_{ij}\in 0,1$ : coverage status (1 = visited).

CPP for single robot

To address the mCPP issue, we can initiate coverage of the designated area using a solitary robot. As indicated by the previous analysis, the problem of path planning for a single robot to cover the area can be reformulated as finding the shortest fully coverage path ${\mathcal{P}}_i$ with the minimum turns.

$$min\Vert {\mathcal{P}}_i\Vert \text{s.t.}{\mathcal{P}}_i\supseteq U$$

where $\Vert {\mathcal{P}}_i\Vert$ represent the path length of ${\mathcal{P}}_i$ .

CPP for multi-robot

Like the one-robot CPP dilemma, the mCPP quandary involves determining the shortest path lengths.

$$min\underset{1\le i\le N}{max}\Vert {\mathcal{P}}_i\Vert \text{s.t.}\bigcup _{i=1}^N{\mathcal{P}}_i=U$$

where $\Vert {\mathcal{P}}_i\Vert$ denotes the length of path ${\mathcal{P}}_i$ .

DARP partitioning algorithm

The decomposition and allocation of regions for partitioning (DARP) algorithm partitions $\mathcal{G}$ into $k$ connected regions $\mathcal{R}0,\dots ,\mathcal{R}k-1$ for $k$ robots.

Mathematical formulation:

Input: Robot positions $\mathcal{P}=\mathbf{p}0,\dots ,\mathbf{p}k-1$ where ${\mathbf{p}}_i$ represents the position of the $i^{th}$ robot.

Output: Cover map $\mathcal{C}$ where $\mathcal{C}(\mathbf{c})=i$ if $\mathbf{c}\in {\mathcal{R}}_i$ . The robot covers a map is $\mathcal{C}$ , which is a mapping that assigns each cell $\mathbf{c}$ in the grid environment to a specific region ${\mathcal{R}}_i$ . The notation $\mathcal{C}(\mathbf{c})=i$ indicates that the cell $\mathbf{c}$ belongs to the region ${\mathcal{R}}_i$ .

Properties:

Connectivity: ${\mathcal{R}}_i$ remains 4-connected. Any two cells in the region ${\mathcal{R}}_i$ are connected by a path that only traverses cells within the region.

Balanced: $\Vert {\mathcal{R}}_i|-|{\mathcal{R}}_j\Vert \le 1\mathrm{\forall }i,j$ . The difference in the number of cells between two regions ${\mathcal{R}}_i$ and ${\mathcal{R}}_j$ is at most 1. This ensures that the workload is distributed fairly among the robots.

Complete: $\bigcup _{i=0}^{k-1}{\mathcal{R}}_i=\mathcal{F}$ . Here $\mathcal{F}$ represents the free space, a set of all free cells that the robots can move through or visit in $\mathcal{G}$ .

Methodology and algorithm working

The overall workflow of the hybrid DARP-A* framework is shown in Figure 1. The system operates in two primary modes: an initial planning mode (partitioning and path generation) and an execution monitoring mode. The core decision loop during execution continuously checks: (1) Has a dynamic obstacle been detected? If yes, the localized repair mechanism is triggered. (2) Else, the robot’s assigned region has been fully covered? If yes, the robot idles or returns. This loop continues until the entire area is covered. The following subsections detail each component of this workflow

A* path planning & cost function

For each robot $i$ , generate the coverage path ${\mathcal{P}}_i$ through all $\mathbf{c}\in {\mathcal{R}}_i$ using A* search.

$$f(\mathbf{c})=g(\mathbf{c})+h(\mathbf{c})$$

(1)

where $g(\mathbf{c})$ is the actual cost from start and $h(\mathbf{c})$ is the Manhattan distance heuristic.

Definition 1. The distance between two cells can be calculated as ( $x_{i1},y_{i1}$ ) & ( $x_{j1},y_{j1}$ )

$${\mathbf{D}}_{ij}=\Vert {\mathbf{x}}_{i1}-{\mathbf{x}}_{j1}\Vert +\Vert {\mathbf{y}}_{i1}-{\mathbf{y}}_{j1}\Vert$$

(2)

$${\mathbf{d}}_{ij}=\sqrt{({\mathbf{x}}_{i1}-{\mathbf{x}}_{j1}{)}^2+({\mathbf{y}}_{i1}-{\mathbf{y}}_{j1}{)}^2}$$

(3)

If two cells satisfy the condition $D_{ij}\le$ l, called adjacent; therefore, the robot can seamlessly traverse from one cell to another at each time step as shown in Figure 2. The two cells will be in line if $D_{ij}=d_{ij}$ , otherwise a minimum of one turn is required to travel between any two cells.

The heuristic function $h(\mathbf{c})$ can be calculated using the following equation:

$$h(\mathbf{c},{\mathbf{c}}_{\text{goal}})=|c_x-c_{{\text{goal}}_x}|+|c_y-c_{{\text{goal}}_y}|$$

(4)

Path construction

On moving the robot for coverage ${\mathcal{P}}_i$ denotes the ordered sequence of waypoints of grid cells that Robot $R_i$ must traverse to cover its assigned region while avoiding obstacles. The order of cells in ${\mathcal{P}}_i$ is determined by the coverage planning and incorporates obstacle constraints from the environment map. It has to visit all cells in ${\mathcal{R}}_i$ exactly once (full coverage) while minimizing redundant travel.

Initially, the algorithm sorts region cells lexicographically:

$${\mathcal{S}}_i={\text{sort}}_{(x,y)}({\mathcal{R}}_i)$$

(5)

After sorting the region, with equation (5), connect sequential waypoints to plan all paths, which generates the complete coverage path for each robot

$${\mathcal{P}}_i=[{\mathbf{p}}_i^{\text{start}}]\oplus \underset{j=1}{\overset{m}{⨁}}\text{A* }({\mathbf{c}}_{j-1},{\mathbf{c}}_j)[1:]$$

(6)

where $\oplus$ denotes path concatenation, and $[1:]$ removes the duplicated start point. The A* algorithm uses equation (1), the Manhattan distance as a heuristic $h(\mathbf{c})$ calculated from (4), and searches only within the assigned region ${\mathcal{R}}_i$ . In that region, a mobile robot finds the nearest free position to the blocked cell using the following equation:

$${\mathbf{p}}_f=\underset{\mathbf{p}\in \mathcal{N}*({\mathbf{p}}_b)}{\text{argmin}}\Vert \mathbf{p}-{\mathbf{p}}_b{\Vert }_1$$

(7)

where $\mathcal{N}*(\mathbf{p})$ is the connected free component of $\mathbf{p}$ and ${\mathbf{p}}_f$ is typically the final (or found) position chosen from the set of $\mathcal{N}*(\mathbf{p})$ , ${\mathbf{p}}_b$ is the base or starting position of the robot in a grid environment. And finally, the robot covers the path by performing a constrained A* search within region ${\mathcal{R}}_i$ : a node of ( $\mathbf{s}$ , $\mathbf{g}$ , ${\mathcal{R}}_i$ )

• $\mathbf{c}\in {\mathcal{R}}_i$ .

• If $s(\mathbf{c})=0$ (traversable cell).

• Priority queue keyed by equation (1)

This approach utilizes the coordinate grid system, also known as a grid map, to model the environment and navigation of the AMR. The advantage of the grid-based representation lies in significantly reducing the complexity involved in abstracting intricate environments. And while finding the path between two points. In contrast, a draw bias is that it significantly reduces the complexity of being challenging. If it is too tiny, it will enhance the intricacy of successive search algorithms and consume substantial memory resources. On the other hand, if it is too large, there is a risk that it may not accurately represent the real environment and could result in a collision during AMR planning. Therefore, when utilizing grid modeling for path planning environments, careful consideration must be given to balancing actual environmental conditions with the requirements of the search algorithm in selecting division standards.

Dynamic obstacle handling

When moving and planning a path during area coverage, a dynamic obstacle ${\mathbf{o}}_d$ appears; the environment can then be updated accordingly. Update grid: $s({\mathbf{o}}_d)\leftarrow 2$ .

After updating the coverage, it recomputes the regions and replans the path using the following approach: recompute regions: ${\mathcal{R}}_i^{\prime }=\text{DARP}({\mathcal{G}}^{\prime })$ ; replan paths: ${\mathcal{P}}_i^{\prime }=\text{plan\_all\_paths}({\mathcal{R}}_i^{\prime })$

$$\begin{array}{rl}{\mathbf{o}}_d& \sim \mathcal{U}(\{\mathbf{c}\in \mathcal{G}\mid s(\mathbf{c})=0\wedge \mathcal{V}(\mathbf{c})=0\}\mathrm{\setminus }\bigcup _i{\mathcal{P}}_i)\\ s({\mathbf{o}}_d)& \leftarrow 2\\ {\mathcal{R}}_i^{\prime }& =\text{DARP}({\mathcal{G}}^{\prime },\mathcal{P})\text{( Local repair) }\\ {\mathcal{P}}_i^{\prime }& =\text{A* }({\mathcal{R}}_i^{\prime })\end{array}$$

Here ${\mathcal{P}}_i^{\prime }$ denotes the updated path set, and ${\mathcal{R}}_i^{\prime }$ is the updated region assignment. Using the local repair strategy, only affected regions are modified and maintains $\sum |{\mathcal{R}}_i^{\prime }|=\sum |{\mathcal{R}}_i|-1$ .

Turn count and minimization

Turn count ${\tau }_i$ for path ${\mathcal{P}}_i=[{\mathbf{c}}_0,{\mathbf{c}}_1,\dots ,{\mathbf{c}}_n]$ : can calculate for checking energy-efficient paths:

$$\mathrm{\Delta }{\mathbf{d}}_t=(\mathrm{\Delta }{x}_t,\mathrm{\Delta }{y}_t)={\mathbf{c}}_t-{\mathbf{c}}_{t-1}$$

(8)

where ${\mathbf{c}}_{\mathbf{t}}$ is the grid cell position at time step in ${\mathbf{p}}_{\mathbf{i}}$ and $\mathrm{\Delta }{\mathbf{d}}_t=(\mathrm{\Delta }{x}_t,\mathrm{\Delta }{y}_t)$ is the displacement vector at step $t$ . When a robot moves from one coordinate to another $\mathrm{\Delta }{\mathbf{d}}_t$

$${\tau }_i=\sum _{t=2}^{n-1}[1-\delta (\frac{\mathrm{\Delta }{\mathbf{d}}_t}{\Vert \mathrm{\Delta }{\mathbf{d}}_t{\Vert }_2},\frac{\mathrm{\Delta }{\mathbf{d}}_{t-1}}{\Vert \mathrm{\Delta }{\mathbf{d}}_{t-1}{\Vert }_2})]$$

(9)

Parameter performance metrics

Table 1 outlines the key parameters used to evaluate the performance of the approach, including coverage ratio, path length, turn count, load balance, and runtime. The formal definitions of each metric are given with significance.

DARP working process

The DARP approach for optimal multi-robot area covering route planning is customized to tackle the challenge of mCPP, wherein a flock of moving robots is assigned to cover an allocated area that includes predetermined obstacles effectively.

Table 1.

Performance evaluation metrics.

Metric	Expression	Significance
Coverage ratio	$\rho =\frac{|\{\mathbf{c}\mid \mathcal{V}(\mathbf{c})=1\}|}{|\mathcal{F}|}$	Completeness
Path length	$L=\sum _i|{\mathcal{P}}_i|$	Energy efficiency
Turn count	${\tau }_{\mathrm{total}}=\sum _i{\tau }_i$	Motion efficiency
Load balance	$\beta =\frac{\underset{i}{max}|{\mathcal{P}}_i|}{\underset{i}{min}|{\mathcal{P}}_i|}$	Work distribution
Runtime	$t_{\mathrm{exec}}$	Computational efficiency

At the algorithm’s initiation, the terrain is systematically partitioned into equal areas, each of which is specifically assigned to an individual robot. This allocation ensures that each robot has a distinct territory to cover. A key emphasis of DARP lies in delivering a non-backtracking solution, meaning that robots avoid revisiting areas that have already been covered. This feature is pivotal for optimizing the overall coverage process. DARP’s objective is to find the shortest coverage path for each robot in its assigned area, thereby improving coverage efficiency. One of DARP’s distinctive features is its ability to quickly adapt to the environment without needing an extensive setup stage. The algorithm’s optimization technique involves iteratively updating each robot’s area in a cyclic manner. While each robot individually improves its path for coverage, the coordinated effort achieves the overall goals of multi-robot coverage. This collaborative coordination ensures that all robots, working together and in balance, effectively cover the entire area.

DARP with dynamic area partitioning

After the desired division of area is achieved, robots move and cover their partitioned allocated area if any dynamic obstacle appears in the path we used the hybrid DARP and obstacle-aware A* with dynamic obstacle avoidance that follows the principle of the (STC) algorithm to produce the optimal route for each robot to achieve the integrated approach DARP and A* locally re-partition affected regions and re-plan the path by equation (6) asa method given in Section “Dynamic obstacle handling” using ${\mathcal{P}}_i^{\prime }$ = $\text{A* }({\mathcal{R}}_i^{\prime })$ full coverage of the required area of interest. Hybrid DARP-A* achieves better complexity with $O(d^2)$ in typical scenarios for $n$ cells, discussed in detail in Section “Discussion and limitations” of complexity analysis, making it suitable for real-time applications with dynamic grids (Figures 3 to 5).

STC adopted approach

STC is a structured path-planning approach in which a robot systematically traverses a coverage area by following a spanning tree constructed over a discretized grid. Each cell in the grid corresponds to a specific unit of the environment, and the robot ensures that each unit is visited exactly once, minimizing overlaps and redundancy.

Figure 3.

Robot trajectory generating multiple turns.

Figure 4.

Divide area-based region partition (DARP) algorithm flowchart divide areas based on robots’ initial positions. ¹⁴

Figure 5.

Path planning by spanning tree coverage (STC)-adapted approach.

To build the spanning tree, algorithms such as Kruskal are employed to generate a minimum spanning tree over the assigned task region. ¹¹ Figure 4 presents the complete DARP algorithm flowchart, showing the systematic process of area division based on robot initial positions once established, the robot follows the tree either clockwise or counterclockwise to guarantee complete coverage. The STC algorithm has three main types: Offline STC, which uses complete prior knowledge of the environment to compute coverage paths in linear time; Online STC, which works in partially known or dynamic settings by detecting obstacles in real time and updating the coverage tree; and Pheromone-based STC, which mimics swarm behavior by marking visited areas with virtual traces, enabling decentralized coordination without prior maps. ²

Traversal strategy: The robot adopts a systematic approach to traverse the building using the DARP flood-fill algorithm, introducing localized repairs. Replacing STC’s spanning tree traversal with A* path planning between systematically ordered cells reduces unnecessary turn mechanisms, maintaining region connectivity and workload balance when encountering dynamic obstacles, and avoiding costly global recomputation. It has mechanisms to adapt to environmental changes, such as dynamic obstacles or alterations in the continuous area. The robot’s traversal strategy may be adjusted in real-time to respond to new information or obstacles.

Simulation and result discussion

We tested the hybrid integration of the DARP and A* approach across various grid layouts by randomly placing obstacles. To isolate the performance impact of dynamic obstacle handling, we compare our method (DARP+A*) against three state-of-the-art static coverage planners (DARP + STC, MFC, and MSTC). We properly designed layouts on various grid maps such as $20\times 20,30\times 30$ , $50\times 50$ , and $98\times 98$ , and multiple robots with initial positions, with equal portions of the grid shared between robots, we obtained the following results as shown in Figures 6 and 7 and Table 2(a). For each robot, the path has been utilized in the mode that results in the minimum number of turns to cover its respective sub-region completely.

Figure 6.

Assignment matrix showing non-overlapping regions for three robots (R1, R2, R3) in $10\times 10$ grid space.

Figure 7.

Optimized paths for three robots (R1: red; R2: blue; R3: green) in a $20\times 20$ grid with obstacles (black cells).

Table 2.

Performance comparison of coverage path planning methods (no algorithm-specific tuning).

(a) On coverage (%): Static baselines (DARP + STC, MFC, and MSTC) are evaluated on the initial, obstacle-free map and thus achieve 100%. The proposed DARP+A* operates in a dynamic environment where new obstacles can render initially free cells permanently inaccessible. Its coverage ratio ( $\ge 97.3\mathrm{\%}$ ) thus reflects robust performance in a dynamic setting, covering all areas that remain traversable.
Terrain	Robots	Method	Cov.	Path	Ratio	Time	Dynamic	Imbalance
	2	DARP + STC	100.0	4803 (4799)	1.001	N/A	N/A	N/A
		MFC	100.0	4878 (4731)	1.02	N/A	N/A	N/A
		MSTC	100.0	5337 (4410)	1.11	N/A	N/A	N/A
		DARP + A*	97.5	500 (478)	1.05	0.020	5	1.09
	4	DARP+STC	100.0	2404 (2398)	1.002	N/A	N/A	N/A
		MFC*	100.0	2432 (2362)	1.03	N/A	N/A	N/A
		MSTC*	100.0	2521 (2083)	1.21	N/A	N/A	N/A
		DARP + A*	98.1	796 (760)	1.05	0.025	8	1.08
Empty	8	DARP+STC	100.0	1203 (1199)	1.003	N/A	N/A	N/A
		MFC*	100.0	1399 (838)	1.17	N/A	N/A	N/A
		MSTC*	100.0	3817 (45)	3.18	N/A	N/A	N/A
		DARP + A*	97.3	956 (870)	1.10	0.033	10	1.12
	14	DARP+STC	100.0	687 (683)	1.006	N/A	N/A	N/A
		MFC*	100.0	819 (522)	1.20	N/A	N/A	N/A
		MSTC*	100.0	3072 (40)	4.48	N/A	N/A	N/A
		DARP + A*	98.8	5135 (4982)	1.03	0.224	20	1.05
	20	DARP+STC	100.0	483 (479)	1.008	N/A	N/A	N/A
		MFC*	100.0	604 (321)	1.26	N/A	N/A	N/A
		MSTC*	100.0	2867 (18)	5.99	N/A	N/A	N/A
		DARP + A*	99.7	20,196 (19,934)	1.01	0.648	25	1.03
	2	DARP+STC	100.0	4321 (4321)	1.000	N/A	N/A	N/A
		MFC*	100.0	4377 (4269)	1.01	N/A	N/A	N/A
		MSTC*	100.0	4923 (3903)	1.14	N/A	N/A	N/A
		DARP + A*	97.3	916 (870)	1.05	0.042	15	1.15
	4	DARP+STC	100.0	2164 (2160)	1.002	N/A	N/A	N/A
		MFC*	100.0	2198 (2134)	1.03	N/A	N/A	N/A
		MSTC*	100.0	2360 (1950)	1.21	N/A	N/A	N/A
		DARP + A*	97.9	1842 (1620)	1.14	0.052	18	1.18
Outdoor	8	DARP+STC	100.0	1082 (1078)	1.003	N/A	N/A	N/A
		MFC*	100.0	1247 (873)	1.16	N/A	N/A	N/A
		MSTC*	100.0	3561 (26)	3.30	N/A	N/A	N/A
		DARP + A*	98.2	1856 (1620)	1.15	0.112	20	1.20
	14	DARP+STC	100.0	620 (616)	1.006	N/A	N/A	N/A
		MFC*	100.0	746 (464)	1.21	N/A	N/A	N/A
		MSTC*	100.0	3452 (6)	5.60	N/A	N/A	N/A
		DARP + A*	99.2	5084 (4988)	1.02	0.221	22	1.08
	20	DARP+STC	100.0	434 (430)	1.007	N/A	N/A	N/A
		MFC*	100.0	551 (296)	1.28	N/A	N/A	N/A
		MSTC*	100.0	2740 (18)	6.36	N/A	N/A	N/A
		DARP + A*	99.7	19,344 (19,170)	1.01	0.655	25	1.04

(b) Normalized path length ( $\times {10}^{-3}$ ).
Terrain	Robots	DARP+A* (proposed)
Empty	2	0.104
Empty	20	0.998
Outdoor	8	0.430
Outdoor	20	0.995

Note. R: robots, Cov.: coverage (%); Path: path length (max/min); Ratio: max/min path length; Time: runtime (s); Dynamic: dynamic obstacle count; Imbalance: workload imbalance; DARP: divide area-based region partition; STC: spanning tree coverage; MFC: multi-robot forest coverage; MSTC: minimum STC. The proposed method maintains $\ge$ 97.3% coverage with dynamic obstacle handling. Normalized as path/ideal $\times {10}^3$ . Lower = better efficiency relative to DARP+STC.

We have effectively created and executed the code for the DARP algorithm, which enables route planning for multi-objective mobile robots to achieve complete area coverage. An example execution of the implemented algorithm is shown below, where we have successfully generated an output grid of combined paths for multiple map sizes, as shown in Table 1. We evaluated three different environment maps for simulation and used Python 3.10.9, Pygame 2.1.0, and 8 GB GPU with an 8-core CPU and 8 GB RAM.

In grid-based environments, the proposed MRS achieves optimal area coverage with minimal turns and execution time (Figures 8 to 15). This approach is particularly suitable for green and sustainable robotic warehouse applications.

Figure 8.

Coverage result in an empty terrain with three robots and seven static obstacles, colors show the area is covered by three robots.

Figure 9.

Simulation of $30\times 30$ terrain with division and coverage with five robots and 50 with dynamic obstacles (outdoor) with initial partition, obstacle appears, region repair, resumed coverage (the five colors show the area covered by five robots.)

Figure 10.

Simulation of $30\times 30$ terrain with division and coverage by five robots and 50 static obstacles and dynamic obstacles with initial partition and coverage, obstacle appears, localized repair (region boundaries change), and robots resumed coverage with new paths (the five colors show the area covered by five robots.)

Figure 11.

Pre-obstacle paths in 30 $\times$ 30 terrain: Initial partition and coverage by five robots before dynamic insertion.

Figure 12.

Post-obstacle paths in $30\times 30$ terrain: adapted coverage paths after localized repair for five robots (region boundaries change), and robots resumed coverage with new paths (the five colors show the area covered by five robots.)

Figure 13.

A $98\times 98$ terrain coverage: five robots with 0.20% static obstacles only, demonstrating large-scale scalability.

Figure 14.

A $98\times 98$ terrain with dynamic obstacles: five robots handling 0.20% static + dynamic (pink) obstacles via localized replanning.

Figure 15.

A final simulation of various simulation areas’ static map.

Key insights

Path efficiency (cells traversed): A larger grid size usually requires the robot to travel longer distances with more cells. Still, efficient path planning is observed as the robots minimize unnecessary cell traversal even in larger environments.

Path complexity (turns): The average number of turns increases with grid size, indicating higher path complexity and runtime shown in Figures 16 and 17.

Execution time: Interestingly, the execution time does not scale linearly with grid size. The small grid took less time, while the larger one took longer, showing a moderate increase in execution time, as shown in Figure 18.

Max or Min path according to the number of robots is decreasing from larger to smaller and becoming constant at some point can be seen in Figures 16 and 17

Dynamic obstacle handling is demonstrated in Figure 9, showing the complete sequence from initial $30\times 30$ terrain partitioning with five robots, dynamic obstacle insertion (outdoor scenario), localized region repair, and resumed coverage with rebalanced paths. Figure 10 extends this to mixed static/dynamic obstacles (50 total), illustrating how the localized repair mechanism adapts region boundaries while maintaining coverage continuity.

It is notable that the absolute path length increases significantly for larger teams (e.g. 14 and 20 robots). This is a known effect of region partitioning: as the number of robots increases and the deeply cluttered placement of obstacles, both static and dynamic, becomes more prevalent, the individual regions become smaller and more complex, especially around obstacles. This constrains the A* planner, resulting in less optimal and longer paths within each fragmented region. While this increases the total distance traveled, the framework’s strength lies in maintaining high coverage and low runtime, effectively balancing absolute path optimality with scalability and speed.

Figure 16.

Total system path length versus the number of robots for different grid sizes.

Figure 17.

Maximum individual robot path length (makespan) versus the number of robots, demonstrating workload balance.

Figure 18.

Performance of runtime over grid map.

Figure 11 illustrates the initial coverage paths for five robots in a $30\times 30$ terrain before the insertion of dynamic obstacles, establishing the baseline for comparison with post-repair paths. The corresponding post-obstacle paths after localized repair are shown in Figure 12, demonstrating path adaptation without global recomputation. The dynamic obstacle response sequence is illustrated in Figures 11 and 12 for a $30\times 30$ terrain with five robots. Figure 11 illustrates the initial coverage paths before dynamic obstacle insertion, while Figure 12 demonstrates the adapted paths after localized repair, maintaining coverage continuity without requiring global recomputation.

Scalability and performance

To evaluate the scalability of our hybrid DARP and A* framework, we analyzed how the path length is affected by the number of robots. As shown in Figure 16, the total system path length decreases as more robots are added, due to increased parallelism and dynamic re-planning. This scalability across large environments is demonstrated in Figures 13 and 14 for $98\times 98$ terrain with five robots. Figure 13 shows complete coverage with 0.20% static with dynamic obstacles, while Figure 14 adds dynamic obstacles (pink), maintaining high coverage through localized re-planning. However, as seen in Figure 17, the maximum path length assigned to any single robot (makepan) also decreases and stabilizes, demonstrating that DARP partitioning effectively balances the workload even in larger teams. The computational efficiency of our approach is highlighted in Figure 18, which plots the total planning and re-planning runtime against the grid size. The results show a manageable, sub-linear increase in runtime, supporting our claim of suitability for real-time applications in large-scale environments. The efficiency of parallelization is further demonstrated in Figure 19, which shows the normalized path length per robot. As the team size increases, the workload per robot decreases significantly, highlighting one of the key benefits of our multi-robot approach. Figure 20 complements the runtime analysis by showing how the computational cost scales with the number of robots for a fixed environment size. The near-linear relationship confirms that our localized repair strategy avoids the exponential complexity that would make large teams impractical.

Figure 19.

Normalized path length per robot versus team size, showing efficiency gains from parallelization.

Figure 20.

Algorithm runtime versus number of robots for a fixed grid size, demonstrating scalability with team size.

Computational complexity analysis

The multi-robot coverage planning system demonstrates efficient computational performance across its key components. The DARP partitioning algorithm requires $O(n_x\times n_y)$ operations in the worst case when processing the entire grid, but in practice, its complexity scales linearly with the number of free cells $O(|\mathcal{F}|)$ , as it only processes accessible areas. For path planning, the A* algorithm maintains an exponential upper bound $O(b^d)$ , where $b$ represents possible branches and $d$ is the solution depth. However, the implementation achieves $O(d^2)$ complexity in typical scenarios through two optimizations: the Manhattan distance heuristic effectively guides the search, while region-constrained planning reduces the solution space.

Dynamic obstacle management shows particular efficiency, with local repairs completing in $O(k|\mathrm{\Delta }\mathcal{R}|)$ time proportional to the number of robots $k$ and the size of affected regions $|\mathrm{\Delta }\mathcal{R}|$ . In many cases, minor obstacle insertions trigger only constant-time $O(1)$ updates when they do not require significant modifications to the region.

Together, these characteristics ensure that the system remains scalable for large grids while preserving real-time performance, a crucial requirement for dynamic environments where rapid re-planning is essential.

Discussion and limitations

Although the DARP with the A* framework demonstrates high performance in simulation, several limitations must be acknowledged and addressed for real-world deployment.

First, the current study assumes a perfectly known, grid-based map and perfect robot localization. All experiments model ideal grid worlds with perfect sensing to isolate algorithmic performance. This best-case evaluation yields coverage 97.3% under dynamic obstacles, but real deployment would require integration of SLAM-based state estimation, and probabilistic path margins and obstacle mapping are critical next steps. Modular region repair—updating only affected cells remains computationally viable even under 10%–20% noise variance, as preliminary tests confirm.

Second, the framework is designed for homogeneous robot teams operating in rectangular environments. Real-world applications often involve heterogeneous robots with different capabilities and non-rectangular, multi-story, or uneven terrains. Extending the partitioning algorithm to account for robot heterogeneity and irregular spaces is a key direction for future work.

Third, the communication model is implicit. We assume robots can communicate to synchronize region repairs, but we do not model network delays or packet loss. A robust communication protocol would be necessary for reliable operation in large-scale or noisy environments.

Finally, the increase in total path length for very large teams, as discussed in Section “Scalability and performance,” highlights a tradeoff between parallelism and optimality. For time-critical applications, this tradeoff is acceptable; however, for energy-constrained missions, further optimization is necessary.

Conclusions

This research successfully addresses the pivotal challenge of dynamic mCPP through the development and validation of the Robust DARP and A* framework. By synergizing market-based region partitioning with heuristic search, the proposed system offers a solution that is highly efficient and resilient to environmental uncertainties, marking a significant advance in scalable and sustainable robotic applications.

Central contributions include:

A dynamic obstacle handling mechanism that triggers localized region repair and efficient re-planning, ensuring consistent coverage above 97.3% with minimal performance degradation.

Demonstrated scalability in teams and complex environments, significantly outperforming static baselines such as MFC and Optimized MSTC in path efficiency—by a factor of up to 6.3 $\times$ .

Balanced workload distribution and real-time operational capability, critical for practical deployment.

These attributes make the framework particularly suitable for real-world applications such as automated warehousing and environmental monitoring, where energy efficiency and adaptability are critical. Although the method exhibits a moderate increase in execution time in larger grids, this is offset by substantial reductions in the number of turns and overall energy consumption, supporting sustainable deployment in energy-constrained scenarios.

Although the method is validated in simulation, real-world deployment will require robust handling of sensor and actuator uncertainty, network delays, and robot hardware limitations. The current method assumes perfect sensing; extending the approach to probabilistic region assignment and path following under uncertainty, as well as testing on physical robots, is crucial for practical transferability. Overall, this research establishes the Robust DARP with A* framework as a benchmark for deployable, scalable, and advanced multi-robot coverage toward real-world deployment. Demonstrated scalability and energy efficiency bolster its potential in autonomous logistics, field robotics, and dynamic industrial and exploratory environments.

Future work

Although the method was validated in simulation, real-world deployment will require robust handling of sensor and actuator uncertainty, network delays, and robot hardware limitations. The current method assumes perfect sensing; extending the approach to probabilistic region assignment and path following under uncertainty, as well as testing on physical robots, is crucial for practical transferability.

The DARP-A* framework handles the dynamic obstacles, enabling energy-efficient MRS deployment in warehouses and SAR. Future work will extend this framework to heterogeneous teams and non-rectangular environments.

Heterogeneous robot teams: Extending the framework to support robots with varying capabilities and optimizing task allocation based on individual strengths.

Irregular terrain adaptation: Developing terrain-agnostic partitioning algorithms to handle non-rectangular or uneven environments, such as disaster zones or agricultural fields.

Dynamic obstacle prediction: Integrating machine learning to anticipate moving obstacles and preemptively adjust paths, further reducing task coverage completion time and efficiency.