基于问题结构的启发式策略在析取时态问题求解中的应用

智能规划和调度中的许多时态(或时序)问题可以表达为析取时态问题(DTP).目前,多数析取时态问题求解器将析取时态问题看作约束可满足问题(CSP)或可满足问题(SAT),并使用标准的CSP(或SAT)技术来求解DTP.虽然这些技术在求解DTP时已经可以达到较好的效率,然而,文献中极少研究者关注利用DTP本身特殊的结构中隐含的信息来帮助DTP求解.尝试从DTP的拓扑结构中提取出一种启发式策略.这种启发式策略试图从DTP的结构中提取出定性和定量的标准(TVS)来选择优先赋给当前变量的值,同时基于这种定量值选择标准设计了一个动态变量选择策略(TVO).这种技术基于定义的一种DTP的图模型--析取时态网络(DTN).实验结果显示TVS和TVO策略均可以有效减小搜索中节点访问次数;同时它与已有的RSV值选择策略效果相当,而TVO优于最少剩余值(MRV)方法(节省一个数量级以上的访问节点数);此外,配合其他CSP启发技术,可以得到一个高效的DTP求解算法DTN-DTP.     

时态规划综述及研究现状

作为人工智能领域的一个重要分支, 智能规划被广泛应用于机器人、工业生产、商业应用等领域。时态规划是智能规划的前沿子领域。本文从时态特征、规划方法、应用等三个角度出发, 对时态规划进行综述。与规划能力相比, 时态特征的发展已足够成熟; 基于启发式的状态空间搜索是目前的最佳选择; 研究人员仍在寻找更多更好的应用场景。本文旨在用通俗易懂的方式帮助入门学者快速认识时态规划。     

基于Europa2的智能规划动态仿真与建模

仿真与建模是智能规划(特别是时态规划)走向应用的重要而困难的研究主题。目前已有的规划可视化建模工具只能支持领域无关的仿真和建模,无法模拟现实场景。基于时间线的Chronicle规划与Microsoft最新的图形显示技术WPF在某些概念上存在自然的对应关系。基于这样的思想,针对NASA开发的开源时态规划平台——Europa2,使用WPF基础类库和相关工具,研究智能规划能够模拟现实场景的动态仿真和建模的设计方法并给出了实例演示。研究表明,对诸如Europa2一类基于时间线的Chronicle规划系统,可以应用WPF一类通用图形技术进行方便的建模和动态仿真,从而初步解决了规划系统模拟现实场景的仿真和建模难以实现的问题。     

基于动态约束满足框架的强表达时态规划算法

智能规划已经成为人工智能领域最热门的研究主题之一。近年来,智能规划在现实领域的应用越来越广泛,这对规划器的处理能力和效率提出了很大的挑战。以一类强表达时态规划——基于约束区间规划为研究对象,基于动态约束满足框架设计和实现了一个基于约束区间的规划算法LP-TPOP;对算法的可靠性和完备性进行了证明;最后以一个规划实例演示了算法的运行过程。