CS Paper Radar

Time-Optimal Ergodic Retrieval

Christian Sulana, Christian Hughes, Ian Abraham

cs.RO ·submitted 2026-10-15 13:08 UTC · v1

Abstract

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.

Comment
8 pages, 6 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Reward-Guided RRT* for Budgeted Task and Motion Planning

cs.RO cs.AI ·2026-10-26 ·Vinícius Araújo de Oliveira, Gabriel Ferreira Mendes Lourenço, Paulo L. J. Drews-Jr, Armando Alves Neto, Douglas G. Macharet
similarity 0.62
Abstract

Robotic missions involving spatially distributed tasks often require jointly selecting rewarding locations and planning feasible motions under limited travel budgets. This paper proposes Reward-Guided RRT*, a new sampling-based framework that constructs a budget-feasible mission through a sequence of locally joint task-selection-and-motion-planning stages, evaluated directly in the continuous state space, without requiring a precomputed task-transition graph. The method incrementally builds a mission using reward-guided RRT* searches, while a return-feasibility procedure ensures that each selected task can be visited without violating the mission budget. Experiments with increasing obstacle complexity and number of tasks show solutions comparable to VNS-PRM* while requiring substantially fewer sampled states. We also extend the framework to Dubins steering and evaluate it in CoppeliaSim with a scaled car-like robotic platform, demonstrating its ability to incorporate vehicle kinematic constraints.

0.15

Racing the Clock: Teaching VLNs Budget-Conditioned Object Search

cs.RO cs.AIcs.CVcs.LG ·2026-11-12 ·Maitree Meher, Siming He, S. Shankar Sastry, Jitendra Malik, Claire Tomlin +1 more
similarity 0.60
Abstract · 12 pages, 4 figures, 3 tables

How do action budgets shape vision-language navigation (VLN) exploration, and what expert supervision best teaches budget-aware search? We study budget-conditioned object search: finding as many distinct instances of a requested category as possible within a budget, with discovery defined geometrically by camera field of view and proximity. Distinct discoveries provide a denser evaluation signal than single-target success. We cast expert design as a choice of scene abstraction: a single budget-indexed Bellman recursion, applied to different abstractions of the full environment, yields experts that differ in what they know. An object-level Bellman expert is given every target location and reduces search to budgeted routing. A room-level Bellman expert retains observed room connectivity, doorway evidence, and cross-scene semantic priors but withholds the contents of unexplored rooms, so it must search for targets that its student also cannot see. We distill both experts into Uni-NaVid under matched training conditions and also evaluate greedy-frontier supervision on held-out HM3D scenes. Changing only the stated budget changes learned trajectories. Despite higher object-level expert return, room-level supervision achieves the highest mean collection among evaluated VLNs at every tested budget. At 2000 steps, it finds 72.7% of reachable targets, versus 68.5% under greedy-frontier supervision, 65.5% under object-level supervision, and 44.8% for the pretrained VLN. These results show that expert-return rankings need not predict supervision quality for VLN exploration, and motivate choosing an expert's abstraction with the student's information in mind rather than by expert return alone.

0.21

SPARROW: Survival-POMCP for Adaptive Robot Routing, Observation, and Waiting

cs.RO ·2026-09-17 ·Hshmat Sahak, Aoran Jiao, Nicholas Rhinehart, Timothy D. Barfoot
similarity 0.59
Abstract · 8 pages

Temporary obstacles that may block a robot's planned route create a sequential navigation problem: a robot must decide whether to wait for a blockage to clear, reroute, or acquire more information about the obstacle before acting. We formulate graph navigation among temporary obstacles as a partially observable semi-Markov decision process and introduce SPARROW, a belief-space planner built on Partially Observable Monte Carlo Planning (POMCP). SPARROW searches over traversal, observation, and finite-duration waiting actions while maintaining a particle belief over latent obstacle classes and clearance times. Class-conditioned survival models are learned online from both clearance observations and right-censored encounters where the robot reroutes before clearance is observed. A generative model simulates obstacle arrivals and clearances as each action unfolds, so the planner can account for blockages that may occur along alternative routes. We further introduce a value-of-learning criterion that trades the immediate cost of collecting labelled survival data against its expected reduction in future navigation regret. Across two simulation graphs and multiple obstacle-class settings, SPARROW reduces mean time-to-goal by 12-26% relative to OSCAR, a recent survival-based method for the same problem. On a physical mobile robot, SPARROW reduces mean time-to-goal by 20.5% relative to OSCAR while selectively observing, waiting, and rerouting as environment conditions change.

0.30

ST-pRRTC: Parallel Space-Time RRT-C with Adaptive Goal-Time Forests

cs.RO ·2026-09-24 ·Duo Zhang, Jintong Li, Junshan Huang, Jingjin Yu
similarity 0.58
Abstract

We propose ST-pRRTC, a GPU-parallel space- time RRT-Connect motion planner for problems with known obstacle trajectories and unspecified arrival time. Searching over many arrival times broadens temporal coverage but divides a finite planning budget among more backward trees. To address the challenge, ST-pRRTC builds a shared forward tree and an adaptive forest of backward goal-time trees. Its interval root formulation samples goal arrival times continuously and guarantees probabilistic completeness and asymptotic arrival- time optimality under the stated assumptions in a bounded time domain. The practical root recycling policy has no such guar- antees. It adapts a fixed number of backward trees, replacing later roots while retaining useful search progress. Experiments on three dynamic benchmarks show that both variants achieve lower mean first-solution times and earlier mean final arrivals than ST-RRT* and SI-RRT on problems solved by all compared methods. Further experiments demonstrate the benefit of recy- cling over broad arrival-time ranges. Real-robot demonstrations show root-recycling ST-pRRTC planning motions for a UR5e among moving Crazyflie quadrotors.

0.16

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

Expected Free Energy-based Informative Path Planning for Robotic Mars Exploration

cs.RO cs.ITcs.LG ·2026-08-14 ·Ajith Anil Meera, Pablo Lanillos, Wouter Kouw
published similarity 0.58
Abstract · accepted for IWAI 2026

An autonomous robot efficiently exploring an unknown environment, such as looking for water sources on Mars, faces two simultaneous demands: building an accurate information map while quickly finding the regions of greatest value, and paying for every meter of travel and the cost of every measurement it takes. Classical information-seeking and reward-seeking criteria address only one of these objectives at a time. Here, we propose Expected Free Energy (EFE), the principled action-selection objective from active inference, as a unifying criterion for budgeted robotic informative path planning. Maintaining a Gaussian-process belief over the information field, our agent plans continuous trajectories that minimize expected free energy under hard path-length constraints. The results from multiple realizations show that EFE-based planning yields accurate posterior maps and locates the highest-value regions simultaneously, outperforming information-theoretic baselines under the same settings. In robotic exploration, these unified, easy-to-tune principled information-gathering strategies facilitate autonomous deployment while enforcing efficiency and resource constraints.

0.19

Model-Free Adaptive Parameter Tuning for Efficient Multi-Robot Warehouse Operations

cs.RO eess.SY ·2026-08-21 ·Pratap Tokekar, Mouhacine Benosman, Rahul Chandan, Alexandre Ormiga Galvao Barbosa, Michael Caldara +1 more
similarity 0.57
Abstract

Robotic Fulfillment Centers (FCs) store inventory on shelves (pods) arranged in dense blocks. Retrieving a target pod that is buried deep in a block requires moving obstructing pods out of the way (i.e., digout). Multi-robot planners use parameterized cost functions to control digout behavior, producing a spectrum of strategies: at one extreme, obstructing pods are sent to other blocks (using more robots in travel lanes); at the other, pods are shuffled within the block (avoiding lane congestion but increasing extraction time). Each point on this spectrum has different downstream consequences for floor congestion and throughput. The optimal operating point depends on the specific facility configuration and shifts with operational conditions such as varying station demand and congestion patterns, making offline tuning impractical. We present an adaptive parameter tuning framework based on Extremum Seeking Control (ESC) that continuously adjusts planner parameters in response to measured throughput. ESC performs model-free optimization by perturbing parameters with sinusoidal dither signals and correlating perturbations with performance changes to estimate gradients, making it robust to the multi-minute delayed effects and credit assignment challenges inherent in large FC operations. Simulation studies demonstrate that the adaptive policy improves upon fixed policies across several conditions. We observe an improvement in throughput by an average of 5.0% across map and robot fleet size variations, and by 8.4% under dynamic operating conditions. This work eliminates manual parameter provisioning and enables real-time adaptation, providing a self-tuning paradigm for FC storage operations.

0.30

Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics

cs.RO cs.AI ·2026-08-19 ·Masafumi Endo, Kohei Honda, Yuu Jinnai, Ryo Yonetani
benchmark similarity 0.57
Abstract · 11 pages, 6 figures

We present the orienteering problem with uncertain time-varying rewards (OP-UTVR), a novel variant of the orienteering problem (OP). While most existing OP formulations assume rewards to be known in advance, practical applications involve uncertain and time-varying rewards, as with shifting customer demand for delivery agents. OP-UTVR relaxes this assumption by allowing agents to estimate reward dynamics from observations and forecast future rewards. This enables informed routing decisions despite stochastic reward changes and inevitable prediction errors. We address this problem using three planners that differ in planning horizon and online adaptivity, and derive theoretical bounds on their performance under reward stochasticity. We further introduce a mobile service robot benchmark for OP-UTVR, where a robot navigates among pedestrians in indoor environments. Experiments reveal trade-offs between planning horizon and adaptivity, and demonstrate the effectiveness of long-horizon planning with online adaptation.

0.15