共查询到19条相似文献,搜索用时 171 毫秒
1.
在不确定规划领域中,以往对强规划解的研究侧重于解本身,很少考虑不确定转移系统执行动作所需的代价;而已有的研究最小权值强规划解的算法效率不高。针对这一问题,引入模型检测的强规划分层方法,设计了一种快速求解最小权值强规划解的算法。该算法首先将不确定规划问题中的状态进行强规划分层,然后利用分层信息反向搜索最小权值强规划解;且在搜索的过程中,根据算法策略,实时更新所需搜索层数的上界和下界,从而避免了大量的无用搜索,提高了搜索效率。实验表明:所设计的算法能快速求解出最小权值强规划解,求解效率比已有的直接求解最小权值强规划解的算法高;且分层数和动作数越大,优势越明显。 相似文献
2.
3.
模型检测规划中的状态之间的可达关系研究 总被引:1,自引:0,他引:1
当前,对基于模型检测规划研究的算法中存在大量的冗余计算,一些不可能参与构成解的状态动作序偶被反复筛选.文中给出了一种在不确定规划领域求规划解的新思路:在求规划解之前,找到不确定状态转移系统的状态之间的可达关系,从而根据状态之间的可达关系进行约简.提出了不确定状态转移系统的超图、超图的邻接矩阵和可达矩阵等概念,设计了用超图的邻接矩阵求不确定状态转移系统中状态之间可达关系的方法.利用不确定状态转移系统的超图、超图的邻接矩阵和状态之间的可达关系获得了关于弱规划解、强规划解和强循环规划解的一些重要性质.这些性质是关于一些状态动作序偶是否不可能参与构成弱规划解、强规划解和强循环规划解的结论.通过这些性质可以将大量的状态动作序偶直接去掉,从而大幅度简化求规划解的过程,提高求规划解效率. 相似文献
4.
在智能规划领域中,以往对不确定规划问题的研究主要集中于单个Agent,而对多Agent规划的研究则侧重于确定规划。针对该问题,提出基于多Agent的带权值不确定规划问题,对所求解的强规划解,设计使其所需动作权值总和近似最小的算法。根据基于模型检测的强规划分层方法,对每个Agent进行强规划分层,合并所有Agent的分层信息,并在合并的过程中得到同层状态之间的冲突表。在保证冲突最小的情况下,以最小动作权值优先的贪心方法,求出强规划解。实验结果表明,该算法能较快地求解出使所选择的动作权值总和近似最小的强规划解。 相似文献
5.
在不确定规划领域中, 不确定状态转移系统求规划解常常会搜索大量无用的状态和动作, 造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算, 为系统提供引导信息。以非循环可达关系为基础, 定义矩阵的计算规则, 使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等, 并设计了求循环可达关系的算法, 且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系, 在求规划解的过程中可以删除大量无用的状态动作序偶, 降低问题规模, 提高求解规划问题的效率。 相似文献
6.
在不确定规划领域中,在求规划问题的解时,由于缺少引导信息,会导致许多无用状态和动作被搜索,造成冗余计算。所以在求规划解之前,找到不确定状态转移系统中状态之间的可达关系是很有意义的。以往的算法是通过矩阵相乘来模拟状态转移,但该类算法对于规模较大的系统开销较大。因此,提出了用信息传递法来求解可达关系,用矩阵来模拟不确定状态转移系统。其中每个状态记录了其他状态到达该状态的可达信息,通过状态之间的可达信息的传递,求得不确定系统的状态可达关系,以避免大量的矩阵运算。通过实验对比表明,当不确定系统规模较大时,所设计的算法优于矩阵相乘的算法。 相似文献
7.
以规划领域中的不确定状态转移系统作为研究对象,设计了求强规划解问题中的状态分层方法,状态被分层以后,求强规划解只需要从初始状态出发,逐次向下层状态转移到目标状态就可以了,在此基础上,设计了用正向搜索方法求强规划解的算法。实验结果表明:所设计的算法比用反向搜索方法求强规划解算法的效率高。 相似文献
8.
动作的执行在理想情况下是确定的,但现实生活中常常因为意外情况的发生而造成了不确定性,并产生不利影响.针对这种情况,建立了一种新的不确定规划模型,在不确定规划中增加了两个约束:1)所有动作的执行是可逆的;2)若一个状态在理想情况下不能达到目标,那么它不能企图在执行一个动作时发生意外而接近或达到目标.在该模型下设计了求解强循环规划的算法,首先只考虑所有动作的执行是在理想情况下发生的,这时可以将规划子图转换为规划子树并求出规划子树中每个状态的可达性;接下来考虑所有动作执行意外的情况,若动作被意外执行之后不能到达目标状态,则删除这个动作并更新规划子图和规划子树,最后通过遍历规划子图和规划子树求强循环规划解.考虑到有些意外的发生并不可预知,该算法能够在意外发生时只对部分失效的规划解进行更新而不需要重新求规划解.实验结果证明该算法能够快速地更新规划解且与问题的规模大小无关. 相似文献
9.
不确定规划中非循环可达关系的求解方法 总被引:1,自引:0,他引:1
对一个不确定状态转移系统求多个规划问题,那么获得不确定状态转移系统的状态可达关系可以方便求解规划问题,减少冗余计算,建立系统的引导信息。提出一个关于矩阵求不确定领域的状态可达性关系的方法,主要思想是以矩阵乘法来模拟状态转移系统中状态转移,对不确定动作带来的扩散和确定关系带来的聚合进行了统计和处理,从而获得状态可达信息。证明了方法的正确性和有效性。在不确定规划中确定了状态之间的可达性关系,可以在求规划解时删除对规划没有用的状态节点和状态动作序偶;选择能到达目标节点的状态节点和状态动作序偶;进行启发式正向搜索;减少大量冗余计算;提高求解效率。 相似文献
10.
11.
强循环规划的观察信息约简 总被引:1,自引:0,他引:1
在现实的规划领域中,观察信息的获得需要花费一定的代价,然而对于一个规划解来说,一些观察信息在执行规划解的过程中是不会被用到的,所以如何把这些不必要的观察信息去除从而节省实际过程中的成本是非常有必要的。针对强循环规划的观察信息展开研究,提出了一个对强循环规划观察信息进行约简的算法,该算法能够找出在完全可观察条件下强循环规划的最小观察变量集合,通过使用最小观察变量集合,可以进一步提高执行强循环规划解的效率。 相似文献
12.
Wen Liang Chang 《International journal of systems science》2013,44(6):1003-1009
This paper provides a replacement policy for repairable products with free-repair warranty (FRW) under a finite planning horizon from the consumer's viewpoint. Assume that the product is replaced once within a finite planning horizon, and the failure rate of the second product is lower than the failure rate of the first product. Within FRW, the failed product is corrected by minimal repair without any cost to the consumers. After FRW, the failed product is repaired with a fixed repair cost to the consumers. However, each failure incurs a fixed downtime cost to the consumers over a finite planning horizon. In this paper, we derive the three models of the expected total disbursement cost within a finite planning horizon and some properties of the optimal replacement policy under some reasonable conditions are obtained. Finally, numerical examples are given to illustrate the features of the optimal replacement policy under various maintenance costs. 相似文献
13.
14.
针对同时带有弧费用和弧时间的运输网络中最少时间最小费用路的问题,本文提出了一种算法。该算法能高效地求出此类网络中从源节点到目的节点的双目标最短路(最少时间最小费用路)。实例计算表明,该算法是有效的。 相似文献
15.
This paper is concerned with the problem of production planning in a flexible manufacturing system consisting of a single or parallel failure-prone machines producing a number of different products. The objective is to choose the rates of production of the various products over time in order to meet their demands at the minimum long-run average cost of production and surplus. The analysis proceeds with a study of the corresponding problem with a discounted cost. It is shown using the vanishing discount approach for the average cost problem that the Hamilton-Jacobi-Bellman equation in terms of directional derivatives has a solution consisting of the minimal average cost and the so-called potential function. The result helps in establishing a verification theorem, and in specifying an optimal control policy in terms of the potential function. The results settle a hitherto open problem as well as generalize known results. 相似文献
16.
针对家庭服务机器人机械臂高安全性和低算法复杂度的两大需求,提出一种基于空间代价地图的机械臂运动规划新方法。利用空间代价地图来描述机械臂与约束条件发生冲突的可能性,以概率分析代替简单的布尔判断,提供了更合理的最优规划依据,从而实现更安全可靠的规划。同时将一个六自由度的规划问题降维为一个三自由度规划和一个四自由度规划的问题,在此基础上利用无需实时计算的先验碰撞数据代替实时的碰撞检测。利用该方法在ROS的rviz仿真平台上进行验证,结果表明该方法有效地提高了机械臂规划的安全性并降低了计算复杂度,有一定的实用价值。 相似文献
17.
18.
Routing optimisation in some types of networks requires the calculation of the minimal cost pair of disjoint paths such that the cost functions associated with the arcs in the two paths are different. An exact algorithm for solving this NP-complete problem is proposed, based on a condition which guarantees that the optimal path pair cost has been obtained. This optimality condition is based on the calculation of upper and lower bounds on the optimal cost. A formal proof of the correctness of the algorithm is described. Extensive experimentation is presented to show the effectiveness of the algorithm, including a comparison with an integer linear programming formulation. 相似文献
19.
最少时间最小费用路问题的修改Dijkstra算法 总被引:2,自引:0,他引:2
针对同时带有顶点权和弧权的运输网络的最少时间最小费用路问题,首先将该网络转化为一般的只带弧权的运输网络,然后设计了求解该类问题的修改的“带前点标号的Dijkstra算法”,最后给出在物资公路运输中的一个实例。 相似文献