Meeting-Merging-Mission: A Multi-robot Coordinate Framework for Large-Scale Communication-Limited Exploration

Abstract

This letter presents a complete framework Meeting-Merging-Mission for multi-robot exploration under communication restriction. Considering communication is limited in both bandwidth and range in the real world, we propose a lightweight environment presentation method and an efficient cooperative exploration strategy. For lower bandwidth, each robot uses specific polytopes to maintain free space and to generate Super Frontier Information (SFI), which serves as the source for exploration decision-making. To reduce repeated exploration, we develop a mission-based protocol that drives robots to share collected information in stable rendezvous. We also design a complete path planning scheme for both centralized and decentralized cases. To validate that our framework is practical and generic, we present an extensive benchmark and deploy our system into multi-UGV and multi-UAV platforms.

I Introduction

Recently, thanks to the maturity of multi-robot cooperative technology, swarm exploration has received increasing attention in many application areas. Multiple robots can explore wider regions in the time unachievable by a single one, with better fault tolerance and uncertainty compensation. However, in actual exploration missions, communication limitation introduces great challenges to multi-robot exploration tasks and makes the advantages brought by multi robots difficult to leverage. In the real world, especially large-scale environment, it is unrealistic for robots to have global communication capabilities. Besides, transmitting high volumes of sensor data could overwhelm the network capacity. Due to the above realistic factors, the system developed under communication restriction is necessary.

The communication limitations are considered from the following two aspects:

(1) Limited communication bandwidth (LB). LB makes transmitting the commonly used voxel map or point cloud that are convenient for planning and decision-making exceeds the bearing network capacity.

(2) Limited communication range (LR). Robots are constrained to maintain continuous connectivity or execute tasks lonely, introducing great challenges to exploration.

Figure 1: Composite image of the meeting phase of a multi-robot exploration experiment under communication limit in a large underground parking lot.

Figure 2: An overview of our multi-robot exploration system. Each robot maintain an Environment Library through Local Handler(Sec.III). When the connection is built between robots, Meeting Handler will be triggered(Sec.IV).

To resolve the above issues, we propose a complete framework Meeting-Merging-Mission for multi-robot exploration, composed of a lightweight environment presentation method and an efficient cooperative exploration strategy.

For LB, in order to reduce bandwidth for transmission, we use star-convex polytopes to represent known free space. Moreover, utilizing the meshes of the polytopes, we can represent the frontiers which is the boundary of known space. For more efficient exploration decision-making, we generate Super Frontier Infomation (SFI), an integrated information structure representing high-level frontiers and viewpoints. By transmitting star-convex polytopes and SFI, robots obtain the necessary environment information with low bandwidth cost.

For LR, we introduce a new mission-based protocol for a team of robots to execute exploration tasks without global communication. The key is assigning missions to robots that guide them to disconnect actively for independent exploration and rendezvous stably for sharing collected information. Besides, we give a complete path planning scheme to balance both exploration mission and requirement of rendezvous in all process of exploration.

Compared with existing state-of-the-art works, our proposed system can explore large-scale environments in less time. We perform comprehensive tests in simulation and real world to validate the efficiency and practicability of our framework. Summarizing our contributions as follows:

(1) A lightweight environment representation using star-convex polytopes and SFI offering essential environment information to drive exploration.

(2) A new mission-based protocol for multi-robot exploration in the absence of global communication. The distributed protocol reduces repeated exploration and increases exploration efficiency.

(3) A complete path planning scheme in all processes of exploration, including centralized planning in joint meeting phase and decentralized planning in lonely exploration phase.

II Related Work

II-A Environment Representation

For large-scale scenarios, a lightweight environment representation to is of vital importance to meet the practical communication limit. Some works [1, 2] use the Gaussian mixture model (GMM) as a global spatial representation of the environment. GMM learns a density function of obstacle point clouds via the expectation-maximization (EM), compresses a huge amount of data as several parameters. However, unnecessary computation and inaccuracy have been introduced by GMM, as the free space is not recorded but has to be reconstructed for the component update. Katz et al. [3] propose to use the HPR (Hidden Point Removal) operator [4] to determine the visibility of a point cloud given a viewpoint, without reconstruction or normal estimation. Based on HPR, Zhong [5] efficiently generates large, free, and guaranteed convex space among arbitrarily cluttered obstacles. In this way, the visibility and free space information of a complex environment are extracted by the polytope, which is another compact representation.

The above two groups of representation can both drive robots explore. Leveraging the GMM method to model the observed obstacles, information entropy can be calculated for the next viewpoint with large information gain[1]. Furthermore, the polytope-based method generates free space to distinguish known and unknown regions to drive robot exploration. When all the unobserved aims are eliminated by free space, exploration completes. Yang uses convex polyhedrons to estimate 3D free space in [6]. However, the convex constraint makes it conservative, especially when robot is in the intersections, reducing the unknown region eliminating efficiency. Williams [7] uses the method in [4] to generate meshes as frontiers. While without maintaining free space, the deletion of frontiers is done by visibility check. The frontier is not visible if there exists another one intersected by the raycast line between the robot and the frontier, which leads the deletion operation to be conservative and not accurate enough, especially when the free space shape is complex.

Figure 3: The process of free space and super frontier information generation. (a) Generation process of star-convex polytope. (b) The current free space represented by a star-convex polytope. (c) The SFI of the current frame. Note that cluster $F{C}_1$ which is marked by red number 1 is generated above a low obstacle showing the spatial representation capability in the z-axis direction.

II-B Multi-robot Exploration

Based on the communication mechanism, multi-robot exploration can be summarized into three categories: without any connection requirement, with continuous connection requirement, and with active disconnection and reconnection.

In the first category[8, 9, 10, 11, 12, 13], communications are episodic and opportunistic, which could result in repeated exploration and useless energy consumption [14]. The second category requires robots to keep continuous connection, which is the most restrictive class. In [15], robots explore a building subject to the constraint of maintaining line-of-sight communications. In [16], authors present a system in which robots explore the environment while permanently maintaining wireless networking. Jensen [17, 18] proposes several systems which feature a ”mild” form of continuous connection that allows robots to reconnect if it accidentally disconnects in exploration. However, the connection requirements of these approaches might over-constrain the mission objective, resulting in reducted behaviors.

Besides, the third family of the approaches allows robots to disconnect and reconnect actively. De Hoog[19, 20] innovatively propose a role-based exploration framework, and extend it to cover communication-limited cases. Considering the base station, robots are divided into explorers and relays and coordinate through appointed rendezvous positions. The former is assigned to explore unknown environments, and the latter moves back and forth only to deliver information. Later, some work refines the framework. Andre [21] focus on the routing protocols required to share information. Cesare [22] presents an interesting feature that UAVs land and act as fixed relays when run out of battery. However, even if the role-based framework resolves the limited communication range, the periodic meetings will result in many information-less flights, constraining the exploration process.

Different from existing work, without base-station, our proposed framework considers robots equally. We expect them to disconnect actively for independent exploring but reduce information-less flight via our developed mission-based exploration strategy, resulting in efficient exploration in large-scale communication-limited environments.

III Environment Representation

To reduce the bandwidth requirements for transmission, we use the union of a series of star-convex polytopes to represent known free space. We use sampling method to generate star-convex polytope (Sec.III-A). Moreover, we extract meshes from these polytope as frontiers to represent the boundary of known and unknown space. When the free space updates, old frontiers are deleted efficiently (Sec.III-B). Then we cluster frontier meshes into frontier clusters (FC) (Sec.III-C). For better observation for robots, we attach a best viewpoint (VP) to each FC and further integrate viewpoints into super viewpoint (SVP) for decision-making (Sec.III-D). All SVPs and included information in them compose super frontier infomation (SFI), as listed in Tab. I.

TABLE I: Super Frontier Information

Symbol	Explanation
$F_i$	Frontier mesh with center $c_i$ and normal $n_i$
$F{C}_j$	Frontier Cluster with center $C_j$ and normal $N_j$
$V{P}_j$	Viewpoint of $F{C}_j$
$SV{P}_k$	Super viewpoint

III-A Star-Convex based Free Space Generation

Star-convex polytope is a specific polytope which can represent known free space by meshes, as shown in Fig.3(b).

We firstly construct a point set $S_{\text{star}}$ as the source for star-convex polytope generation by sampling in a local voxel map. We uniformly sample points in the cylindrical coordinate system whose origin locates at the position of the robot $P_r$ with radius equals to sensor range $R_{\text{sensor}}$. And the sampling angle range is within robot’s field of view. For each sampled point $P_s$, we cast a ray from $P_r$ to $P_s$. If the ray is unobstructed, $P_s$ is added to a point set $S_{\text{free}}$. Otherwise, if the ray hits obstacles, the first point hit obstacles is added to another point set $S_{\text{obs}}$.

Given point set $S_{\text{star}}=S_{\text{free}}\cup S_{\text{obs}}$, we take $P_r$ as origin and use the following sphere mapping function to flip all points in $S_{\text{star}}$ with radius $r$:

$$P^{\prime }=F(P)=P-P_r+2(r-{\Vert P-P_r\Vert }_2)\frac{P-P_r}{{\Vert P-P_r\Vert }_2}.$$ (1)

Then a convex hull of the flipped points is calculated and a star-convex polytope is determined by the points on the convex hull after sphere mapping inherently, as shown in Fig.3(a). For more details, we refer readers to our previous work [5]. A star-convex polytope is generated when the robot travels a certain distance. The union of a series of star-convex polytopes constitute known free space.

III-B Frontier Generation and Deletion

Figure 4: (a) We project mesh on a unit rasterized sphere and generate the AABB. (b) The query result. Green and red points are inside and outside a polytope, respectively.

We represent frontiers of the environment using the meshes of star-convex polytopes. To obtain these frontier meshes, we delete meshes whose all vertices belong to $S_{\text{obs}}$ and consider the rest meshes as the set of frontier $F$. We denote the purple meshes shown in Fig.3(c) as $F$. For each $F_i$, the center $c_i$ and the normal $n_i$ of it are calculated. As the normal has two directions, we choose the one satisfying $(P_r-c_i)\cdot n_i>0$.

When a new star-convex polytope is generated, frontier meshes inside free space should be deleted. To this end, we need efficiently query whether a mesh is in a polytope and thus propose MeshTable to query if a mesh is inside a star-convex polytope. As Fig.4 (a) shows, given a star-convex polytope, we firstly project all its meshes to a unit rasterized sphere. For each projected mesh, its axis-aligned bounding box (AABB) on the sphere can be obtained. Then each cell in the AABB with its corresponding meshes form a MeshTable. In other words, the MeshTable records which projected mesh each grid is covered by.

For a mesh $F_i$ to be queried, we project its center $c_i$ to the unit sphere and get the corresponding cell. Then, using the MeshTable, meshes corresponded to this cell can be retrieved. We connect vertices of each mesh with the origin of the polytope to formulate a tetrahedron. If $c_i$ is inside one of these tetrahedrons, $F_i$ is inside a star-convex polytope. A mesh is classified as lying outside free space and deleted if it is not inside any star-convex polytopes.

To speed up the query, we build a KD-tree of all star-convex polytopes’ origins. Then, we search within a radius $R$ centered at $c_i$ using this KD-tree, and obtain corresponding polytopes of $F_i$. If $F_i$ is judged as inside one of these polytopes using the above-mentioned MeshTable query, we delete it. The result of querying is shown in Fig. 4 (b).

III-C Frontier Mesh Clustering

To reduce the number of meshes for efficient decision-making, we cluster the frontier meshes. We consider the similarity between meshes from the following three aspects:

1. Tangential distance: $d_t(F_i,F_j)={\Vert (c_i-c_j)\cdot n_j\Vert }_2$,

2. Normal distance: $d_n(F_i,F_j)={\Vert (c_i-c_j)\times n_j\Vert }_2$,

3. Normal difference: ${\delta }_n(F_i,F_j)={\Vert (n_i-n_j)/2\Vert }_2$,

where $c_i,c_j$ and $n_i,n_j$ are the center and normal vector of $F_i$ and $F_j$, respectively. The above similarity criteria are hard to be described by a vector in N-dimensional Euclidean space requiring by most of cluster methods like K-means. So we choose spectral clustering[23], which only needs the similarity matrix between the data.

For spectral clustering, we need calculate a degree matrix $D$ and a similarity matrix $S$ firstly. To obtaion $D$, we connect meshes with their k-nearest euclidean-distance neighbors to form a graph, then the degree matrix of the graph is $D$. For $S$, based on the above criteria, we have:

$S={\left(exp(-s{(F_i,F_j)}^2/2{\sigma }^2)\right)}_{i,j=1\mathrm{\dots }J},$ (2)

$s(F_i,F_j)={\omega }_1{d}_t+{\omega }_2{d}_n+{\omega }_3{\delta }_n,$ (3)

where $s(F_i,F_j)$ is the weighted sum of above three distance and $\sigma$ is the preset parameter of Gaussian function. Given $D$ and $S$, We can finally get frontier clusters using spectral clustering. The clustering example is shown in Fig.3(c), where red numbers represent clusters of frontiers, and the positions of the numbers represent the center of clusters.

Input: Frontier cluters $F{C}_i$ contains frontier meshes $\{F_j,j=1,2,\mathrm{\dots },J\}$.

Output: Viewpoints $V{P}_i$.

1

2$N_i={\sum }_{F_j\in F{C}_i}{n}_j/J$;

3 $C_i={\sum }_{F_j\in F{C}_i}{c}_j/J$;

4 $𝐕=\mathrm{𝐜𝐲𝐥𝐢𝐧𝐝𝐫𝐢𝐜𝐚𝐥𝐒𝐚𝐦𝐩𝐥𝐞}(N_i,C_i)$;

5 $s_{best}=0$;

6

7foreach $v_k\in 𝐕$ do

8 $d\theta =\mathrm{𝐚𝐜𝐨𝐬}(\frac{(s_k-C_i)\cdot N_i}{{\Vert s_k-C_i\Vert }_2})$;

9 $dR=\mathrm{𝐚𝐛𝐬}({\Vert s_k-C_i\Vert }_2-R_{opt})$;

10 $scor{e}_k={\omega }_{\theta }\cdot d\theta +{\omega }_R\cdot dR$;

11 if $scor{e}_k>s_{best}$ then

12 $s_{best}=scor{e}_k$;

13 $V{P}_i=v_k$;

14

15 end if

16

17 end foreach

18

Algorithm 1 Viewpoint Generation

III-D Viewpoint and Super Viewpoint Generation

To observe frontier cluster at an appropriate angle and distance, we generate the best viewpoint for each FC by the method presented in Algorithm 1.

As Algorithm 1 presents, we firstly calculate the normal $N_i$ and center $C_i$ by averaging all the meshes blong to $F{C}_i$. Then we score all the points sampled from cylindrical coordinates whose origin locates at $C_i$. The point with smaller angle error to $N_i$ and colser to appropriate distance $R_{opt}$ has higher weighted score. An example of generated viewpoints is shown in Fig.3(c).

To further reduce the scale of decision-making problem, for viewpoints contained in the same sphere with a given thresholding radius, we integrate them as a super viewpoint $SVP$, as Fig.3(c) shows. Finally, we get $SVP$, each of which consists of $J$ frontier clusters $\{F{C}_j,j=1,2,\mathrm{\dots },J\}$ with viewpoint $\{V{P}_j,j=1,2,\mathrm{\dots },J\}$. All the new generated part of SFI will be stored in the Environment Library.

IV Mission-based Exploration

In this section, we describe an efficient multi-robot exploration strategy with a proposed mission-based protocol. We divide the process of collaborative exploration into two phases: Joint Meeting and Lonely Exploration, corresponding to the Meeting and Local Handler shown in Fig. 2.

IV-A Mission-based Protocol for Multi-robot exploration

We expect robots to move independently for exploring and meet jointly for sharing information, even in the absence of global communication. We define each appointed rendezvous as a mission for robots, including meeting position and time. To achieve our expectation, we develop a centralized planner (see Sec.IV-B) in phase Joint Meeting for mission decision, and further propose a decentralized planner (see Sec.IV-D) in phase Lonely Exploration for path planning.

At the beginning of each exploration task, robots are assigned a mission in the first meeting, as shown in Fig. 5 (a). Then, robots spread out to explore independently. As the environment explored and new frontiers generated, each robot constantly replans by the decentralized planner, which guarantees the appointed meeting position is arrived on time.

However, actually, robots may accidentally meet in the Lonely Exploration phase. For this case, we define an extra rule: if robots with the same mission meet accidentally, they decide a new mission and only one of them keep the old mission. An example is shown in Fig. 5 (b), robots (blue and green) with the same mission (pink) meet accidentally and share information. There is no need for all of them to arrive at scheduled position in pink mission. Thus they decide a mission between them (purple) and only let the blue robot meet with the red robot. By this way, the green robot can spend more time on exploration and improve the efficiency.

Based on the above mission-based protocol, robots explore the whole environment by meeting sequentially with limited communication range, as shown in Fig. 5 (c) and (d).

Besides, in each meeting, robots autonomously cooperate to complete information aggregation. All robots send their message, including generated free space information and SFI, to a ”host” robot. The host robot merges them and eliminates frontiers that are inside the union of all free space, with similar process to Sec.III-B. Then the merged map information is send back to all meeting robots.

Figure 5: The process of a simple demo exploration based on our protocol. Robots are with the colors red, blue, and green, and missions are pink and purple. Grey cells mean unexplored. and light blue cells mean explored.

IV-B Centralized Optimal Decision Planning

After information aggregation, by formulating a constrained integer optimization problem, the host decides a mission and assigns it, including the position and time of the next rendezvous. We consider the following rules:

1. Robots start from their positions, cross intermediate SVPs and reach a rendezvous position.

2. Each intermediate SVP is crossed only once.

To perform optimization, a motion cost between two points is required. It is calculated by:

$$T_m(p_i,p_j)=\frac{\text{Length}(p_i,p_j)}{v_{\text{max}}},$$ (4)

where the path length is estimated by A* search on posegraph similar to [24], which is not the point of our paper.

We then let $R_c=\{1,\mathrm{\dots },n\}$ and $S_c=\{n+1,\mathrm{\dots },m\}$ denote positions of robots and super viewpoints and define three binary decision variables:

• $x_{ij}^k$: set to 1 iff robot $k$ goes from node $i$ to $j$

• $y_i^k$: set to 1 iff the node $i$ is crossed by robot $k$

• $t_i$: set to 1 iff the node $i$ is the rendezvous position

The centralized planning problem is formulated as follows:

$\underset{x_{ij}^k,y_i^k,t_i,\overline{t_i}}{\min }J={\displaystyle \sum _{i\in N_c}}{\displaystyle \sum _{j\in S_c}}{d}_{ij}{\displaystyle \sum _{k\in R_c}}{x}_{ij}^k,$

$s.t.\overline{t_i}=1-t_i,\forall i\in S_c,$ (5)

${\displaystyle \sum _{i\in N_c}}{x}_{ih}^k=y_h^k,\forall k\in R_c,h\in S_c,$ (6)

${\displaystyle \sum _{k\in R_c}}{\displaystyle \sum _{j\in S_c}}{x}_{hj}^k=1,\forall h\in R_c$ (7)

${\displaystyle \sum _{j\in S_c}}{x}_{hj}^k\overline{t_h}=y_h^k\overline{t_h},\forall k\in R_c,h\in S_c,$ (8)

${\displaystyle \sum _{j\in S_c}}{x}_{hj}^k{t}_h=0,\forall k\in R_c,h\in S_c,$ (9)

${\displaystyle \sum _{k\in R_c}}{y}_h^k\overline{t_h}=\overline{t_h},\forall h\in R_c,$ (10)

${\displaystyle \sum _{k\in R_c}}{y}_h^k{t}_h=n{t}_h,\forall h\in R_c,$ (11)

${\displaystyle \sum _{i\in S_c}}{t}_i=1,$ (12)

where $N_c=R_c\cup S_c$ and the cost $d_{ij}$ of crossing from node $i$ to node $j$ is calculated by $d_{ij}=T_m(p_i,p_j)$. Eq.(7) means each robot starts from their current positions. Eq.(9) and Eq.(11) mean that robots arrive at the viewpoint which is chose as rendezvous position, and Eq.(8) and Eq.(10) mean that other viewpoints is crossed by a robot once. Eq.(12) means that rendezvous position is unique.

IV-C Hierarchical Sub-optimal Decision Planning

Actually, routing problem is commonly considered after rendezvous position is fixed. Thus, optimizing rendezvous variables $t_i$ and path planning variables $\{x_{ij}^k,y_i^k\}$ jointly is difficult and we plan to take it as future work. In this section, we aim to develop a hierarchical approach by firstly determining the rendezvous position and then solving a simplified problem. Firstly, we define the distance between a node and robots as

$$d(p_v)=\sum _{k\in R_c}{T}_m(p_v,p_k)$$

where $p_v$ and $p_k$ is positions of node $v$ and robot $k$. Then we have following options to determine the meeting position:

1. Furthest-Meeting: take the node $v={\text{max}}_{v\in N_c}d(p_v)$ as the rendezvous position.

2. Nearest-Meeting: take the node $v={\text{min}}_{v\in N_c}d(p_v)$ as the rendezvous position.

3. Shortest-Meeting (Optimal): retrieve each node $i$, assume $t_i=1$ and conduct optimization to get optimal cost $J_i$. Then select the node $v={\text{min}}_{v\in N_c}{J}_v$ as rendezvous position.

Each of these methods can simplify formulated problem. In Sec.V, we compare the performances of using these methods and choose the Furthest-Meeting for best balancing efficiency and optimality.

As the rendezvous position is determined, the decision planning problem turns into a vehicle routing problem (VRP) [25]. We firstly use a heuristic function for initial path search and then utilize meta-heuristics method for local route search. In detail, from the positions of robots, we extend paths by iteratively adding the cheapest arc to the routes. In this way, we obtain an initial solution efficiently. Finally, we adopt the extended guided local search (EGLS) algorithm [26] to find an improved solution.

Until now, we have determined a rendezvous position $P_c$ and some paths $\mathrm{\Psi }=\{1,\mathrm{\dots },n\}$ for robots, where ${\mathrm{\Psi }}^k=\{i|y_i^k=1\}$. Fig. 6 shows the paths by using the Furthest-Meeting method. We then choose the maximum cost of paths as the basic time $T_b$ and set $T_e$ as extra time for exploration. Besides, to guarantee robots have enough time to rendezvous sequentially, the rendezvous time $T_c$ is:

$T_c=T_e+\text{max}(T_b+T_{cur},T_l^1+T_m(P_l^1,P_c),$ (13)

$\mathrm{\dots },T_l^n+T_m(P_l^n,P_c)),$

where $(P_l^k,T_l^k)$ is the last mission of the robot $k$ and $T_{cur}$ is the current time.

Figure 6: Planned path using the Furthest-Meeting method.

IV-D Decentralized Path Planning for Single Robot

After the mission and paths are assigned to robots, they spread out to explore independently. Meanwhile, as environment is explored and new SVPs are generated, each robot continuously replans paths to cross some SVPs and arrives at the next rendezvous positions on time. Furthermore, to alleviate repetitive exploration, we introduce penalties to the area that is assigned to other robots for exploring.

For a single robot $r$, we let $P_r$ be the position of it, $P_m$ be the next appointed meeting position, and $S_d$ be the set of SVPs. Then, we define the penalty $p_i$ of node $i$:

where ${\mathrm{\Psi }}^k$ is the path assigned to the robot $k$.

Finally, we formulate the decentralized path planning as

$\underset{x_{ij},y_i}{\min }J={\displaystyle \sum _{i\in N_d}}{\displaystyle \sum _{j\in P_m\cup S_d}}{d}_{ij}{x}_{ij}+{\displaystyle \sum _{i\in P_m\cup S_d}}{p}_i{y}_i,$

$s.t.{\displaystyle \sum _{i\in N_d}}{x}_{ih}=y_h,\forall h\in P_m\cup S_d,$ (14)

${\displaystyle \sum _{j\in S_d}}{x}_{hj}=y_h,\forall h\in P_r\cup S_d,$ (15)

${\displaystyle \sum _{j\in S_d}}{x}_{hj}=0,h\in P_m,$ (16)

$y_h=1,\forall h\in P_r\cup P_m,$ (17)

${\displaystyle \sum _{i\in N_d}}{\displaystyle \sum _{j\in P_m\cup S_d}}{d}_{ij}{x}_{ij}\le T_m-T_{cur},$ (18)

where $N_d=P_r\cup P_m\cup S_d$, $T_m$ is the scheduled time of next meeting, and $T_{cur}$ is the current time. Note that adding penalty ${\sum }_{i\in P_m\cup S_d}{p}_i{y}_i$ is to avoid robot exploring areas that are assigned to other robots. Eq.(14) and Eq.(15) provide constrained relationship between $x_{ij}$ and $y_i$. Eq.(16) denotes that the robot arrives at meeting position and does not leave. Eq.(17) means that the robot must start from its current position and end with the meeting position. Eq.(18) means that the robot is guaranteed to arrive meeting in time.

The decentralized path planning problem can be considered as a variant of capacitated vehicle routing problem (CVRP) [25]. While a robot moving, it utilizes the latest planned path as an initial solution and refine it using EGLS.

V Experiment

In this section, we conduct various simulation comparisons and real-world experiments to validate our proposed framework and present its advanced performance. As for multi-robot autonomous navigation, we use EGO-Swarm [27] to generate smooth and safe tajectories.

V-A Comparisons and Benchmark

V-A1 Bandwidth Comparisons

Figure 7: Bandwidth comparision of environment information used to drive exploration using GMM and our method.

Figure 8: The process of a exploration experiment with three quadrotors. Areas in different colors denote the region explored by different robots.

In this part, we compare bandwidth cost with GMM-based methods mentioned in Sec.II-A. In GMM method, point cloud $Z$ is modeled as $J$ normal distributions. According to the method and parameters described in [1], we take $J=|𝒵|/R_c$ with $R_c=160$ to yield good performance. With the same frequency, we compare the bandwidth of data volume of the environment represented by GMM and our method when the data is transmitted over the network. We test with different obstacle densities (percent by volume) and sensor ranges. As the result shown in Fig. 7, the bandwidth cost of our method is lower than the GMM method in all cases, especially for dense obstacles and large sensor range.

V-A2 Meeting Position Decision Comparisons

We compare three methods of meeting position selection as mentioned in Sec.IV-B. We simulate three cases: three robots with 30-35 SVPs, six robots with 45-60 SVPs, and ten robots with 100-120 SVPs. Each experiment is conducted 20 times in 100m x 100m environments with 100-150 obstacles. Fig. 9 shows the cost $J$ and solving time $t$ of three methods. As shown, the method with minimum cost consumes the most time, while the Furthest-Meeting method better trade-off between solving time and cost.

Figure 9: Solving time and cost comparisons between three different meeting place selection strategies.

Figure 10: Simulation environment and trajectories of three drones

V-A3 Strategy Benchmark

We conduct various simulated experiments to compare our method with Burgard’s [8] and Rooker’s [16] methods. They are representative works of exploration without communication constraints and with continuous connection requirements, respectively. We simulate several environments with obstacles, shown as Fig. 10. The sensor range and communication range are set to $10m$ and $3m$, respectively. We test with different building sizes and robot numbers, with four criteria including exploration time, repeated exploration proportion, independent exploration proportion, and length of trajectories. The results are shown in Tab. II and Tab. III. According to the statistics, our proposed method outperforms in exploration time, and efficiently reduces repeated exploration in all cases, especially in large-scale environment.

Figure 11: Generated star-convex polytopes in a real-world experiment.

TABLE II: Robots Number Benchmark

Scenario	Method	time(s)	repeated(%)	independent(%)	$l_{traj}$(m)
	Ours	440	22.2	61.1	401
#Robots=2	Burgard’s[8]	683	63.6	80.1	663
	Rooker’s[16]	1581	98.1	98.7	1439
	Ours	397	20.0	36.5	351
#Robots=3	Burgard’s[8]	492	80.9	89.7	475
	Rooker’s[16]	1337	96.8	95.4	1233
	Ours	403	20.3	29.5	309
#Robots=4	Burgard’s[8]	451	63.5	59.2	422
	Rooker’s[16]	1107	95.7	94.1	907

TABLE III: Environment Size Benchmark

Scenario	Method	time(s)	repeated(%)	independent(%)	$l_{traj}$(m)
	Ours	118	20.1	60.1	109
$2500m^2$	Burgard’s[8]	139	63.6	81.8	131
	Rooker’s[16]	128	98.1	99.2	122
	Ours	283	20.0	55.3	271
$5500m^2$	Burgard’s[8]	398	80.9	89.2	372
	Rooker’sk[16]	801	98.2	97.7	753
	Ours	440	22.2	61.1	401
$10000m^2$	Burgard’s[8]	683	70.3	79.3	663
	Rooker’s[16]	1581	96.7	95.4	1439

V-B Real-World Experiment

Real-world experiments are presented on both UGVs and UAVs platforms, as shown in Fig. 12. Each of these robots is equipped with a lidar-inertia localization module and a multi-robot planning module. They are deployed in a large underground parking lot for exploration.

In the $50m\times 30m$ UGV testing area, we conduct experiments with a 2.5m communication range and a 5m sensor range. In the $60m\times 40m$ UAV testing area, we set a 4.5m communication range and an 8m sensor range. In all experiments, our proposed framework can drive multi-robot the exploration efficiently under communication limits. We refer readers to the video for more information. As shown in Fig. 11, our generated star-convex polytopes cover the whole explored environment. One of the experiment processes is shown in Fig. 8. In this experiment, 3 UAVs explore coordinately with a max velocity of 1m/s. Even if without global communication, they finish the exploration in 250s. For comparison, we also conduct a single UAV exploration. However, the UAV fails to accomplish the task after it runs out of battery after 8min operation.

Figure 12: Different platforms used for real-world experiments.

VI Conclusion

In this paper, we develop a framework for multi-robot exploration under communication limits. To reduce transmission bandwidth, we utilize star-convex polytopes to represent explored free space and incrementally update SFI to drive exploration. To coordinate without global communication, we introduce a mission-based protocol for robots to explore independently and rendezvou to share information. Future works will be extended to the multi-robot exploration considering localization drift. Robots will plan to actively improve localization quality. Avoiding representing free space via a single occupancy map, we can conduct loop closures without intractable volumetric map and frontier fusion.