Algorithm for Patrolling Traversable Circle with Multiple Robots

Patrolling known environments is one of the fundamental tasks for robots, with broad applications in real-world scenarios such as security surveillance, border patrol, and facility monitoring. The problem has garnered significant attention in computational geometry and robotics research. The primary objective of robot patrolling is to ensure continuous and long-term coverage of a designated area, where efficiency is measured by idle time—the maximum time interval between consecutive visits to any point in the region. A shorter idle time indicates higher efficiency.

This paper introduces a novel model called the traversable circle, which consists of a circular boundary and an internal diameter that must be patrolled simultaneously. Unlike traditional models that focus solely on boundary or interior patrol, the traversable circle presents a more complex challenge due to the need for robots to coordinate their movements across both the circular perimeter and the diameter. The study explores efficient patrolling strategies for two and three variable-speed robots, analyzing geometric properties and proving the optimality of the proposed algorithms.

Problem Description and Related Work

The Traversable Circle Model

The traversable circle, denoted as CL, is defined as a circle C with radius 1 and a diameter L. Robots can move along either the circular boundary or the diameter, with additional directional choices at the intersection points of the diameter and the circle, referred to as path selection points. These points introduce complexity, as robots must decide whether to continue along the boundary or switch to the diameter.

The goal is to minimize the idle time, defined as the maximum time interval between consecutive visits to any point on the traversable circle. The challenge lies in balancing coverage of both the boundary and the diameter while accounting for variable robot speeds.

Existing Patrolling Algorithms

Two fundamental algorithms serve as benchmarks for patrolling problems: the partition algorithm and the cycle algorithm.

The partition algorithm is optimal for linear segments. It divides the segment into sections proportional to the robots’ speeds, with each robot patrolling its assigned section at maximum speed. The idle time for a segment of length L patrolled by k robots with speeds v₁, v₂, …, vₖ is given by 2L divided by the sum of their speeds.

The cycle algorithm is optimal for circular boundaries. It positions robots at equal intervals along the circumference, moving in the same direction at a uniform speed. The idle time for a circle with circumference C patrolled by k robots is C divided by the product of the number of active robots and their speed.

While these algorithms perform well in their respective scenarios, neither is sufficient for the traversable circle, which requires a hybrid approach.

Two-Robot Patrolling Strategies

Identical Maximum Speeds

When two robots have the same maximum speed v, the optimal strategy divides the traversable circle into two closed semicircles, each consisting of half the circumference and the full diameter. Each robot patrols one semicircle at maximum speed, ensuring continuous coverage. The idle time for this strategy is (π + 2)/v.

Optimality Proof:
Any alternative strategy either increases the idle time or fails to cover all points within the required interval. For instance, if robots switch between boundary and diameter patrol without forming closed loops, some regions experience longer idle times. The semicircular division ensures minimal idle time by leveraging the robots’ identical speeds.

Different Maximum Speeds

When robots have distinct speeds (v₁ > v₂), the patrol strategy must account for their differing capabilities. Three cases emerge based on the speed ratio v₂/v₁:

Low-Speed Ratio (v₂/v₁ ≤ 2/π):
The faster robot (a₁) assists the slower one (a₂) by covering part of the diameter. The idle time is (2π + 4)/(v₁ + v₂).
Moderate-Speed Ratio (2/π < v₂/v₁ ≤ (π + 2)/2π):
The faster robot patrols the boundary exclusively, while the slower robot handles the diameter. The idle time is 2π/v₁.
High-Speed Ratio (v₂/v₁ > (π + 2)/2π):
Both robots patrol separate semicircles, with idle time (π + 2)/v₂.

Optimality Proof:
No alternative strategy achieves a lower idle time. For example, if the faster robot attempts to cover both boundary and diameter without coordination, some regions remain underpatrolled. The proposed strategy ensures balanced coverage by dynamically adjusting patrol responsibilities based on speed ratios.

Three-Robot Patrolling Strategy

Extending the analysis to three robots introduces additional coordination challenges. The proposed algorithm adjusts robot speeds to optimize coverage:

Speed Adjustment:
• If v₃ < 2v₂/π, the middle-speed robot (a₂) reduces its speed to πv₃/2.

• If v₃ ≥ 2v₂/π, the slowest robot (a₃) increases its speed to 2v₂/π.

• If v₁ ≥ v₂(2 + π)/π, the fastest robot (a₁) reduces its speed to v₂(2 + π)/π.
Patrol Coordination:
• The fastest robot (a₁) alternates between boundary and diameter patrol, covering segments proportional to its speed.

• The middle-speed robot (a₂) continuously patrols the boundary.

• The slowest robot (a₃) oscillates along the diameter.

Optimality Analysis:
The idle time is minimized when the speed ratio is approximately v₁:v₂:v₃ ≈ 1:0.69:0.44. In this configuration, the idle time is 19/25 of that achieved by the partition algorithm, demonstrating significant efficiency gains.

Simulation and Experimental Validation

Extensive simulations validate the theoretical results. For two robots, idle times align with predictions across varying speed ratios. The semicircular division strategy consistently outperforms alternatives, particularly when speed disparities are large.

For three robots, the proposed algorithm achieves lower idle times compared to both partition and cycle algorithms. The optimal speed ratio (1:0.69:0.44) yields the best performance, with idle times up to 24% shorter than traditional methods.

Conclusion and Future Work

This study presents efficient patrolling algorithms for the traversable circle, proving optimality for two and three robots. The hybrid approach, combining partition and cycle strategies, ensures minimal idle time while accommodating variable robot speeds.

Future research directions include:
• Generalizing the algorithm for an arbitrary number of robots.

• Incorporating weighted regions to prioritize high-importance areas.

• Exploring dynamic environments where the traversable circle changes over time.

The traversable circle model bridges the gap between boundary and interior patrol, offering a versatile framework for real-world applications.

doi.org/10.19734/j.issn.1001-3695.2024.04.0128

Was this helpful?

0 / 0