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

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

Applications of the Heuristics Based on Problem Structure to Disjunctive Temporal Problems

Many temporal problems arising in intelligent planning and scheduling can be expressed as disjunctive temporal problems (DTPs). Most of DTP solvers in the literature treat DTPs as constraint satisfaction problems (CSPs) or satisfiability problems (SATs), and solve them using standard CSP (SAT) techniques. They are proved to be very powerful in solving DTPs, however, unfortunately little work has been done on utilizing topological information encoded in DTPs to guide the search for solutions. Presented in th...