Multi-Robot Connected Fermat Spiral Coverage

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 01:54:52

Abstract: We introduce Multi-Robot Connected Fermat Spiral (MCFS), a novel algorithmic framework for Multi-Robot Coverage Path Planning (MCPP) that adapts Coverage Fermat Spiral (CFS) from the computer graphics community to multi-robot coordination for the first time. MCFS uniquely enables the orchestration of multiple robots to generate coverage paths that contour around arbitrarily shaped obstacles, a feature notably lacking in traditional methods. Our framework not only enhances area coverage and optimizes task performance, particularly in terms of makespan, for workspaces rich in irregular obstacles but also addresses the challenges of path continuity and curvature critical for non-holonomic robots by generating smooth paths without decomposing the workspace. MCFS solves MCPP by constructing a graph of isolines and transforming MCPP into a combinatorial optimization problem, aiming to minimize the makespan while covering all vertices. 
Our contributions include developing a unified CFS version for scalable and adaptable MCPP, extending it to MCPP with novel optimization techniques for cost reduction and path continuity and smoothness, and demonstrating through extensive experiments that MCFS outperforms existing MCPP methods in makespan, path curvature, coverage ratio, and overlapping ratio. Our research marks a significant step in MCPP, showcasing the fusion of computer graphics and automated planning principles to advance the capabilities of multi-robot systems in complex environments.

Main paper: 
 introduction: 
 In the evolving landscape of multi-robot systems, the efficiency and effectiveness of Multi-Robot Coverage Path Planning (MCPP) (Almadhoun et al. 2019 ) remain pivotal in a myriad of applications, ranging from environmental monitoring (Collins et al. 2021 ) to search-and-rescue operations (Song et al. 2022 ) in complex workspaces. Traditional methodologies, such as cellular decomposition (Latombe and Latombe 1991; Acar et al. 2002) and grid-based methods (Gabriely and Rimon 2001; Hazon and Kaminka 2005) , have laid a solid foundation for understanding and navigating the challenges inherent in these tasks. However, as the complexity of environments and the demand for more efficient coverage increase, there is a growing need for innovative strategies that can adeptly handle workspaces rich in irregular obstacles with both high precision and adaptability.This paper introduces a novel algorithmic framework, called Multi-Robot Connected Fermat Spiral (MCFS), which revolutionizes MCPP by building upon the principles of Coverage Fermat Spiral (CFS) (Zhao et al. 2016 ) from the computer graphics community. This represents the first application of leveraging CFS to solve MCPP challenges in automated planning and robotics, showcasing a unique interdisciplinary fusion. MCFS stands out for its unique ability to coordinate multiple robots in generating contour-like coverage paths, elegantly adapting to the intricacies of arbitraryshaped obstacles-a characteristic not typically addressed by traditional methods. This contouring ability of MCFS results in not only more organic and less segmented coverage but also enhanced task efficiency in both time and energy expenditure by balancing the path costs across multiple robots, as indicated by the makespan (Zheng et al. 2010 ) metric.Besides task efficiency, a key challenge in MCPP is managing the deceleration and sharp turns required by nonholonomic robots. Traditional methods (Lu et al. 2023 ; Vandermeulen, Groß, and Kolling 2019) , often focused on minimizing path turns, are constrained to rectilinear workspaces and rely on decomposing the area into rectangles. This approach is less effective in arbitrary-shaped environments. In contrast, the essence of our MCFS framework lies in its global coverage strategy, conceptualizing the paths as a series of interconnected spirals that seamlessly integrate the movements of multiple robots. This strategy results in smooth covering paths without the need for decomposition, inherently accounting for path curvature-a vital factor for efficient robotic navigation.Drawing inspiration from the original application of CFS (Zhao et al. 2016 ) in additive manufacturing (Gibson et al. 2021) , our MCFS framework innovatively adapts CFS to tackle the MCPP problem, which generates continuous and smooth coverage paths by converting a set of equidistant contour-parallel isolines into connected Fermat spirals. MCFS first constructs a graph of isolines (Sec. 3), associating each vertex with an isoline and connecting it to associated vertices of adjacent isolines. It then reduces the MCPP problem to Min-Max Rooted Tree Cover (MMRTC), a combinatorial optimization problem that finds a forest of trees to cover all vertices of the graph while minimizing the makespan (Sec. 4). Our framework is versatile, allowing coverage paths to start from arbitrary starting points as required in MCPP, and optimizes the distribution of the cov-erage of both multiple whole isolines and segments of an isoline among multiple robots, showcasing an innovative approach to effectively managing the makespan, curvature, and path continuity for each robot. Key Contributions: (1) We propose a unified version of CFS that standardizes the stitching of adjacent isolines, allowing for customized priorities in selecting stitching points and providing scalability and ease of adaptation to MCPP by enabling coverage paths to start from any given initial robot positions. (2) We demonstrate how our MCFS framework extends this unified version of CFS to MCPP and effectively solves the corresponding MMRTC problem. (3) We introduce two optimization techniques: one that adds edges between non-adjacent but connectable pairs of isolines to expand the solution space and another that refines the MM-RTC solution for balanced path costs and reduced overlap in multi-robot coverage. (4) We present extensive experimental results validating the superiority of our MCFS framework over state-of-the-art MCPP methods in metrics of makespan, path curvature, coverage ratio, and overlapping ratio, showcasing its effectiveness in diverse coverage scenarios. 
related work: 
 We categorize existing Single-Robot Coverage Path Planning (CPP) and MCPP methods into grid-based, cellular decomposition, and global methods. We refer interesting readers to (Tomaszewski 2020) for a more detailed taxonomy. Grid-Based Methods: Grid-based methods abstract workspaces into square grids (Hazon and Kaminka 2005; Kapoutsis, Chatzichristofis, and Kosmatopoulos 2017; Tang, Sun, and Zhang 2021) , allowing for the application of various graph algorithms. One prominent method, Spanning Tree Coverage (STC) (Gabriely and Rimon 2001) , constructs a minimum spanning tree and then generates circumnavigating paths on the tree to cover the workspace. STC-based MCPP methods (Hazon and Kaminka 2005; Tang and Ma 2023) work by finding a set of trees that jointly visit all vertices and assigning each robot a path that circumnavigates a tree. While convenient, the complexity of optimally solving grid-based MCPP grows exponentially in the workspace size and the number of robots. Cellular Decomposition Methods: These methods decompose the workspace into sub-regions by detecting geometrical critical points, such as trapezoid (Latombe and Latombe 1991) and Morse (Acar et al. 2002) decomposition. CPP methods generate zigzag paths in these sub-regions for coverage (Choset 2000; Wong and MacDonald 2003) , and MCPP methods connect and assign these sub-regions, filled with zigzag paths, to robots for cooperative coverage (Rekleitis et al. 2008; Mannadiar and Rekleitis 2010; Karapetyan et al. 2017) . Additionally, some research optimizes the direction of the zigzag paths for single robots (Oksanen and Visala 2009; Bochkarev and Smith 2016) . Although efficient, these methods are less suitable for obstacle-rich or non-rectilinear workspaces due to their reliance on geometric partitioning. Global Methods: Global CPP methods directly generate paths to cover the workspace without decomposing it. They fall into two types: the first type generates separate paths that contour around obstacles (Yang et al. 2002) , and the second type generates a closed path, including Spiral Path (Ren, Sun, and Guo 2009) and CFS (Zhao et al. 2016 ) that are notable for their continuous and smooth paths. CFS paths are especially convenient as their entry and exit points are 150 adjacent, facilitating the integration of multiple paths. A recent paper has built a CFS path based on an exact geodesic distance field to cover a terrain surface (Wu et al. 2019 ). However, to our knowledge, there are no global methods yet developed for MCPP. In this section, we present our unified version of CFS, an adaptation of the original CFS (Zhao et al. 2016 ) concept. The original CFS employs a two-phase process to transform a set of equidistant isolines into a closed path 160 that covers an input polygon workspace. It utilizes a graph structure, where vertices represent individual isolines and edges connect vertices whose respective isolines have adjacent segments. Initially, the original CFS identifies a set of "pockets"-connected components on the spanning tree 165 of the graph. The first phase transforms the isolines within each pocket into a Fermat spiral (Wiki 2023a) , and the second phase stitches these isolated Fermat spirals to construct the final, connected Fermat spiral by traversing the pockets using the graph edges.Our unified version of CFS modifies the graph construction of isolines and consolidates the original two-phase process into a singular, cohesive operation for the CPP problem. The primary modification in our approach lies in the stitching phase. Rather than explicitly identifying pockets 175 and then stitching isolated Fermat spirals, we employ a unified procedure for every pair of stitchable isolines. Instead of explicitly identifying pockets and then stitching the resultant isolated Fermat spirals, our method integrates a unified process that simultaneously addresses both the conversion 180 of isolines within a pocket into Fermat spirals and the interconnection of these spirals. This integrated process is applied to every pair of stitchable isolines, effectively merging the conversion and stitching phases. By traversing a rooted spanning tree of the graph, the same connected Fermat spiral 185 is obtained as the original CFS.The advantage of our unified CFS approach is twofold. Firstly, it enhances scalability, facilitating the incorporation of diverse utilities within the framework. Secondly, it simplifies the extension of CFS to MCPP, as will be elaborated 190 in Sec. 4. By integrating and streamlining the conversion and stitching processes, our approach improves the efficiency and versatility of CFS for complex CPP challenges. 
constructing isolines and the isograph: 
 We describe our approach for generating layered isolines 195 from a given polygon workspace to be covered and building the isograph. The polygon is enclosed by its boundary, consisting a set of interior boundary polylines that represent obstacles and an exterior boundary polyline. Generating Layered Isolines: The procedure starts by sam-200 pling a 2D mesh grid of points within the polygon. A distance field is built for these points, representing their shortest distance to the polygon boundary (encompassing both the interior obstacle boundary polylines and the exterior boundary polyline). We denote the distance step size between isolines as l, and the largest distance to the polygon boundary among all points as l max . We then use the Marching Squares algorithm (Wiki 2023b) to generate layered isolines for each layer i = 1, 2, ..., ⌊l max /l⌋. This ensures that the distance between each point in the layer-i isoline and the polygon boundary is l × i. The last step resamples equidistant points along each isoline, maintaining a consistent distance of l between adjacent points. Building the Isograph: We define isograph of the layered isolines as an undirected graph G = (V, E), where V is the set of isovertices, each associated with a unique isoline. For ease of reference, we let I v and L v denote the isoline associated with any v ∈ V and its respective layer. Similar to the original CFS (Zhao et al. 2016) , we define a connecting segment set O u,v for any pair of isovertices u, v ∈ V in adjacent layers (i.e., |L u -L v | = 1) as:O u→v = {p ∈ I u | ∀z ∈ V, d(p, I v ) < d(p, I z ) ∧ L z = L v }(1) where d(p, I) denotes the distance between point p and isoline I. Unlike the original CFS which directly constructs an undirected edge (u, v) if O u→v is nonempty, we also consider O v→u for edge construction. This consideration provides flexibility in traversing the isograph in any order and from any root isovertex in the CFS context. It also avoids adding edges (u, v) where the respective isolines I u and I v are separated by multiple isolines, as such pairs may be unsuitable for stitching in the CPP context (see Sec. 3.4).Therefore, we define a set O u,v of stitching tuples for any u, v ∈ V in adjacent layers as:O u,v = {(p, q) ∈ O u→v × O v→u | p = C u (q) ∧ q = C v (p)}(2) where C u (p) denotes the nearest point along isoline I u to point p. Subsequently, an undirected edge (u, v) is formed for any u, v ∈ V in adjacent layers with a nonempty O u,v .Each tuple (p, q) ∈ O u,v serves as a candidate stitching tuple to connect isolines I u and I v by stitching p to q and B u (p) to B v (q), where B u (p) denotes the point preceding p along isoline I u in counterclockwise order.While the original CFS assigns a weight of |O u→v | to each edge to retain a low-curvature path when determining the isograph traversal order for connecting isolated Fermat spirals, we currently leave the edge weight definition application-specific and will explicitly address this objective in Sec. 3.3 for every stitching operation.We detail our unified version of CFS in Alg. 1, which takes as input an isograph G and an entry point p 0 . The algorithm starts by identifying the isovertex r containing p 0 (line 1) as the root for obtaining the Depth-First-Search (DFS) traversal edges of G. Line 2 initializes the CFS path π to be constructed and the set U to record points already used for stitching the isolines. The main loop then iterates over the DFS edges (line 3) and stitches the corresponding pair of isolines for each edge (line 5-6). Specifically, a stitching tuple (p, q) is selected via any selector (line 5). For any isovertex v ∈ V , we use I v (p) to denote the counterclockwise path along isoline I v starting at p and ending at B v (p). This path segment is then stitched into π using the selected stitching tuple (line 6). The set U is updated to include these newly se-260 lected stitching tuples (line 7). Following the interation over all DFS edges, the final path π is constructed to stitch together all isolines and completely cover the given polygon.We now propose three stitching tuple selectors, each de-265 signed to select an appropriate stitching tuple s from a given set O u,v for connecting isolines I u and I v . Fig. 1 with its stitching tuple already selected by f cfs , will be visited before (u, v) in the DFS traversal (line 3). Assuming that (z, u) is visited first with the selected stitching tuple(p ′ , q ′ ) ∈ O z,u , f cfs then checks for s = (p, q) in O u,vwhere B(p) = q ′ . If such a tuple exists, it is selected for 280 (u, v); otherwise, the first tuple in O u,v is selected. Minimum Curvature Stitching (MCS) Selector: The MCS selector f mcs iterates through O u,v to identify the stitching tuple s = (p, q) that minimizes the curvature difference ∆κ(s) before and after stitching, defined as:EQUATIONwhere κ π (p) and κ Iu (p) denote the curvatures at any point p on the new stitched path π using s and on the original isoline I u , respectively. Formally, the MCS selector is defined as f mcs (O u,v ) = arg max s∈Ou,v ∆κ(s).  
multi-robot cfs coverage: 
 In this section, we present our MCFS framework for solving MCPP. MCFS computes multiple trees from an input isograph, each corresponding to a different robot, and then applies CFS on each tree to compute individual coverage paths. In Sec. 4.1, we detail the CFS-based formulation of MCPP and introduce its reduction to Min-Max Rooted Tree 325 Cover (MMRTC) (Even et al. 2004; Tang and Ma 2023) .Since there can still be unnecessary repetition in the coverage paths resulting from an optimal MMRTC solution, we present two optimization techniques, isograph augmentation in Sec. 4.2 and solution refinement in Sec. 4.3, aiming to further enhance the MCPP solution.We present our problem formulation of MCPP that facilitates the extension of CFS. The problem of MCPP is to find a set Π = {π i } i∈I of coverage paths for a set I of robots that minimizes the makespan (i.e., the maximum path cost). where each T i ∈ T is a tree rooted at r i . Let V (T ) and E(T ) denote the vertex set and edge set of any tree T , respectively. The solution set T must satisfy v ∈ i∈I V (T i ) to ensure coverage of every v ∈ V . Since CFS stitches each isolineI v of v ∈ V (T i ) to construct the coverage path π i ∈ Π, we have c(π i ) = |π i | = v∈V (Ti) |I v | = c(T i ).Hence, for any isograph G and set R of root isovertices for the robots, the heuristic values in Eqn. (4) and Eqn. ( 5) are identical under CFS, effectively reducing MCPP to MMRTC. We employ the Mixed Integer Programming (MIP) model proposed in (Tang and Ma 2023) to solve MMRTC optimally. The optimal set of trees obtained is then used to produce coverage paths by applying our unified CFS (Alg. 1) on each tree. Fig. 4-(a ) and (b) illustrate a 2-tree MMRTC instance and its crresponding solution.In Sec. 3.1, the isograph building process considers each edge only for two isolines in adjacent layers. This process, while efficient, often results in a sparse graph structure in the isograph and thus an undesirable MMRTC solution where certain isovertices are repetitively covered by multiple trees. One common example of such repetition appears for a cut isovertex, defined as a vertex whose removal increases the number of connected components in the graph. Such repetitions become more common as the number of trees (robots) increases or when tree roots are clustered, thereby leading to increased makespan and reducing the overall quality of MCPP solutions. To mitigate this issue, we propose to augment the sparse isograph with additional edges connecting isovertices in non-adjacent layers. This augmentation aims to reduce the sparsity of the isograph and allow MMRTC trees to explore new routes for joint coverage, thereby reducing repetitions and balancing tree costs.𝑣 ! 𝑣 " 𝑣 # 𝑝 ! 𝑝 " 𝑝 #The augmentation of an isograph G = (V, E) operates by adding a set E # of augmented edges, defined as:EQUATION) where d G (•, •) denotes the graph distance between any two isovertices in G, and δ is a hyperparameter that sets the augmentation level. The set E # is then used to update G by setting E = E ∪E # . For edges in E # , stitching tuples are constructed differently from those in adjacent layers described in Sec. 3.1. Without loss of generality, we consider an edge (v 1 , v k+1 ) ∈ E # and its shortest path (v 1 , v 2 , ..., v k+1 ) in the original G (i.e., each segment (v i , v i+1 ) is part of E and k is the graph distance between v 1 and v k ). The set O v1,v k+1 comprises all pairs of p 1 on the isoline of v 1 and p k+1 on the isoline of v k+1 that can be feasibly connected, forming valid stitching tuples (p 1 , p k+1 ). Such points are connectable iff they form a sequence of consecutive stitching tuples (p 1 , p 2 ) ∈ O v1,v2 , . . . , (p k , p k+1 ) ∈ O v k ,v k+1 , which ensures that the straight-line segment between the pair does not intersect more than k -1 or any obstacles within the workspace. Given that the distance between adjacent isolines is set as l (Sec. 3.1), we assign a weight w e = l × k to each augmented edge e = (u, v) ∈ E with a layer difference of k (i.e., |L u -L v | = k), which approximates the additional path cost incurred by any tree containing the augmented edge. The cost of any tree T is thus updated to c(T ) = v∈V (T ) w v + e∈E(T ) w e in MMRTC solving.Despite isograph augmentation reducing isovertex repetitions in the optimal MMRTC solution, two bottlenecks persist in achieving a better MCPP solution. The first bottleneck results from certain isovertex repetitions that remain unresolved by augmentation alone, notably when multiple robots share the same root isovertex or multiple trees use the same vertex. To tackle this, we implement the PAIRWI-SEISOVERTICESSPLITTING (PIS) function, designed to disperse the coverage of the isoline of an isovertex with repetitions amount multiple robots. The second bottleneck arises from the limitation of an optimal MMRTC solution in balancing tree costs when isoline traversing costs vary signifi- 17 sort T by the evaluated costs in ascending order Algorithm 2: MMRTC Solution Refinment Input: isograph G = (V, E), optimal MMRTC solution T 1 T * ← T , U ← ∅ 2 M ← {u ∈ V | T ∈T |{u} ∩ V (T )| > 1} 3 ADDIMPROVINGREPETITION(T , M, U ) if M = ∅ 4 max-18 P ← {(u, v) | u, v ∈ V (T [-1])/U ∧ deg(u, T [-1]) = 1} 19 for ((u, v) , T ) ∈ P × T do 20 if u ∈ {b ∈ V (T ) | ∃(b, x) ∈ E, x / ∈ V (T )} then 21 T ← (V (T ) ∪ {u}, E(T ) ∪ {(u, v)}), M ← M ∪ {u} 22E T ← {(u, x) | x ∈ N T (u)} ∪ {(v, x) | x ∈ N T (v)} 29 E ′ T ← {(z, x) | (•, x) ∈ E T } ▷ see Fig. 4-(c) 30 T ′ s ← {(V (T ) ∪ {z}/{u, v}, E(T ) ∪ E ′ T /E T ) | T ∈ T s } 31 h ← σ({c(T )} T ∈T ′ s ) 32 mark T ′ s as nonadjacent if ∃ T ∈ Ts and (z, x) ∈ E ′ T , |Oz,x| = 0 33 for (z, x) ∈ E ′ T with𝐬 ! 𝐬 " 𝐺=(𝑉, 𝐸) 𝑇 # 𝑇 $ 𝑇 # % 𝑇 $ % 𝑟 ! 𝑟 " 𝑟 ! 𝑟 " 𝑟 ! 𝑟 " 𝑎 𝑏 (a) (b) (c) (d)𝑢 𝑢 𝑣 𝑣 its heuristic value h and the post-split tree set T s to updateT * s if h < h * [Line 11].The best tree set T * s for splitting u with the smallest heuristic value is then integrated into the MMRTC solution T [Line 12], with a subsequent update to T * [Line 13]. If M is empty, the process calls AIR again to potentially add an additional improving repetition [Line 14].As every iteration records isovertices used for PIS in U and AIR only adds unused isovertices, Alg. 2 terminates after at most |V |/2 iterations since two new isovertices are added to U in Line 12 in each iteration. Add Improving Repetition (AIR): The AIR function (Lines 16-22) identifies an isovertex from the highest-cost tree in the tree set T and adds it to a low-cost tree. It first sorts T by tree costs in ascending order [Line 17] and then builds a set P of isovertex pairs from the highest-cost tree T [-1] [Line 18]. Note that P contains only those pairs where both isovertices are not in U (hence, unused for PIS), and the first isovertex u in each pair must be a leaf (having a degree of 1), making it an ideal candidate to be split from Instances: We conduct the experiments using MCPP instances displayed in Fig. 5 , where the polygon workspace that needs to be covered is already filled with paths. The distance l between adjacent isolines in all instances is 0.1, which is also the cover diameter of the robots. The number of robots (|I|) of the instances range from 2 to 9. In instances char-I and char-P, two robots and four robots share the same root isovertex, respectively. In instance 2-torus, three pairs 525 of robots share three root isovertices, respectively. In all other instances, robots start from different root isovertices.Metrics: In addition to the makespan τ , we report the following metrics to evaluate an MCPP method and its solution: (1) Curvature: Average curvature of all paths (smaller values indicate smoother paths). ( 2) Coverage: Ratio between the covered area and the total workspace. (3) Overlapping: Ratio between the repeatedly covered area and the total workspace area. (4) Runtime: Total runtime of the method, including the MIP model solving time (when applicable).Stitching Tuple Selectors: Tab. 1 compares curvature among the random, CFS, and MCS stitching tuple selectors. Both CFS and MCS selectors outperform the random selector, with average reductions of 24.6% and 27.9%, respectively. For less complex workspaces like 2-torus that can be 540 filled with smooth isolines, the CFS selector with staircaselike stitching paths outperforms the MCS selector since the MCS selector struggles to distinguish small curvature differences. However, for complex workspaces like office, the MCS selector significantly excels by strategically selecting sharp corner points as stitching tuples, thereby substantially reducing the curvature. Based on these findings, the MCS selector will be used in the MCFS framework for the remainder of our experiments. to the non-rectilinear workspaces in our instances, we use overlay grids to approximate the workspaces, followed by shortest pathfinding for robot return to root positions postcoverage. Note that the reported coverage and overlapping ratios for TMC and TMSTC * are approximations due to the workspace approximation and small intersection of their coverage paths with obstacles, whereas the values for MCFS are exact. In Tab. 2, while the average coverage ratios of TMC, TMSTC * , and MCFS are comparably close (with a 3.51% variance), MCFS demonstrates an average makespan reduction of 32.0% and 27.9%, curvature reduction of 75.7% and 47.8%, and overlapping ratio reduction of 13.6% and 20.9% compared to TMC and TMSTC * , respectively. Both MCFS and TMC require longer runtime due to solving MIP models for MMRTC and MTSP, respectively, especially in instances with larger isographs or more robots, such as 2torus and office). Fig. 7 and Fig. 8 visualize the coverage paths planned by TMC and TMSTC * , respectively. These paths exhibit a back-and-forth boustrophedon pattern, leading to high curvature and imperfect coverage around complex obstacles. In contrast, MCFS notably excels in generating smooth paths that efficiently contour around arbitrarily shaped obstacles, a clear visual advantage over the other methods as shown in Fig. 5 .  
conclusions: 
 We proposed the MCFS framework, an innovative approach that blends principles from computer graphics and automated planning to tackle the challenges of covering arbi-620 trarily shaped workspaces in complex MCPP tasks. MCFS leverages our novel unified version of CFS to bring scalability and versatility for multi-robot scenarios by computing multiple rooted trees that jointly cover an input graph of isolines. We also developed two effective optimization 625 techniques that significantly enhance the solution quality. We validated the effectiveness of MCFS in various scenarios through rigorous experimentation and analyses, benchmarked against state-of-the-art MCPP methods. Future work includes improving isoline generation to further boost the 630 coverage ratio, developing heuristics to accelerate the PIS function for large numbers of robots or isolines, and speeding up MMRTC solving. 
: 
 chestration of multiple robots to generate coverage paths that contour around arbitrarily shaped obstacles, a feature notably lacking in traditional methods. Our framework not only enhances area coverage and optimizes task performance, particularly in terms of makespan, for workspaces rich in irregular obstacles but also addresses the challenges of path continuity and curvature critical for non-holonomic robots by generating smooth paths without decomposing the workspace. MCFS solves MCPP by constructing a graph of isolines and transforming MCPP into a combinatorial optimization problem, aiming to minimize the makespan while covering all vertices. Our contributions include developing a unified CFS version for scalable and adaptable MCPP, extending it to MCPP with novel optimization techniques for cost reduction and path continuity and smoothness, and demonstrating 
 
 Appendix:  


Decision: The paper studies a variant of the multi-robot coverage problem and suggests using specific techniques from computer graphics to solve it. This is an interesting direction and all reviewers acknowledge that the work is likely to provide value to the ICAPS community as the presented method is original and addresses several challenges that can not be easily handled within the commonly used approaches (like the ones based on the cellular decomposition).

The main concern is the clarity. The ideas behind the algorithms are not clearly presented and are hard to understand. It is highly recommended to enhance the presentation (e.g. by providing more illustrative examples and a beginner material that walks through the fundamentals of CFS).

Reviews: review: strength_weakness: strength_weakness: The experimental analysis seems to consider specific scenarios but there is no reference to benchmarks.
questions: questions: Is there any MCPP benchmark to be considered for evaluating the effectiveness of the approach?

Is the cost for encoding MCPP negligible? Or should this be a further cost to be considered in the evaluation?
strength_weakness: strength_weakness: •	The idea and algorithms are not clearly presented, and are hard to understand. 
•	The equations are not well defined and some parts do not make sense. 
•	The experiments are not well designed. Their claims on energy consumption are not supported by their experiments.
questions: questions: •	In abstract: 
-	You define CFS as Coverage Fermat Spiral here. But the title of Section 3 is Connected Fermat Spiral (CFS). Please double check and make it consistent. 
•	In introduction: 
-	Please clarify what do you mean by ‘more organic and less segmented coverage’. 
-	‘adeptly’ is a typo. 
-	‘Key Contributions: …’, it’s a weird way of starting a new paragraph. 
•	In Related Work: 
-	‘interesting readers’ is a typo. 
-	‘geometrical critical’ is a typo. 
•	In Connected Fermat Spiral (CFS): 
-	It is better to first define graph structure. 
-	It is unclear how vertices can represent an isoline? Do you mean dividing an isoline into a sequence of waypoints? Then, how do you express the sequence/order/association of the waypoints on an isoline? A conventional graph <V, E> does not express such information. Please clarify. 
-	It is unclear what are adjacent segments. 
-	It is unclear what is a pocket. What are the components you are referring? Please clarify. 
-	Please avoid citing Wiki. Use a proper citation instead. 
-	‘Rather than explicitly identifying …. Instead of explicitly identifying …. ‘ it seems two redundant sentences here. Please double check. 
-	What do you mean by ‘layered isolines’? I guess you mean isolines on different levels. Please double check and clarity. 
-	Please clarify how do you sampling a 2D mesh grid of points within the polygon. For instance, is it uniform sampling in each dimension? 
-	What is a distance step size? Each layer should be each level. 
-	It is hard to understand Eq. (1). if Lz = Lv, Iz and Iv would overlap (one isoline). Why d(p, Iv) < d(p, Iz)? This equation does not make sense to me, please clarify. 
-	It is unclear to me what it means if Ouv is non-empty. Please clarify. 
-	‘It also avoids adding edges (u, v) where the respective isolines Iu and Iv are separated by multiple isolines’ it is also unclear to me how this can be achieved by Eq. (1), please clarify. 
-	The logical and symbol in Eq. (2) is improper here. Just use a comma. 
-	Eq. (2) also does not make sense to me. If p is uniquely defined as the nearest point on Iu to q, (p, q) should just be a fixed point. What is the point defining a space Qu-v \times Qv-u? 
-	‘Subsequently, an undirected edge (u, v) is formed for any u, v ∈ V in adjacent layers with a nonempty Ou,v.’ Since Eq. (1) and (2) are not clear to me, it is hard to see what this means and how it is achieved.
-	‘connect isolines Iu and Iv by stitching p to q and Bu(p) to Bv(q), where Bu(p) denotes the point preceding p along isoline Iu in counterclockwise order.’ It is unclear to me 
1)	how connecting Iu and Iv is achieved by stitching p, q, Bu(p), Bv(q). 
2)	why stitching Bu(p) to Bv(q)? Is it for continuity? Then why stitching only one preceding point? Is it better to stitch more points for continuity? 
3)	if for other purposes, please clarify. 
-	CFS (Zhao et al. 2016) you just need to cite this paper once the first time you mention it. 
-	It seems to me ‘versatile’ means the starting point can be on a random level, instead of the lowest level. If I’m right, please state clearly. Otherwise, please clarify what versatile means. 
-	In Fig.1, all figures start from the lowest level. Can you give some examples where the starting point is on a random level? 
•	In Multi-Robot CFS Coverage: 
-	It is unclear to me how the authors address task allocation, cost distribution, and cooperation. Task allocation and cost distribution are mentioned as advantages of their method in Introduction. Cooperation is necessary for multi-robot operations. 
-	If Eq. (4) is the objective for multi-robot operation, the robots only find the paths that minimize the overall cost. Then, how do they achieve task allocation and cost distribution? 
-	‘Π, the path length is linear in |π| and thus the cost of any path π can be evaluated as c(π) = |π|’ If the cost is just path length, what is the point optimizing continuity and smoothness? 
-	It is unclear to me what E# represents. 
•	In Empirical Evaluation: 
-	I can’t see any evaluation on energy consumption (total or balanced). Perhaps the path curvature can somehow reflect the energy consumption, it needs to be rigorously defined.
strength_weakness: strength_weakness: 1. The paper is a tough read for non-computer graphics readers. I have traditional MAPF experience as well as some single-agent coverage experience but found the methods section hard to understand. I, and I think other readers, would really appreciate a beginner supplementary material that walks through fundamentals of CFS. One example is "Branch-and-cut-and-price for multi-agent path finding" which discusses a Branch-Cut-Price integer programming approach for MAPF. They specifically include supplementary material for MAPF readers unfamiliar to the general integer programming approach in the beginning of their methods section. I.e. look at Section 4 in  https://www.sciencedirect.com/science/article/pii/S0305054822000946#sec4 which refers the reader to https://ars.els-cdn.com/content/image/1-s2.0-S0305054822000946-mmc1.pdf which serves as a great primer.  I think including something similarly would really help the readability of the paper.
1b. Methods were hard to understand although the corresponding paragraph text helped to an extent. "PAIRWISEISOVERTICESSPLITTING" in Algorithm 2 is particularly tough to parse and I am unsure if anyone can understand it without the paragraph. Even with the paragraph understanding what is going on is hard.
1c. I did not understand Figure 3 at all. I found Figure 4 to be immensely helpful on the otherhand.
questions: questions: Major questions: None

Minor questions:
1. How would this method work for robots with kinematic constraints? I.e. if robots have a minimum turning radius, would MCFS still be applicable or would other machinery be required?
2. The isoline decomposition causes agents to cover long neighboring corridors of regions, as opposed to other approaches which generally have agents cover more compact regions. I.e. for the I in ICAPS (cute example by the way), the two agents have these long sections next to each other, when other approaches would generally split it to a top and bottom half. I am curious if your refinement process could work on arbitrary "isolines" that cover the region? I.e. instead of using CFS which produces longer neighboring isolines, other approaches could produce more compact isolines which could then be used in your method. Is this relevant future work that generalizes this idea or is CFS required?