论文部分内容阅读
智能规划是人工智能领域研究的热点问题之一,其理论和方法可广泛应用于机器人路径规划和事件调度等领域中。基于启发式搜索的规划方法是智能规划领域的重要分支,其求解方法是利用领域知识提供的启发信息引导状态空间上的路径搜索,由于其搜索效率和求解规模方面的优势,使其成为智能规划领域的研究前沿,受到国内外研究者的广泛关注。
但是,随着现实应用中问题结构复杂度的不断增加和数据规模的逐步扩大,传统的启发式搜索方法面临状态空间组合爆炸的问题,限制了求解效率和求解规模的提升。为了进一步压缩搜索空间,提升求解效率,扩大求解规模,本文引入路标对启发式搜索规划问题中的搜索算法和启发式函数两个关键因素进行更加精确的引导,分别提出了基于路标倾向的随机游走规划方法、基于命题路标约束的启发式评估方法和基于代价预分配的启发式评估方法,并将所提理论在人工智能交叉领域——基于模型的诊断中进行了应用研究,具体贡献如下:
(1)针对基于启发式搜索的规划方法中长距离随机搜索算法搜索方向不够明确的问题,提出一种基于路标倾向的随机游走规划方法,用于降低搜索算法对启发信息的依赖度,改善随机游走搜索过程的盲目性。首先,通过路标信息设置随机动作选择概率对搜索方向进行指引,改进随机游走搜索算法中均等随机动作选择概率产生的搜索方向随机性过大的问题,实现路标对随机游走方向的精确控制,从而引导搜索过程逐渐实现更多路标;其次,结合路标计数启发式,对状态节点进行启发式估值,避免访问过多的状态节点,以更快地生成规划解,进而提高求解效率。为验证算法的性能,选用典型的标准规划问题域进行了实验验证,实验结果表明:在路标信息的引导下,随机游走过程能够更快地完成长距离的状态转移,大幅压缩了搜索空间,提升了时间效率,降低了求解代价。
(2)针对领域知识开发不足导致的启发式估值不够准确和计算复杂度高的问题,提出了两种利用路标设计启发式函数的方法:基于命题路标约束的启发式评估方法和基于代价预分配的评估方法。首先,基于命题路标约束的启发式评估方法在路标切割启发式的基础上利用命题路标修改前提定位规则,构造更加合理的判决图,完成动作路标的提取切割、代价分配并累加最大代价启发式作为启发式估值,对状态节点进行评估;其次,基于代价预分配的启发式评估方法,利用命题路标的支持动作为放松规划问题提供必要代价,识别各个待实现路标的支持动作后,完成代价预分配工作,以解决基于命题路标约束的启发式评估方法中提取切割集合计算量较大,影响启发式估值效率的问题,进一步提升启发式估值的准确性;最后,结合最好优先搜索算法实现规划求解过程,提升求解效率。为验证算法性能,在若干典型的标准规划问题域上进行了实验验证,实验结果表明:与传统路标切割启发式评估方法相比,上述两种启发式评估方法减少了评估状态个数、提高了启发式估值准确性、降低了计算复杂度。
(3)将智能规划应用于基于模型诊断领域,针对诊断问题中可能出现的候选诊断不精确问题,提出一种使用路标启发式进行判断和诊断加速的方法。该路标启发式能够指导故障的搜索过程,并利用规划方法对候选诊断进行修复。首先,建立基于模型诊断和规划的结合模型,采用增量诊断结果作为规划的初始状态,采用启发式搜索规划方法求解非故障状态。其次,针对增量诊断中的多候选路径,提出一种基于路标启发式,使用路径规划进行探测的方法。设计了两种不同策略的故障诊断与修复算法:一种是利用可控事件修复所有可能的故障,另一种是通过可控事件和可观测事件的反馈进行测试,得到唯一的解并修复故障。实验表明,该方法能够有效提高诊断的效率和精确性。
综上所述,本文利用路标对启发式搜索规划问题中的搜索算法和启发式函数两个关键因素进行更加精确的引导,优化了随机游走搜索算法的搜索效率、提高了启发式函数对状态节点的评估效率和质量,并在多个标准测试问题域上对上述算法进行验证,同时,将智能规划方法应用于基于模型诊断问题,提高了诊断求解效率,并对诊断结果进行修复。结果表明:本文所提算法提高了启发式搜索规划方法的求解效率和求解质量,扩展了智能规划方法的应用领域,具有一定的理论和应用价值。
但是,随着现实应用中问题结构复杂度的不断增加和数据规模的逐步扩大,传统的启发式搜索方法面临状态空间组合爆炸的问题,限制了求解效率和求解规模的提升。为了进一步压缩搜索空间,提升求解效率,扩大求解规模,本文引入路标对启发式搜索规划问题中的搜索算法和启发式函数两个关键因素进行更加精确的引导,分别提出了基于路标倾向的随机游走规划方法、基于命题路标约束的启发式评估方法和基于代价预分配的启发式评估方法,并将所提理论在人工智能交叉领域——基于模型的诊断中进行了应用研究,具体贡献如下:
(1)针对基于启发式搜索的规划方法中长距离随机搜索算法搜索方向不够明确的问题,提出一种基于路标倾向的随机游走规划方法,用于降低搜索算法对启发信息的依赖度,改善随机游走搜索过程的盲目性。首先,通过路标信息设置随机动作选择概率对搜索方向进行指引,改进随机游走搜索算法中均等随机动作选择概率产生的搜索方向随机性过大的问题,实现路标对随机游走方向的精确控制,从而引导搜索过程逐渐实现更多路标;其次,结合路标计数启发式,对状态节点进行启发式估值,避免访问过多的状态节点,以更快地生成规划解,进而提高求解效率。为验证算法的性能,选用典型的标准规划问题域进行了实验验证,实验结果表明:在路标信息的引导下,随机游走过程能够更快地完成长距离的状态转移,大幅压缩了搜索空间,提升了时间效率,降低了求解代价。
(2)针对领域知识开发不足导致的启发式估值不够准确和计算复杂度高的问题,提出了两种利用路标设计启发式函数的方法:基于命题路标约束的启发式评估方法和基于代价预分配的评估方法。首先,基于命题路标约束的启发式评估方法在路标切割启发式的基础上利用命题路标修改前提定位规则,构造更加合理的判决图,完成动作路标的提取切割、代价分配并累加最大代价启发式作为启发式估值,对状态节点进行评估;其次,基于代价预分配的启发式评估方法,利用命题路标的支持动作为放松规划问题提供必要代价,识别各个待实现路标的支持动作后,完成代价预分配工作,以解决基于命题路标约束的启发式评估方法中提取切割集合计算量较大,影响启发式估值效率的问题,进一步提升启发式估值的准确性;最后,结合最好优先搜索算法实现规划求解过程,提升求解效率。为验证算法性能,在若干典型的标准规划问题域上进行了实验验证,实验结果表明:与传统路标切割启发式评估方法相比,上述两种启发式评估方法减少了评估状态个数、提高了启发式估值准确性、降低了计算复杂度。
(3)将智能规划应用于基于模型诊断领域,针对诊断问题中可能出现的候选诊断不精确问题,提出一种使用路标启发式进行判断和诊断加速的方法。该路标启发式能够指导故障的搜索过程,并利用规划方法对候选诊断进行修复。首先,建立基于模型诊断和规划的结合模型,采用增量诊断结果作为规划的初始状态,采用启发式搜索规划方法求解非故障状态。其次,针对增量诊断中的多候选路径,提出一种基于路标启发式,使用路径规划进行探测的方法。设计了两种不同策略的故障诊断与修复算法:一种是利用可控事件修复所有可能的故障,另一种是通过可控事件和可观测事件的反馈进行测试,得到唯一的解并修复故障。实验表明,该方法能够有效提高诊断的效率和精确性。
综上所述,本文利用路标对启发式搜索规划问题中的搜索算法和启发式函数两个关键因素进行更加精确的引导,优化了随机游走搜索算法的搜索效率、提高了启发式函数对状态节点的评估效率和质量,并在多个标准测试问题域上对上述算法进行验证,同时,将智能规划方法应用于基于模型诊断问题,提高了诊断求解效率,并对诊断结果进行修复。结果表明:本文所提算法提高了启发式搜索规划方法的求解效率和求解质量,扩展了智能规划方法的应用领域,具有一定的理论和应用价值。