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.
Figures & tables
Figure 1: An illustration summarizing the proposed approach. Given a search environment, we pre-compute a collection of paths that together cover the search environment and satisfy the physical constraints. Online, we use an iterative, data-driven algorithm that assign paths to the sensors for data collection and detects interesting regions in the environment quickly, despite the noisy measurements.
Figure 2: We model a measurement at node i∈C (are humans present near the damaged house?) as a realization of a Bernoulli random variable νi with an unknown mean μi .
Rsk
\displaystyle=\begin{cases}\begin{array}[]{ll}J(t,Q_{k}),&\ \text{sensor }s\text{ can execute path }Q_{k},\\ 0,&\ \text{otherwise.}\end{array}\end{cases}
(8)
Algorithm 1 Bandit-based search algorithm
Symbol
Description of the sets (at iteration t )
Hi(t)
Measurement history of node i until iteration t .
K(t)
Nodes in C labeled as interesting; approximates Iθ .
R(t)
Nodes in C labeled as uninteresting; approximates C∖Iθ .
X(t)
Unlabelled nodes in C .
P(t)
Paths in PM with an unlabelled node; active paths.
Ps(t)
Paths in P(t) that start from or end at station s∈S .
Table 1: List of sets used in Algorithm 1 . Here, C is the candidate set, and PM is the M -path cover.
Figure 3: Illustration of Algorithm 2 with a path length bound M=7 . (a) Environment with stations (black), obstacles (blue), and candidate nodes (white); the team moves through accessible nodes via edges in Ndyn , ( 15 ). (b) Shortest-paths forest F from leaves (green) to stations, computed by Dijkstra’s algorithm. (c) Example paths in PM+ formed by merging shortest paths; solid blue: transfer paths, dashed black: non-transfer paths, dotted magenta: some of the redundant paths, as identified by the greedy heuristic. We skip plotting the remaining redundant paths for better visualization. (d) Algorithm 2 output.
Figure 4: Effect of team size d on labeling progress with d=1 (left), d=2 (middle), and d=4 (right). As expected, increasing the team size reduces the number of iterations required to label all candidate nodes. The proposed method detects all of the interesting nodes earlier than the random baseline.
Figure 5: Fraction of paths in P(t)∖Q(t) added to Q(t) at iteration t in Step 8 – 10 of Algorithm 1 (left), fraction of paths in P(0) that are active at iteration t , and the utilization of the search team (right) for d∈{1,2,4} which translates to team sizes of ∣S∣d∈{2,4,8} respectively. We report m=0 in the top row and m=30 in the bottom row.
We introduce Flickering Multi-Armed Bandits (FMAB) to model sequential decision-making in environments with changing action availability, where accessibility of the next action is restricted to a subset dependent on the agent's current choice. We formalize these constraints through stochastically evolving graphs where actions are limited to local neighborhoods. This mobility-constrained structure imposes a dual challenge: the statistical requirement of information acquisition and the physical overhead of navigation. We analyze FMAB under i.i.d. Erdős--R'enyi and Edge-Markovian process, proposing a two-phase lazy random walk algorithm for robust exploration. We establish high-probability sublinear regret bounds and prove near-optimality via a matching information-theoretic lower bound. Our results characterize the intrinsic cost of learning under local-move constraints, complemented by a robotic disaster-response simulation.
Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1
University of Colorado Boulder, USA. · INRIA Paris, France.
We study trajectory optimization in mobile sensing systems that must identify which member of a finite candidate set is the true target, while maintaining reachability to all potential candidate targets, under resource constraints. Deferred-Decision Trajectory Optimization (DDTO) addresses this setting by computing trajectories that reach individual targets but remain coincident for as long as possible before separating toward different targets. We propose Active-Sensing DDTO (AS-DDTO), which extends DDTO by adding a trajectory-dependent information-acquisition term to the planning objective. The resulting planner maintains reachability to candidate targets while biasing the coincident portion of the trajectories toward regions that enable earlier target identification. The framework supports Bayesian updates and conformal candidate-set updates for distance-dependent sensing. We derive a mixed-integer conic reformulation and provide guarantees on recursive feasibility, belief concentration, and fixed-time coverage for the raw conformal candidate set. Numerical simulations show improved target identification compared with standard DDTO under distance-dependent sensing uncertainty and limited sensing budget.
Farbod Siahkali, Mengxue Hou, Vijay Gupta
Department of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47906, USA · Department of Electrical Engineering, University of Notre Dame, Notre Dame, IN 46556, USA
Mobile crowdsensing (MC) recruits mobile users to perform sensing tasks using their smartphones, enabling large-scale applications such as traffic monitoring and environmental sensing. A fundamental challenge is online worker recruitment under uncertainty, where the platform must learn workers' sensing performance while operating with a limited budget. Existing learning-based MC recruitment methods typically assume that each worker's sensing quality is stationary with a fixed mean over time. In practice, however, worker performance often improves with experience and eventually stabilizes, while the incurred sensing cost can be unknown in advance due to time-varying device and context states. In this paper, we study a budget-constrained online recruitment problem in which the platform selects one worker in each round, observes the sensing quality and incurred cost, where the expected sensing quality of each worker increases with experience and eventually converges to a plateau, and repeats until the budget is exhausted. We formulate this problem as a structured bandit model where each worker's expected reward evolves according to an unknown increasing-then-converging function of its participation count, and each worker has an unknown expected cost. We develop a cost-aware online learning framework that jointly learns evolving reward trajectories and heterogeneous costs, detects performance saturation, and allocates the limited budget to maximize long-term sensing utility. We provide theoretical performance guarantees and validate the proposed approach through extensive experiments, demonstrating consistent improvements over baselines that ignore experience-driven dynamics or assume known costs.
Yin Huang, Qingsong Liu, Jie Xu
Manning College of Information and Computer Sciences, University of Massachusetts Amherst