arXiv:2501.15249cs.AI2025-01AAAI被引 4

提出自动抽象方法,让通用规划在可变数量对象下仍能保证正确性。

An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types

  • 用计数器抽象同类对象,构建可验证的简化模型
  • 在特定条件下,抽象后求解的计划可直接用于原问题
  • 适合处理对象数量可变的规划任务,如仓储、调度

通用规划旨在找到一个能解决多个相似规划实例的单一计划。抽象技术广泛用于通用规划,其中定性数值规划(QNP)是常见抽象模型。近期研究证明:若一个计划能解决一个声音且完备的抽象问题,则其精化后可解原问题。然而,现有自动抽象方法难以保证声音性,更无法保证完备性。本文提出一种针对可打包类型(baggable types)的通用规划自动声音且完备抽象方法。采用一种变体QNP——有界QNP(BQNP),其中整型变量仅增减1。由于BQNP不可判定,我们设计并实现了一个声音但不完备的求解器。提出从经典规划实例自动生成BQNP问题的方法:为每组不可区分的对象包引入计数器。定义了‘合适可打包域’类别,证明在此类域中,通过该方法获得的BQNP问题是通用规划问题的声音且完备抽象——其实例共享相同对象包结构,但包大小可不同。因此,对BQNP问题的解进行精化后,即为通用规划问题的解。我们在多个领域实现该方法,实验验证了其有效性。

原文摘要 · Abstract (English)

Generalized planning is concerned with how to find a single plan to solve multiple similar planning instances. Abstractions are widely used for solving generalized planning, and QNP (qualitative numeric planning) is a popular abstract model. Recently, Cui et al. showed that a plan solves a sound and complete abstraction of a generalized planning problem if and only if the refined plan solves the original problem. However, existing work on automatic abstraction for generalized planning can hardly guarantee soundness let alone completeness. In this paper, we propose an automatic sound and complete abstraction method for generalized planning with baggable types. We use a variant of QNP, called bounded QNP (BQNP), where integer variables are increased or decreased by only one. Since BQNP is undecidable, we propose and implement a sound but incomplete solver for BQNP. We present an automatic method to abstract a BQNP problem from a classical planning instance with baggable types. The basic idea for abstraction is to introduce a counter for each bag of indistinguishable tuples of objects. We define a class of domains called proper baggable domains, and show that for such domains, the BQNP problem got by our automatic method is a sound and complete abstraction for a generalized planning problem whose instances share the same bags with the given instance but the sizes of the bags might be different. Thus, the refined plan of a solution to the BQNP problem is a solution to the generalized planning problem. Finally, we implement our abstraction method and experiments on a number of domains demonstrate the promise of our approach.

通用规划抽象方法可打包类型定性数值规划

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。