Markov决策过程的蚁群规划算法

Ant planning algorithm based on Markov decision processes

在智能规划问题上,寻找规划解都是NP甚至NP完全问题,如果动作的执行效果带有不确定性,如在Markov决策过程的规划问题中,规划的求解将会更加困难,现有的Markov决策过程的规划算法往往用一个整体状态节点来描述某个动作的实际执行效果,试图回避状态内部的复杂性,而现实中的大量动作往往都会产生多个命题效果,对应多个命题节点。为了能够处理和解决这个问题,提出了映像动作,映像路节和映像规划图等概念,并在其基础上提出了Markov决策过程的蚁群规划算法,从而解决了这一问题。并且证明了算法得到的解,即使在不确定的执行环境下,也具有不低于一定概率的可靠性。

In the classical planning problems,to found a planning solution is a NP problem or even a NP complete problem. If the executing effects of the action take uncertainty,such as the planning problem of Markov Decision Processes（MDP）, the problem will be more difficult.Some concepts such as the reflection action,reflection path-section,and reflection planning graph are presented based on the graph plan algorithm,and the ant colony planning algorithm will be designed based on them.In the algorithm,the actions can generate more nodes that each one is a representation of a proposition.It is proved that there is no less than a certainty probability that the solution of the ant colony planning algorithm will be reliability even in the uncertain action executing environments.