Authors: Devin Wild Thomas, Solomon Eyal Shimony, Wheeler Ruml, Erez Karpas, Shahaf S. Shperberg, Andrew Coles
Organizations: University of New Hampshire, USA · Ben-Gurion University of the Negev, Israel · Technion - Israel Institute of Technology, Israel · Technion – Israel Institute of Technology, Israel · King's College London, UK · King’s College London, UK
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.
Figures & tables
Figure 1: Typology of SIPP and TDSP Planning Problems.
Figure 2: Food delivery robot example.
Figure 3: Point obstacle O moves with velocity −1/s , approaching point agent A .
Figure 4: An edge ATF with parameters ⟨ζ,α,β,Δ⟩ .
Figure 5: An example SIPP ATF compilation for edge e∈E from u∈S to v∈S .
Figure 6: Example demonstrating α>β in a plan ATF.
Figure 7: Counterexample to SIPP dominance for Augmented SIPP with ≤↓f↑α↑β (or ≤↓f↑α ).
Figure 8: State C has been added to the delivery robot example (Figure 2 ) to illustrate calculating the ATF of a multi-edge plan.
Figure 9: Compound ATFs from the Delivery Robot Example (see Figure 8 )
Figure 10: A SIPP plan ATF with parameters ζ,α,β , and Δ .
Figure 11: Compound ATF plan insertion example: p3 is inserted into {p1,p2} . The three plan ATFs A[p1],A[p2], and A[p3] are shown with segments strongly dominated by {p1,p2,p3} dotted. The breakpoints of {p1,p2,p3} are b0,...,b7 .
Figure 12: Examples of the interaction of two plan ATFs A[p1] and A[p2] in forming the cATF A[s,d]
Figure 13: Examples of the two possible configurations for a ζ image, b .
Figure 14: Example of the four possible configurations for an α image, b .
Figure 15: Example of the four possible configurations for an β image, b .
Figure 16: Example of the two possible configurations for a minimization breakpoint, b .
Figure 17: Benchmark grid maps.
Figure 18: SIPP geometric mean runtime and unsolvable rate, for 2D grid pathfinding instances with random obstacles with (minDuration, maxDuration) ∈{(5,50),(10,100),(50,500)} , and occupancy ∈[0.05,0.93] .
Figure 19: The distribution of SIPP expansion rates on randomly generated SIPP instances.
Figure 20: Augmented SIPP Overhead
Figure 21: aSIPP αβ Overhead
Figure 22: The time for which SIPP plans are valid versus the time required to find them.
Figure 23: The distribution of the number of reference time updates for RePEAT over the instances for our three different maps.
Map
den520d
random512
64room
% Solved in 30 min
60.3
77.8
96.3
% Solved in 100 s
34.5
36.1
80.5
Table 1: RePEAT Performance
Figure 24: Ratio of Augmented SIPP calls to resulting solution ATF size for RePEAT instances that found a solution.
Figure 25: Average online query time for ATFs generated by the RePEAT experiments.
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× speedup over state-of-the-art spatiotemporal planners.
Executing a multi-agent plan can be challenging when an agent is delayed, because this typically creates conflicts with other agents. So, we need to quickly find a new safe plan. Replanning only the delayed agent often does not yield an efficient plan, and sometimes cannot even yield a feasible one. On the other hand, replanning other agents may lead to a cascade of changes and delays, and it is computationally expensive. We show how to efficiently replan a single delayed agent by tracking and using the temporal flexibility of other agents while avoiding cascading delays. This flexibility is the maximum delay that the agent can take without changing the order with agents other than the initially delayed agent, or further delaying other agents. Our algorithm, FlexSIPP, precomputes all possible plans for the delayed agent and returns the changes to the other agents within the given scenario. We demonstrate our method in a real-world case study of replanning trains in the densely-used Dutch railway network and in the MovingAI MAPF benchmark set. Our experiments show that FlexSIPP provides effective solutions relevant to real-world adjustments, and within a reasonable timeframe.
Issa Hanou, Eric Kemmeren, Devin Wild Thomas +1
Delft University of Technology · University of New Hampshire
Safe navigation under uncertain time-dependent blockage requires anticipating observations before committing to motion. We present StochSIPP, an exact contingent planner for temporal roadmaps with uncertain edge and vertex statuses revealed locally during execution. StochSIPP uses SIPP to generate certified-safe macro-actions that terminate at the next observation or the goal, and bounded AND/OR search over a cached action--observation graph to select actions for every reachable observation outcome. Optimistic and robust SIPP relaxations provide admissible lower and upper bounds for bounded AND/OR search. When every interval declared deterministically safe is truly safe, sensing is exact, and execution follows the planned timing, the resulting policy is provably collision-free. With correct independent probabilities and complete action and outcome generation, it minimizes expected arrival time within the roadmap and horizon. Experiments on controlled roadmap instances show that StochSIPP preserves the observed success of safe fixed-path baselines while reducing arrival time, and solves gated scenarios in which conservative fixed-path planners return no plan. A scalability study further reveals rapid growth as the number of simultaneously observed uncertain statuses increases.
Ajith Kemisetti, Shahaf S. Shperberg, Yoonchang Sung
The University of Texas at Austin · Ben Gurion University of the Negev · Nanyang Technological University