处理条件效果的互斥延迟算法的研究

An algorithm on interfering actions deferment for handling conditional effects in the intelligent planning

通过将带有条件效果的动作分解成元件,然后利用互斥延迟算法进行规划图的扩张,得到规划图.规划图生成后,从初始条件出发,利用一个前向的搜索过程进行搜索以求规划解.在搜索中,选择的不是单个的动作,而是独立集,这样可以明显地减小搜索空间,而且在搜索过程中,还利用了独立集之间的执行次序作为独立集选择的启发式,加快搜索过程.该算法大大地简化了搜索过程,提高了搜索效率.

This paper introduces the concepts of orderly interfering components and non-orderly interfering components in order to resolve the problem of interfering actions deferment with conditional effects. It is very convenient for the algorithm to create a plan graph. After the plan graph is created, a forward search process can begin from the initial condition. In the search process, the independence set instead of single action is choosen to support the subgoal. This can significantly reduces the search space. Also, the order between the independence sets is used as heuristics to speed up the search process. So the algorithm greatly improves the search process.