frontmatter 
title: Linear Search with Probabilistic Detection and Variable Speeds
venue: To Appear at IWOCA 2025 - The 36th International Workshop on Combinatorial Algorithms
doi: 10.1007/978-3-031-98740-3_31
date: 2025-01-01
authors:
  - "[[Jared Coleman]]"
  - Oscar Morales-Ponce
links:
  - https://arxiv.org/pdf/2505.09429
  - https://github.com/kubishi/code_multi_speed_cow
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."
tags:
  - cooperative-robots
  - online-algorithms

Linear Search with Probabilistic Detection and Variable Speeds

Jared Coleman, Oscar Morales-Ponce

To Appear at IWOCA 2025 - The 36th International Workshop on Combinatorial Algorithms · January 1, 2025 · doi:10.1007/978-3-031-98740-3_31 · arXiv · GitHub

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 · Updated