We address planning in environments where feasible states or actions vary over time. Typical examples are path planning among moving obstacles (SIPP) and boarding a train only while it is stopped at a station. Because obstacles or trains move, the feasibility of a location or action changes with time, causing the optimal plan and its duration to depend on the actual start time. In practice, the execution start time is often unknown until planning finishes or another agent gives the go‑ahead, yet most existing planners either ignore this dynamism or assume a known start time, which oversimplifies feasibility assessment and limits real‑world applicability.
We relax the known‑start‑time assumption and define any‑start‑time planning. The key technical contribution is the compound arrival time function (cATF), a compact representation that encodes the optimal plan as a function of the start time. Building on heuristic graph search, we replace scalar cost propagation with function propagation along edges, allowing cATFs to be assembled during the search.
We prove that the size of a cATF grows at most linearly with the problem size. Experiments on the SIPP problem show that, on hard instances, agents that rely on replanning often fail, whereas any‑start‑time algorithms using cATFs can instantly retrieve the optimal plan once the actual start time is known.
By enabling efficient representation and reasoning for time‑dependent plans, this work lays a foundation for planning in dynamic worlds.
Review