不确定规划中状态循环可达关系的求解方法

在不确定规划领域中, 不确定状态转移系统求规划解常常会搜索大量无用的状态和动作, 造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算, 为系统提供引导信息。以非循环可达关系为基础, 定义矩阵的计算规则, 使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等, 并设计了求循环可达关系的算法, 且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系, 在求规划解的过程中可以删除大量无用的状态动作序偶, 降低问题规模, 提高求解规划问题的效率。     

不确定规划中可达关系的快速求解算法

在不确定规划领域中,通常需要在同一个不确定状态转移系统中解决多个规划问题,如果能得到不确定规划中状态之间的可达关系即可方便求解该规划问题,然而现有矩阵乘法求解可达关系时存在算法复杂度高的问题。为此,设计一种快速求解不确定规划中状态之间可达关系的算法,将确定动作和不确定动作区分处理,先求解所有确定动作的可达关系,再采用链表和队列求解不确定动作的可达关系。实验结果表明,与矩阵乘法相比,该算法能得到更全面的可达关系,且求解效率更高。     

不确定规划中循环可达状态信息的维护

动态环境下,动作执行的不确定性会因外部因素存在变动,因此将导致不确定系统中的状态可达关系可能发生改变.为解答这一问题,论文对信息传递法中状态之间可达关系的更新方式进行改进,提出一种新的状态可达关系的维护算法.该算法将变更的状态之间可达关系与原可达矩阵对比,利用邻接矩阵中对应可达信息对变更后状态的可达信息进行修改,然后通...     

不确定可逆规划的强循环规划解

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

顺序价值迭代算法求解不确定规划

基于Markov决策过程(MDP)的规划方法可以处理多种不确定规划问题,价值迭代算法(VI)是求解MDP的经典算法,但VI需要计算更新每个状态的值,求解过程相当缓慢。在分析了MDP状态图本身的因果依赖关系的基础上,提出一种改进的价值迭代算法,称为顺序价值迭代算法(SVI)。它先将一个MDP分解成多个拓扑有序的强连通分量,然后应用价值迭代算法顺序求解各个分量,这样处理可以避免对大量无用状态的计算并使得可用状态排成拓扑序列。对比实验结果证明了该算法的有效性及优异性能。     

利用有向环的性质求解可达关系

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

信息传递法求不确定系统中的状态可达关系

在不确定规划领域中,在求规划问题的解时,由于缺少引导信息,会导致许多无用状态和动作被搜索,造成冗余计算。所以在求规划解之前,找到不确定状态转移系统中状态之间的可达关系是很有意义的。以往的算法是通过矩阵相乘来模拟状态转移,但该类算法对于规模较大的系统开销较大。因此,提出了用信息传递法来求解可达关系,用矩阵来模拟不确定状态转移系统。其中每个状态记录了其他状态到达该状态的可达信息,通过状态之间的可达信息的传递,求得不确定系统的状态可达关系,以避免大量的矩阵运算。通过实验对比表明,当不确定系统规模较大时,所设计的算法优于矩阵相乘的算法。     

确定树求强规划解

定义了确定树,设计了求确定树的方法。基于该方法设计了求强规划解的算法,找到每个初始状态对应的确定树,在找到确定树之后,求强规划解不需要从目标状态一直搜索到初始状态,只需要从目标状态反向找到确定树的任意一个节点,再通过这个节点在确定树中反向搜索到初始状态从而得到一个强规划解。实验结果表明：所设计的算法比用反向搜索方法求强规划解的算法的效率高。     

求解不确定TSP问题的蚂蚁算法

提出了不确定旅行商问题模型,该模型将路径长度看作动态可变的。从实际应用来说,该模型考虑了交通运行中的不确定情况,比经典旅行商问题更具有灵活性及实用价值,利用该模型得到的结果将更适于指导车辆对运行路线的选择。同时提出了一种基于蚂蚁算法的混合方法求解不确定旅行商问题,并给出了解的评价标准。实验结果显示,该方法能够加速蚂蚁算法的收敛性,可以有效求解不确定旅行商问题。     

不确定层次任务网络规划研究综述

层次任务网络(Hierarchical task network, HTN)规划作为一项重要的智能规划技术被广泛应用于实际规划问题中, 传统的HTN规划无法处理不确定规划问题.然而, 现实世界不可避免地存在无法确定或无法预测的信息, 这使许多学者开始关注不确定规划问题, 不确定HTN规划研究也成为HTN规划研究的前沿.本文从HTN规划过程出发分析了不确定HTN规划问题中涉及的三类不确定, 即状态不确定、动作效果不确定和任务分解不确定; 总结了系统状态、动作效果和任务分解等不确定需要扩展确定性HTN规划模型的工作, 以此对现有不确定HTN规划的研究工作加以梳理和归类; 最后,对不确定HTN规划研究中仍需要解决的问题和未来的研究方向作了进一步展望.     

特种车辆维修空间可达性评价方法研究

可达性作为维修性的定性指标,缺少定量评价的方法。传统方法只针对装备的整体进行定性评价,不能对不同的等级维修和单个维修动作进行评价。通过对维修性设计中的结构性因素进行分析,得到了空间可达性的主要影响因素。在虚拟维修仿真平台的基础上对工具旋转角度和作业空间比进行了量化评分,给出了针对维修作业过程中单个零部件拆卸的空间可达性评价方法。单个动作评价方法为等级维修的整体空间可达性评价提供了数据基础,并为新型特种车辆的维修方案论证和研制的空间可达性评价提供了手段。     

基于预案模板的HTN规划知识建模方法及其应用

应急决策是应急管理的基础和核心,H TN( Hierarchy Mask Nct)规划为应急决策提供了一种有效手段,是目前研究的热点问题。针对基于HTN规划求解应急决策问题存在领域知识难于建模的问题,在利用基于PetriNet的工作流模型对应急预案进行建模的基础上,提出了一种将预案模板转化为H`I'N规划领域知识模型的方法。在此基础上,将基于预案模板的应急决策问题建模为应急任务规划问题,利用HTN规划系统SHOP2 (Simple Hierarchical Ordered Planner 2)进行规划求解,实现复杂应急态势条件下通过选择和组织应急计划片段科学制定应对方案,并以某区域洪灾应急响应为例开展了应用研究。     

一种强跟踪扩展卡尔曼滤波器的改进算法

针对模型不匹配卡尔曼的状态估计发散和应用范围限于连续系统问题,提出一种基于有限差分强跟踪滤波嚣（STFDEKF）．在滤波计算中,引入强跟踪滤波因子修正滤波器的状态预协方差矩阵。滤波精度得以提高,滤波器应用有限差分方法计算滤波过程中非线性函数的偏导数。扩大了适用范围．几种卡尔曼滤波器经过仿真比较。STFDEKF应用于复杂非线性系统状态估计时．具有较高数值稳定性、强跟踪性和较宽应用范围．     

坐标测量机测量点通用可达性分析方法

坐标测量机接触式点位测量必须事先分析测量点的可达性以免测量时发生 碰撞,并给出测量点的可达方向,为测量方向选择提供基础。对于目前常见的各种类型探针, 论文提出了一种通用的测量点可达性分析方法。由用户交互建立任意类型的探针和测头等测 量机部件的简化模型,可达性分析首先根据探针类型快速排除不可达方向,然后通过计算测 量机部件与工件、夹具等障碍物的最小距离精确判断测量点在各个测量方向下的静态可达性 和动态可达性,由此可得到测量点的全部可达方向。在可达性分析中对障碍物进行了离散化 处理,因此,该方法适用于任意复杂程度的零件。     

动态未知环境中移动机器人的滚动路径规划及安全性分析

借鉴预测控制滚动优化原理,研究了全局环境未知且存在动态障碍物情况下的机器人路径规划问题.提出的基于滚动窗口的移动机器人路径规划方法充分利用机器人实时测得的局部环境信息,以滚动方式进行在线规划,合理结合了优化与反馈,对动态环境具有良好的适应性.还对规划算法的安全性进行了分析.     

状态自动机矩阵模型的代数性质

有限自动机理论是控制理论、对象程序测试、神经网络、保密学等众多学科领域的重要研究工具犤1～4犦,探索有限自动机理论研究的新思路具有重要学术意义。文章在有限自动机矩阵模型表示方法基础上,采用矩阵理论和布尔代数为工具,针对无输出情形的特殊有限自动机(状态自动机),研究给出了基本代数性质及相应的物理意义。在采用新的数学方法进行有限自动机理论研究方面作了有益的探索,采用这种方法有利于算法设计和计算机自动处理。     

领航计划报预处理方法探讨

当前民航系统使用的AFTN（航空固定电信网）报文存在格式、内容、数据不规范的问题,致使FDP系统（飞行数据处理系统）报文识别率不高。本文针对FPL（领航计划报）报文进行预处理,对于重复性FPL报文,采用直接查询调用历史数据的方法。而新报文则根据FPL报文标准进行规范性判断和纠正处理,并将处理结果保存为历史数据作为下一轮处理的参考数据。实验证明,原本FDP系统无法识别的FPL报文经过预处理后再进入FDP系统,FDP系统识别率可以达到75％以上,FDP系统的FPL报文识别率得到了显著的提高。     

基于启发式搜索的灵活规划的算法研究与系统实现

随着智能规划研究的深入,经典规划已不能满足实际应用的需要.本文分析了经典规划无法满足实际应用要求及产生灵活规划的原因.在对启发式搜索和灵活规划深入研究的基础上,提出了利用启发式搜索的方法来处理灵活规划问题的思想,并给出了基于启发式搜索的灵活规划算法和求解模型.采用智能规划中的基准问题对该算法进行测试,实验表明该方法在处理很多领域问题上都可以得到非常好的效果.