Multi-robot rendezvous and exploration are fundamental challenges in the domain of mobile robotic systems. This paper addresses the coordination problem of enabling multiple robots to eficiently converge on a common location within an initially unknown and communicationrestricted indoor environment. The robots start from distinct locations with no prior knowledge of the environment's layout or any pre-established meeting point. Communication is only possible after rendezvous, adding an extra layer of complexity. In this context, we propose a novel approach that integrates exploration and rendezvous into a unified strategy, hence bridging the gap between the two. Traditionally, exploration has been focused on rapidly mapping the environment, often leading to suboptimal rendezvous performance in later stages. Our method adapts standard frontier-based exploration techniques, prioritizing frontiers not only for map expansion but also for rendezvous opportunities. We introduce a mechanism that allows robots to "forget" previously explored regions, redirecting their attention to unexplored areas and enhancing rendezvous likelihood. To evaluate our approach, we conduct experiments in realistic 3D simulations using ROS, showcasing its efectiveness in achieving faster rendezvous times compared to conventional exploration strategies while maintaining a comparable level of environmental coverage.
CEUR ceur-ws.org
Multi-robot rendezvous is a coordination problem characterizing many multi-robot systems (MRS) where mobile robots must eficiently travel to or in the immediate vicinity of a common location in a shared environment.
evaluated by the total time or distance taken for all robots to reach the meeting point, the smaller the better. These metrics are often interpreted as proxies for both energy consumption and quality of service.
Computing and executing eficient rendezvous strategies represent key components in MRS application domains where robots need to physically meet to share collected information or collaborate on some localized task. Distributed data-gathering ofers many settings where multi-robot rendezvous is required or can play a fundamental role. nEvelop-O
2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Examples include autonomous exploration [
In this scenario, the rendezvous problem is augmented by the dificulty of online
exploration, namely the problem of building a complete and accurate map of an initially
unknown environment. Exploration is customarily performed by steps. (i) The robot
identifies a set of promising candidate locations in the already mapped portion of the
environment. (ii) Among them, the robot selects the most promising one, computing
utilities and costs of taking perceptions along the way to that location. (iii) Upon
selection, the location is reached and the obtained perceptions are integrated into the
partial map of the environment. The process then repeats from (i) until a termination
condition is met (often a threshold over the percentage of the explored area). When a
multi-robot team is involved, each robot can carry out its exploration independently,
or they can coordinate by communicating with each other, and exchanging maps and
plans [
Methods for multi-robot rendezvous typically leverage pre-determined coordination
strategies among robots (pre-established rendezvous areas, biases applied to strategies
to search for others, etc.) or execute online search strategies in a commonly known
map to meet others. One distinction among existing approaches can be made between
symmetric and asymmetric rendezvous. In symmetric rendezvous, all robots have the
same role in seeking a meeting with others. In the asymmetric case, instead, some robots
can be explorers, while others are relays, i.e., they have to meet and transfer knowledge
acquired by other robots to each other or to a base station. Another distinction is between
intentional rendezvous and accidental rendezvous. The former ones happen when the
meeting is already scheduled among agents following some kind of coordination. The
latter ones take place without a pre-arrangement. Other approaches undertake an ofline
study of the problem, by deriving theoretical properties of the optimal solution from the
specific geometrical features of the environment [
Multi-robot rendezvous and exploration have been studied together, mainly as
alternating phases that robots undergo in the scope of a given task. Often the two phases of
exploration and rendezvous are mutually exclusive; when the robots are exploring, their
interest is to acquire new knowledge; when the robots decide to rendezvous, they travel
to a location in the mapped area. This decoupling between the two phases can introduce
suboptimal performance, as robots are forced to alternate between the two behaviors
in a coordinated way. The work of [
In this work, we study how to address rendezvous and exploration simultaneously in a
multi-robot system. Importantly, we investigate how standard frontier-based techniques
for exploration can be extended to tackle both problems. Frontier–based exploration
strategies are widely used as they are simple yet efective, allowing robust exploration in
heterogeneous contexts. The inherent greedy nature of frontier-based exploration (see
(i)-(iii) above) results in quickly mapping those regions where the most free space lies,
leaving behind portions of the environment that are less informative. As a consequence
of this fact, robots quickly explore the larger portion of the map; after that, they spend
a considerable amount of time filling the gaps of the not-selected frontiers. As noted
in [
We consider a team of homogeneous robots equipped with the same perception, navigation, and communication capabilities. We assume a strongly limited communication model: each robot has a communication range of radius and, to exchange any information, two robots must be inside each other’s range and have an unobstructed line of sight. Each robot starts from a random location, unknown to the others, in a given environment whose map is initially unknown. Our objective is to have the robots form a connected group so that, from that moment on, they can collectively plan and navigate in the environment while keeping a formation.
Formally, we define the rendezvous condition by requiring that the locations occupied by the team members satisfy a hard and a soft constraint. The hard constraint requires the robots to form a connected configuration as per the communication model described above (so each robot should, in principle, be able to communicate with another one in a multi-hop fashion). The soft constraint requires that robots should be close to each other, to navigate in a formation. Ideally, this requirement should enforce a maximum distance between the locations of any pair of robots. However, setting it as a hard constraint to reach a rendezvous would in many cases prevent the problem’s feasibility. Indeed, with many robots and in environments that do not ofer open-area regions, connected groups of robots might not find a way to maneuver into a joint configuration that, without collisions, realizes the required mutual uniform-distance formation. For this reason, in our method, we seek this condition as much as possible while allowing for its violation when no other option is available.
Our proposed method is based on extending a standard frontier-based exploration
strategy [
Using this framework, the robot aims to reach the boundaries of its current map, ideally without going back on its steps but continuously moving forward, until the whole environment is mapped. In our method, we bias exploration by introducing an information decay mechanism on the mapping process so that the robot is also driven to go back on its steps, following the intuition that this backtracking mechanism will promote accidental rendezvous among robots.
To do so, we keep track of the exploration trace of the robot, i.e., the area around the trajectory of the robot during the exploration run. An example of that area is shown in Figure 1. The exploration trace is obtained by taking track of an ordered set of robot poses from its trajectory, sampled at a given frequency from the global robot trajectory. We use the communication range as the width of each pose, centered around the robot , thus creating a circular pattern of radius around each pose.
We create a new set of frontiers ∈̄ ̄ that is obtained by using an information decay mechanism on the exploration trace. More precisely, we retain a subset of the robot exploration trace containing the ≤ most recent robot poses. Each pose is characterized by a timestamp indicating when it was obtained; poses are removed after a time is passed after their acquisition. When a pose is removed we artificially create a new frontier ∈̄ ̄ as the contour of the diference of the area before and after the removal of the pose. An example of this mechanism is shown in Figure 2, where such artificial frontiers are highlighted in dashed red.
As a result of this, while in a standard frontier-based exploration the robot selects the next most promising location from a set of frontiers ℱ = , in our method the robot selects the most promising location from ℱ = ∪ .̄ In this way, the robot is pushed to partially backtrack on its steps to revisit parts of the environments that have already been explored.
In this paper, we rank frontiers according to a linear combination of their distance
from the current position of the robot, and their length, similar to what is proposed in [
When two or more robots are within their sensing range , they join a common cluster. In each cluster, one robot is elected as a leader, while the other robots are termed followers. The robots’ leader in a cluster continues the frontier-based exploration, while the others are tasked with following it. Each cluster formed by robots { , , …} has a set of frontiers ℱ = {ℱ1, ℱ2, …} and a shared exploration trace = { 1, 2, …} that is created by sharing the frontiers ℱ and the exploration trace for all robots ∈ .
The process of frontier and exploration-trace sharing is performed once each time a robot joins a cluster; after that, the knowledge is retained by the leader of the cluster. During this process, we remove also frontiers ̄ that overlap with the cluster exploration trace , as represents the area of the environment that was recently jointly explored by the cluster. An example of the process of merging two exploration traces and when the two robots merge in a single cluster is shown in Figure 3. After a cluster is formed, only the leader of the cluster adds frontiers to ℱ . The leader of the cluster is selected using a predefined agreement (e.g., the lexicographic order).
The robots belonging to the same cluster move together in a formation, following the cluster leader. If a robot loses connection with the remainder of a cluster, as an example because it was stuck after hitting an obstacle, the robot is removed from the cluster and resumes the frontier-based exploration task.
We implemented our method using ROS [
The experiments are performed in a complex indoor environment simulated in Gazebo, using 4 robots, and performing 6 random runs for each method and averaging the results. During each exploration run, we record the time required to perform a rendezvous among all robots, the size max | | of the largest cluster of robots, and the combined area explored by the robots . A run is ended when max | | is equal to the number of robots.
We used a Turtlebot3-burger robot with a speed of 0.3 m s−1 and with a 2D lidar with a
range of 10 m; each robot performs SLAM using Gmapping [
(and standard deviation) to complete the rendezvous changing the own navigation stack implemented using move base1. We simulate sensors and actuation errors of the robot, to have a setting that poses challenges similar to those of a real-world experimental run. We set a parameter of 333 s for the information decay of a robot pose in , and we consider a sensing range for multi-robot clustering and communication of 2.7 m. A new pose is added to the exploration trace each 2 s, and we add a frontier to ̄ after 9 poses have been collected (18 s). These parameters are experimentally set to have a set of frontiers ̄ that cover the robot path, without adding too many frontiers. We set = 1/4 .
Figure 4 shows the trajectories performed in two of the runs of FE (left) against our method (right). While with FE multiple robots cover the same parts of the environment, our method allows the robot to perform a shorter trajectory before meeting altogether.
Figure 5 shows the average time required by the four robots to perform a rendezvous, while Figure 6 shows the average time and standard deviation for forming a cluster of sizes 2, 3, and 4, respectively. It can be appreciated how our method not only allows the robot to perform a rendezvous in less time but also how our performance is more stable across diferent runs, with a lower standard deviation.
In this work, we have presented a framework for allowing an MRS to perform a rendezvous in a previously unknown environment while performing exploration. To do so, we have introduced a mechanism for information decay on top of a frontier-based exploration approach. Preliminary results are promising and clearly show how our framework allows the robot to perform a rendezvous in less time than a classic frontier-based exploration approach. Future results will involve a more exhaustive experimental evaluation.