确定树求强规划解6[1].23.doc

确定树求强规划解胡雨隆1,文中华1,2,常青1,陈建林1HU Yu-long, WEN Zhong-hua, CHANG Qing, CHEN Jian-lin 1. 湘潭大学 信息工程学院，湖南 湘潭 4111052. 智能制造湖南省高等学校重点实验室，湖南 湘潭 4111051. College of Information Engineering, Xiangtan University, Xiangtan, Hunan 411105, China2. Key laboratory of Intelligent Manufacture of Hunan Province, Xiangtan University, 411105, ChinaE-mail: Strong planning solution via determined treeAbstract: This paper defined the determined tree and designed a method to seek determined tree. This design algorithm first find the initial state corresponds to the determination of each tree After found the tree, no need for strong planning solution has been searching from the goal state to the initial state, and only determined from the target state reverse to find any node of Tree, then through the node reverse search the initial state in the tree to be a strong planning solution. The results show that: the design of algorithms than the reverse search method solution for strong planning algorithm efficiency.Key words: determined tree; non-determinate; strong planning solution; reverse search摘 要: 本文定义了确定树，设计了求确定树的方法.本文设计的算法首先找到每个初始状态对应的确定树，在找到确定树之后，求强规划解就不需要从目标状态一直搜索到初始状态了，只需要从目标状态反向找到确定树的任意一个节点，再通过这个节点在确定树中反向搜索到初始状态从而得到一个强规划解。实验结果表明：所设计的算法比用反向搜索方法求强规划解的算法的效率高。关键字: 确定树；不确定规划；强规划解；反向搜索1 引言基金项目：国家自然科学基金(the National Natural Science Foundation of China under Grant No.60773047)；湖南省自然科学基金(the Natural Science Foundation of Hunan province of China under grant No.09JJ6090)；湖南省重点学科建设项目(the Construct Program of the Key Discipline in Hunan Province of China under Grant No.081202)；湖南省教育厅科研项目(the Scientific Research Fund of Hunan Provincial Education Department of China under Grant No.08C874)；智能制造湖南省高等学校重点实验室（湘潭大学）开放课题(the Open Program of Key laboratory of Intelligent Manufacture of Human Province(Xiangtan University)of China under No.2009IM07)。作者简介：胡雨隆(1986)，男，硕士生，主要研究领域为智能规划；文中华(1966)，男，博士，副教授，主要研究领域为智能规划，图论及算法；常青(1987)，男，硕士生，主要研究领域为智能规划；陈建林(1983)，男，硕士生，主要研究领域为智能规划。确定性是一种对客观世界简单化了的描述，它假设客观世界是沿着一条完全可预测的路径演化发展的。相比之下，不确定性更贴近于现实，因为所谓完美的系统模型原则上是不可能得到的。所以对在不确定的规划领域求解规划问题的研究是十分有意义的。目前使用基于模型检测的规划方法来处理带有不确定性的规划问题1,2已经成为不确定规划领域的一个新的热点。在使用基于模型检测的规划方法来求强规划解时，基本的算法都采用了反向搜索3-8，就是从目标状态进行宽度优先搜索找到初始状态。这样的搜索方式存在一些不足：搜索过程中状态数量膨胀速度很快；随着问题规模的增大，反向搜索层次的递增，待搜索状态增加，冗余的工作就越来越多。从而导致求强规划解的效率低,能解决的问题规模小。在一个不确定的状态转移系统中，大多数的状态转移是确定的。对这些确定动作的利用可以优化强规划解的求解方法。本文提出确定树的概念，在求解强规划解之前构建多个（看初始状态的个数）以初始状态为根的确定树。再进行反向搜索时，只需从目标状态搜索到每个确定树的任一状态。然后从该状态在确定树中反向搜索到初始状态就可以得到一个强规划解了。这样避免了直接反向搜索带来的不必要状态膨胀，减少的反向搜索的搜索空间并且在树中是有向搜索，从而减少了搜索时间提高了效率。本文设计了算法，实验验证了所设计的算法比用反向搜索方法求强规划解的算法的效率高。2 相关定义定义1 一个规划领域是一个不确定的状态转移系统 = (S, A, )，其中，S是一个有限状态集，A是一个有限动作集， : S A 2S是状态转移函数。 被用来刻画不确定性：在s下执行动作a所可能得到的结果状态的集合就是(s, a)。 若(s, a)非空，则称动作a在状态s下是可执行的。在状态s下可执行的状态动作序对的集合记作A(s, A)=(s, a); s/(s, a)，aA。定义2 设 = (S, A, )是一个规划领域，一个对于的规划问题P是一个三元组(, S0, Sg)，其中，S0 S是初始状态集合，Sg S是目标状态集合。定义3 a是一个确定动作当且仅当(s, a)有且仅有一个状态，当状态s1可以通过执行n(n 1)个确定动作a1，a2，a3，an到达s2时，我们称s1确定到达s2。定义4 T= (s, S/, A/)是一个基于不确定的状态转移系统 = (S, A, )以s为根的确定树，其中，S/是一个有限状态集，A/是一个有限动作集。有：1. s S/，若a是一个确定动作，有s/ = (s, a) 则S/ = S/ s/，A/ = A/ a。2. 若s1 S/，a1是一个确定动作，有s2 = (s1, a1)并且s2 S/则S/ = S/ s2，A/ = A/ a1。确定树的根节点到树的每一个节点都是可以确定到达的。定义5 在s下执行动作集合A所可能得到的结果状态的集合记作(s, A)。(s, A) = (s, a1) (s, a2) (s, an)，其中a1, a2, , an A。B是一个状态动作序对集合，B经过状态转移得到的状态集合记作(B)。(B) = (si, ai);( si, ai) B 。3 确定树方法求强规划解的算法设P = (, S0, Sg)是一个不确定的状态转移系统 = (S, A, )上的一个规划问题，规划问题P是在上求从初始状态集合S0出发到目标状态集合Sg的强规划解。3.1 算法思想算法首先对S0中的每个元素构建确定树，构建树的方法是先对所有动作进行一次遍历，找出所有的确定动作并将动作按可执行的状态进行分类，形成一个新的动作集A1 = A(s1, A1), A(s2, A1), , A(sn, A1)其中 s1, s2, , sn S。再在已分类的动作中构建确定树。例如：s1 S0，s1为确定树T的根，则(s1, A1)中的所有不属于T的状态为s1的儿子，对应的动作为相应的边。再对s1的儿子进行相同的操作，如此循环直到当前树T的所有叶子sx，都有(sx, A1) T。此时一棵以s1为根的确定树就构建完成了。假设已经对m个初始状态构建了确定树T1, T2, , Tm。使用反向搜索求强规划解的算法从目标状态反向寻找m棵确定树，找到树中的任意的一个状态即为找到了这棵树。若没有能找到所有的树，则该规划问题没有强规划解。若找到所有的树，就在树中反向找到目标状态，返回一个强规划解。3.2 算法设 = (S, A, g)为一个不确定的状态转移系统。S有n个状态，S0有m个状态，s1, s2, s3, , sm, , sn是S的n个状态，前m个是初始状态。T=t1, t2, , tm为确定树的集合。P为问题的强规划解，正向搜索方法求强规划解的算法如下：1. function FORWARDTREE(, S0, Sg)2. T=CREATTREE(, S0);3. P=SEARCH(T, , Sg);4. return P;5. end;算法可以从功能上分为两部分，所以主函数FORWARDTREE(, S0, Sg)只是封装了两个子函数。CREATTREE(, S0)函数实现的是对每一个初始状态创建一棵以之为根的确定树。并返回确定树集合。SEARCH(T, , Sg)函数 实现的是从目标状态反向找到T，再找到初始状态并返回一个强规划解。下面讲解这两个函数的实现。1. function CREATTREE(, S0)2. A/ = CLASSIFYACTION(A);3. for i = 1 to m4. ti.ADDHEAD(si);5. A1 = A(si, A/);6. S/ = (A1);7. while(S/ ti)do8. A2 = ;9. for j = 1 to |A1|10. if(sj, aj) ti)then11. ti.ADDACTION(sj, aj);12. A2 = A(si, a1), A/) A2;13. fi;14. next j;15. A1 = A2;16. S/ = (A1);17. done;18. next i;19. return T;20. end;该函数的目标是构建确定树，其中A/ 是动作集合，A2, A2是状态动作序对集合，S/是状态集合。ti是T的一个元素，表示一棵确定树，它具有添加头节点和非头节点的函数。第2行的函数CLASSIFYACTION(A)是对原始动作集合进行确定动作分类，就是将所有的确定动作组成一个新的动作集合；第3行是对每个初始状态构建确定树；第4，5行分别是添加根节点，初始化当前可执行的状态动作集合；第6行求出树的当前可扩充节点集合S/；第7到17行是构建当前树；第7行：当树的当前可扩充节点为空或属于当前树，则当前树构建完成，跳出循环；第8行：初始化当前可执行的状态动作集合A2 ；第9行：对A1的每个元素进行向下扩充的处理；10，11行是将当前可执行的不属于当前树的动作加入当前树；12，15行是更新当前可执行的状态动作集合，也就是进入树的下一层。1. function SEARCH(T, , Sg)2. 1 = STRONG-PLAN(T, , Sg, S/);3. 2 = ;4. for i = 1 to m5. 2 = 2 SEARCHTREE(ti, si, s/i);6. next i;7. return 1 2;8. end;该函数通过反向确定树搜索得到强规划解，第2行的STRONG-PLAN(T, , Sg, S/)函数是文献3反向搜索强规划解算法的一个修改，原算法是从目标状态搜索到初始状态并返回强规划解。而这里不再是搜索到初始状态集S0，而是搜索到确定树集合T并返回反向搜索阶段的解。S/是用来存储反向搜索所搜索到的确定树的状态（保存每棵树第一个被搜索到的状态，因为树在被找到后就不再被搜索）。第3行是初始化确定树搜索阶段的解2；第4行到第6行是在每棵树中搜索相应的初始状态，SEARCHTREE(ti, si, s/i)函数是从s/i开始找父亲状态直到找到根状态si并返回从si到s/i的一条确定路径。第7行是返回强规划解。4 算法示例分析例1： = (S, A, g)是一个不确定状态转移系统，P = (, S0, Sg)是上的一个规划问题。如图1所示，初始状态集合S0 = s1，目标状态集合Sg = s10, s11。规划问题P是求从S0到Sg的强规划解。算法首先对一个不确定状态转移系统进行提取确定动作集合，确定动作为A(s1, A1) = move(r1, l1, l2), move(r1, l1, l3)，A(s2, A1) = move(r1, l2, l4) ，A(s4, A1) = move(r1, l4, l2), move(r1, l4, l8)， A(s5, A1) = move(r1, l5, l3), move(r1, l5, l7)，A(s7, A1) = move(r1, l7, l5)。 图1 一个不确定状态转移系统在确定动作集合基础上构建确定树t，A(s1, A1)的确定动作可以在树的根状态s1执行，故将动作move(r1, l1, l2), move(r1, l1, l3)加入t，此时树的带扩展叶子为s2 和s3，s2的可执行动作集为A(s2, A1)=move(r1, l2, l4) ，而s3没有可执行的确定动作，s4又不属于t，故将move(r1, l2, l4)加入t。s4成为待扩展的叶子，依照上面的方法，则将动作move(r1, l4, l8)加入t，在通过s8扩展到s6。s6可扩展状态为空。故返回树t，如图2所示。图 2 由图1得到的一棵确定树 在树构建完成后开始从目标状态反向搜索，从目标状态s10, s11依次搜索到的是 s9， s8。当搜索到s8时，反向搜索因为已经找到所有的树而停止搜索。此时得到的规划解1 = move(r1, l9, l11) , move(r1, l8, l10) 。再在树中反向找到初始状态s1从而得到的规划解2 = move(r1, l4, l8),move(r1, l2, l4),move(r1, l1, l2)。最后返回强规划解 = move(r1, l4, l8), move(r1, l2, l4) , move(r1, l1, l2) , move(r1, l9, l11) , move(r1, l8, l10)。5 算法分析该算法可以分成3个部分：构建确定树，反向搜索确定树，树中搜索初始状态。设动作集大小为x，状态集大小为n，初始状态数为m。第一部分构建确定树第一步是遍历全部动作并进行确定动作的筛选和分类。第二步是从根向下扩展树。第一步的最坏时间复杂度是O(x)。第二步的最坏时间复杂度是O(m*x)。那么构建确定树阶段的最坏时间复杂度为O(m*x)。第二部分反向搜索确定树的最坏时间复杂度是O(n2*x)，而第三部分搜索初始状态的最坏时间复杂度为O(m*n)。显然在实际情况中m比x和n都小很多，所以该算法的运行时间主要是由第二部分反向搜索所耗费的。而第二部分的算法和文献3求强规划解的算法类似。故在最坏的情况下本文提出的算法与原始的求强规划解的算法的时间复杂度是同一数量级（最坏情况为反向搜索直接搜索到树的根状态），最坏情况即为确定树完全没有缩小反向搜索的搜索空间。所以在平均情况下本文提出的算法是提高了效率的。6 实验结果及分析算法实现中状态标识，动作集合，状态集合都采用一维数组表示。实验中均将初始状态数设置为2，目标状态设置为3。本文算法与文献3的反向搜索算法的运行时间比较如表1所示：表1 运行时间比较状态数文献3算法时间本文算法时间100.00027s0.00053s300.00102s0.00092s500.00157s0.00090s1000.00699 s0.00284s3000.11112s0.02737s5000.50331s0.02657s10003.71246s2.35303s150014.17875s10.88645s200033.77124s6.49334s从实验结果可以看出本文算法在9个实验中的平均运行时间比原算法少，并且随着状态数目的增加效率随之提高。这是因为当状态数越大时，本文算法求确定树的时间相对反向搜索的时间就越小。但是本文算法的效率是不稳定的，这是由于本文算法的效率要看确定树的大小以及确定树的方向。但是本文算法可以保证在最坏情况下和原反向算法的效率在同一数量级。本文算法的主要思想是初始状态构建确定树来缩小反向搜索的搜索空间。由于每一个状态转移系统可构建的确定树大小和方向都不同，所以缩小搜索空间的能力也不同。故本文算法提高了效率，但存在不稳定性。实验证明了以上观点。7 结论本文提出并设计了用确定树求强规划解的算法，利用初始状态扩张出来的确定树缩小求解时的搜索空间。实验证明所设计的算法是有效的。本文的进一步工作有：1. 提取整个状态转移系统存在确定树，并利用这些树来求强规划解。2. 利用确定树来求强循环规划解，弱规划解。参考文献1 Huang W, Wen ZH, Jiang YF, Chen AX. Comparison between two languages used to express planning goals: CTL and EAGLE. In: Yang Q, Webb G, eds. Proc. of the 9th Pacific Rim Intl Conf. on Artificial Intelligence (PRICAI 2006). Berlin: Springer - Verlag, 2006. 180 189.2 Huang W, Wen ZH, Jiang YF, Wu LH. Observation reduction for strong plans. In: Veloso MM, ed. Proc. of the 20th Intl Joint Conf. on Artificial Intelligence (IJCAI 2007). AAAI Press, 2007. 1930 1935.3 A. Cimatti, M. Pistore, M. Rovveri, P. Traverso. Weak, strong, and strong cyclic planning via symbolic model checkingJ. Artificial Intelligence, 2003, 147