Linear Search by a Pair of Distinct-Speed Robots

Area of Science:

• Robotics and Artificial Intelligence
• Distributed Systems and Algorithms
• Operations Research

Background:

• Two mobile robots start at the same point on an infinite line, tasked with locating a stationary target at an unknown position.
• The search concludes when both robots reach the target.
• Robot communication occurs via wireless transmission or by physically meeting.

Purpose of the Study:

• To develop and analyze optimal search strategies for two mobile robots on a line.
• To minimize the worst-case search time, considering various robot speed ratios and communication models.
• To establish theoretical lower bounds for the search time.

Main Methods:

• Algorithm design for two distinct communication models: wireless and communication by meeting.
• Worst-case analysis to determine the maximum search time as a function of target distance.
• Derivation of lower bounds to prove optimality of proposed strategies.

Main Results:

• An optimal search strategy is proposed for the communication by meeting model, covering all speed ratios.
• For the wireless communication model, an optimal strategy is presented for speed ratios up to a certain threshold.
• It is proven that beyond this threshold, wireless communication offers no advantage over communication by meeting.

Conclusions:

• The study provides optimal search algorithms and theoretical bounds for two-robot target search on a line.
• The effectiveness of wireless communication is limited to specific robot speed ratios.
• The findings extend previous research on robot search problems, offering a comprehensive solution for various scenarios.