Kubishi Research Group

Backlinks

  • Welcome
Home

❯

Publications

❯

Multimodal Search on a Line

Multimodal Search on a Line

  • cooperative-robots
  • online-algorithms
Jared Coleman, Dmitry Ivanov, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce
To Appear at SIROCCO 2025 - 32nd International Colloquium on Structural Information and Communication Complexity
January 1, 2025
10.1007/978-3-031-91736-3_15
PDF

Abstract

Inspired by the diverse set of technologies used in underground object detection and imaging, we introduce a novel multimodal linear search problem whereby a single searcher starts at the origin and must find a target that can only be detected when the searcher moves through its location using the correct of p possible search modes. The target's location, its distance d from the origin, and the correct search mode are all initially unknown to the searcher. We prove tight upper and lower bounds on the competitive ratio for this problem. Specifically, we show that when p is odd, the optimal competitive ratio is given by 2p+3+√(8(p+1)), whereas when p is even, the optimal competitive ratio is given by c: the unique solution to (c-1)^4 - 4p(c+1)^2(c-p-1) = 0 in the interval [2p+1+√(8p), ∞). This solution c has the explicit bounds 2p+3+√(8(p-1)) ≤ c ≤ 2p+3+√(8p). The optimal algorithms we propose require the searcher to move infinitesimal distances and change directions infinitely many times within finite intervals. To better suit practical applications, we also propose an approximation algorithm with a competitive ratio of c+ε (where c is the optimal competitive ratio and ε > 0 is an arbitrarily small constant). This algorithm involves the searcher moving finite distances and changing directions a finite number of times within any finite interval.


Created with Quartz v4.5.2 © 2025

  • GitHub
  • Discord Community