自动规划是人工智能的一个分支,研究如何通过计算确定行动,将初始情境转变为满足指定目标的情境。规划系统接收世界的某种表示、智能体可采取的行动以及期望结果,然后构建计划或策略。根据问题的不同,系统的输出可以是行动序列、具有偏序关系的一组活动、带有时间安排的调度方案,也可以是根据观测结果选择行动的策略。
规划的特点在于显式推理行动的后果及其相互作用。例如,一项配送任务可能需要决定由哪辆车运送包裹、车辆是否必须先加油,以及哪些活动可以同时进行。该领域融合了知识表示与推理、搜索、数学优化以及不确定条件下的决策。其方法广泛应用于航天器运行、工业工作流程、自主机器人和软件智能体等领域。
经典规划为这一领域奠定了尤为重要的基础:它假定初始状态已知、行动具有确定性,而且世界只会通过模型中表示的行动发生变化。其他规划形式则引入了时间、资源、不完全信息、随机结果、相互作用的智能体或层次化过程。在这些不同形式中,一个核心区别始终存在:找到在模型中正确的计划,并不等于确保该计划能在物理环境或计算环境中成功执行。
历史发展与思想基础
自动规划源于早期关于问题求解和符号人工智能的研究。自20世纪50年代末起,艾伦·纽厄尔、赫伯特·A. 西蒙和J. C. 肖开始开发通用问题求解器,探索手段—目的分析:将当前情境与目标进行比较,选择能够缩小差距的算子,并建立应用该算子所需的条件。尽管这一系统的表示能力和性能有限,但它确立了一种影响深远的智能行动观:智能行动在于构建中间子目标,而非直接选择一个孤立的响应。
另一项重要的理论基础来自逻辑。在由约翰·麦卡锡提出,并经帕特里克·海斯等人后续发展的情境演算中,动作被表示为产生新情境的过程,而逻辑语句则描述在这些情境中哪些命题成立。这揭示了框架问题:如何明确说明一个动作发生时,哪些事物保持不变。移动一个箱子会改变它的位置,但通常不会改变它的颜色、其他每个箱子的位置,或某个无关房间内的物品。高效的规划表示需要刻画这种持续不变性,而不必为每个动作逐一列举所有不受影响的事实。
理查德·法イク斯和尼尔斯·尼尔森于1971年在Shakey机器人项目中推出的STRIPS规划系统,提供了一种影响尤为深远的操作性表示方法。动作通过前置条件以及待添加或删除的事实列表来描述。这种受限语言使状态转移易于计算,并成为后续理论分析和基准规划研究的基础。对子目标相互作用的研究也表明,仅仅分别求解每个目标可能会失败:实现某一条件的动作,可能破坏另一个已经建立的条件。积木世界中的例子成为展示这些依赖关系的经典范例。
此后,研究逐渐分化出多种方向,包括规划空间方法、层次分解、约束推理和更有效的状态空间搜索。20世纪90年代出现了数项重大进展。考茨和塞尔曼在1992年的研究中将规划与命题可满足性联系起来;布卢姆和弗斯特于1995年提出Graphplan;HSP和FF等启发式规划器则在世纪之交推动高效前向搜索成为主流方法之一。这些进展并不是一种技术被另一种技术依次取代,而是提供了不同途径,用于利用动作结构、表示相互作用并控制组合搜索。
规划领域定义语言(PDDL)于1998年随首届国际规划竞赛一同推出,为研究人员提供了交换领域描述和问题实例的通用语言。后续版本增加了持续性动作、数值量、偏好和轨迹约束等特性。通用表示和竞赛使比较更加系统化,同时也揭示出,规划性能在很大程度上取决于所支持的语言子集、优化准则以及基准领域的结构特征。
形式模型、规划与计算难度
一种常见的有限经典规划模型可表示为元组
其中, 是命题事实的集合, 是动作集合, 是初始状态, 是目标。状态 记录当前为真的事实。按照通常采用的封闭世界约定,未包含在状态中的事实均为假。动作 具有前提条件 、添加效果 和删除效果 。如果前提条件成立,执行该动作后的后继状态为
这种表示方式明确给出了动作的适用条件和状态更新方式。
顺序规划是一个可从 开始执行的动作序列 ,且满足 。例如,一个包裹最初位于仓库 ,一辆卡车也位于 ,目的地为 。装货要求包裹和卡车位于同一地点;行驶会改变卡车的位置;卸货则将包裹从卡车转移到卡车当前所在的地点。“包裹位于 ”这一目标本身并未规定这些中间步骤。规划器需要根据状态转移模型推导出这些步骤,并避免出现先卸货后装货之类的动作序列。
找到任意一个有效规划与优化规划是不同的任务。动作可以具有非负代价,此时规划的代价为
其他优化目标包括尽量缩短总耗时、减少燃料消耗、减少错过截止期限的次数,或综合考虑多个相互冲突的指标。动作序列最短,并不意味着代价最低或执行最快:一个耗时较长的动作虽然动作数量更少,但执行时间可能长于若干并发活动。有些形式化框架还区分硬约束和偏好:每个可接受的规划都必须满足硬约束,而违反偏好则会受到惩罚。
经典模型看似简单,背后却隐藏着很高的计算复杂性。对于 个相互独立的布尔事实,即使动作和初始状态都能以紧凑的形式描述,也可能存在 个状态。对于标准的命题 STRIPS 规划,判定是否存在任何规划是一个 PSPACE 完全问题。所需规划的动作数量可能随输入规模呈指数增长。因此,某个规划器能够快速处理规模很大的实际实例,并不能说明任意规划问题都容易求解;它可能利用了有利的问题结构,也可能接受次优解,或者两者兼有。
复杂性还取决于表示方式。逐一显式列出所有状态,与通过变量和动作模式描述状态,所对应的输入规模并不相同。将动作步数上限固定为输入规模的多项式,会改变所讨论的判定问题;限制动作效果或依赖关系,也可能得到更易求解的子类。反过来,加入表达能力足够强的数值运算或不受限制的层次化机制,则可能使某些规划形式变得不可判定。因此,有意义的可解性论断需要明确所用语言、优化目标、规划时域和各项假设,而不能把“规划”视为单一的计算问题。
领域语言与知识工程
实用的规划描述通常将可复用的领域与具体问题分开。领域定义对象类型、谓词和动作模式;问题则提供特定实例中的对象、初始条件和目标。像 load(package, truck, location) 这样的动作模式,是许多具体动作的简写。用实际对象替换其中参数的过程称为落地化。类型和静态关系可以排除不可能的替换,但当动作模式包含许多参数或对象数量很大时,朴素的落地化方法仍可能生成极其庞大的动作集合。
PDDL 之所以成为标准交换语言,部分原因在于这种分离方式支持可复用的建模和受控扩展。其语法会标明所需的功能,使规划器能够拒绝不支持的构造,而不是在不作提示的情况下错误地解释它们。基本的 STRIPS 风格描述使用谓词和动作效果,而表达能力更强的语言子集还包含否定前提条件、量化、条件效果和派生谓词。条件效果规定,只有在执行时某个附加条件成立,才会发生相应变化。派生谓词由其他事实推导而来,而不是由动作直接改变,因此适合用于表示可达性等关系。
另一种内部表示使用有限域变量,而非彼此独立的布尔命题。例如,可以用一个变量表示卡车的位置,其取值为各个可用的货运站,从而避免出现卡车同时位于多个地点的组合。规划器可以发现诸如“每个包裹恰好位于一个位置”这样的不变量,再将命题式描述编译为更紧凑的、基于变量的形式。领域转移图描述各个变量如何变化,因果图则记录变量之间的依赖关系。这些结构既有助于预处理,也有助于启发式估计。
领域模型所体现的知识库往往与搜索算法同样重要。遗漏前提条件可能会允许执行物理上不可能的动作;缺失效果则可能导致实际可行的解无法在模型中表示。资源约束、互斥条件以及有关状态持续性的假设,都必须以一致的方式编码。例如,如果装载动作不要求卡车位于包裹所在的位置,就可能产生简短却毫无意义的计划。不变量可以揭示此类错误,而小型诊断问题则更便于判断失败究竟源于搜索还是建模。
模型验证与计划验证并不相同。验证器检查某个具体计划是否遵循形式化的动作语义,以及是否实现了所声明的目标。但仅凭验证器本身,无法确定领域是否准确表示了预期环境。借助与形式验证和本体(计算机科学)的联系,可以使规约更加清晰,但抽象仍然不可避免。物流模型可能忽略轮胎磨损、道路坡度或装载时的几何关系,因为这些细节与其规划层级无关。模型是否足够恰当,取决于被省略的细节是否会使交由该层级作出的决策失效。
状态空间搜索与启发式引导
经典规划可以理解为在隐式定义的状态图中寻找一条路径。在前向搜索中,初始节点为 ,后继节点由可应用的动作产生,目标测试则检查所需条件是否成立。后向搜索则从目标出发,推导足以实现目标的前驱条件,通常采用回归方法。前向搜索的优势在于状态具体,动作适用性易于检查;回归可以将注意力集中在与目标相关的动作上,但可能遇到复杂的条件组合。无论采用哪个方向,都仍需处理相互影响的子目标。
广度优先搜索等无信息搜索方法能够找到单位代价下的最短规划,但往往会探索过多状态。因此,现代规划器高度依赖启发式方法,利用 估计从状态 出发尚需付出的代价。A星搜索使用 确定状态的优先级,其中 是已经付出的代价。在适当条件下,包括所用启发式具有可采纳性、从不高估最优剩余代价时,A星搜索能够找到最优规划。贪心最佳优先搜索仅依据 确定优先级,通常能更快地找到令人满意的规划,但一般不保证最优性。
一大类规划启发式源于删除松弛。去除删除效应后,事实会单调累积:装载包裹不再删除它原先所在位置这一事实,使用资源也可能不再使其变得不可用。这种松弛后的问题更容易推理,也能提供哪些动作可能有助于实现目标的信息。不同的近似方法会产生不同的估计值。最大代价启发式以保守方式合并各项前提条件的估计值,在标准假设下可以具有可采纳性;加性启发式将各项前提条件的估计值相加,可能重复计入共用的工作。FF启发式提取一个松弛规划,以提供有用的引导,但通常不具有可采纳性。
其他方法通过抽象推导代价下界。模式数据库针对仅保留选定状态变量的简化问题,存储其精确求解代价。代价划分可以将动作代价分配给不同的抽象,使各抽象的估计值能够相加而不重复计数。里程碑用于识别每个解都必须实现的事实或执行的动作,不过,计算和利用里程碑时,需要注意它们的顺序以及实现它们的不同方式。这些方法刻画了问题的不同侧面,因此,组合方法和算法组合往往比单一的通用启发式表现更好。
搜索性能还取决于重复检测、同优先级时的选择规则、优先算子和内存管理。在确定性的经典规划任务中,如果一个动作序列重新到达先前已到达过的状态,可能不会带来任何有用信息。状态哈希和关闭列表可以抑制这种重复,剪枝技术则可排除能够证明为冗余的备选方案。尽管如此,启发式平台和局部极小值仍可能存在:许多状态可能看起来同样有希望,或者通往解的每条路径在起初都可能使估计值增大。因此,搜索增强方法必须在对每个状态进行更强推理的开销与评估数量庞大得多的状态的开销之间取得平衡。
规划图、可满足性与约束编码
规划不一定要通过逐个显式搜索世界状态来进行。Graphplan 构建一种由命题层和动作层交替组成的分层规划图。从初始事实出发,每个动作层都包含那些前提条件在上一命题层中得到支持的动作。持续动作将事实传递到下一层,互斥关系则记录彼此不相容的动作或命题。动作之间可能发生冲突,原因包括:一个动作删除了另一个动作的前提条件,两个动作的效果相矛盾,或支持它们的条件无法在相应层中同时成立。
规划图是一种用于推理可达性的紧凑结构,而不是对所有可达世界状态的完整枚举。同一命题层中出现的事实未必能够同时实现,因为两两互斥的信息无法涵盖所有高阶依赖关系。因此,Graphplan 会先构建足够多的层,使各目标都得到支持且彼此不互斥,再通过反向搜索提取规划。对于无法实现的子目标组合,可以将其记录下来,以免重复进行无效推理。这种架构将开销较低的前向传播与更具选择性的反向搜索分离开来。
另一种有影响力的方法是将有界规划转化为布尔可满足性问题。对于规划时域 ,命题变量描述时间步 上的事实与动作发生情况。子句对初始状态、目标条件、动作前提、效果以及事实的持续性进行编码。解释性框架约束确保:若没有动作能够解释某个事实的变化,该事实的真值就不能改变。根据编码方式的不同,附加约束可以强制动作顺序执行,也可以允许彼此相容的动作并行发生。随后,即可将一个满足赋值解码为规划。
通常会逐步增大规划时域,直到找到可满足的编码,不过也可以采用其他策略和下界估计技术。在时域 上求解失败,只能证明该编码所限定的范围内不存在规划;通常并不能证明不设界限的规划任务无解。此外,最短并行时域不同于最短顺序执行长度,也不同于最低代价。如何定义并行相容性十分重要,因为有些编码只有在多个动作可以按某种合适的顺序执行时,才允许它们出现在同一层中。
基于约束的规划将这一思路扩展到了命题变量之外。整数规划可以表达动作选择和资源平衡,而可满足性模理论则将逻辑结构与线性算术等理论相结合。时态规划任务和数值规划任务往往能从这些表达能力更强的语言中受益。这类方法的吸引力在于,可以利用具备传播、冲突学习和优化机制的强大通用求解器。其局限性在于,编码本身可能变得十分庞大,也可能掩盖对规划有用的结构。比较这类方法时,需要综合考虑预处理、编码耗时、求解器耗时,以及解码结果的语义。
偏序规划与层次规划
顺序规划为每一对动作都确定先后顺序,即使其中许多活动彼此独立。偏序规划则只表示保证正确性所必需的顺序。例如,一个规划可以规定包裹必须在运输前装载、在运输后卸载,而不确定一项无关的检查是在装载之前还是之后进行。任何满足这些顺序约束的线性化结果,都必须保持规划的预期语义。这种最小承诺方法能够揭示并发执行的可能性,并推迟某些决策,避免过早决策导致搜索分支成倍增加。
因果链规划明确表示动作之间的依赖关系。因果链 表示动作 为动作 建立条件 。如果另一个动作可能在产生该条件的动作与使用该条件的动作之间使 不再成立,它就会威胁这条因果链。可以通过将威胁动作安排在产生条件的动作之前或使用条件的动作之后来消除威胁,有时也可以通过限制变量绑定来实现。搜索通过修复缺陷来推进,这些缺陷包括尚无支持的前提条件和未解决的威胁。这与前向状态空间搜索不同,因为这里的搜索节点是不完整的规划,而不是完全确定的世界状态。
层次任务网络规划引入了另一种结构:利用领域专用的方法,将任务分解为更小的任务。例如,交付货物这一高层任务可以分解为获取车辆、提取货物、运输货物和移交货物。原始任务对应可执行的动作;复合任务则通过分解方法逐步细化,方法所附的条件说明其适用情形。一个解既必须能够正确执行,也必须符合初始任务网络所允许的分解方式。
层次结构可以编码过程性知识,而纯粹基于目标的规划器原本需要自行重新发现这些知识。它也可以有意限制解空间。例如,即使其他动作序列也能达到相同的最终状态,一家公司仍可能只允许采用特定的审批和发运流程。Dana Nau 及其同事于1999年提出的 SHOP,就是一种按执行顺序对任务进行推理的层次规划系统,因此能够根据已知的当前状态评估方法的适用条件。其他层次规划系统则允许采用偏序任务网络和更灵活的分解策略。
这些额外知识并非没有代价。分解方法需要编写、检查和维护,而不完整的方法库可能会排除有效的解。不受限制的递归层次形式化描述,其可判定性和复杂性性质可能与经典规划截然不同。层次结构也不同于仅仅在经典规划领域中加入宏动作:分解不仅能加快动作序列的发现,还能定义哪些动作序列是允许的。在实际系统中,可以将层次结构与因果推理相结合,使规定的流程与对备选动作、资源分配和执行顺序的搜索并存。
时间、资源与连续过程
经典规划不考虑动作的持续时间,但在许多应用中,活动何时发生、重叠多长时间都至关重要。时态规划对具有持续时间的动作进行建模,并将条件和效果关联到动作的开始、结束或其间的时间区间。例如,运输动作可能要求车辆在动作开始时位于出发地,在执行过程中消耗燃料,并在动作结束时使车辆到达目的地。某项安全条件则可能必须在整个执行过程中始终成立。因此,要保证规划正确,不仅需要推理动作的先后顺序,还需要推理条件在哪些时间区间内成立。
玛丽亚·福克斯(Maria Fox)和德里克·朗(Derek Long)于2003年发布的 PDDL2.1,为数值规划和时态规划的相关构造确立了影响深远的语义。它在处理并发动作时,对同时访问正在变化的值作出了限制,通常以“无移动目标”(no moving targets)原则来描述。这类细则避免了含糊的解释,例如某个动作恰好在另一个动作改变某个值的同一瞬间依赖该值。时态规划器必须遵循其所采用的语义,而不能将所有表面上互不冲突的重叠执行都自动视为有效。
时间约束通常使用简单时态网络来表示。其变量是时间点,约束则限定时间点之差的上下界:
这些界限可以表达动作持续时间、截止时间和先后次序要求。一致性检查可归结为基于图的差分约束推理,从而将时态规划与最短路径问题的算法联系起来。一个一致的时态网络可以表示多种可能的调度方案,而非一张完全固定的时间表。当持续时间部分受环境控制时,动态可控性等更强的概念所关注的是:执行决策能否根据观测到的完成时间进行调整,同时仍然满足约束。
资源会引入额外的相互影响。机器、装卸平台等可再生资源在使用后会重新变得可用;燃料等消耗性资源则会不断减少,除非得到补充。即便两个活动的逻辑前置条件并不冲突,容量约束也可能禁止它们重叠执行。反过来,并发执行有时又是必需的:例如,一个智能体可能必须扶住某个部件,让另一个智能体将其安装到位。规划决定需要开展哪些活动,而调度则为这些活动分配时间和资源;不过,许多现实任务要求联合求解这些决策,而不是严格按先规划、后调度的流水线方式处理。
混合模型将离散动作与连续变化结合起来。电池电量、温度或储罐液位可能在活动过程中发生变化,自主过程也可能在智能体未采取显式动作的情况下持续进行。如果只检查起点和终点的值,就可能漏掉其间对不变条件的违反。因此,表达能力更强的模型需要对变化速率、中间状态以及由条件触发的事件进行推理。这种表达能力会带来相当大的计算困难,因此实际系统往往采用受限的动力学、保守近似,或与符号规划相结合的专用数值求解器。
不完全信息与随机结果
经典规划假设初始状态已知,且动作的效果可预测。当信息不完全时,规划器可以转而基于信念状态进行推理:信念状态是可能的世界状态的集合,或这些状态上的概率分布。如果一个包裹可能位于两个仓库中的任意一个,就不能把它的位置视为一个已知事实。必须针对与智能体所掌握信息相符的各种可能情况来评估动作;观测则可能在不直接推进实际配送任务的情况下减少不确定性。
保形规划寻求一种不依赖执行期间的新观测、却仍能在给定不确定性下成功的规划方案。例如,只要动作语义允许,保形规划的解可以安排访问两个可能的取货地点。条件规划允许根据观测结果设置分支,例如先检查一个仓库,再根据检查结果选择路线。此时,输出的是条件规划方案或策略,而非单一的固定动作序列。感知本身也必须纳入模型:能够观测什么、在什么条件下可以观测、观测有多可靠,以及获取信息是否会改变世界。
非确定性规划将动作表示为具有多个可能结果的动作,但不一定为这些结果赋予概率。不同的解概念提供不同的保证。强解保证沿每一条可能的结果路径都能到达目标。强循环解可以允许重试和循环,而最终能否成功取决于适当的公平性假设。例如,在公平性假设下,反复尝试一个存在成功结果的动作可能是可接受的;但如果允许环境永远选择失败结果,就不能接受这种做法。这些区别决定了所谓的解究竟能提供什么保证。
当结果具有概率,且需要考虑成本或奖励时,规划就与马尔可夫决策过程联系起来。在折扣奖励形式下,最优价值函数满足
其中 。求解结果通常是将状态映射到动作的策略。动态规划方法利用这种递归结构,而启发式搜索可以将计算集中于与特定初始条件相关的状态。面向目标的随机最短路径建模采用类似的思想,但需要对终止性和成本作出相应的假设。
部分可观测性引出了部分可观测马尔可夫决策过程,其中观测用于更新状态上的概率分布。即使实际状态空间是有限的,由此形成的信念空间通常仍是连续的。精确求解的计算代价可能很高,因此催生了基于点的近似方法、采样方法和在线搜索。选择更简单的模型往往起着决定性作用:最坏情形下的非确定性规划、基于概率的期望成本优化,以及风险约束规划,回答的是不同的问题。平均表现良好的策略并不自动具备最坏情形下的安全保证。
执行架构与实际应用
规划是对行动将如何改变模型所描述的世界的一种预测;执行则用实际发生的事件来检验这一预测。因此,执行架构需要调度行动、观察行动结果,并检查支撑后续步骤的假设是否仍然成立。监控可以发现行动失败、错过截止时间、资源耗尽或外部变化等情况。适当的应对方式可能是重试、修复局部规划片段、重新调度剩余行动,或从观测到的状态出发求解新的规划问题。
重新规划并不只是脱离当前情境,再运行一次原来的规划器。有些行动可能已经开始执行,有些承诺可能已经传达给其他智能体,而放弃尚未完成的规划也可能产生成本。规划修复旨在保留有用结构的同时适应变化后的条件。执行时的灵活性同样重要:偏序规划或时间安排灵活的规划,可以在不重新规划的情况下消化某些扰动。一个不必要地固定所有开始时间的系统,可能比保留允许时间区间的系统更脆弱。
机器人技术使符号推理与物理推理之间的界限尤为明显。“拿起杯子”这样的高层行动,需要机器人能够到达合适的抓取位姿、机械臂具有无碰撞轨迹,并满足适当的几何关系。任务与运动规划将符号层面的行动选择与连续空间中的几何可行性相结合。当运动规划发现某个物体挡住路径时,符号规划可能需要修改;而移开障碍物又可能带来新的操作选择。感知和同时定位与地图构建还会给规划所依赖的状态本身带来不确定性。
空间任务提供了一些引人注目的示范。1999年,美国国家航空航天局的“远程智能体”实验在“深空一号”探测器上运行,将规划和调度与执行及基于模型的诊断结合起来。此后,“地球观测一号”任务利用“自主科学航天器实验”,将星载科学分析与规划和执行连接起来。这类系统说明,仅有规划器还不够:资源约束、通信机会、故障处理以及执行层,共同决定了抽象层面选定的活动能否可靠地付诸实施。
其他应用包括制造、维护、运输、工作流组合和自动配置。在多智能体环境中,规划必须考虑共享资源、协调以及其他参与者行动的影响。协作式车队可以优化联合配送,而各自追求自身利益的智能体则会引入超出普通单智能体规划范畴的策略问题。当知识和决策权限分散在不同主体之间时,与分布式计算的联系就变得重要。在所有这些应用中,系统能否部署都取决于模型的适用边界:独立检查、监控和后备处置机制用于应对那些即使规划在形式上有效也无法排除的故障。
学习、语言模型与实证评估
传统上,规划假定动作模型和控制知识由外部显式提供。机器学习则可以从观测到的状态转移中推断前提条件和效果,预测动作持续时间,估计代价,或引导搜索。学习动作模型与学习启发式函数并不相同:前者改变规划器对动作作用的描述,后者改变各种可能方案被优先探索的顺序。学习所得模型中的错误可能使计划失效,而引导机制中的错误则可能主要降低效率,或损害最优性,具体取决于该机制的使用方式。
规划与强化学习的关系尤为密切,但二者并不等同。无模型学习系统可以在不显式构建计划的情况下习得动作策略。基于模型的系统则学习或接收状态转移动力学模型,并利用规划来选择行为。规划方法可以提供训练目标、生成合成经验,或在学习得到的控制器内部求解局部决策问题。反过来,学习得到的价值估计和动作偏好也可以引导符号搜索。这些方法是否有用,取决于训练任务是否涵盖部署时遇到的结构变化。
大语言模型为转译自然语言请求、提出动作序列以及辅助构建领域描述提供了更多接口。它们生成的文本并不会自动成为可执行或有效的计划。看似合理的序列可能遗漏某个前提条件,引用不可用的对象,或重复使用同一资源。将语言模型与符号规划器或验证器连接起来的架构,把候选方案生成与显式检查分离开来。这是神经符号人工智能的一种形式,不过,要使检查切实有效,仍需具备充分刻画任务的形式化模型。
因此,实证评估衡量的不仅是输出看起来是否合理。常见指标包括覆盖度,即在资源限制内求解的实例数量,以及运行时间、峰值内存、计划代价、与已知下界或最优解的差距。最优规划器与满意规划器追求不同的目标,不应将它们视为提供相同保证而加以比较。独立验证依据基准测试所规定的语义检查正确性。报告结果时,还必须区分搜索时间与领域转换、基化所耗费的时间,因为后两者可能占据总计算开销的大部分。
泛化能力仍是学习型规划组件面临的核心问题。在几乎相同的问题实例上进行训练和测试,可能掩盖系统在处理更大的对象集合、陌生的目标组合或改变后的动作动力学时遇到的困难。当系统涉及学习所得模型时,分布偏移可能同时影响性能和正确性。经典规划器面临一个相关但不同的挑战:在既有基准测试系列上表现良好,并不保证面对新结构时仍然高效。因此,当前研究正在探索避免完全基化的提升推理、更有力的不可解性证明、经过验证的规划组件、学习得到的抽象,以及既能接受不那么形式化的任务描述、又能保留形式化保证的接口。