Kubishi Research Group

Backlinks

  • Welcome
Home

❯

Publications

❯

Linear Search with Probabilistic Detection and Variable Speeds

Linear Search with Probabilistic Detection and Variable Speeds

  • cooperative-robots
  • online-algorithms
Jared Coleman, Oscar Morales-Ponce
To Appear at IWOCA 2025 - The 36th International Workshop on Combinatorial Algorithms
January 1, 2025
10.1007/978-3-031-98740-3_31
PDFPDF

Abstract

We present results on new variants of the famous linear search (or cow-path) problem that involves an agent searching for a target with unknown position on the infinite line. We consider the variant where the agent can move either at speed 1 or at a slower speed v ∈ [0,1). When traveling at the slower speed v, the agent is guaranteed to detect the target upon passing through its location. When traveling at speed 1, however, the agent, upon passing through the target's location, detects it with probability p ∈ [0,1]. We present algorithms and provide upper bounds for the competitive ratios for three cases separately: when p=0, v=0, and when p,v ∈ (0,1). We also prove that the provided algorithm for the p=0 case is optimal.


Created with Quartz v4.5.2 © 2025

  • GitHub
  • Discord Community