基于感知行动的一个双向规划算法研究.docVIP

基于感知行动的一个双向规划算法研究 范新刚 彭湘凯 （广州城建职业学院 信息工程系，广东广州 中国 510925） 摘要：规划最主要的内容是对Agent行动进行推理，但Agent对真实世界环境的知识是不完备的，因此这种情况下的规划，需要感知行动以扩充Agent的知识状态，带有感知的行动的规划，其结果不再是一个简单的行动序列，而是带有感知行动及其条件说明的条件规划。本文根据Agent知识状态空间的有哪些信誉好的足球投注网站方向，讨论了正向规划、反向规划，最后提出了一个能够处理感知行动和条件规划的双向规划算法BCPS(Bi-direction Conditional Planning with Sensing actions)。 关键字：规划，条件规划，正向规划，反向规划，双向规划 中图法分类号：TP391 文献标识码： A A Bi-direction Conditional Planning algorithm based on Sensing actions FAN Xin-gang （Information Enginecring Department ,Guangzhou City Construction College,Conghua Guangdong, china 510925） Abstract：The most important aspect of planning is reasoning about actions. But in reality agent’s knowledge about environment is often incomplete. Then sensing actions are needed in these situations to collect information in cases it is needed to expand the agents knowledge about environment. Then planning with incomplete information is no longer a simple sequence of actions, but a conditional plan with sensing actions. In this paper based on the searching directions, the algorithms for planning obtained by means of progression searching, regression searching are discussed in details and a bi-direction planning algorithm(BCPS) is proposed . Keywords:planning,conditional planning, progression planning , regression planning , bi-direction planning . 引言 具有感知行动的规划是智能规划中的一个重要分支，感知行动首先要解决的问题是感知行动的形式化描述及推理。 对感知行动的表示和推理，一般基于一些经典方法的扩展。情景演算和流演算方法中，广泛采用可能世界语义模型表示Agent的知识，在对感知行动和非感知行动进行推理时，将世界状态之间的可达性关系作为流，通过定义执行行动后，所能达到的世界之间的可达性关系——即定义可达性关系流的后继状态公理，来描述执行一个行动后，Agent的知识是如何改变的。[1]中Scherl 和Levesque同样采用可达性关系来描述Agent的知识改变，并给出了一个重要的结论：感知行动不改变知识流之外的流，非感知行动只影响相应的知识流。类似STRIPS方法中,[2]对行动描述语言A进行了扩展，称为AK语言，能够对感知行动进行形式化描述，并通过定义状态转移函数，对感知行动和非感知行动进行推理。 初始状态信息不完备情况下，需要在某些时候执行感知行动以获取足够的信息，不同于非感知行动，感知行动的结果是不确定的——遇到一个未知状态变量，需要考虑它各种不同的取值，只有在它的各种取值情况下，规划都可成功达到目标，才说这个规划是可靠的。因此，在感知行动执行后，即应该根据所感知状态变量的不同取值情况，对规划进行分支，每条分支都必须要达到目标。可见，若所感知的状态变量有k种可能的取值结果，则相应的规划就应当在感知行动后出现k条分支——称这种根据条件进行分支的规划为条件规划。 智能规划问题的解就是按照某种有哪些信誉好的足球投注网站策略，找到一个行动序列。有哪些信誉好的足球投注网站策略按有哪些信誉好的足球投注网站空间可分为规划空间有哪些信誉好的足球投注网站策略和环境空间有哪些信誉好的足球投注网站策略。而在环境空间有哪些信誉好的足球投注网站中，按照有哪些信誉好的足球投注网站方