Overcoming probabilistic faults in disoriented linear search

DOI10.1007/978-3-031-32733-9_23MaRDI QIDQ6148081zbMATH OpenOpenAlexFDO

Authors Konstantinos Georgiou, Nikos Giachoudis, Evangelos Kranakis

Publication date 11 January 2024

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.15608

zbMATH Keywords

linear searchmobile agentsprobabilistic faults

Mathematics Subject Classification ID

Computer system organization (68Mxx) Communication complexity, information complexity (68Q11) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We consider search by mobile agents for a hidden, idle target, placed on the infinite line. Feasible solutions are agent trajectories in which all agents reach the target sooner or later. A special feature of our problem is that the agents are $p$-faulty, meaning that every attempt to change direction is an independent Bernoulli trial with known probability $p$, where $p$ is the probability that a turn fails. We are looking for agent trajectories that minimize the worst-case expected termination time, relative to competitive analysis. First, we study linear search with one deterministic $p$-faulty agent, i.e., with no access to random oracles, $pin(0,1/2)$. For this problem, we provide trajectories that leverage the probabilistic faults into an algorithmic advantage. Our strongest result pertains to a search algorithm (deterministic, aside from the adversarial probabilistic faults) which, as $po0$, has optimal performance $4.59112+epsilon$, up to the additive term $epsilon$ that can be arbitrarily small. Additionally, it has performance less than $9$ for $pleq0.390388$. When $po1/2$, our algorithm has performance $Theta(1/(1-2p))$, which we also show is optimal up to a constant factor. Second, we consider linear search with two $p$-faulty agents, $pin(0,1/2)$, for which we provide three algorithms of different advantages, all with a bounded competitive ratio even as $pightarrow1/2$. Indeed, for this problem, we show how the agents can simulate the trajectory of any $0$-faulty agent (deterministic or randomized), independently of the underlying communication model. As a result, searching with two agents allows for a solution with a competitive ratio of $9+epsilon$, or a competitive ratio of $4.59112+epsilon$. Our final contribution is a novel algorithm for searching with two $p$-faulty agents that achieves a competitive ratio $3+4sqrtp(1-p)$.

Cites work

• Better upper bounds for searching on a line with Byzantine robots
• Group search on the line
• scientific article; zbMATH DE number 4057247 (Why is no real title available?)
• More on the linear search problem
• On the linear search problem
• Online searching with turn cost
• Parallel searching in the plane
• Probabilistically faulty searching on a half-line (extended abstract)
• Rendezvous search when marks are left at the starting points
• Search on a line with faulty robots
• Searching for a one-dimensional random walker
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• Searching in the plane
• The theory of search games and rendezvous.
• Theory of optimal search
• Weighted group search on a line \& implications to the priority evacuation problem
• Yet more on the linear search problem

Cited in

(1)

• Overcoming probabilistic faults in disoriented linear search

This page was built for publication: Overcoming probabilistic faults in disoriented linear search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6148081)