基于U-规划图与动作效果相关的规划识别研究

谷文祥，綦小龙，王慧玲，黄秀林

（1.东北师范大学计算机科学与信息技术学院，长春130117;2.长春建筑学院基础教学部，长春130607;3.伊犁师范学院电子与信息工程学院，新疆维吾尔自治区伊宁 835000）

0 引 言

规划识别涉及两个角色：执行者和观察者。给定一个由执行者执行的动作集合和琐碎的现象（动作产生的效果），观察者的任务就是根据观察到的动作序列或动作产生的效果集合推断执行者的目标，进而推断执行者执行的规划[1]。无论什么系统，只要期望其与另一个智能体产生一种协作行为或竞争行为，则规划识别就是一个至关重要的组件[2]。因此，规划识别问题在许多领域得到了发展，比如信息安全、自然语言处理、故事理解、智能用户接口和多智能体规划[3-5]等。

根据执行者和观察者的关系，规划识别问题被分成3类：1）协作式规划识别。智能体积极配合识别器的识别，智能体所执行的动作有意让识别器理解。2）对手式规划识别。智能体所做的动作对识别方造成了威胁，破坏了识别方的正常规划，而且智能体还会阻止或干扰识别器对其识别[6，7]。3）洞孔式规划识别。笔者主要关注的是洞孔式规划识别问题，也是目前规划识别问题研究最广泛的一种情况，即执行者既不阻碍观察器对其观察也不作任何处理。

目前，解决洞孔式规划识别问题最受欢迎和最有效率的是由Kautz[4]提出的基于事件层的规划识别方法。后来，姜云飞利用与或图扩展了这种方法，在文献[8]中提出了基于规划知识图的规划识别方法。这两种方法由于都是有规划库的规划识别，所以都不可避免地遇到以下问题：1）规划库的构建是困难的;2）在较大系统中，规划库的手工编码是不可能的;3）较大规划库的更新和维护花费较大;4）由于是有库的规划识别，所以限制了规划识别器对新规划的识别。

因为构建规划库存在许多问题，学者们尝试采用了无规划库的规划识别方法，其中有代表性的是J Hong的基于目标图分析的目标识别[9]。该方法要求动作序列是完全可观察的，并且每个时间步只执行一个动作，使该识别器的应用受到了一定的限制。后来，殷明浩[10]在图规划框架下提出了基于规划图的增量式代理目标识别方法。该方法对动作序列是否是完全可观察的没有要求，而且允许每个时间步可由多个动作并行执行。但是，它对观察到的动作效果处理得不好。该方法假设当观察到一个动作效果时，支持它的动作只有一个，则该动作被选择，否则不做处理。

对于部分可观察的规划识别问题而言，利用观察到的动作效果对智能体的规划和目标进行推断是至关重要的。目前，研究者主要关注的是支持观察到的动作效果是一个动作的情况。然而，在大多数实际问题中，支持动作往往不是唯一的。如果这些动作处理的不好，就会产生许多无关的规划，从而影响识别系统的效率。笔者针对支持该效果的动作是多个的情况，智能体如何根据现有的信息为该效果确定最终的支持动作进行了研究并给出了相应的FSas算法。

1 FSas算法

在部分可观察的规划识别系统中，不仅要求该系统能对观察到的动作进行处理，还要求对观察到的动作效果也能进行处理。在该领域，存在一些没有观察到的动作，所以通过观察到的动作或动作效果，推断出智能体的规划和目标显得至关重要。目前，研究者们主要关注的是由观察到的动作推断智能体的规划和目标，而借助于观察到动作效果进行推理的研究较少。原因是动作效果的支持动作往往不是唯一的，如果对这些动作处理不好就会产生许多不相关的规划，从而影响了识别系统的效率。目前，普遍采用的方法是假设支持观察到命题的动作只有一个，这虽然使识别器处理相对简单，但常常不符合实际情况。为此，笔者提出了由观察到的动作效果求解其支持动作的FSas算法。

首先给出定义。这些定义与以往所给的定义不同。在以往的定义中由观察到的命题给动作约束下定义时只考虑简单的情况：1）当观察到一个确定发生的命题时支持它的动作是唯一的，没有考虑支持该命题的动作是多个的情况;2）观察到的命题出现在动作的前提条件中，没有考虑该动作的其他前提条件的状态。鉴于以往定义存在的缺陷，笔者给出了如下定义。为方便叙述和算法的实现，引入三值逻辑即-1，0，1，表示动作或命题的状态。-1表示命题或动作在当前时间步不为真;0表示命题或动作在当前时间步可能为真也可能不为真;1表示命题或动作在当前时间步为真。

定义1 P是值为1的命题，如果P出现在某个动作的前提条件中，且该动作的其他前提条件的值不为-1，则把这样的动作约束称为前提条件D-动作约束。

显然，满足前提条件D-动作约束的动作一定发生。

这样给出定义1是考虑到命题值是0的情况。当一个命题的值为0时，其真假是不确定的。可能这个命题的值确实为1，但并没有观察到。由于笔者关注的是洞孔式规划识别问题，所以给出了此定义。

由此可知，对于规划识别系统而言，支持命题P的动作越少，产生的无关规划越少，所以对识别系统能准确而快速地识别出智能体的目标也越有利;反之则不然。它会给识别系统带来一定的困难。因此，当观察到一个确定发生的动作效果时，识别器如何根据现有的信息快速而准确地确定其支持动作，对规划识别系统是极为有意义的。

笔者给出了FSas算法。该算法利用互斥计算、支持命题数最多动作的计算以及回退处理，不断剪除确定观察到的动作效果的支持动作，使支持动作的空间达到最小，从而为观察到的命题确定最少数量的支持动作。下面给出FSas算法。

1.1 支持命题数最多的动作计算

对于洞孔式规划识别系统中的执行者而言，希望做尽可能少的动作实现自己的目标。因为其执行的动作越多，被观察器观察到的动作也越多，从而其目标被识别的可能性也越大。如果执行者执行一个动作就能实现其目标，则不需做两个或更多的动作完成该目标。因此，笔者选用了支持命题数最多的动作。

1.2 互斥计算

在部分可观察的规划识别问题的某些研究领域里，允许执行者在一个时间步并行执行多个动作。这个条件的放松给识别器的识别带来了一定的难度。当识别器根据现有的信息经过推断得到在某个时间步有些动作确定发生，而有些动作是不确定的，对这些不确定的动作如果处理得不好就可能产生许多不一致的规划而影响识别器的效率。笔者使用互斥计算剪除没有价值的动作，以缩小支持动作的空间。

命题2 动作ai从其所支持的所有命题的动作集合中删除，不会使这些命题没有支持动作。

1.3 回退计算

如果当前支持该命题的所有动作，都与前面已选的支持某个命题的动作bi互斥，则需要回退。首先，找出所有的bi支持的事实集合Pi（bi）;然后将Pi（bi）集合中的bi删去，为当前命题选定一个支持动作。如果Pi（bi）已被处理过，将其插入到链表末端，重新处理;否则，继续顺序处理下一个Pi（a）。

1）若支持该命题的动作只有一个时，则设置该动作的值为1。

2）支持该命题的动作有多个时：

①利用在命题层t-1确定为真的命题集合进行筛选。

将ai值设置为1;否则，随机选择一个支持动作将其值设置为1，并标记命题P。

②利用互斥关系对支持该命题的动作进行筛选。

则分别找出支持P的动作，支持Pr（a）的动作。

则将Pi（A）中的动作的值设置为1且将其添进A集合中。

Else将Pi（A）添进集合N中

{选择一个Pi（A）∈N，由Pi（A）和A（Pj）可以得到Pi（A）中每个动作所支持的事实数。

If al不属于A

If al与A中的动作不互斥

则将al的值置为1，并将其添进A集合中。

则将al从Pi（A）集合中删除，go to Step1

Else该动作的值置为1，将其添进A集合中。

If Pi（A）中的每个动作都与已选的某个动作（b）互斥，则回退，即为该动作所支持的命题重新选择动作，并将该动作从它所支持的所有命题的动作集合中删除。

}

2 实例说明

笔者通过一个一般化的例子，说明FSas算法的执行情况。用ai表示在t-1时间步中动作，P为时间步t-1确定为真的命题。a表示在时间步t确定发生的动作。

已知 a，P 是确定为真的动作和命题，Pr（a）={p1，p2，p3，p4}，P1（A）={a1}，P2（A）={a2，a3}，P3（A）={a2，a3}。a1（P1）={p1}，a3（P2）={p2，p3}，a2（P3）={p3，p2}。M={a1，a2，a3}。a2与a1互斥。

其实该算法可将命题层t-1确定为真的动作效果和动作层t确定为真的动作结合在一起进行推理，这种情况相对简单，所以在这只考虑了最坏的情况，即二者中的一个发生。

3 结 语

笔者对识别器观察到一个命题为真时，识别器如何根据现有的信息减小支持该命题的动作空间进行了研究并给出了相应的Fsas算法。该研究在规划识别的理论及其应用研究都具有一定的参考价值。

后期的工作有以下两个方面：1）将FSas算法和文献[7]提到的规划识别系统结合，使该系统能更好地根据观察到的动作效果进行推理，从而扩展该识别系统的应用;2）在1）的框架下处理对象集合动态可变的规划识别问题。

：

[1]MALIK GHALLAB，DANA NAU，PAOLO TRAVERSO.Automated Planning：Theory and Practice[M].Burlington：Morgan Kaufmann Publish，2004.

[2]MATHIAS BAUER.Intergrating Probabilistic Reasoning into Plan Recognition[C]∥Proceedings of the 11th Euro Conference on Artificial Intelligence.（ECAI’94）.New York，USA：ECAI，1994：620-624.

[3]KAUTZ H，ALLEN J.Generalized Plan Recognition[C]∥Proceedings of National Conference on Artificial Intelligence.[S.l.]：AAAI Press，1986：32-37.

[4]KAUTZ H.A Formal Theory of Plan Recognition[D].Rochester：Department of Computer Science，Rochester University，1987：1-65.

[5]GU Wen-xiang，YIN Ji-li.The Recognition and Opposition to Multiagent Adversarial Planning[C]∥Proceedings of the Fifth International Conference on Machine Learning and Cybernetics.Dalian，China： [s.n.]，2006：2759-2761.

[6]谷文祥，李丽，李丹丹.规划识别的研究及其应用[J].智能系统学报，2007，2（1）：1-15.

GU Wen-xiang，LI Li，LI Dan-dan.Research and Application of Plan Recognition[J].CAAI Transactions on Intelligent Systems，2007，2（1）：1-15.

[7]谷文祥，殷明浩，徐丽.智能规划与规划识别[M].北京：科学出版社，2010：174-175.

GU Wen-xiang，YIN Ming-hao，XU Li.Intelligent Planning and Plan Recognition[M].Beijing：Science Press，2010：174-175.

[8]姜云飞，马宁.一种基于规划知识图的规划识别算法[J].软件学报，2002，13（4）：686-692.

JIANG Yun-fei，MA Ning.A Plan Recognition Algorithm Based on Plan Knowledge Graph [J].Journal of Software，2002，13（4）：686-692.

[9]HONG JUN.Goal Recongnition through Goal Graph Analysis[J].Journal of Artificial Intelligence Research，2001，15（2）：1-30.

[10]YIN M，SUN J，LU S，et al.A Novel Framework for Plan Recognition：Graphplan as a Basis[C]∥Proceedings of the 7th IJCAI WK on NRAC.[S.l.]：AAAI Press，2007：472-476.