PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Planning in a Dynamic World

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

arXiv:2610.03312v1cs.AI

TL;DR

When state or action feasibility changes over time, optimal plans depend on the execution start time, which may be unknown during planning. The paper uses arrival-time functions in heuristic search to plan across start times; it proves linear plan size and reports that replanning can fail on difficult SIPP problems where any-start-time planning appears fast enough.

  • Problem

    In dynamic worlds, optimal plans can depend on execution start time, but planning methods commonly assume a known start time or a static world.

    Source: §1 · p. 1

  • Method

    The paper plans across start times using arrival-time functions and heuristic search that composes function-valued costs.

    Source: §1 · p. 2, §3.2 · p. 10, §4.4 · p. 17

  • Results

    The algorithms are proved correct and produce plans of at most linear size; experiments found SIPP problems where replanning utterly fails while any-start-time planning appears fast enough for practical use.

    Source: §9 · p. 46

  • Takeaways & Limitations

    Any-start-time planning can reveal how long SIPP plans remain valid with minimal additional overhead and help agents cope with dynamic environments despite unpredictable planner runtime.

    Source: §9 · p. 46

    The formulation assumes complete knowledge of the environment, including present and future state and edge safety.

    Source: §2.1.1 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

In dynamic worlds, a plan’s feasibility and optimality can depend on when execution begins, yet that start time may not be known when planning must start. The paper introduces any-start-time planning and illustrates how its optimal plan changes with departure time.

1 Introduction

  • Unknown execution times arise when planning must finish before an external event or permission to act, while traditional approaches assume a known start time or static world.A plan ready in advance can avoid waiting until the desired start time is known to begin planning.Source: §1 · p. 1
  • The paper positions any-start-time planning within time-dependent shortest paths, whose general solutions can grow super-polynomially.The introduction contrasts this with the linear-sized solutions of its SIPP-based subset.Source: §1 · p. 2
  • Any-start-time planning generalizes SIPP to find optimal plans for all start times, with solution size linear in problem size.The resulting plan can defer commitment to an execution start time until online.Source: §1 · p. 2

1.1 Running Example: Food Delivery Robot

  • In the delivery example, a train blocking the faster road creates breakpoints where the slower route or waiting for the train becomes optimal.The plotted arrival-time function has constant or increasing segments corresponding to waiting or acting.Source: §1.1 · p. 3
  • The any-start-time approach represents plan costs as functions of time and uses function composition rather than scalar addition in heuristic search.It represents states and actions as safe or unsafe over continuous time.Source: §1 · p. 2, §1.1 · p. 3

2 Background

The background connects safe interval path planning (SIPP) with time-dependent shortest paths (TDSP), identifying any-start-time planning as their linearly sized overlap. It reviews SIPP’s interval representation and earliest-arrival search before outlining the broader TDSP framework.

2 Background

  • Any-start-time planning is the intersection of SIPP and the TDSP subset with linearly sized solutions.The paper states that this relationship had not previously been specifically explored.Source: §2 · p. 4

2.1 Safe Interval Path Planning

  • SIPP represents dynamic environments through safe intervals for states and actions, covering time-dependent applicability beyond collision-free pathfinding.The paper notes applications including multi-agent pathfinding, railway planning, and robotic manipulators.Source: §2.1 · p. 4

2.1.1 Problem Statement: Safe Interval Path Planning

  • A SIPP state pairs a configuration with a safe time interval, while an edge specifies when departure is safe and has a constant action duration.The formulation assumes ample planning time and complete knowledge of present and future state and edge safety.Source: §2.1.1 · p. 5

2.1.2 SIPP Example: 1D Moving Obstacle

  • In the one-dimensional moving-obstacle example, the obstacle’s arrival determines safe-interval endpoints and can make an action edge unavailable.The agent’s move toward the obstacle is never safe, so that edge is omitted from the SIPP graph.Source: §2.1.2 · pp. 5–6

2.1.3 Solving SIPP

  • SIPP prunes search using temporal dominance: arriving at a state as early as possible is optimal because the agent can wait within its safe interval.Successor arrival times are constrained by edge and destination intervals before pruning.Source: §2.1.3 · pp. 6–7

2.2 Time-Dependent Shortest Paths

  • TDSP seeks shortest paths for all departure times using time-dependent edge costs, represented here through arrival-time functions.General TDSP solutions can be super-polynomial, while a restricted family of edge slopes has linear solution complexity and includes SIPP’s case.Source: §2.2 · pp. 7–8

3 Heuristic Search with Arrival Time Functions

Augmented SIPP extends SIPP to return a plan alongside an arrival-time function, capturing related plans across different start times. It compiles safe-interval constraints into edge functions, composes them for paths, and searches over those functions.

3.1 Compiling the Augmented SIPP Graph: Calculating Edge ATFs

  • If safe intervals are inexact, SIPP may be incomplete relative to the real problem being modeled.An example is modeling an irregular obstacle with a bounding circle.Source: §3.1 · p. 8
  • Each edge receives a piecewise-linear ATF compiled from its edge, source-state, and destination-state safe intervals.The ATF uses four parameters and represents unsafe departure times with an infinite arrival time.Source: §3.1 · pp. 9–10

3.2 Augmented SIPP Plan Costs: Calculating Path ATFs

  • Composition preserves the edge ATF structure, but intermediate waiting can yield plan ATFs with α>β; e1e2e3 has parameters ⟨0,6,2,3⟩.In the example, the first edge permits departure only before time 2, while the final edge requires waiting until time 8.Source: §3.2 · pp. 10–11

3.3 Augmented SIPP: Heuristic Search With ATFs

  • Augmented SIPP propagates plan ATFs during successor generation and returns the goal plan’s ATF, while expanding the same nodes as SIPP.It replaces scalar g-values with plan ATFs and retains SIPP’s tie-breaking and heuristic.Source: §3 · p. 8, §3.3 · pp. 12–13

4 Theoretical Properties of Augmented SIPP

This section establishes theoretical properties of Augmented SIPP, including when cost-ordering or ATF-dominance pruning preserves optimal plans and how α/β tie-breaking affects isotonicity. It also describes how aSIPPαβ supports any-start-time planning using optimistic open-list bounds and solutions optimal over nonzero intervals.

4 Theoretical Properties of Augmented SIPP

  • Any-start-time planning uses α and β tie-breaks to favor plans optimal for longer and valid for longest, respectively, supporting efficient progress in RePEAT.These orderings are unavailable to regular SIPP; the section frames the secondary sort as a tie-break for a well-behaved ordering.Source: §4 · p. 13, §4.4 · p. 17

4.1 Augmented SIPP is SIPP

  • With the same scalar heuristic, node ordering, pruning, and tie-breaking, Augmented SIPP and SIPP expand the same states in the same order with equivalent g-values.Under a shared ordering, Augmented SIPP also retains SIPP’s completeness and optimality properties.Source: §4 · p. 13, §4.1 · p. 15

4.2 Background: Cost-algebraic Heuristic Search

  • A cost algebra represents edge and path costs with a cost set, composition operator, ordering, and identity, generalizing scalar-cost accumulation.For Augmented SIPP, ATFs are composed along a plan instead of scalar costs being summed.Source: §4.2 · p. 15, §4.4 · p. 17

4.3 Pruning in Cost-algebraic Heuristic Search

  • Pruning a cost-algebraic search using its total cost ordering does not eliminate all optimal plans, by isotonicity.If one of two plans to a shared state is no worse, extending both by the same suffix preserves that ordering.Source: §4.3 · p. 16

4.4 Augmented SIPP is a Cost-algebraic A*

  • Augmented SIPP is a cost-algebraic A* under f and f/g orderings, yielding admissibility and, for isotone orderings, optimal efficiency.Its path costs are ATFs composed along plans rather than scalar costs summed along edges.Source: §4.4 · pp. 17–18

4.5 Pruning vs Node Ordering in Cost-algebraic Search With Non-isotone Tie-breaking

  • With ≤↓f↑α↑β, an earlier-arriving path can be worse after extension because a stricter α constraint erases its arrival advantage while another path remains valid longer.The example shows the extended ATF bc dominates ac, so pruning by the total search ordering can discard a better continuation.Source: §4.5 · p. 19
  • Weaker pruning retains more non-dominated nodes to find a solution respecting the full ≤↓f↑α↑β ordering, making it more informative and reducing later any-start-time searches.The tradeoff is doing less pruning in the initial Augmented SIPP search and potentially more expansions there.Source: §4.5 · pp. 19–20
  • ATF-dominance pruning preserves optimal plans, and with an admissible heuristic the first goal expanded by aSIPPαβ is optimal.ATF dominance is isotonic, so a dominated node can be safely pruned; the total ordering is not a safe substitute for this pruning rule.Source: §4.5 · p. 20

4.6 How aSIPPαβ Aids Any-start-time Planning

  • With an admissible heuristic, the open list collectively underestimates the any-start-time plan cost, while retaining a node representing a state along each hypothetical optimal plan.The retained node’s ATF is no greater than the corresponding optimal-plan ATF.Source: §4.6 · p. 21
  • An admissible-heuristic aSIPPαβ solution dominates all other nodes in its f-layer on [0, β), guaranteeing optimality for a strictly positive duration.Its optimality may continue until β or until its ATF intersects a higher-f node’s ATF.Source: §4.6 · p. 21

5 Solving Any-start-time Planning

Any-start-time planning extends SIPP to find optimal plans for every safe departure time. It represents the solution as a compound arrival time function (cATF) that can be queried for the optimal plan and arrival time.

5 Solving Any-start-time Planning

  • Figure 8 adds state C to the delivery-robot example to illustrate calculating an ATF for a multi-edge plan.Source: Figure 8 · p. 22
  • @SIPP seeks a shortest plan to the goal for every safe departure time from the initial state.Its solution is represented as a cATF queried for the optimal plan and corresponding arrival time at a given departure time.Source: §5 · pp. 21–22
  • RePEAT repeatedly runs aSIPPαβ from increasing start times and stores the results in a cATF.It updates a reference time to track how far into the future the current plans are provably optimal.Source: §5 · p. 22

5.1 Worked Example: Delivery Robot Any-start-time Planning

The delivery-robot example illustrates how Augmented SIPP computes plans over time and how RePEAT extends the set of start times for which those plans are optimal.

5.1 Worked Example: Delivery Robot Any-start-time Planning

  • The example adds state C before the rail crossing so that some delivery plans contain multiple edges.It restricts the scenario to one day and uses the 24-hour clock with durations in minutes.Source: §5.1 · pp. 22–23
  • Augmented SIPP initializes its search with the identity ATF and orders the open list by earliest expected arrival time.The example uses h(n) as cost-to-go assuming states and actions are always safe.Source: §5.1 · p. 23
  • Expanding the initial restaurant state generates successors along its two outgoing edges, and expanding RC considers two plans through RCA.The second RCA plan is retained because it is not dominated, despite having a worse g(n).Source: §5.1 · p. 23
  • RePEAT starts another Augmented SIPP search when the current plan is no longer known to be optimal for later departures.In the example, the next search starts at 15:19; a later search starts at 15:29 after the current plan’s optimality ends.Source: §5.1 · pp. 23–24
  • Figure 9a distinguishes plan portions proven optimal from portions whose optimality remains unknown to the search; Figure 9b shows the final cATF.Source: §5.1 · p. 24

5.2 Solving @SIPP: RePEAT

RePEAT repeatedly runs Augmented SIPP from later reference times and accumulates a set of plans covering start times. Its reference-time update marks how far the current plans are provably optimal.

5.2 Solving @SIPP: RePEAT

  • RePEAT repeatedly calls aSIPPαβ with monotonically increasing start times to build plans that contain the optimum for any start time.Unlike Augmented SIPP, which finds one plan optimal for a specified start time, RePEAT accumulates plans over time.Source: §5.2 · p. 24
  • RePEAT is an anytime algorithm: as it runs, it extends the future horizon for which it has optimal plans.If the reference time progresses at least as fast as time passes, RePEAT will have an optimal solution when signaled to act.Source: §5.2 · pp. 24–25
  • After each search, RePEAT advances the reference time to the earliest departure time when the solution is no longer provably optimal, then adds the latest solution to the cATF.The reference-time update uses the open list returned by aSIPPαβ.Source: §5.2 · p. 25
  • The search begins with a cATF mapping the entire timeline to infinite cost, then repeatedly searches from the current reference time.This initial mapping reflects that no goal-reaching plans have yet been found.Source: §5.2 · p. 25

5.3 Representing Any-Start-Time Plans: Compound ATFs

A cATF represents which plan is optimal at each departure time, enabling fast plan and arrival-time queries. Its interval mapping is updated as plans are inserted and compared.

5.3 Representing Any-Start-Time Plans: Compound ATFs

  • A cATF is an ordered mapping from time intervals to plans, with each interval identifying a plan optimal for those departure times.A plan may map to multiple disjoint intervals; the mapping has coverage and correctness properties.Source: §5.3 · pp. 25–26

5.3.1 Plan Insertion

  • Insertion takes the lower hull of the existing cATF and the new plan’s ATF, retaining the better plan over each interval.A new plan can dominate on two disjoint intervals, which the separate flat and rising segments can represent.Source: §5.3.1 · pp. 26–27
  • Plan insertion has worst-case complexity O(|c| ln(|c| + |p|)), linear in overlapping segments and logarithmic in the compound ATF size.The implementation uses interval overlaps to determine which segments to retain.Source: §5.3.1 · p. 27

5.3.2 Calculating Arrival Times with a Compound ATF

  • A compound ATF query uses binary search over its ordered intervals, then computes arrival time from the ATF mapped to the matching interval.The query runtime is O(log(c)).Source: §5.3.2 · p. 27

5.3.3 Compound ATF Dominance

  • Dominance checking compares ATFs at their breakpoints; for ordered ATFs, its runtime is O(|A| + |A′|).For two plan ATFs the check is O(1), while a compound ATF may require checking all breakpoints.Source: §5.3.3 · pp. 27–28

5.4 Updating the Reference Time

RePEAT advances a reference time by checking when its current plan may cease to be optimal, and the paper proves that it is complete and optimal over time.

5.4 Updating the Reference Time

  • The reference time marks the earliest start time for which an optimal solution is not yet known, and the update seeks the latest newly certified time.The update examines where other open nodes' arrival time functions intersect the current solution's function.Source: §5.4 · p. 28
  • The returned solution dominates other plans optimal at the reference time, but need not dominate plans that become optimal later, particularly after β(n).The solution is optimal at the reference time and at least until α(n).Source: §5.4 · p. 28
  • The update checks for intersections between the solution's rising segment and open nodes' flat segments, returning the earliest intersection or β(solution) if none occurs before it.If open is empty, the new reference time is infinity.Source: §5.4 · p. 29
  • The reference-time update traverses open in O(|open|log(|open|)) worst-case time, or can use an unordered traversal in O(|open|).The authors note that either traversal leaves overall runtime unchanged because open was already constructed during the search.Source: §5.4 · p. 29
  • RePEAT is complete and optimal for all time because its reference time increases monotonically while each iteration preserves optimality through that time.The proof combines the initial optimal solution, monotonic reference-time updates, and induction.Source: §5.4 · p. 29

5.5 Replanning SIPP

RSIPP waits until execution begins, runs SIPP from the current time, and retries if planning finishes with an invalid plan.

5.5 Replanning SIPP

  • RSIPP waits until the start time, runs SIPP from the current time, and returns the plan only if it remains valid after planning completes.If the plan is no longer valid, the algorithm loops back and runs SIPP again.Source: §5.5 · pp. 29–30
  • RSIPP performs no computation ahead of time; it waits until the start time before running its planner.It is presented as an offline planner used at query time.Source: §5.5 · p. 29
  • RSIPP returns a single plan and therefore does not solve the any-start-time planning problem.Source: §5.5 · p. 29

6 On the Complexity of Any-start-time Planning

This section analyzes the complexity of any-start-time planning, establishing a linear space bound for plans and a quasi-quadratic worst-case runtime bound for RePEAT in terms of safe intervals and reference-time breakpoints.

6.1.1 Illustrating the Possible Types of ATF Breakpoints

  • ATF segments have slopes {−∞,0,1,∞}, and every non-redundant pair of minimization breakpoints has an α breakpoint between them.A distinct minimization breakpoint not also an image must be followed by an α image.Source: §6.1.1 · pp. 31, 34

6.1.2 Constraining the Number of Primitive Images

  • The solution has linearly many primitive breakpoints because each edge breakpoint contributes at most one image, with at most three edge breakpoints per edge.The solution ATF is monotone non-decreasing; plans with loops are dominated.Source: §6.1.2 · pp. 34–35

6.1.3 Constraining the Number of Minimization Breakpoints

  • Each minimization breakpoint is followed by an α image, so minimization breakpoints are also linear in the number of graph edges.This bounds all compound ATF breakpoints, yielding linear space complexity.Source: §6.1.3 · pp. 35–36

6.1 The Space Complexity of Any-Start-Time Plans

  • The compound arrival-time function has linear space complexity in the number of graph edges.The input graph size counts safe intervals on states and actions, or the local search space in an infinite state space.Source: §6.1 · p. 30, §6.1.3 · p. 36

6.2 Time Complexity of RePEAT

  • RePEAT runs in O((|E| + |V|)|E|log(|V|)) time.The bound follows from a linear number of calls to Augmented SIPP, each taking O(|E|log(|V|)) time.Source: §6.2 · p. 36
  • At most |E|+|V| Augmented SIPP rounds are required, giving worst-case runtime O((|E|+|V|)|E| log(|V|)), quasi-quadratic in the number of safe intervals.Each reference-time update either adds a plan ATF with a primitive image or eliminates a primitive image from the compound ATF.Source: §6.2 · p. 36

7 Empirical Evaluation

The evaluation tests Augmented SIPP, replanning, and RePEAT on dynamic-obstacle grid problems, finding that replanning can be too slow for plan validity while RePEAT plans can be queried quickly. It also examines search overhead and the factors that shape RePEAT’s runtime.

7.1.2 Problem Instance Generation

  • The benchmark used three contrasting Moving AI Lab maps and random time-dependent obstacles, with SIPP runs used to select challenging settings that mostly remained solvable.The selected settings were minDuration = 10, maxDuration = 100, and occupancy = 0.35; tests used reproducible instances and a roughly 1 MHz measured SIPP expansion rate.Source: §7.1.2 · pp. 37, 40, §7.1.3 · p. 40

7.2 The Practicality of Augmented SIPP

  • Augmented SIPP’s median runtime overhead was −2%, −8%, and −11% for den520d, random512, and 64room, respectively.The central 95% of overhead values spanned [−24.1%, 0.9%], [−30.0%, 8.1%], and [−30.6%, 7.9%], respectively; overhead was typically negative.Source: §7.2 · pp. 40–41, Figure 20 · p. 41
  • aSIPPαβ runtime exceeded Augmented SIPP by over 100× in some cases, while its expansion counts generally grew as a relatively low-power function of SIPP expansions.The authors interpret this as more expansions, but not exponentially more, than the corresponding SIPP searches.Source: §7.2 · p. 41, Figure 21 · p. 42

7.3 The Adequacy of Replanning

  • 0.6%, 10.8%, and 11.1% of den520d, random512, and 64room instances took longer to plan than the resulting SIPP plans remained valid.In those cases, replanning may be inadequate; an agent may repeatedly fail to plan quickly enough to execute, or discover invalidity only after much of the plan.Source: §7.3 · pp. 41–42, Figure 22 · p. 42

7.4 The Practicality of RePEAT

  • RePEAT instances split between low-level hard cases dominated by a few difficult searches and high-level hard cases requiring many searches for more complex plans.The frequency of low-level hard cases may differ because bottlenecks can produce simpler ATFs; den520d may have more frequently changing optimal plans.Source: §7.4 · pp. 42–43, Figure 23 · p. 43
  • Many instances were challenging, yet RePEAT planned the next 100 seconds within 100 seconds; den520d was hardest for RePEAT despite being easiest for SIPP.The experiments also measured whether RePEAT found a 100-second plan within the 30-minute limit.Source: §7.4 · p. 43
  • The geometric-mean ratio of Augmented SIPP calls to solution ATF size was 1.02, with a maximum of 2.0.For solved instances, the ratio’s 95% confidence interval for the geometric mean was [1.015, 1.025].Source: §7.4 · p. 43
  • Online queries of RePEAT’s solution ATFs took less than a microsecond on average, though a cache miss can slow a single query.The reported average was based on one billion uniformly drawn queries per solution ATF over [0,100).Source: §7.4 · p. 43

8 Discussion

Any-start-time plans can support decisions about delays, trade-offs, backup actions, and coordination among agents. The discussion situates the approach among time-dependent shortest-path, temporal-planning, and replanning methods, and describes its applicability beyond grid pathfinding.

8.1 Applications of Any-start-time Planning

  • Any-start-time plans let an agent assess the arrival-time trade-off of taking on a second delivery before completing its original one.A situated planner can also use the plan to evaluate whether additional search is worth delaying execution.Source: §8.1 · pp. 43–44
  • A backup any-start-time plan can encode emergency avoidance maneuvers, while multi-agent planners can query plans to estimate delay costs and adjust routes.The discussion describes trains treating other trains’ nominal plans as dynamic obstacles and querying contingency plans when delays occur.Source: §8.1 · p. 44
  • The methods apply beyond grid pathfinding to planning problems with time-varying state or action feasibility and an earliest-goal objective.The paper identifies that formulation as sufficient for calculating any-start-time plans.Source: §8.1 · p. 44
  • The approach represents cost-so-far g as a function composed along a plan, complementing related real-time SIPP work that backs up cost-to-go h using ATFs.The discussion frames function-valued heuristic search as a broader use of ATFs.Source: §8.1 · pp. 44–45

8.2 Related Work

  • The paper specializes time-dependent shortest-path planning and generalizes SIPP, while distinguishing its setting from temporal planning without exogenous change and replanning-based methods.The discussion reviews prior TDSP formulations and notes that incremental search still requires viable planning times, whereas real-time search is limited to forgiving domains without dead ends.Source: §8.2 · pp. 45–46

9 Conclusion

The conclusion frames unknown execution start time as a reason to represent plan cost as a function of time. It reports correct algorithms with plans of at most linear size and experimental evidence that replanning can fail while any-start-time planning can be practical.

9 Conclusion

  • Representing plan cost as a function of time supports compact composition across plans and new best-first heuristic-search variants.The paper adapts results from time-dependent shortest-path work to represent and compose these functions.Source: §9 · p. 46
  • The algorithms are proved correct, and the resulting plans are at most linear in problem size.The conclusion also reports SIPP experiments in which replanning can fail, while any-start-time planning appears fast enough for practical use.Source: §9 · p. 46
  • For SIPP, any-start-time planning reveals how long a plan is valid with minimal additional overhead, and it offers a way to handle dynamic environments when runtime is hard to predict.The work also provides function-valued representations for heuristic search when g and f are better represented as functions than scalars.Source: §9 · p. 46
Loading 2610.03312v1…