图规划框架下的启发式搜索的研究与发展

随着智能规划研究的深入,以往的规划器已不能满足实际应用的需要。为了提高规划器求解实际问题的能力,启发式搜索产生了。对近10年来各种启发式搜索方法进行了分析,指出了它们的优缺点,并进行了比较。同时对智能规划及其启发式搜索的未来发展方向进行了分析与预测,旨在让研究和关心该领域的学者较为全面地了解这一领域。

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

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

基于有序爬山法的前向启发式搜索规划

根据快速前向启发式搜索规划器FF中放宽规划图和有利动作之间的关系,定义了状态适用度函数的概念,可对后继扩展状态的启发式估值进行快速近似的比较。在此基础上,结合增强型爬山法搜索后继状态的贪婪选择机制,提出了一种改进的局部搜索算法——有序爬山法,即根据状态适应度函数对所有待扩展的后继状态进行排序,并加入到扩展优先队列。在启发式估值阶段,适应度高的状态将被优先计算评估,有利于更快地发现较优状态,从而减少调用启发式估值程序的次数。通过在国际规划大赛基准测试领域的实验结果表明,该方法减少了搜索节点的数目和搜索时间,有效地提高了启发式搜索效率,而计算状态适应度及对状态进行排序的时间消耗几乎可以忽略,因此整体规划性能比FF有显著的提升。

不确定规划中一种观察信息高效约简算法

在不确定规划中,可通过观察周围的信息来区分多个状态,但周围的观察信息较多,因此如何从大量的观察信息中筛选必须的信息非常重要。以往算法是在直接搜索过程中增加一些剪枝条件来达到优化的目的,存在一定的局限性。在对观察信息约简研究中,为提高搜索效率,设计一种高效的不确定规划中观察信息约简算法。该算法将规划问题转化为求解0-1矩阵的覆盖问题,使用数据结构十字链表来表示0-1矩阵,通过维护十字链表并采用启发式函数来加速求解一个最小观察变量集。实验结果表明,该算法不仅能够找最小观察变量集,而且运行速度超过同类算法。

平面布局专家系统的自学习智能回溯搜索策略

本文研究了一种基于方图用于平面布局设计的搜索控制机——SARM.阐述了状态节点(方图)的扩充操作规则,制订了选择扩充节点的启发式原则,提出了处理搜索失败的自学习智能回溯搜索控制策略.

部分满足问题规划启发式研究

在很多现实规划问题中,Agent通常不具备足够的资源获得所有的目标。因此,需要寻找满足目标子集的规划。本文对部分满足规划问题进行了描述,提出了一种解决部分满足规划问题的新方法。讨论了代价信息在规划图中的传播及如何利用代价信息选择目标子集,并给出了基于代价的启发式来引导回归搜索。采用智能规划中的基准问题对提出的方法进行了实验验证,实验表明该方法可以获得质量更高的规划解,最后提出了今后的改进方向。

用于游戏NPC路径规划的改进遗传算法

针对游戏非玩家控制(NPC)路径规划中传统遗传算法计算速度慢、正确率低等问题,设计了改进型遗传算法。提出了最佳种群规模估计方法,设计了基于精英主义思想的遗传算子。根据游戏地图的特点,引入了基于启发式深度优先搜索的变异操作。与传统遗传算法以及其他学者的改进算法进行了对比实验。实验结果表明:算法能够在保证正确率的前提下,提高计算速度,并且在多目标的环境下同样适用。

海洋多平台多传感器协同监测任务智能规划技术

海洋多平台多传感器协同监测任务智能规划技术面向大型复杂海洋传感网络,能够在海洋信息平台及传感设备大规模海上部署的情况下进行大批量的任务规划和观测资源分配,形成海洋情报分析-系统行动规划-行动规划实施-精确情报再收集的良性闭环监测模式。针对重要海上态势,能够通过多平台、多传感器协同行动规划手段,对情报进行持续的、多手段协同的精确观测,有效提升海洋传感网络的监测效率和精确度,显著降低系统对指挥调度人员的素质经验要求,极大提升了海洋传感网络系统的指挥调度智能化自动化水平。该技术全面分析了海洋传感网络的共性特点和特性差异,充分考虑了海上环境、能源、通信等多方面制约因素,建立具有广泛适应性的海洋多平台多传感器协同监测任务智能规划问题模型,能够快速移植到不同的海洋传感网络,采用差分进化、蚁群、贪心等多种群体人工智能算法和状态空间启发式搜索算法,满足不同业务场景规划的需求,同时具备智能约束匹配和规划冲突消解的能力,实现运行规划动态调整、系统资源实时匹配和协同保障。