摘要：动作的执行在理想情况下是确定的,但现实生活中常常因为意外情况的发生而造成了不确定性,并产生不利影响.针对这种情况,建立了一种新的不确定规划模型,在不确定规划中增加了两个约束:1)所有动作的执行是可逆的;2)若一个状态在理想情况下不能达到目标,那么它不能企图在执行一个动作时发生意外而接近或达到目标.在该模型下设计了求解强循环规划的算法,首先只考虑所有动作的执行是在理想情况下发生的,这时可以将规划子图转换为规划子树并求出规划子树中每个状态的可达性;接下来考虑所有动作执行意外的情况,若动作被意外执行之后不能到达目标状态,则删除这个动作并更新规划子图和规划子树,最后通过遍历规划子图和规划子树求强循环规划解.考虑到有些意外的发生并不可预知,该算法能够在意外发生时只对部分失效的规划解进行更新而不需要重新求规划解.实验结果证明该算法能够快速地更新规划解且与问题的规模大小无关.

摘要：在智能规划领域中,以往对不确定规划问题的研究主要集中于单个Agent,而对多Agent规划的研究则侧重于确定规划。针对该问题,提出基于多Agent的带权值不确定规划问题,对所求解的强规划解,设计使其所需动作权值总和近似最小的算法。根据基于模型检测的强规划分层方法,对每个Agent进行强规划分层,合并所有Agent的分层信息,并在合并的过程中得到同层状态之间的冲突表。在保证冲突最小的情况下,以最小动作权值优先的贪心方法,求出强规划解。实验结果表明,该算法能较快地求解出使所选择的动作权值总和近似最小的强规划解。

摘要：当前,对基于模型检测规划研究的算法中存在大量的冗余计算,一些不可能参与构成解的状态动作序偶被反复筛选.文中给出了一种在不确定规划领域求规划解的新思路:在求规划解之前,找到不确定状态转移系统的状态之间的可达关系,从而根据状态之间的可达关系进行约简.提出了不确定状态转移系统的超图、超图的邻接矩阵和可达矩阵等概念,设计了用超图的邻接矩阵求不确定状态转移系统中状态之间可达关系的方法.利用不确定状态转移系统的超图、超图的邻接矩阵和状态之间的可达关系获得了关于弱规划解、强规划解和强循环规划解的一些重要性质.这些性质是关于一些状态动作序偶是否不可能参与构成弱规划解、强规划解和强循环规划解的结论.通过这些性质可以将大量的状态动作序偶直接去掉,从而大幅度简化求规划解的过程,提高求规划解效率.

摘要：现实的规划问题中,观察信息的获取所需的代价是不同的,并且在规划解执行过程中,并非所有的观察信息都是有意义的,因此为了减少执行过程中的开销而对大量的带权值的观察信息进行约简就显得十分重要。首次针对带权值的观察信息约简问题做出研究,定义了带权值的最优观察集的概念,设计了SOWOS算法。该算法找出所有需要区分的状态对,用贪心的思想使搜索按指定顺序选择观察变量,并在搜索的过程中增加剪枝,减少了大量不必要的搜索,最终求得总花费最小的观察集,达到了减少执行成本的目的。实验结果表明,SOWOS算法可以高效地求得带权值的最优观察集,对减少规划执行中的开销贡献明显。

摘要：不确定规划研究的最终目标是求出规划解,但是由于缺少引导信息,直接求规划解会导致大量的无用状态和动作被搜索。获得状态间的可达关系可以避免冗余计算。目前求可达关系的方法效率较低,因此设计了一种求可达关系的新方法。将不确定状态转移系统抽象成一个图,在这个图中,查找状态之间的可达信息是否形成一个有向环。若存在一个有向环,说明环内每两个状态之间都有可达关系。将其中一个状态作为父节点,并且将这个环内所有状态的可达关系记录在父节点中,通过访问父节点的可达信息更新环内状态的可达信息,减少了许多无用的状态和动作被搜索。实验结果表明,所设计的算法不仅能得到更全面的可达关系,而且效率也高于已有的算法。

摘要：现实世界中,动作的执行通常都要耗费一定的代价,且由于外界环境的干扰,动作执行后的结果具有不确定性。针对这一问题,对不确定状态转移系统的动作赋予权值,使用概率分布表示状态转换的随机性,提出了强循环规划解的期望权值,并且设计了求最小期望权值强循环规划解的方法。该方法的主要思想是使用深度优先搜索求出规划问题的所有强循环规划解,再将强循环规划解分别转换成以状态到目标状态的期望权值为变元的线性方程组,最后使用高斯消元法解方程组,从而找出最小期望权值强循环规划解。

摘要：在不确定规划领域中,以往对强规划解的研究侧重于解本身,很少考虑不确定转移系统执行动作所需的代价;而已有的研究最小权值强规划解的算法效率不高。针对这一问题,引入模型检测的强规划分层方法,设计了一种快速求解最小权值强规划解的算法。该算法首先将不确定规划问题中的状态进行强规划分层,然后利用分层信息反向搜索最小权值强规划解;且在搜索的过程中,根据算法策略,实时更新所需搜索层数的上界和下界,从而避免了大量的无用搜索,提高了搜索效率。实验表明:所设计的算法能快速求解出最小权值强规划解,求解效率比已有的直接求解最小权值强规划解的算法高;且分层数和动作数越大,优势越明显。

摘要：为提高求解效率,设计一种求强规划解的简化分层算法。以传统分层算法为基础,引入贪心选择策略,对每个非目标状态的动作进行筛选,去除对求解强规划解无益的动作,加快状态向下搜索的速度,并在改进分层的基础上,优化求强规划解策略,由于在求解过程中会存在大量重复搜索,因此建立一个集合保存已访问状态的信息,避免对状态的重复搜索。分析结果表明,在初始状态到达目标状态路径都不重合的情况下,改进算法的时间复杂度为O(nm)(n为初始状态个数,m为层数),在都重合情况下为O(m),优于普通正向搜索算法与反向搜索算法。

摘要：随着人工智能的快速发展,智能规划中的不确定规划问题逐渐成为研究热点。在不确定系统中,由于受外部干扰因素影响,状态转移和到达结果都是不确定的,并且不确定转移系统执行动作需要花费一定代价。针对该问题,对不确定系统中的动作赋权值,用概率分布表示状态转移的不确定性,提出强规划解的期望权值,设计了求最小期望权值强规划解的方法。该算法首先将不确定规划问题中的目标状态集并入已搜索状态集,运用反向搜索求最小期望权值强规划解;在搜索过程中,需不断将最小期望权值所对应状态并入已搜索状态集,并更新未搜索状态集,迭代上述搜索步骤,直到已搜索状态集不变化为止,从而找出最小期望权值强规划解。