©2016-2024 Matools All rights reserved,
粤ICP备17059708号
摘要
本文旨在讲明：
1）规划问题定义（PDDL）为一个搜索问题
2）前向搜索，后向搜索，及搜索的启发式
3）从规划图获得启发式及提取规则
一、PDDL
规划问题定义：Plainning domain definition language，简称PDDL
第7章的混合命题逻辑Agent没有领域相关启发知识就能找到规划，因为其使用了基于问题的逻辑结构的领域无关启发知识。
但是它依赖于无变量命题推理，这意味着有许多动作和状态时会忙的一笔。
因此，规划研究者选择了要素化（factored representation）——用一组变量表示世界的一个状态的表示方法。可使用PDDL语言。
每个状态称为流（fluent）（状态变量的同义词）的合取,这些流是基元的（无变量），无函数的原子。
一组基元（无变量）的动作能够表示为单个动作模式（action schema）。这个动作模式是一种提升表示。
现在，我们将规划定义成了一个搜索问题：有一个初始状态，一个action函数，一个result函数以及一个目标测试。
1.2 例子：航空货物运输
涉及装载、卸载货物，以及从一个地方飞到另一地。
这个问题用：Load，Unload，Fly三个动作定义。 对应有两个谓词：In（c，p）表示货物在机，At（x，a）表示x（机或物）在机场a。
基本的PDDL是没有全称量词的。
1.3 经典规划的复杂性
本节考虑规划的理论上的复杂性，并区分两个决策问题。
PlanSAT：询问是否存在解决一个规划问题的某个规划
限界（bounded）PlanSAT：询问是否存在用于找到最优规划的、长度小于k的一个解。
后者是NP-完全的，而PlanSAT属于P。换言之，最优规划通常困难，但次优规划有时是容易的。
二、状态空间搜索规划算法
现在我们把注意力放到规划算法上。重点关注：前向搜索，后向搜索。
2.1 前向状态空间搜索
太低效，不实用。
前向搜索：从初始状态出发，使用问题的动作，向前搜索目标状态
后向搜索：从目标的状态集出发，使用动作的逆，向后搜索初始状态。
1）前向搜索容易探索到无关动作
2）规划问题常有大的状态空间
对前向搜索来说，显然，没有精确的启发式，即使相对小的问题实例也是无望的。但是规划的许多现实应用还是能自动导出非常强的独立于领域的启发知识，这使得前向搜搜具有可行性。
2.2 后向相关状态搜索
从目标开始，向后应用动作，直到找到达到初始状态的步骤序列。在每一步考虑一组相关状态，而不是单个状态。
从目标开始，对一组状态进行描述的文字之合取。
可喜的是，PDDL表示的设计使得后退动作很容易。
最后一个问题是：决定哪些动作是后退的候选动作，在前向中我们选择适用的动作——在规划中可能是下一个步骤的那些动作
在后向中，我们需要相关的动作——导致当前目标状态的规划中可以作为最后一个步骤的那些动作。
一个动作要与一个目标相关，则必须明显对目标有贡献。
尽管后向搜索是分支因子低于前向，然而，后向使用状态集而不是单个状态的事实使得它更加难以想出好的启发知识，这就是当前主流偏向前向的主要原因。
三、规划的启发式
没有好的启发式函数，无论前向后向都不高效。
可采纳的启发式。可以通过更容易求解的松弛问题导出。
将搜索问题想成一个图，节点为状态，边为动作。问题是要找一条连接初始状态到目标状态的路径。
有2个方法来松弛这个问题：
1）加入更多的边，使得路径更容易被找到
2）多个节点组合到一起，将状态空间抽象为具有更少状态的形式
* 忽略前提启发式
* 忽略删除列表启发式
定义启发式的关键思想是分解（decomposition）
文末诗词
玉台挂秋月。铅素浅，梅花傅香雪。
——田为《江神子慢》
热门工具 换一换