CS Paper Radar

Movement Stability of D-Optimal Sensor Placement Under Projector Perturbations

Isabella Yin, Laura P. Schaposnik

eess.SP math.OC ·submitted 2026-10-06 11:03 UTC · v1

Abstract

In time-varying D-optimal subset selection, the number of replaced coordinates does not measure physical displacement: when the optimal selection for a set of mobile sensors changes, a single sensor may have to cross the entire graph. We therefore measure movement by a bottleneck matching distance on a fixed mobility graph, and define the distance margin at radius P as the smallest old-objective loss among configurations farther than P from the current maximizer. Our main result shows that if the projector drift is small and the distance margin at a chosen radius exceeds an explicit threshold, then every maximizer of the new objective lies within that radius, without tie-breaking rules or uniform conditioning assumptions over subsets. Moreover, we show that separation information of this kind is genuinely needed: a weighted-path construction shows that, at a fixed baseline eigengap, an arbitrarily small perturbation can move an optimal sensor from one end of the graph to the other, so no bound depending only on perturbation size and eigengap can vanish with the perturbation. We also give a finite certificate, conditions under which local and Voronoi restrictions retain a global optimum, and oversampled and regularized extensions, and we identify the learned dictionary criteria to which the results apply.

Comment
21 pages, 2 images

Closest papers

Nearest neighbours by meaning across the whole index.

Global Optimality of Pose Graph Optimization

cs.RO eess.SP ·2026-10-10 ·Shuan Ding, Ruishuang Chen, Mengfan Cao, Zaiyue Yang
theory similarity 0.58
Abstract

Pose Graph Optimization (PGO) is a classical and widely applied problem in state estimation for robotics, playing a fundamental role in localization, mapping, and navigation. Yet, it is nonconvex in nature and may have many local minimizers, thus difficult to analyze. In this paper, we investigate the optimization landscape and establish a sufficient condition of global optimality for PGO. The ultimate goal of this paper is to theoretically confirm that the optimization landscape is benign and attractive around the global minimizer, if noise is smaller than an explicit and a priori bound. To reveal such an insight, this paper develops three main technical results. First, we identify a proper basin of attraction (BOA) containing global minimizer, and characterize its geometric property by showing that its radius is controlled by noise in an explicit way. Then, by exploring the first order optimality conditions of PGO, we prove that a local minimizer is globally optimal if a noise-controlled criterion is satisfied. Finally, by combining above two results, we prove that one and only one local minimizer exists in the BOA and this minimizer is globally optimal, when the noise is smaller than an explicit bound that can be verified a priori. Numerical simulations validate the proposed theory under various random cases, showing that the obtained conditions provide an effective criterion for certifying the global optimality of PGO.

0.36

Adaptive search with path-constrained mobile sensors using multi-arm bandits

cs.RO cs.LGmath.OC ·2026-10-29 ·Abraham P. Vinod, Parth K. Thaker, Gautam Dasarathy, Stefano Di Cairano
similarity 0.55
Abstract · 24 pages, 5 figures

We study a constrained sequential decision problem for detecting regions of interest from noisy online measurements collected by a team of energy-constrained mobile sensors. The sensor motion is restricted to a precomputed set of feasible paths that satisfy mobility constraints, limited available energy by requiring return to charging stations, and avoidance of known obstacles. We cast the resulting active path selection as a multi-armed bandit problem and propose an iterative search algorithm that adaptively assigns paths using confidence bounds computed from the collected data. We also propose a graph-based method to construct low-cardinality path covers under the team's constraints. We establish finite-time and anytime probabilistic correctness guarantees for the proposed algorithm, derive non-asymptotic upper bounds on the times required to detect all regions of interest and to label all nodes, and show that these bounds match algorithm-independent lower bounds up to constant factors for a broad class of problem instances. Using numerical simulations, we illustrate the behavior of the proposed approach and the effect of path redundancy and team size on search performance.

0.15

When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes

cs.DC cs.CGcs.MA ·2026-10-03 ·Animesh Maiti, Prakhar Shukla, Abhinav Chakraborty, Subhash Bhagat
theory similarity 0.55
Abstract

We study the \textit{optimal gathering} problem over a finite set of designated \textit{meeting nodes} for \textit{asynchronous, anonymous,} and \textit{oblivious} mobile robots on an infinite grid under crash faults. The robots have global visibility and strong multiplicity detection, but share neither a coordinate system nor chirality. The objective is to gather all non-faulty robots at a \textsc{Weber Meeting Node}, minimizing the total Manhattan distance from their initial positions. Up to $n-2$ robots may crash permanently, and such crashes are indistinguishable from arbitrary delays. Existing approaches often rely on a designated robot to break symmetry, whose crash may block the remaining robots indefinitely. Instead, our approach enables every robot to independently select the same target from its snapshot, while target-dependent restricted shortest paths preserve the target as a \textsc{Weber Meeting Node}. We prove that, under strong multiplicity detection, optimal gathering is impossible from certain fully symmetric configurations. For all remaining configurations, our algorithm \textsc{CrashTolerantWeberGathering()} selects a unique common target, preserves its optimality throughout the execution, and allows non-faulty robots to progress without waiting for crashed robots, thereby guaranteeing gathering in finite time.

0.14

Belief-Driven Search in Connectivity-Constrained Mobile Sensor Networks with Convergence Guarantees

eess.SY ·2026-10-28 ·George J. Ziavras, Ziqiao Zhang, Shreyas Sundaram, Christopher G. Brinton
theory similarity 0.54
Abstract · 8 pages, 6 figures, 2 tables. Extended version with full proofs

Multi-agent search and coverage is critical to autonomous exploration, search-and-rescue, and defense applications. This paper investigates settings where a mobile sensor network is tasked with coordinating to discover the position of a stationary target within a bounded region. We develop a Bayesian update scheme where agents iteratively combine local uncertainties derived from their sensor measurements through inverse variance weighting to get a better global understanding of where the target may be located given some prior belief. Network agents' trajectories are governed by a primal-dual gradient update rule that simultaneously minimizes the expected sensing uncertainty and enforces network connectivity among the agents. We prove that the belief converges to the target under mild planner conditions, with an explicit exponential rate of false-hypothesis rejection and a bound on expected search time. Simulation results show that we can successfully find the target and collapse belief to the ground truth target location while ensuring connectivity of our sensor network. They also empirically confirm our theoretical bounds and planner conditions. Finally, we compare against a naive lawnmower sweeping strategy, showing that our method locates the target more quickly when the prior is informative.

0.36

Towards Certifiable State Estimation under Observability Degeneracy

cs.RO ·2026-10-14 ·Baoshan Song
theory similarity 0.53
Abstract

Certifiable optimization provides global optimality guarantees for non-convex state estimation in robotics. However, under severe physical sensing degeneracy, convex Semidefinite Programming relaxations solved via Interior-Point Methods suffer from rank expansion, rendering direct semidefinite solving and spectral rounding algebraically invalid. In this paper, we establish a universal candidate-driven dual certification framework that resolves this challenge without incurring rank expansion. First, from an epigraph perspective, we prove that while sensing degeneracy expands the primal optimal set into a flat equi-cost face, cost tightness and multiplier recovery remain strictly intact, enabling global verification without direct semidefinite solving. Second, we propose an observability-aware local search using solution remapping, coupled with a closed-form dual multiplier recovery scheme that executes in sub-microsecond latency. Third, we derive a model-specific adaptive dual safety threshold parameterized by the minimum non-zero eigenvalue of the observable Hessian and uneradicated residual leakage, preventing false rejections of optimal candidates under weak observability. We validate our universal framework with robust registration under degenerate measurements.

0.11

Partial-Scan-and-Move Source Seeking for Mobile Robots

eess.SY cs.RO ·2026-09-20 ·Bo Wang, Ishvar Sitaldin
similarity 0.53
Abstract

This paper presents a partial-scan-and-move strategy for source seeking with a mobile robot equipped with an offset scalar sensor. At each robot position, the sensor collects source field measurements while the robot rotates. Instead of requiring a complete circular scan before every move, we ask when the measurements collected over only part of the circle are already sufficient to determine the next action. We develop a gradient estimation method for partial scans together with a confidence set that accounts for measurement noise and local field variation. The robot uses this confidence set to decide whether it is close enough to the source or has enough information to move in a descent direction. We show that, under suitable conditions, each decision can be made within a prescribed partial scan and that the robot reaches a desired neighborhood of the source in finitely many moves with high probability.

0.25

Stochastic Multi-Robot Monitoring on Graphs under Markovian Mobility

cs.DS ·2026-08-20 ·Walid Ben-Ameur, Tijani Chahed, Shamisa Nematollahi
theory similarity 0.53
Abstract

We study a stochastic multi-robot monitoring problem on a connected graph $G=(V,E)$, where each robot moves according to a Markov chain on $G$ and monitors the closed neighborhood of its current vertex. The performance of $r$ robots is evaluated in steady state via two objectives: average-case coverage (the expected number of covered vertices) and worst-case coverage (the minimum coverage probability over all vertices). We consider three models: independent homogeneous strategies, where all robots share the same stationary distribution; independent heterogeneous strategies, where robots use different stationary distributions; and centralized strategies, allowing arbitrary correlations between robot locations. For the heterogeneous model, we prove that maximizing average coverage is NP-hard even for two robots, and that replicating an easy-to-compute optimal homogeneous strategy yields a \(\left(1-\left(1-\frac{1}{r}\right)^r\right)\)-approximation for both objective functions in the heterogeneous setting; moreover, no polynomial-time algorithm can achieve a ratio better than \(1-\nicefrac{1}{e}\) unless \(\text{P}=\text{NP}\). Centralized strategies can exploit correlations to reduce redundancy. We develop a hierarchy of approximation factors: for any positive integer \(r'\le r\), writing \(r=hr'+b\) with \(0\le b<r'\), block coordination yields a \(1-\left(1-\frac{r'}{r}\right)^h\left(1-\frac{b}{r}\right)\) approximation for both objectives. We also establish NP-hardness and a tight \(1-\nicefrac{1}{e}\) inapproximability bound. Moreover, we prove diminishing-returns properties with respect to the number of robots: a non-increasing-ratio property holds for the average-case objective in all settings, but not for the heterogeneous worst-case objective.

0.29

Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model

cs.DC cs.CGcs.MAcs.RO ·2026-10-03 ·Prakhar Shukla, Animesh Maiti, Shivam Kumar, Subhash Bhagat
similarity 0.52
Abstract

We investigate the mutual visibility problem for a swarm of $n\ge3$ autonomous mobile robots under the budget-constrained mobility fault model. The robots are opaque, so if three robots are collinear, the middle robot obstructs the visibility between the other two. Each robot is assigned a finite movement budget, reflecting its limited energy, that bounds the total distance it may traverse during the execution. Moreover, an arbitrary number of robots may become permanently immobile due to mobility faults. The objective is to design a distributed algorithm that enables the non-faulty robots to coordinate their movements so that, within a finite time, every non-faulty robot attains unobstructed visibility of all robots in the system, including the faulty ones, while respecting the prescribed movement budget. We consider luminous robots operating under the $\mathsf{SSYNC}$ model with non-rigid movements, without any agreement on their local coordinate systems, and equipped only with a {\it common fixed reference point}. We present a deterministic distributed algorithm that solves the problem despite an arbitrary number of mobility faults. The algorithm guarantees mutual visibility for the non-faulty robots, respects the movement budget of every robot, provides collision-free movements for the robots, and uses only 12 light colors.

0.26