aiqbench analysis
This research introduces a novel data structure called the compound arrival time function (cATF) to solve planning problems where feasibility changes dynamically, such as navigating moving obstacles or boarding trains at specific times. By encoding optimal plans as functions of start time rather than scalar costs, the proposed algorithms enable efficient lookups even when execution timing is uncertain until the final moment. This advancement addresses a critical gap in classical planning theory, offering scalable solutions for real-world robotic and autonomous systems operating in non-static environments.
Optimal Planning in a Dynamic World
arXiv:2610.03312v1 Announce Type: new 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.
Authors:Devin Wild Thomas (1), Solomon Eyal Shimony (2), Wheeler Ruml (1), Erez Karpas (3), Shahaf S. Shperberg (2), Andrew Coles (4) ((1) University of New Hampshire, USA, (2) Ben-Gurion University of the Negev, Israel, (3) Technion - Israel Institute of Technology, Israel, (4) King's College London, UK)
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.
Artificial Intelligence (cs.AI)
arXiv:2610.03312 [cs.AI]
(or arXiv:2610.03312v1 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2610.03312 arXiv-issued DOI via DataCite (pending registration)
Full text under the publisher's open licence · 348 words
