arXiv：cs.AI· Devin Wild Thomas (University of New Hampshire, USA), Solomon Eyal Shimony (Ben-Gurion University of the Negev, Israel), Wheeler Ruml (University of New Hampshire, USA), Erez Karpas (Technion - Israel Institute of Technology, Israel), Shahaf S. Shperberg (Ben-Gurion University of the Negev, Israel), Andrew Coles (King's College London, UK)·· 5 小时前AI 评分36
动态世界中的最优规划：任意起始时间规划与 cATF 数据结构
Optimal Planning in a Dynamic World
AI 导读
研究者提出"任意起始时间规划"设定，放宽规划需已知执行起始时间的假设，并给出基于启发式图搜索的通用算法。其核心数据结构复合到达时间函数（cATF）将最优计划编码为起始时间的函数，沿边传播函数而非标量代价，规模最多与问题规模呈线性关系。在 SIPP 移动障碍物路径规划实验中，依赖重规划的智能体在困难问题上常失败，而使用 cATF 的算法在起始时间确定后可快速查出最优计划。
正文
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.
| Comments: | 48 pages, 25 figures |
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | 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) |
Submission history
From: Devin Thomas [view email]
[v1]
Fri, 2 Oct 2026 13:50:36 UTC (1,214 KB)
来源：arXiv：cs.AI · arxiv.org