Multirobot rendezvous with visibility sensors in nonconvex environments

Anurag Ganguli, Jorge Cortés, Francesco Bullo

Abstract

This paper presents a distributed control law for the multi-robot rendezvous problem in non-convex, simply connected environments. Unlike previous approaches that assume global visibility or convex spaces, the proposed Perimeter Minimizing Algorithm ensures that a group of agents, equipped only with local line-of-sight sensors, can gather at a single point without losing connectivity. By maintaining visibility constraints through geometric safe zones and utilizing a specialized proximity graph, the algorithm guarantees convergence while allowing for significant agent mobility. Simulations demonstrate the algorithm's robustness to sensor noise and asynchrony in complex floor-plan environments.

Introduction

The "rendezvous problem" is a fundamental challenge in multi-robot coordination: how can a group of independent agents gather at a single, common location? While this task is straightforward in open, convex fields where every robot can see every other robot, it becomes significantly more complex in real-world environments like office buildings or urban corridors. These non-convex spaces introduce walls and corners that can easily break the line-of-sight connectivity required for coordination.

The primary technical hurdle is connectivity maintenance. If two robots rely on line-of-sight sensors (such as LIDAR) to track one another, a single move behind a corner can result in a permanent loss of contact. This paper addresses the realistic scenario where robots have limited-range sensors and must navigate a maze-like environment without "breaking the chain" of the group's visibility graph.

The Perimeter Minimizing Algorithm

The authors propose the Perimeter Minimizing Algorithm, a distributed approach that relies on geometric constructions to ensure safety and progress toward the goal.

Constraint Set Generation

To prevent visibility loss, the algorithm calculates a convex "safe zone" for every pair of visible robots. These zones are defined such that if both robots remain within their respective sets, they are guaranteed to maintain line-of-sight in the subsequent time step. This geometric approach transforms a complex coordination problem into a series of local, constrained optimization tasks.

Geometric construction of visibility constraints used to define safe movement zones.

Key Components

  1. Robust Visibility: To account for sensor noise and the physical dimensions of robots, the algorithm operates on an "$\epsilon$-contraction" of the environment. By treating walls as slightly thicker than they are, the system creates a safety buffer that prevents grazing collisions or accidental visibility loss at corners.
  2. Locally-Cliqueless Visibility Graphs: Maintaining every possible visibility link is overly restrictive and hampers movement. The authors utilize a specialized proximity graph that prunes redundant edges. This allows robots more freedom to navigate around obstacles while ensuring the overall group remains a single connected component.
  3. Circumcenter Law: In each discrete time step, a robot calculates the intersection of all its movement constraints (from its neighbors and the environment) and moves toward the circumcenter—the center of the smallest enclosing circle—of the resulting feasible set.

Theoretical Guarantees

The convergence of the algorithm is proved using a Lyapunov function based on the perimeter of the relative convex hull of the robots. In a maze, the shortest path between two points is a geodesic that bends around corners rather than a straight line. The authors adapt the concept of a convex hull to this relative geometry, proving that the perimeter of this hull strictly decreases over time until all robots reach the same point.

Experimental Results

The algorithm was evaluated through extensive numerical simulations in a polygonal floor plan resembling a typical office layout. In a setup with 20 robots, the system consistently achieved rendezvous despite random initial positions and limited sensing ranges.

The three stages of multi-robot rendezvous: initial connected state, path evolution, and final gathering point.

Key findings from the simulations include:

  • Robustness to Noise: The robots successfully gathered in 90-100% of test cases even with 10% distance error and 5° angular sensor noise.
  • Asynchrony: The algorithm remains effective when robots operate on independent, unsynchronized clocks, a critical requirement for real-world distributed systems.
  • Computational Efficiency: With a complexity of $O(M^2 \log M)$ (where $M$ is sensor resolution), the algorithm is suitable for real-time implementation on standard robotic hardware.

Conclusion and Future Work

While the Perimeter Minimizing Algorithm provides a rigorous solution for simply connected environments, several avenues for future research remain. The current formal proof does not cover environments with "holes" (e.g., pillars or islands), although simulations suggest the algorithm may still perform well. Additionally, extending the theory to account for dynamic obstacles and complex vehicle dynamics (such as non-holonomic constraints in car-like robots) would further bridge the gap between theory and practical deployment.

Summary updated

BibTeX
@article{ganguli2006multirobot,
  author = {Anurag Ganguli and Jorge Cortés and Francesco Bullo},
  title = {{Multirobot rendezvous with visibility sensors in nonconvex environments}},
  journal = {IEEE Trans. Robotics},
  year = {2006},
  doi = {10.1109/tro.2009.2013493},
}
Figure