CS Paper Radar

Capturing a Moving Target on Star Graphs by Two Communicating Mobile Agents

Khaled Jawhar, Evangelos Kranakis

cs.DC ·submitted 2026-10-08 13:40 UTC · v2
theory

Abstract

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.

Comment
12 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Searching the Plane in the Segment Visibility Model

cs.DM cs.DC ·2026-11-02 ·Evangelos Kranakis
theory similarity 0.60
Abstract

We study deterministic search by $n \geq 2$ unit-speed robots starting at the origin of the Euclidean plane. We introduce the concept of \emph{segment visibility} whereby a stationary target $x$ at distance $d=\|x\|>0$ is discovered at the first instant $t$ when $x$ belongs to the segment joining a pair of robots at time $t$. Discovery time is compared with the omniscient optimum $d$. We distinguish two knowledge models according to whether the robots know $d$ in advance. For $n=2$ robots, in the \emph{known-$d$} model, we give a symmetric four-phase algorithm and prove that its competitive ratio is optimal: $1+\sqrt3+π/6$; the matching lower bound follows from the known-distance two-robot shoreline-search theorem through an explicit reduction to segment detection. For $n=2$ robots, in the \emph{unknown-$d$} model, a three-circle construction and a quantitative initial-path estimate yield the stronger lower bound $\sqrt3+π/6+\sqrt{17}/4 \approx3.286425990$, giving an explicit positive cost for not knowing the radius; we also analyze a feasible antipodal-diameter logarithmic-spiral algorithm with optimized ratio $8.928516954\ldots$, thus proving that the competitive ratio when $d$ is unknown is at least $ \sqrt3+π/6+\sqrt{17}/4 $ and at most $8.928516954\ldots.$ For $n \geq 3$ robots, the competitive ratio of finding the target is exactly $\sec (π/n)$ regardless of whether or not $d$ is known to the robots.

0.19

Collision-free Movement on Grids and Beyond

cs.MA cs.DS ·2026-09-25 ·Hendrik Molter, Meirav Zehavi
similarity 0.59
Abstract

We study collision-free movement problems on graphs, where the task is to coordinate a set of robots so that they reach a target formation satisfying a desired property while minimizing the total travel distance. This framework extends two classical models: (a) minimizing movement [Demaine et al., TALG '09, '14], which does not enforce collision avoidance, and (b) coordinated motion planning or multi-agent path finding [Eiben et al., SoCG '23, Deligkas et al., ICALP '24, among many others], where each robot is assigned an explicit target position. We focus on the setting where the target formation of the robots should be connected. We analyze the parameterized complexity of the problem with respect to the number of (main) robots and the total travel length on grid graphs and two natural generalizations thereof: planar graphs and unit disk graphs.

0.22

Evacuating from Eventually Emerging Targets on the Line

cs.DM ·2026-11-15 ·Konstantinos Georgiou, Caleb Jones, Liza Krupsky
theory similarity 0.57
Abstract · 52 pages

We introduce and study Eventually Emerging Linear Search, an online evacuation problem on the line that, to the best of our knowledge, has not been studied before. In this problem, $n$ unit-speed agents with wireless communication start at the origin and search for a hidden target at location $x$, where $|x|\geq1$, that becomes detectable at an unknown time $T$. Visiting $x$ before time $T$ reveals nothing, and the search terminates only when all agents have reached the target. We study two competitive measures. In the emergence-aware model, the target location becomes known to the offline algorithm at time $T$, giving cost $T+|x|$. In the fully-informed model, the offline algorithm knows $x$ from the beginning, giving cost $\max\{|x|,T\}$. For one agent, the optimal competitive ratio is $9$ under both measures, as in classical cow-path search. For two agents, we give an algorithm with competitive ratio $3+\sqrt6$ under both measures, and prove it optimal within the class of origin-separated algorithms, in which each agent performs strictly expanding origin-return excursions on a fixed half-line. We also prove the unconditional lower bounds $4.35$ and $4.38$ for the emergence-aware and fully-informed measures, respectively. These bounds are computer-assisted; we derive finite linear programming relaxations for arbitrary algorithms and certify their infeasibility using exact rational Farkas certificates. For three agents, we prove analytically the unconditional lower bounds $3.1014$ and $3.2823$ for the emergence-aware and fully-informed measures, respectively, and introduce a geometric three-peak family. Different parameter choices give the corresponding upper bounds $4.010599$ and $4.340445$. These bounds lie below the corresponding two-agent lower bounds, so a third agent provably improves both measures.

0.36

Dispersive Tree Agreements for Multi-Robot Coordination

cs.RO cs.MAmath.OC ·2026-10-22 ·Shashank A. Deshpande, Blake T. Edwards, Jonathan P. How
similarity 0.56
Abstract · 18 pages, 5 figures, 7 tables

Multi-robot coordination of nonlinear systems is naturally formulated as joint-space optimal control subject to joint constraints. Existing methods that approach joint optimality remain largely centralized and offline, while decentralized, real-time counterparts target safe navigation without pursuing the joint optimum. This paper develops a decentralized, real-time planner that approaches the joint optimum as an anytime process. We extend a recent single-robot framework that searches dispersive trees of forward-propagated commands to coordinate a multi-robot team near-optimally. We first show that the inter-robot coupling can be effectively replaced by some local constraints, under which locally grown dispersive trees contain a near-optimal agreement. It is this structure that the robots pursue by a negotiation driven by decentralized column generation. In the quiescent limit, this negotiation is shown to settle on a near-optimal agreement. Our real-time protocol, WarpWeaver, runs the negotiation asynchronously over a receding horizon and closes on quiesced agreements even when deadlines cut it short. In simulation, WarpWeaver reduces total travel time by up to 22% against centralized offline planners on the Dynobench suite and by up to 16% against a decentralized real-time baseline, and outperforms a task-specific planner on networked navigation. Hardware experiments on six robots planning onboard demonstrate real-world implementability.

0.16

Min-Max Uniform Circle Formation by Asynchronous Mobile Robots

cs.DC cs.CGcs.MA ·2026-10-04 ·Animesh Maiti, Prakhar Shukla, Subhash Bhagat
similarity 0.55
Abstract

Given a set of point robots $\mathcal{R}$ in the Euclidean plane and a target circle $\mathbf C$ enclosing all robot positions, the \textsc{Min-Max Uniform Circle Formation (MMUCF)} problem requires the robots to move to distinct positions on $\mathbf C$ such that the final configuration forms a regular $n$-gon while minimizing the maximum distance traveled by any robot. Uniform circle formation is a fundamental coordination task in swarm robotics with applications in perimeter monitoring, surveillance, boundary coverage, and pattern formation. The literature does not address the optimization of the maximum individual displacement during the formation process. In this work, we study the min--max versions of the circle formation and uniform circle formation problems, where the goal is to minimize the maximum distance traveled by any robot. We consider these problems under the $\mathcal{ASYNC}$ model, where robots are autonomous, anonymous, identical, homogeneous, oblivious, and silent, and operate under the \textit{Look--Compute--Move} model with non-rigid motion. We first give necessary conditions for a deterministic solution and then present deterministic, distributed, and collision-free algorithms that form a circle and a uniform circle in finite time while minimizing the maximum movement. The algorithms ensure that robots reach distinct positions on the circle and, in the uniform case, equally spaced positions on $\mathbf C$ under the considered model.

0.17

Emergence, Not Bandwidth: Physical Coupling and the Limits of Learned Multi-Agent Communication

cs.LG cs.MAcs.RO ·2026-09-28 ·Mihir Chauhan, Aniket Bera
similarity 0.55
Abstract

Rate-limited multi-agent teams raise three questions the emergent-communication literature has answered only empirically: what an optimal message should encode, what compression costs over a horizon, and when a learned protocol is unique enough for a teammate to read. We answer them for rate-limited Dec-POMDPs, then measure how far reinforcement learning falls short of the optimum. Our theorems fix what is achievable independently of any learner, so a gap between an engineered and a learned sender at the same bit budget is an optimization fact, not an information-theoretic one. We instantiate this on three MuJoCo arenas spanning zero, partial and rigid physical coupling, charging every condition exactly 2 bits per decision, and create the discriminating regime by closing a physical side channel within one arena, holding bodies, task and reward fixed. Communication value is governed by coupling: under rigid coupling through a shared object, no channel beats silence (+0.001 +/- 0.001, p = 0.982, n = 25), since proprioception already carries that information; without coupling, every condition solves the task; under partial coupling, the engineered 2-bit sender reaches an interquartile mean of 1.000 but the learned one reaches 0.482, indistinguishable from silence (p = 0.400, n = 25). With a shared alphabet, bandwidth cannot explain the gap. Warm-starting from an engineered receiver localizes the failure: the same channel reaches 0.857 versus 0.562 cold-started (p < 0.001), so it is neither representational nor one of maintenance; reinforcement learning fails to discover the protocol. Cross-play shows learned protocols are individually meaningful but mutually unintelligible: self-play 0.980 collapses to 0.144 across seeds, and our best constructed alignment leaves at least 77% of that gap. All headline results use 25 seeds per arena and seven published baselines at matched rate.

0.15

Lie Rarely, Lie Big: Stealthy Insider Attacks on LLM Robot Teams

cs.RO cs.MA ·2026-10-03 ·Sribalaji C. Anand, George J. Pappas
similarity 0.54
Abstract · Under review

When a team of robots delegates planning and mutual trust to LLM agents, a single compromised robot can corrupt the shared outcome. We study this threat in a grounded task: a multi-robot survey in which measurements can be verified against the physical world, but every verification costs budget that would otherwise advance the mission. We treat the compromised robot as a stealthy adversary in the system-theoretic sense: it is limited not by an energy bound but by the team's own detectors. We then derive two bounds. First, the probability that the adversary's reports are verified is bounded below in terms of the degrees in the communication graph and the verification budget. Second, the map error caused by any stealthy adversary is bounded above by the value of a linear program over the adversary's bias distributions; its solution is an exchange rate between stealth budget and damage: below a critical verification level the worst stealthy attack tells rare, full-magnitude lies on the records least likely to be verified, and above it the better purchase is small biases hidden in the noise. In experiments where the honest robots are LLM agents, both bounds hold at the budget the attack actually spent. The experiments also show that which records an LLM robot re-checks is unbiased, but how much it re-checks is unpredictable.

0.17

Search and Rescue on the Plane

cs.DM ·2026-08-12 ·Jared Coleman, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce
similarity 0.54
Abstract

We study a planar variant of the search and rescue problem whereby an agent starting at an arbitrary position $P_{θ,r} = (r\cosθ, r\sinθ)$ in the plane must locate an object at an unknown position on the positive $x$-axis and deliver it to the origin. Our main contribution is to characterize the optimal form of any competitive algorithm, derive closed-form expressions for the competitive ratio, and identify a critical angle $θ^* \approx 15.6^\circ$ which yields a phase transition to optimal competitive search and delivery in the following sense. For each angle $-π\leq θ\leq π$ we compute a checkpoint (landing position on the $x$-axis) where the agent must go first prior to initiating a search on the $x$-axis in order to optimize the competitive ratio of search and delivery. We show that if $|θ| \geq θ^*$ then the checkpoint is at the origin, while if $|θ| < θ^*$ then the agent should land at the checkpoint $(r \cdot k_{|θ|}, 0)$ on the $x$-axis, where $k_{|θ|}$ is a real number given by an explicit formula we present.

0.04