不确定可逆规划的强循环规划解  

Solving Strong Cyclic Planning in Nondeterministic Reversible Planning Domain

作　　者：唐杰[1] 文中华[1] 汪泉[1] 黄巍[2] 

机构地区：[1]湘潭大学信息工程学院,湖南湘潭411105 [2]中国科学技术大学计算机科学与技术学院,合肥230052

出　　处：《计算机研究与发展》2013年第9期1970-1980,共11页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61070232;61272295;61105039)

摘　　要：动作的执行在理想情况下是确定的,但现实生活中常常因为意外情况的发生而造成了不确定性,并产生不利影响.针对这种情况,建立了一种新的不确定规划模型,在不确定规划中增加了两个约束:1)所有动作的执行是可逆的;2)若一个状态在理想情况下不能达到目标,那么它不能企图在执行一个动作时发生意外而接近或达到目标.在该模型下设计了求解强循环规划的算法,首先只考虑所有动作的执行是在理想情况下发生的,这时可以将规划子图转换为规划子树并求出规划子树中每个状态的可达性;接下来考虑所有动作执行意外的情况,若动作被意外执行之后不能到达目标状态,则删除这个动作并更新规划子图和规划子树,最后通过遍历规划子图和规划子树求强循环规划解.考虑到有些意外的发生并不可预知,该算法能够在意外发生时只对部分失效的规划解进行更新而不需要重新求规划解.实验结果证明该算法能够快速地更新规划解且与问题的规模大小无关.The execution of actions is deterministic under ideal conditions. But in accidents cause uncertainty and make negative impact. In response to the real world, many this status, a new nondeterministic planning model is established, and two constraints are added in nondeterministic planning. 1）The execution of all actions is reversible ~ 2）If an action is executed in accidents, it is only possible to deviate from the target states. A solution {or strong cycle planning is proposed in the model. At the first step, the execution of all actions is supposed to occur in ideal situation. Then, planning subgraph is converted to planning subtree and seeking out reachability of each state in planning tree. And then, the accident situation that execution of actions cause is considered. If it cannot reach target state that action is executed by accident, this action is deleted and planning subgraph and planning subtree are updated, Finally, the algorithm solves strong cycle planning through traversal planning subgraph and planning subtree. Taking into account some accidents are unpredictable, the algorithm only updates the part of solution which is already invalid and needn＇t get repeatedly a solution. Experimental results show that the algorithm can quickly update planning solution and the problem is independent o~ the size.

关 键 词：不确定可逆规划 规划子树 规划子图 强循环规划 不可靠执行 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]