提出动态树数据库，高效压缩规划中的状态集合
Dynamic Tree Databases in Automated Planning
- 设计可动态扩展的树形数据结构，压缩状态空间
- 在经典与数值规划任务中实现数个数量级的压缩比
- 适合大规模自动规划场景，运行开销极低
在大规模任务的显式状态空间搜索中，如何紧凑表示生成的状态集是一个核心挑战。树数据库（tree databases）源自模型检测，最佳情况下每个生成状态仅需常数空间，但需要预先分配大量内存。本文提出一种新型动态树数据库，用于压缩命题变量和数值变量的状态集合，并证明其保持了静态版本的优良特性。在基于实例化和提升的规划任务上的实证评估显示，该方法在经典与数值规划问题中实现了数个数量级的压缩比，且运行时间开销几乎可忽略。
原文摘要 · Abstract (English)
A central challenge in scaling up explicit state-space search for large tasks is compactly representing the set of generated states. Tree databases, a data structure from model checking, require constant space per generated state in the best case, but they need a large preallocation of memory. We propose a novel dynamic variant of tree databases for compressing state sets over propositional and numeric variables and prove that it maintains the desirable properties of the static counterpart. Our empirical evaluation of state compression techniques for grounded and lifted planning on classical and numeric planning tasks reveals compression ratios of several orders of magnitude, often with negligible runtime overhead.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。