Planning algorithms usually assume you know exactly when a robot or agent will start moving. A new paper says that assumption breaks more often than planners admit.
Researchers tackle planning problems where feasibility shifts over time, like dodging moving obstacles or catching a train that is only boardable while it is stopped at the station. Most existing planners either ignore that dynamism or assume the start time is fixed and known in advance, which falls apart when execution cannot begin until another agent gives the go-ahead. The paper defines what it calls any-start-time planning and introduces a data structure called a compound arrival time function, or cATF, that encodes the optimal plan as a function of when execution begins rather than as a single fixed-cost path. Their graph-search algorithm builds cATFs by propagating these functions along edges instead of scalar costs, and the authors prove a cATF never grows more than linearly with problem size. Tests on SIPP, a standard moving-obstacle path-planning benchmark, showed that on hard instances, agents that replan from scratch once the start time becomes known often fail outright, while the cATF approach just looks up the precomputed answer.
This matters beyond SIPP. It applies anywhere a plan has to wait on a signal it does not control, like a warehouse robot queued behind a human operator or a shuttle merging into traffic managed elsewhere. The usual workaround, replanning the moment you learn the start time, turns out to be a reliability risk disguised as a simplification. Precomputing a function of start time instead of a single answer trades upfront compute for instant, dependable lookups later.
It is a benchmark result on one planning problem, not a deployed system, so the real test is whether cATFs hold up once obstacles, agents, and start-time uncertainty all multiply at once.