CS Paper Radar

Optimal Planning in a Dynamic World

Devin Wild Thomas, Solomon Eyal Shimony, Wheeler Ruml, Erez Karpas, Shahaf S. Shperberg, Andrew Coles

cs.AI ·submitted 2026-10-02 13:50 UTC · v1
theory

Abstract

Background: We address the problem of planning when the set of feasible states or actions changes over time. For example, in the problem of path planning among moving obstacles (sometimes known as SIPP), the feasibility of being at a particular location can change as the obstacles move. Or, the action of boarding a particular train is feasible only while it is stopped at the station. This dynamism means that the optimal plan and its duration can change depending on when execution begins. In practice, execution start time is often unknown until planning has completed or another agent gives the go-ahead. However, most prior planning work either ignores dynamism or assumes a known start time. This makes it straightforward to assess state and action feasibility but is impractical for some applications. Objectives: In this paper, we relax the assumption of a known start time. We define the setting of {\em any-start-time planning} and provide algorithms for it. Methods: We present a data structure called a compound arrival time function (cATF) that compactly encodes the optimal plan as a function of start time. We provide general-purpose planning algorithms, based on heuristic graph search, that assemble cATFs by propagating functions along edges instead of scalar costs. Results: We prove that the size of a cATF is at most linear in the problem size. An experimental evaluation of an implementation for the specific problem of SIPP shows that, on difficult problems, agents that rely on replanning often fail, while any-start-time algorithms using cATFs can quickly look up the optimal plan once the execution start time is known. Conclusions: By enabling efficient representations and reasoning for time-dependent plans, this work provides a foundation for planning in dynamic worlds.

Comment
48 pages, 25 figures

Closest papers

Nearest neighbours by meaning across the whole index.

MeshSIPP: Efficient Lattice Planning in Dynamic Environment

cs.AI cs.RO ·2026-10-07 ·Marat Agranovskiy, Konstantin Yakovlev
benchmarktheory similarity 0.65
Abstract

Autonomous navigation in dynamic environments requires computing spatiotemporal trajectories that satisfy non-holonomic motion constraints. When the trajectories of the moving obstacles are predictable or known, a promising approach is to rely on the combination of state lattices constructed from precomputed feasible motion primitives and Safe Interval Path Planning -- a search-based algorithm with strong theoretical guarantees. While this approach yields feasible paths, the rich primitive sets needed for smooth navigation induce a large branching factor, which becomes costly when coupled with time-dependent obstacle intervals. To this end, we present MeshSIPP, an efficient planner that removes the computational bottleneck by exploiting the fact that many primitives sweep the same regions and can therefore be validated together. MeshSIPP propagates primitives as spatial bundles, screens them with lightweight bounding-interval checks, and defers the expensive exact departure-time search until a primitive reaches its terminal state. A time-aware pruning rule additionally discards redundant space-time branches early in the search. We prove that the resulting search is complete and optimal. Extensive experiments over more than 6,000 benchmark instances and real-time ROS~2 simulations show that MeshSIPP achieves up to a 3$\times$ speedup over state-of-the-art spatiotemporal planners.

0.18

DynoFluxBench: Benchmarking Kinodynamic Space-Time Planners in Dynamic Environments

cs.RO ·2026-09-16 ·Franz Queißner, Andreas Orthey, Wolfgang Hönig
benchmark similarity 0.63
Abstract · 8 pages

Robots that leave structured, static environments must plan motions that are kinodynamically feasible and safe among moving obstacles. However, there are no dedicated benchmark frameworks that combine both aspects. To overcome this, we present DynoFluxBench, a framework to compare kinodynamic planners in known, dynamic environments with unbounded arrival time. To demonstrate its utility and establish strong baselines, we develop three dedicated planners, named ST-Db-RRT, ST-GBRRT, and KIST, that fuse kinodynamic and space-time methods, covering different kinodynamic search paradigms: ST-Db-RRT expands with randomly selected discontinuity-bounded motion primitives using trajectory optimization, whereas KIST and ST-GBRRT maintain a kinodynamically feasible tree with different heuristic guidance. We analyze the probabilistic completeness guarantees of those new planners in dynamic environments. Finally, we evaluate ST-Db-RRT, ST-GBRRT, and KIST using DynoFluxBench, showing that ST-Db-RRT reaches a first solution up to 32 times faster, while KIST and ST-GBRRT remain valuable where trajectory optimization is fragile. Videos and further analysis can be found at https://dynofluxbench.github.io/dynofluxbench/.

0.32

LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions

cs.RO cs.AIcs.MA ·2026-11-07 ·Dachuan Liu, Shuai Zhou, Shizhe Zhao, Zhongqiang Ren
publishedhighly cited similarity 0.63
Abstract · 15 pages, 14 figures

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all agents start at the same time and always take a time unit. This assumption may limit the use of MAPF planners in practice. To get rid of this assumption, recently, an algorithm called Loosely Synchronized Rule-based Planning (LSRP) was proposed, which can find sub-optimal solutions for many agents. However, LSRP often finds poor quality solutions due to its unbounded sub-optimality. This paper develops a new anytime planner called LSRP* that can keep improving solution quality after the initial solution is obtained until the runtime budget depletes. We analyze the properties of LSRP* and test it against several baselines with up to 1000 agents on various maps. LSRP* can handle up to 25% more agents than LSRP and can reduce up to 40% of the solution cost found by LSRP.

0.61

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

The Cost of Executability: Temporal Margins for Continuous-Time Multi-Agent Path Finding under Closed-Loop Control

eess.SY ·2026-10-14 ·Sabino Roselli, Alvin Combrink, Ze Zhang
benchmark similarity 0.61
Abstract

Multi-agent path finding (MAPF) solvers are evaluated on the schedules they produce, not on how well those schedules can be executed. Specifically, continuous-time optimal solvers can achieve even lower cost than their discrete counterparts by scheduling agents with near-zero temporal/spatial separation, and by exploiting graphs with higher connectedness; however, such schedules may prove hard to execute under a realistic controller. We integrate AOC-CBS, an anytime-optimal continuous-time MAPF solver, into a fleet coordination framework in which each agent tracks its timed path using model predictive control, and we evaluate the resulting system on congested MovingAI benchmark instances with 21 to 40 agents. Without intervention, only a fraction of the instances complete execution. We then apply T-robustness by adding a time-margin, i.e., a minimum temporal gap between agents at shared locations, as well as spatial inflation of the agent footprint. Increasing either margin raises execution success, for a relatively small increase in the schedule's sum-of-costs; it also improves how closely agents adhere to the schedule: when tracking each agent's position throughout execution and comparing it against the position it should occupy according to the schedule, the mean discrepancy falls significantly as the margin increases. In general, the two margins have different effects; temporal margin decreases deviation, giving the controller room to stay on schedule. Spatial margin affects deviation less and instead increases the clearance between agents, so that the same deviation no longer leads to a blocking stall. They are nonetheless substitutes rather than complements: spatial inflation is almost free in schedule cost, but its effect on execution success is small and does not compound with a temporal margin already in place.

0.12

Dijkstra as an Oracle for Online Stochastic Shortest Path Navigation with Provable Guarantees

cs.RO cs.AImath.OC ·2026-08-18 ·Mansur M. Arief, Ali Akarma, Ahmad Alfan Alfian Irfan
similarity 0.61
Abstract

Mobile robots that operate in side by side with humans and critical facilities must reach their goals at low cost, despite often unknown true traversal costs of the map apriori and imperfect actuation. Planners that solve the underlying stochastic shortest path problem exactly, such as value iteration, require computation that grows with the diameter of the map, whereas Dijkstra's algorithm is fast but is usually considered inexact once transitions are stochastic. This study shows that Dijkstra's algorithm can remain an exact planning engine under a condition that is much weaker than the causality condition often invoked in the literature, namely nonnegativity of a reduced cost defined on the determinized map. Building on this characterization, an online learner DORA (Dijkstra Oracle Reduced-cost Algorithm) is proposed for robot navigation that calls a shortest path oracle a fixed number of times per episode, never estimates a transition kernel, and adds a logarithmic survival weight when the probability of contact with a dynamic obstacle must stay within a budget. In the numerical experiments involving three other benchmarks that cover grid world navigation, directional drilling, and drone surveillance, the learner matches optimistic value iteration that is given the true transition kernel while performing 4.5 to 19.3 times less planner work, reduces contacts during learning by a factor of seventeen relative to determinize and replan, and keeps the contact rate within budgets that span two orders of magnitude. These results indicate that shortest path search supports safe and efficient online navigation and path planning tasks.

0.13

Real-Time Motion Planning with Dynamic Hazards: Classical vs. Learning-Based Methods

cs.RO cs.AI ·2026-10-08 ·Eran Iceland, Alexander Tuisov, Oren Gal, Ariel Barel, Alfred M. Bruckstein
publishedbenchmark similarity 0.60
Abstract · This paper is scheduled to be presented at the 2027 International Symposium on Artificial Life and Robotics (AROB 2027)

We study real-time motion planning in dynamic hazard fields through a controlled comparison between classical planning and learning-based methods. Rather than introducing a new planner, we construct a unified benchmark in which representative classical and learning-based methods face the same environments, motion constraints, information assumptions, and evaluation metrics. The test environment consists of planar domains populated with rotating sprinkler-like hazards that generate time-varying forbidden regions via sweeping angular sectors. Our results show a clear regime shift. In deterministic environments, classical planners achieve near-perfect success and higher-quality paths, though sometimes at the cost of substantial planning or replanning time. Under stochastic obstacle dynamics, however, online search becomes strongly budget-sensitive: low budgets lead to frequent failure, while high budgets improve success at the cost of latency and longer trajectories. PPO-based policies, trained under the same scenario distribution, consistently outperform in latency, success rate, and path quality in these stochastic regimes. Overall, the results indicate that uncertainty in obstacle evolution, more than partial observability, is the dominant factor determining which planning paradigm is practically effective for the problem at hand.

0.25

Motion Planning with Temporal Logic Precedence Specifications in Dynamic Environments via Spacetime Augmented Graphs of Convex Sets

eess.SY ·2026-10-19 ·Shilin You, Lars Lindemann, Tyler H. Summers
similarity 0.60
Abstract

We extend the augmented graph of convex sets GCS framework for motion planning with temporal logic precedence specifications to dynamic environments in which obstacles, keys, and doors undergo piecewise-linear translation and/or dilation over time. The main insight is that piecewise-linear motion of polytopic sets in R^d lifts exactly to a static polytopic partition of spacetime R^d X R_>=0. We show that the main result from the static case carries over to spacetime essentially without modification: a shortest path in the spacetime augmented GCS provides an exact optimal solution to the motion planning problem with precedence specifications. Moreover, the layered subgraph lattice that encodes signal temporal logic (STL) precedence specifications retains precise correspondence with the Bellman--Held--Karp (BHK) algorithm, and the full library of restricted but expressive STL specifications generalizes to the dynamic setting. Further, the framework allows time-gated keys and doors, collectible or passable only within a temporal window. The geometric side of the framework requires two modifications: a causality constraint (the time coordinate of a trajectory must be non-decreasing) and a spacetime speed constraint (bounded physical velocity), both of which are convex in the Bézier control points.

0.23