Planning methods for changing environments that adapt to unknown start times
Optimal Planning in a Dynamic World
Artificial Intelligence
Summary
Planning a route or action can be tricky when conditions change over time, like trains arriving or moving obstacles in the way. This paper looks at how to plan when you don't know exactly when you'll start moving, which is often the case in real life. The authors introduce a new way to store all possible best plans depending on start time, so once you know when you can start, you can quickly find the best plan. Their experiments show this works better than replanning from scratch many times. This helps machines or robots plan smarter in changing situations.
What this means in practice
- •For robotics engineers: Develop robot navigation systems that can quickly find optimal paths in environments with moving obstacles without needing to know the start time ahead of execution.
- •For transportation planners: Create scheduling tools that determine best boarding plans for passengers when train arrival times are uncertain before planning finishes.
Authors
Devin Wild Thomas, Solomon Eyal Shimony, Wheeler Ruml, Erez Karpas, Shahaf S. Shperberg, Andrew Coles
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.