带标记的反向搜索的规划识别算法

摘要

规划识别是指根据观察到的动作集合来推断agent的目标,并将这些观察到的动作组成一个关于该目标的规划.应用规划识别,agent可以从片段的、部分的观察动作中获得完整的规划.而agent不能观察到的动作和还没发生的动作则可以被预测.规划识别的应用领域非常广泛,如自然语言理解,故事理解,多agent协作,智能用户接口等.常用的规划识别的方法是建立一个规划库,然后通过搜索和匹配装置来获得规划.但由于所观察到的动作的片面性以及同样的动作经常出现在不同的规划中这一性质,使得确定一个无二义性的规划变得很困难.因此,研究者们提出了很多方法来解决此问题.本文给出了用带标记的反向搜索的算法解决规划识别问题的方法，该方法在解图的生成时采用从下往上动态生成解图的方法，同时完成计算和图的生成过程。同时还引入了一个阈值，这样我们可以对一些发生的可能性很小的规划及时地剪裁掉。而对于多个OR节点，则对它们进行了标记，这样做既减少了冗余节点，同时又解决了动态生成新的观察现象节点的问题，使得当新增加一个观察现象节点时，不用完全重新生成解图，只需增加一些边和动态更新可能性值和标记即可。 总之，这种方法同规划知识图方法相比，使得求解的结果更合理，更好地解释了观察到的现象。同时可以动态增加新节点。