Solving Strong Cyclic Planning in Nondeterministic Reversible Planning Domain

The execution of actions is deterministic under ideal conditions. But in the real world, many accidents cause uncertainty and make negative impact. In response to 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 for 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 of the size.