摘要： 为提高求解效率,设计一种求强规划解的简化分层算法。以传统分层算法为基础,引入贪心选择策略,对每个非目标状态的动作进行筛选,去除对求解强规划解无益的动作,加快状态向下搜索的速度,并在改进分层的基础上,优化求强规划解策略,由于在求解过程中会存在大量重复搜索,因此建立一个集合保存已访问状态的信息,避免对状态的重复搜索。分析结果表明,在初始状态到达目标状态路径都不重合的情况下,改进算法的时间复杂度为O(nm)(n 为初始状态个数,m 为层数),在都重合情况下为O(m),优于普通正向搜索算法与反向搜索算法。
关键词:
不确定规划,
强规划解,
分层状态,
贪心策略,
模型检测,
智能规划
Abstract: This paper designs a quick solution to solve the simplified layered strong planning algorithm to increase the
settlement efficiency. It is based on the introduction of greedy strategy,screening for non-target state for each action. This algorithm removes useless action plan for solving the strong solution to accelerate the state down search speed. On the basis of improved stratification, optimization and strong strategic planning solution, because the solution process is repeated,there are a lot of searching,and therefore the algorithm creates a collection to save the state having access to information,to avoid duplication of state search. After analysis,in the condition that the paths which are the intial state to goal state are overlapping,and the time complexity of this algorithm is O(nm),(n is the number of the initial state,m is the number of layers). The time complexity is O(m) in the condition that all the initial states to the target states are
coincident. And the results are better than the ordinary forward search algorithm and reverse search algorithm.
Key words:
nondeterministic planning,
strong planning solution,
hierarchical state,
greedy strategy,
model checking,
intelligent planning
中图分类号: