CS Paper Radar

Search and Rescue on the Plane

Jared Coleman, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce

cs.DM ·submitted 2026-08-12 13:22 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Evacuating from Eventually Emerging Targets on the Line

cs.DM ·2026-11-15 ·Konstantinos Georgiou, Caleb Jones, Liza Krupsky
theory similarity 0.59
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

Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement

cs.AI ·2026-09-06 ·Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng, Trung Thanh Nguyen, Phuong Khanh Nguyen +1 more
benchmarktheory similarity 0.58
Abstract

Bounded-suboptimal search seeks a solution within a factor $w$ of optimal while reducing search effort. Focal Search (FS) uses heuristic guidance within FOCAL, the frontier nodes eligible under the threshold $w f_{\min}$, but its deterministic policy may leave $f_{\min}$ unchanged for many expansions. We introduce Probabilistic Focal Search (PFS), which follows the FS guided choice with probability $p$ and expands a minimum-$f$ OPEN node with probability $1-p$. The latter branch encourages the lower bound to advance, enlarging FOCAL and admitting nodes that may lead to feasible solutions. By balancing guidance and lower-bound advancement, this mechanism can reduce time to a bounded solution when progress is limited by delayed FOCAL admission. As a secondary transfer experiment, we apply the same scheduler to Dynamic Potential Search, yielding Probabilistic Dynamic Potential Search (PDPS). We benchmark PFS against FS on N-Puzzle, Pancake Sorting, and the Traveling Salesperson Problem (TSP), and evaluate its anytime extension on the Generalized Covering TSP (GCTSP), using multiple $w$ and $p$ values. Across these benchmarks, the largest gains occur when long $f_{\min}$ plateaus delay useful FOCAL admissions; in such settings, the probabilistic factor may reduce node expansions by about 90\% or more (e.g., on N-Puzzle and TSP). For the anytime algorithm family, Anytime Probabilistic Focal Search (APFS) outperforms all tested algorithms in evaluating anytime methods on GCTSP. We also observe that the benefit is smaller when the deterministic search already advances efficiently (e.g., Pancake Sorting), indicating that the probabilistic factor is most useful when FOCAL admission is a search bottleneck. The PDPS transfer shows that the mechanism also transfers to potential guidance, although its common-success effects remain domain- and bound-dependent.

0.20

Searching the Plane in the Segment Visibility Model

cs.DM cs.DC ·2026-11-02 ·Evangelos Kranakis
theory similarity 0.58
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

Strategic Facility Location in Euclidean Spaces

cs.GT cs.DS ·2026-09-04 ·Kim Thang Nguyen, Lucas Perotin, Bertrand Simon
similarity 0.57
Abstract

The strategic facility location problem is defined as follows: $n$ agents report their location in a metric space, and the objective is to design a \emph{mechanism} deciding the (possibly randomized) location of a facility such that agents have no incentive to lie about their position. We focus on the egalitarian cost, which means that the goal of the mechanism is to minimize the expected maximal facility-agent distance. Meanwhile, mechanisms must be \emph{truthful} (or \emph{strategyproof}): no agent may decrease their expected distance to the facility via lying on their location. Designing truthful mechanisms minimizing the approximation ratio is a well-studied problem, and the optimal solution is known for the real line. We focus in this paper on higher dimension Euclidean spaces, for which gaps remain between the best known lower and upper bounds. We first show that, maybe counter-intuitively, the problem is easier for two agents on the plane rather than on the line: the mechanism can exploit the additional dimension to prevent more efficiently agent lies. Based on this intuition, we devise lower bounds for $\mathbb R^d$ asymptotically matching the best known approximation factor of $2$ for large $d$. We also provide novel mechanism ideas, improving over the best known algorithms on the plane, and when the agents belong to $\mathbb R^d$ but the facility may use an additional dimension.

0.03

The logarithmic spiral is optimal for shoreline search: a computer-assisted proof

cs.CG math.OCmath.MG ·2026-09-21 ·Alexander Temerev
similarity 0.56
Abstract · 20 pages (13 of main text, then four appendices), 3 figures, 1 table

A ship starts at a point of the plane and moves at unit speed; it has to reach an unknown straight line, of which neither the distance nor the direction is known. The competitive ratio of a path is the supremum, over all lines, of the time at which the line is reached divided by its distance. Baeza-Yates, Culberson and Rawlins conjectured that a logarithmic spiral, with ratio $C_{\mathrm{sp}} = 13.8111351794611\ldots$, is optimal. We give a computer-assisted proof. Paths are arbitrary: the distance from the start and the polar angle may both decrease. The proof lifts the set of found directions to the universal cover of the circle, where unfolding the polar angle can only increase it (Kneser-Poulsen on the line); a bookkeeping inequality with a monotone final source then bounds the covered measure by the reward of a three-state relaxed control problem, in which inward motion is an ordinary control and excursions below the guaranteed disk are impulses. An explicit $C^1$ storage function, a tensor cubic B-spline plus a closed-form term, satisfies the dissipation inequalities of that problem at the spiral's level and is tight only at the spiral; this is verified with about $10^6$ boxes of Arb ball arithmetic, an exact jet and an interval Hessian at the spiral.

0.44

Mechanism Design for Facility Location Games Under a Prelocated Facility

cs.GT ·2026-08-31 ·Genjie Qin, Qizhi Fang, Wenjing Liu
publishedtheory similarity 0.55
Abstract

We study the problem of locating a new homogeneous facility under a prelocated facility. Here, a set of $n$ agents is located on a real line or a circle, each of whom has her location as private information, and her cost is the (expected) distance from her location to the nearest facility. Our goal is to design mechanisms which can approximately minimize the maximum cost or the social cost while eliciting agents' private information truthfully (i.e., strategy-proof). Based on real-life scenarios, we consider the problem in two settings: the general setting where each agent can be located at both sides of the prelocated facility, and the special setting where all the agents are located at the same side of the prelocated facility. For agents on a line, in the general setting, we design the best possible deterministic strategy-proof mechanism with $2$-approximation and provide a lower bound of $1.5-ε\textbf{ }(ε>0)$ for any randomized strategy-proof mechanism under the maximum cost objective. For the social cost, we obtain an upper bound of $n$ for deterministic strategy-proof mechanisms and lower bounds of $1.5$ and $1.0425$ for any deterministic strategy-proof mechanism and any randomized strategy-proof mechanism, respectively. In the special setting, we further provide a randomized strategy-proof $5/3$-approximation mechanism for the maximum cost and a deterministic strategy-proof $(n-1)$-approximation mechanism for the social cost. For agents on a circle, we provide a deterministic strategy-proof 2-approximation mechanism under the maximum cost objective.

0.39

Oblivious Self-Distance Symmetric Rendezvous on the Integer Line

cs.DM ·2026-09-12 ·Konstantinos Georgiou, Claude Gravel, Joey Kapusin, Lazar Mandic
similarity 0.55
Abstract

Symmetric rendezvous on the line is a search problem in which two agents, initially placed at distance $2d$, must follow the same randomized strategy to meet as quickly as possible. In the standard model, agents may condition their actions on the entire execution history, and both the known- and unknown-distance variants admit expected rendezvous time $Θ(d)$. We study the role of memory by introducing oblivious self-distance strategies, in which an agent's decision depends only on her position relative to her own starting location. For an initial separation of $2d$, let $R_d$ denote the optimal oblivious expected rendezvous time in the known-distance setting. We develop two finite-state frameworks based on absorbing Markov chains. Truncated chains give computable upper bounds through finite-support strategies, while weak-peek chains give lower bounds through a revealed-information relaxation. Together, they provide a mechanism for certifying optimality. Using that mechanism, we determine $R_1$ exactly and prove that it is attained by a finite-support strategy. For $d=2,\ldots,6$, numerical optimization gives the same truncation structure and objective values, yielding rigorous upper bounds below $7.83d^2$. We do not prove that the computed weak-peek minimizers are global, but the stability of the computations leads us to conjecture that they are, in which case the corresponding truncated strategies are optimal. We also prove that $R_d=Θ(d^2)$. In the unknown-distance setting, we construct a universal strategy, independent of $d$, with expected rendezvous time $O(d^{2+η})$ for every fixed $η>0$. Thus, under the memory restriction, the known-distance rendezvous time becomes quadratic, while near-quadratic performance remains possible even without knowing $d$. The asymptotic analysis uses birth-death Markov chains and their electrical-network interpretation.

0.47

Time-Optimal Ergodic Retrieval

cs.RO ·2026-10-15 ·Christian Sulana, Christian Hughes, Ian Abraham
similarity 0.54
Abstract · 8 pages, 6 figures

Retrieval tasks are a form of search task where a robot must explore, find an object, and return with it as quickly as possible. Recent work in ergodic control has demonstrated time-optimal path planning for search tasks where visitation is proportionally matched, within some tolerance, to a given target distribution. However, these planners minimize the duration of a full deterministic search, while retrieval missions end their search at an unknown point in the trajectory and must return to a given base. In this work, we propose a new formulation of the time-optimal ergodic search problem that models detection as a Poisson process and minimizes total mission time by including the return phase in the objective. Experimental results show that time-optimal ergodic retrieval (TOER) achieves up to $19\%$ shorter mission durations relative to ergodic baselines and that this advantage grows as the return phase becomes more costly. Simulation and hardware implementations validate TOER's compatibility with environments of non-convex geometry as well as both 2D and 3D search domains.

0.25