Source-linked AI summary
Capturing a Moving Target on Star Graphs by Two Communicating Mobile Agents
Khaled Jawhar, Evangelos Kranakis
TL;DR
The paper studies two-robot capture of a moving target on an m-ray star, where ray structure and limited knowledge complicate search. It analyzes F2F and S/R strategies across knowledge settings, finding that S/R’s asymptotic benefit depends on ray parity and that lower bounds remain an open gap.
Problem
Moving-target capture on m-ray stars, especially under asymmetric communication and different levels of target knowledge, is relatively unexplored.
Source: §1 · p. 1Method
The paper designs two-robot search strategies under F2F and S/R communication and analyzes NoDistance, NoSpeed, and NoKnowledge settings.
Source: §1 · p. 1Results
S/R offers no asymptotic improvement over F2F for even m, while for odd m it reduces the exponent in u from m+3.
Source: §1.5 · p. 3Takeaways & Limitations
Ray parity and communication model influence competitive ratios, with odd-ray symmetry breaking enabling an S/R improvement.
Source: §1.5 · p. 3, §3 · p. 7Obtaining a tighter lower bound that more closely matches the upper bound remains future work.
Source: §4 · p. 11
Abstract
from arXiv · showhide
We study a problem of searching for a mobile target in an $m$-ray star graph, a natural generalization of linear search to multiple directions. The target is placed adversarially on one of the rays and may move with constant speed. We investigate a two-robot setting, where cooperation and communication play a central role. We study two communication models: the Face-to-Face (F2F) model, where robots communicate only upon meeting, and the Sender-Receiver (S/R) model, where communication is asymmetric. We focus on the {\em away model}, in which the target moves {\em away} from the origin with speed $v<1$. We design search strategies that minimize the competitive ratio and analyze the problem under three knowledge assumptions: \emph{NoDistance}, \emph{NoSpeed}, and \emph{NoKnowledge}. For each setting, we derive upper bounds on the competitive ratio and for some cases, we derive the lower bound. Our results highlight how the number of rays and the communication model influence the competitive ratio.
1 Introduction
The introduction frames mobile-target search on an m-ray star as a problem combining multiple search directions with target motion, and studies how communication, prior knowledge, and ray parity affect competitive ratio. It sets out a two-robot analysis under F2F and S/R communication, several knowledge settings, and upper and lower bounds.
1.1 Problem Formulation and Objectives
- The study aims to quantify how initial knowledge, communication constraints, and ray parity affect two-robot competitive ratios for capturing an oblivious moving target.The three settings are NoDistance, NoSpeed, and NoKnowledge.Source: §1.1 · p. 1
1.2 Context and Motivation
- The paper addresses moving-target capture in star graphs, a comparatively less explored setting, and examines how S/R communication and ray parity relate to performance.It motivates S/R with heterogeneous systems where only one agent may have a long-range transmitter or beacon.Source: §1.2 · p. 2
1.3 Model, Preliminaries, and Notation
- The model has m infinite rays and two unit-speed robots; an away-moving target has speed v<1, and the offline benchmark captures it in time u·d.NoDistance means known v and unknown d; NoSpeed means known d and unknown v; NoKnowledge means neither is known.Source: §1.3 · p. 2
1.4 Related Work
- Related work spans line, tree, and star-graph search, while this paper examines two-robot moving-target capture on m-ray stars under F2F and S/R communication.The introduction identifies communication constraints, target dynamics, and partial knowledge as factors in strategy design and performance.Source: §1.4 · p. 2
1.5 Results of the paper
- For even m, S/R provides no asymptotic improvement over F2F; for odd m, it reduces the exponent in u from m+3.The introduction also reports constant upper bounds when speed is known, while NoSpeed and NoKnowledge introduce logarithmic overhead in u or M=max{d,u}.Source: §1.5 · p. 3
2 Searching for a Moving Target Using the F2F model
The F2F strategies search two consecutive rays in synchronized rounds, returning to the origin between rounds. Across NoDistance, NoSpeed, and NoKnowledge settings, the paper gives competitive-ratio upper bounds, with analyses that distinguish ray-count parity.
2.1 Overview of the Search Strategy
- In synchronized rounds, the robots search two consecutive, previously unexamined rays to a chosen depth, then return to the origin before expanding the search.The overview describes scaling the search radius by an exponentially increasing parameter sequence.Source: §2.1 · p. 3
2.2 NoDistance Away Model
- NoDistance uses equal search distances for both robots in each round, and Theorem 2.1 analyzes its competitive-ratio upper bound across even and odd ray counts.If neither robot finds the target, both return to the origin, move to the next pair of rays, and increase the distance.Source: §2.2 · pp. 3–4
2.3 NoSpeed Away Model
- NoSpeed has both robots guess the target’s speed with an increasing sequence, raising the guess after each unsuccessful round; Theorem 2.2 gives an upper bound for even m.The speed guesses are v_i = 1 − 2^-f_i, and each round explores two consecutive rays.Source: §2.3 · p. 4
2.4 NoKnowledge Away Model
- NoKnowledge has both robots increase guesses for target speed and initial distance after each unsuccessful round; Theorem 2.3 gives an upper bound for odd m.The guesses are v_i = 1 − 2^-f_i and d_i = 2^g_i; the proof also considers even m.Source: §2.4 · pp. 6–7
3 Searching for a Moving Target Using the S/R model
The Sender-Receiver model improves the upper bound over Face-to-Face communication for odd-ray stars, while even-ray symmetry prevents an improvement. The section gives strategies and bounds for NoDistance, NoSpeed, and NoKnowledge settings.
3 Searching for a Moving Target Using the S/R model
- For even m, any deterministic Sender-Receiver algorithm can be simulated in Face-to-Face with the same competitive ratio; for odd m, the section gives a better Sender-Receiver upper bound.The odd-ray strategy uses an additional exploration iteration that gives the sender another chance to encounter and report the target.Source: §3 · pp. 7–8
3.1 NoDistance Away Model
- In NoDistance, two robots explore consecutive rays in increasing-distance rounds, and Algorithm 4 has competitive ratio at most the stated bound; when v=0, CR=10.If either robot finds the target, it travels with it; the sender informs the receiver when the sender captures it.Source: §3.1 · p. 8
3.2 Lower Bound for the NoDistance model, when the target is static
- The NoDistance lower-bound analysis adapts a trajectory-speed technique from to the m-ray setting and derives a lower bound for the static-target case.The supplied theorem expression is incomplete, so its bound is not stated numerically here.Source: §3.2 · pp. 8–9
3.3 NoSpeed Away Model
- In NoSpeed, the robots use increasing guesses for target speed and explore consecutive rays until one catches the target; Algorithm 5 has the stated competitive-ratio upper bound.A missed iteration leads to a larger speed guess in the next round.Source: §3.3 · pp. 9–10
3.4 NoKnowledge Away Model
- In NoKnowledge, the robots increase both speed and distance guesses while exploring consecutive rays; Algorithm 6 has the stated competitive-ratio upper bound.The strategy catches the target in an iteration when its speed and initial distance are no greater than that round’s guesses.Source: §3.4 · pp. 10–11
4 Lower Bounds and Performance Gaps
The section establishes baseline lower bounds for capturing moving targets on m-ray star graphs and explains how target drift and unknown initial distance constrain search. It identifies tighter lower bounds as an open direction.
4 Lower Bounds and Performance Gaps
- CR ≥ 1 + m(1 + v) is given as a trivial moving-target lower bound because a deterministic strategy may need to explore all m rays.The bound is stated for moving targets in the worst case.Source: §4 · p. 11
- The baseline bound is CR(A) ≥ 1 + Ω(m(1 + v)) when target drift during sequential exploration of an unknown distance d is accounted for.For unknown d, geometric search radii must grow by a factor a ≥ 1 + v to catch up after traversing m−1 wrong rays.Source: §4 · p. 11
- The lower-bound argument compares online search with an offline robot that knows the target’s ray and uses an adversarial placement on the last ray explored.While robots clear the first m−1 rays, the target moves farther from the origin, increasing the distance the online strategy must cover.Source: §4 · p. 11
- Obtaining a tighter lower bound that more closely matches the upper bound remains an important direction for future research.Source: §4 · p. 11
5 Conclusion and future work
The paper studies two-robot capture of an oblivious moving target on an m-ray star graph under F2F and S/R communication, deriving algorithms and bounds across knowledge settings. Future work includes tighter lower bounds and extending the setting to multiple searchers.
5 Conclusion and future work
- The paper studies capturing an oblivious moving target on an m-ray star graph with two robots under F2F and S/R communication models.Source: §5 · p. 11
- The analysis considers different levels of target knowledge, and the authors report designing new algorithms and proving upper and lower bounds.Source: §5 · p. 11
- Future work includes improving lower bounds and extending the study to multiple searchers capturing an oblivious moving target in star graphs.Source: §5 · p. 11