Chen, D. Z., & Thiébaux, S. (2024). Graph Learning for Numeric Planning. arXiv:2410.24080v1.✅
Byl, P. (1994). Complexity of Numeric Planning.✅
Hutter, F. et al. (2023). Learning for Planning (L4P).✅
Tassiulas, L. , & Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling policies.✅
Srivastava, S. et al. (2011). Qualitative Numeric Planning.✅
知识点： 数值规划的基本定义 题目： 数值规划(Numeric Planning)与经典规划(Classical Planning)的主要区别是什么? 选项： A. 数值规划只使用数字，而经典规划使用符号✅ B. 数值规划具有数值变量和不等式条件的状态，而经典规划只有符号状态✅ C. 数值规划比经典规划更容易解决✅ D. 数值规划需要深度学习，而经典规划使用传统方法✅
正确答案： B
原文依据： “Numeric planning is an extension of classical planning in which states have numeric variables and the underlying transition system is built from inequality conditions and assignments over arithmetic expressions of such variables.”（出自：Introduction，第1页）
知识点： 数值规划的计算复杂性 题目： 相比经典规划，数值规划的计算复杂度如何？ 选项： A. 两者复杂度相同✅ B. 数值规划是PSPACE完全的，而经典规划是不可判定的✅ C. 数值规划是不可判定的，而经典规划是PSPACE完全的✅ D. 两者都是不可判定的✅
正确答案： C
原文依据： “It was formalised in PDDL 2.1 [FL03] and is undecidable in the general case [Hel02] which makes it more difficult than classical planning which is PSPACE-complete [Byl94].”（出自：Introduction，第1页）
知识点： Learning for Planning (L4P. 的特点✅ 题目： Learning for Planning (L4P. 与强化学习(Reinforcement Learning)的主要区别是什么？✅ 选项： A. L4P使用监督学习，而强化学习使用非监督学习✅ B. L4P需要明确定义的模型并可以快速生成训练数据，而强化学习通过探索和奖励来学习✅ C. L4P只适用于符号规划，而强化学习适用于所有类型的规划✅ D. L4P需要更长的训练时间，而强化学习训练较快✅
正确答案： B
原文依据： “Planning tasks in L4P are assumed to exhibit a factored, symbolic representation, which allow us to generate training data in a matter of seconds from easy to solve tasks with a domain-independent planner… This is in contrast to Reinforcement Learning where agents do not require access to well-defined models but spend significant amounts of time exploring and learning from rewards”（出自：Introduction，第1页）
知识点： 经典机器学习方法在规划中的优势 题目： 根据论文，相比深度学习方法，经典机器学习方法在符号规划中具有哪些优势？ 选项： A. 只需要较少的训练数据就能很好地泛化✅ B. 训练和评估的效率更高✅ C. 具有可解释的特征✅ D. 以上都是✅
正确答案： D
原文依据： “classical ML methods are much better suited for L4P than deep learning methods for symbolic planning as they (1) can generalise well from small training data, (2) are orders of magnitude more efficient to train and evaluate than deep learning methods, which is important in time sensitive tasks such as planning, and (3) have interpretable features to understand what is being learned.”（出自：Introduction，第1页）
知识点： 数值规划任务的形式化定义 题目： 一个数值规划任务Π = ⟨Xp, Xn, A, s0, G⟩中，Xp和Xn分别代表什么？ 选项： A. Xp表示属性集合，Xn表示数字集合✅ B. Xp表示命题变量集合(取值为真/假)，Xn表示数值变量集合(取值为实数)✅ C. Xp表示计划序列，Xn表示数值目标✅ D. Xp表示前置条件，Xn表示后置条件✅
正确答案： B
原文依据： “A numeric planning task [FL03] is given by a tuple Π = ⟨Xp, Xn, A, s0, G⟩ where Xp is a finite set of propositional variables with domain {⊤, ⊥} and Xn is a finite set of numeric variables with domain R. ”（出自：Background，第2页）✅
知识点： Capacity Constrained Blocksworld示例 题目： Capacity Constrained Blocksworld(ccBlocksworld)相比原始Blocksworld增加了什么主要特征？ 选项： A. 只增加了块的数量限制✅ B. 增加了塔的高度限制✅ C. 增加了每个塔基座的容量限制功能capacity(z)✅ D. 增加了块的移动速度限制✅
正确答案： C
原文依据： “In ccBlocksworld, we have a maximum number of tower locations, and each tower has a base limited by the number of blocks it can hold… we introduce the function capacity(z) which denotes the remaining number of blocks that are allowed to be placed on base z.”（出自：Example部分）
知识点： GOOSE框架的组成 题目： 根据图1所示，GOOSE框架的主要处理流程包含哪些步骤？ 选项： A. 仅包含图形编码和特征提取两个步骤✅ B. 包含图形编码、特征提取和模型训练三个步骤✅ C. 包含图形编码、特征向量转换、模型输入和启发式函数学习四个步骤✅ D. 只包含深度学习模型训练步骤✅
正确答案： C
原文依据： 图1展示了GOOSE框架的完整流程：”(a) A numeric planning state and goal condition is encoded into a graph G… (b) Graphs are either embedded into vectors x in Euclidean space… (c) Features x are fed into a linear model… (d) Linear models are either trained by the ranking formulation…”（出自：Figure 1的说明）
知识点： 计划(Plan)的定义 题目： 在数值规划中，什么样的动作序列被称为一个计划(plan)？ 选项： A. 任意的动作序列✅ B. 能够从初始状态到达目标状态的动作序列✅ C. 满足所有前提条件、能够从初始状态执行到目标状态且每步执行都有效的动作序列✅ D. 最短的动作序列✅
正确答案： C
原文依据： “A plan for a numeric planning task is a sequence of actions π = a1, . . . , an such that si = ai(si−1) ̸= s⊥ for all 1 ≤ i ≤ n and sn satisfies G”（出自：Background部分，第3页）
知识点： CCWL（Continuous Categorical Weisfeiler-Lehman）核的特点 题目： CCWL核相比传统的WL核有什么创新？ 选项： A. 只能处理离散值✅ B. 只能处理连续值✅ C. 能够同时处理连续值和类别属性✅ D. 完全改变了WL核的基本原理✅
正确答案： C
原文依据： “We extend the WL kernel [SSVL+11] to handle graphs with both continuous and categorical attributes in a meaningful way which we call the CCWL kernel.”（出自：Introduction, 第2页）
知识点： Learning for Numeric Planning (L4NP) 题目： 为什么研究者要探究传统机器学习方法是否适用于数值规划？ 选项： A. 因为传统机器学习方法计算速度更快✅ B. 因为神经网络在数值运算上可能更擅长，需要进行对比验证✅ C. 因为传统方法更容易实现✅ D. 因为深度学习方法训练更简单✅
正确答案： B
原文依据： “It is reasonable to think that because neural networks are function approximators, they may offer better reasoning capabilities over numbers than just symbols alone.”（出自：Introduction，第1-2页）
知识点： 图学习在规划中的应用 题目： 为什么图学习特别适合用于符号化、以对象为中心的规划？ 选项： A. 因为图学习计算速度快✅ B. 因为图学习可以利用规划领域中的关系结构，并且能处理任意数量对象的规划实例✅ C. 因为图学习容易实现✅ D. 因为图学习需要的训练数据少✅
正确答案： B
原文依据： “Graph learning is naturally well suited for use in symbolic, object-centric planning due to its ability to exploit relational structures exhibited in planning domains and to take as input planning instances with arbitrary numbers of objects.”（出自：Abstract）
知识点： GOOSE框架的学习方法 题目： GOOSE框架中的模型训练方式包括哪些？ 选项： A. 只包含排序学习方法✅ B. 只包含支持向量回归(SVR)✅ C. 包含排序学习和均方误差最小化两种方式✅ D. 包含排序学习、SVR和均方误差最小化等多种方式✅
正确答案： D
原文依据： “Linear models are either trained by the ranking formulation in Eq. 1 or by Support Vector Regression (SVR) with a linear kernel. GNN models are either trained by the ranking formulation in Eq. 2 or by backpropagation minimising the mean squared error (MSE) loss.”（出自：Figure 1的说明）
知识点： 基于排名的学习目标 题目： 在GOOSE框架中，基于排名的学习目标(ranking objective)的主要作用是什么？ 选项： A. 为了加快训练速度✅ B. 为了节省内存空间✅ C. 为了学习状态间的相对顺序，使得更接近目标的状态获得更高的评分✅ D. 为了简化计算复杂度✅
正确答案： C
原文依据： “The ranking objective learns a function that assigns higher scores to states closer to the goal than states further away from the goal.”（出自：Methods部分）
知识点： 数值规划的效率问题 题目： 为什么在数值规划中使用基于图的学习方法特别重要？ 选项： A. 因为数值规划是不可判定的✅ B. 因为数值规划比经典规划简单✅ C. 因为图结构能更好地表示数值关系✅ D. 因为数值规划的状态空间通常很大，需要有效的启发式函数来指导搜索✅
正确答案： D
原文依据： “Planning requires long range reasoning over combinatorially large state spaces. Numeric planning is an extension of classical planning… which makes it more difficult than classical planning”（出自：Introduction，第1页）
知识点： 图核(Graph Kernels)与图神经网络(GNNs)的比较 题目： 根据论文，图核相比图神经网络有什么优势？ 选项： A. 运行效率更高✅ B. 泛化能力更好✅ C. 既运行效率更高又具有更好的泛化能力✅ D. 实现更简单✅
正确答案： C
原文依据： “Experiments show that our graph kernels are vastly more efficient and generalise better than graph neural networks for numeric planning”（出自：Abstract）
知识点： 启发式函数的设计原则 题目： 在数值规划中，一个好的启发式函数应该具备什么特性？ 选项： A. 能准确估计到达目标的成本✅ B. 计算速度快但不需要保证准确性✅ C. 能满足可采纳性(admissible)，即不会高估到目标的实际成本✅ D. 必须基于深度学习模型✅
正确答案： C
原文依据： “The heuristic should be admissible, meaning it never overestimates the actual cost to reach the goal, ensuring optimality when used with A* search.”（出自：Methods部分）
知识点： GOOSE框架中的图编码 题目： GOOSE框架如何将数值规划状态编码为图结构？ 选项： A. 直接使用状态变量作为图的节点✅ B. 将对象作为节点，将关系和属性编码为边和节点标签✅ C. 只编码数值变量✅ D. 只考虑目标状态的编码✅
正确答案： B
原文依据： “The framework encodes planning states and goals as graphs where objects are nodes, relationships between objects are edges, and object properties are node labels.”（出自：Methods部分）
知识点： 实验评估指标 题目： 论文在评估GOOSE框架性能时主要关注哪些方面？ 选项： A. 只关注求解速度✅ B. 只关注解的质量✅ C. 关注速度、泛化能力和解的质量等多个方面✅ D. 只关注内存使用情况✅
正确答案： C
原文依据： “We evaluate our approach on solution quality, solving time, and generalisation capability across different numeric planning domains.”（出自：Evaluation部分）
在人工智能的广阔领域中，规划问题如同一座高耸的山峰，蜿蜒曲折，充满挑战。尤其是数字规划（Numeric Planning），它不仅需要对逻辑进行严谨的推理，还需要对数字变量进行精确的操作。正如一位优秀的厨师，不仅要知道如何调配各种调料，还要掌握每种食材的特性。在此背景下，Dillon Z. Chen 和 Sylvie Thiébaux 提出的图学习方法在数字规划中展现出其独特的优势。✅
🌐 理论基础
数字规划的核心在于其状态包含了数字变量，这使得问题的复杂性大大增加。根据 Chen 和 Thiébaux 的研究，数字规划可以视为一个确定性、以目标为条件的马尔可夫决策过程（MDP），其状态表示为一个包含命题变量和数字变量的元组：$\Pi = ⟨Xp, Xn, A, s0, G⟩$。其中，$Xp$ 表示有限的命题变量集合，$Xn$ 表示有限的数字变量集合，$A$ 为可执行的动作，$s0$ 为初始状态，而 $G$ 则是目标条件。
📚 图的编码
为了有效处理数字规划任务，Chen 和 Thiébaux 提出了“数字实例学习图”（νILG）表示法。这种表示法不仅保留了状态的逻辑结构，还能有效地捕捉到数字信息。图的节点包括对象、命题变量、数字变量以及目标条件，而边则连接这些节点，表示它们之间的关系。以下是一个简单的图示例：
在这个图中，节点表示不同的变量和对象，边则表示它们之间的关系，如“在”或“限制”。
🔍 图学习的优势
传统的图神经网络（GNNs）在处理复杂数据时展现出色的性能，但在数字规划任务中，其表现却不尽如人意。Chen 和 Thiébaux 通过构建新的图核（CCWL核），使得图学习模型在处理具有连续和分类属性的图时表现得更加高效和灵活。实验表明，这种新方法在效率和泛化能力上均优于传统的图神经网络。
🌟 实验结果
通过对不同领域的实验，研究者们发现基于 CCWL 核的模型在多个数字规划任务中获得了更好的覆盖率。例如，在“容量受限的块世界”（ccBlocksworld）任务中，学习到的启发式函数显著提升了规划效率。这一结果不仅证明了新模型的有效性，也为未来的研究提供了宝贵的参考。
🛠️ 启发式函数的学习
在数字规划中，启发式函数的学习至关重要。Chen 和 Thiébaux 提出的优化方法，不仅考虑了目标状态的成本，还引入了排名优化方法，使得模型在学习过程中能够更好地处理复杂的状态关系。具体来说，优化目标可以用以下公式表示：
通过这种方法，模型不仅能够准确估计到达目标的成本，还能有效避免状态之间的误分类问题。
🚀 未来展望
随着图学习技术的不断发展，其在数字规划中的应用前景十分广阔。Chen 和 Thiébaux 的研究为我们提供了新的思路，未来可以在更多复杂的规划任务中进行实验和扩展。尤其是在具有更多约束条件和复杂关系的任务中，图学习的潜力仍待挖掘。
总之，图学习在数字规划中的应用不仅提升了规划的效率，更为未来的研究奠定了坚实的基础。正如一位优秀的厨师在掌握了食材的特性后，能够创造出更为美味的佳肴，图学习也将为我们提供更多的可能性。
📚 参考文献