CS Paper Radar

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

Abraham P. Vinod, Parth K. Thaker, Gautam Dasarathy, Stefano Di Cairano

cs.RO cs.LGmath.OC ·submitted 2026-10-29 16:52 UTC · v1

Abstract

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.

Comment
24 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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.69
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

Selecting k Paths with the Minimum Longest Path Length in the Stochastic Semi-Bandit Setting

cs.LG ·2026-09-13 ·Shunsuke Aoki, Atsuyoshi Nakamura
similarity 0.61
Abstract

When performing parallel data transmission through a network using multiple paths, it is practically important to minimize the maximum transmission time among the selected paths. This study addresses an online problem in which $k$ paths from an origin vertex to a destination vertex must be selected at each time step within a network represented as a directed graph. Here, the number of paths going through each edge in each parallel data transmission is limited to its capacity, and the time required for transmission is determined stochastically. We formulate the semi-bandit problem of selecting a set of paths to minimize the maximum traversal time among the selected paths and propose an algorithm to solve it.

0.27

Future Information-Directed Sampling for Bayesian Nonstationary Bandits

cs.LG ·2026-09-27 ·Yichen Song, Alessio Russo, Aldo Pacchiano
published similarity 0.61
Abstract · 18 pages. An earlier version appeared at the ICML 2026 DEMO Workshop

Exploration--exploitation is a central trade-off in bandit learning. While classical algorithms such as upper confidence bound methods and Thompson Sampling effectively balance this trade-off in stationary environments, their exploration strategies mainly reduce uncertainty about the current optimal arm, which can be insufficient in nonstationary settings where future optimal arms may differ substantially from current ones. In this paper, we propose Future Information-Directed Sampling (FIDS), a new algorithm for Bayesian nonstationary bandits that explicitly explores to gather information about future optimal arms. We show that FIDS achieves regret comparable to Thompson Sampling up to a small constant factor, while being able to exploit predictive information structures that conventional exploration objectives fail to capture. To address the practical difficulty of posterior inference, we further propose a supervised-learning-based approximation framework that learns the FIDS policy from offline data, and demonstrate its effectiveness on synthetic benchmarks.

0.33

Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits

cs.LG cs.AI ·2026-09-24 ·Michael Jerge, Suman Jana
theory similarity 0.60
Abstract

Many LLM inference problems, including model routing, prefix-cache management, prompt trimming, and test-time search, can be viewed as optimization over a tree. This structure arises naturally from autoregressive generation: every prefix defines a node, and its continuations form a subtree below it. Internal nodes of the tree provide cheap but biased estimates of a region's value, while leaf evaluations are expensive but accurate. Hierarchical bandit methods can exploit this structure, but typically require a specific smoothness schedule to be specified in advance, even though real objectives are often only piecewise smooth and their optima may lie near sharp boundaries. We introduce CANOPY, a multi-fidelity tree bandit that learns where the smoothness prior is valid rather than assuming it globally. CANOPY uses cheap random-path probes to construct an online certificate of local aggregation bias, then directs expensive leaf evaluations toward cells where the certificate detects a smoothness violation. We prove fixed-budget and regret guarantees whose additional cost is additive in the number of discontinuities, recovering the smooth-tree rate when no violations are present and approaching structure-blind search as violations become dense. Across routing, top-$k$ identification, test-time search, caching, and prompt trimming, CANOPY consistently improves matched-budget performance, including $2.9\times$ higher top-10 recall on a 1000-model pool, $1.6\times$ more SWE-bench Verified issues resolved than best-of-$N$, and $3.6\times$ lower median time-to-first-token with prefix caching.

0.17

The Optimal Sampler for Diverse TSP Solutions: Characterization, Limits, and Learning

cs.CG cs.DScs.LG ·2026-10-20 ·Ssu-Yuan Lo, Ching-Kai Wang, Kuan-Lun Chen, Hao-Tsung Yang
benchmarktheory similarity 0.60
Abstract

We address the Diverse Traveling Salesman Problem (D-TSP) that seeks a set of $k$ distinct TSP tours. Each selected tour must not exceed a prescribed multiple of the optimal tour length, while the maximum pairwise Jaccard similarity within the selected set is minimized. This formulation is important for applications requiring both solution quality and fault tolerance, such as logistics planning, robotics, and strategic patrolling. We propose a novel hybrid framework that decomposes D-TSP into a sampling stage and a selection stage. The selection stage is a max-min dispersion problem, for which any approximation better than a factor of two is NP-hard; we therefore focus on the sampling stage. Our contributions are both theoretical and empirical. Theoretically, we give two end-to-end guarantees for the optimal sampling distribution, from two perspectives: including an optimal set in the sampled pool, or having at least $k$ mutually distant tours in the pool. The second reduces the number of samples from exponential to linear in $k$, at the cost of weakening the benchmark from the best $k$ tours to the best $βk$ for some $β> 1$. For practical use, we prove that a pipeline that samples spanning trees and then converts to tours does not hurt the quality of the pool in principle. Empirically, both objectives are learnable, and our experiments not only validate the analysis but also outperform the baselines on both in-distribution and out-of-distribution instances, by a single trained model with no fine-tuning.

0.30

Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets

cs.AI cs.RO ·2026-08-21 ·Jingtao Tang, Hang Ma
benchmarktheory similarity 0.60
Abstract

We formalize the Steiner Traveling Salesman Problem (Steiner-TSP) on Graphs of Convex Sets (GCS), which seeks a minimum-cost closed trajectory through required convex sets while allowing optional transit vertices and revisits. To explore the resulting infinite solution space, we propose a unified branch-and-bound search over rooted walk prefixes. Additive lower-bound-graph costs bound committed prefixes, while a cut-separated connected-flow relaxation lower-bounds the residual cost of visiting every remaining target and returning to the root. Under a uniform positive-cost assumption, best-first traversal terminates after finitely many expansions on every feasible instance without an initial incumbent, whereas depth-first traversal does so once a finite incumbent is available. For a user-specified factor $ε\geq1$, a global lower bound certifies that either strategy's incumbent cost is at most $ε$ times the global optimum. We further demonstrate joint sensing-mode, visitation-order, and continuous-trajectory selection for a mobile-manipulator inspection task, including action precedences expressed in linear temporal logic over finite traces (LTL$_f$). Both traversal strategies find feasible solutions on all benchmark instances within 30s with mean certified optimality gaps of 28.1% and 29.7%, respectively, whereas two recent baselines succeed on only about half of the instances

0.40

Adaptive Operator Selection in Bilevel Large Neighborhood Search for Electric Autonomous Dial-a-Ride Problem under Uncertainty

cs.NE cs.AI ·2026-10-03 ·Ishara Hewa Pathiranange, Aneta Neumann
similarity 0.60
Abstract

The electric autonomous dial-a-ride problem (EADARP) extends the classical dial-a-ride problem by incorporating battery and charging constraints for electric vehicles. In practice, travel-time uncertainty can cause violations of time-window constraints. Large neighborhood search is effective for solving the EADARP, but its performance can depend on the choice of insertion operator during the repair phase. This paper investigates insertion-operator selection within a bilevel large neighborhood search framework for deterministic and chance-constrained variants of the EADARP. In the chance-constrained variant, arc travel times are modeled as independent normally distributed random variables, and upper time-window constraints are enforced probabilistically. We consider six selection methods, namely fixed greedy insertion, fixed regret-based insertion, random selection, a deterministic state-based rule, performance-adaptive ALNS selection, and LLM-based state-aware selection. Experimental results show comparable performance on smaller instances, while differences become more evident on larger and more constrained instances. There is no single strategy that performs best across all instances, and the relative performance of the LLM-based, rule-based, and ALNS strategies varies with the problem instance and experimental setting.

0.25

Positioning a Movable Antenna Without CSI: A Kernelized Bandit Under Costly Movement

eess.SP ·2026-09-23 ·Wonseok Choi, Yunseob Tae, Jeongjae Lee, Songnam Hong
theory similarity 0.60
Abstract · Submitted to IEEE Transactions on Wireless Communications

Movable antenna (MA) systems reconfigure the wireless channel by repositioning the antenna within a confined region. The position optimization behind this capability has been studied under the premise that the channel at every candidate position is known. However, acquiring that knowledge is costly: a position can be measured only after the antenna has moved there, which takes many slots at the speed of the actuator, and the channel drifts meanwhile. We formulate MA positioning as a non-stationary kernelized bandit with a reachability constraint, in which exploration, tracking, and the reward lost in transit are coupled through a single physical action. We propose MoveUCB, which addresses the reachability constraint through a global target search, a persistence rule that holds the target across slots, and a transit-aware movement cost term. We prove that MoveUCB attains sublinear dynamic regret under the standard variation-budget condition of non-stationary bandits alone, with the physical parameters entering only through constants. Simulations against a dynamic-programming oracle and movement-unaware baselines show that MoveUCB attains the lowest regret with about half the travel of the closest baseline that moves.

0.49