时态规划中基于CSP技术的时态约束方法  

A CSP-Based Approach for Temporal Constraints in Temporal Planning

作　　者：伍丽华[1,2] 陈蔼祥[3] 姜云飞[1] 边芮[4] 

机构地区：[1]中山大学软件所,广州510275 [2]中山大学教学实验中心,广州510275 [3]广东商学院数学与计算科学学院,广州510320 [4]广东商学院公共管理学院,广州510320

出　　处：《计算机学报》2012年第8期1759-1766,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(60773201;60970042);广东省自然科学基金项目(10451032001006140);广东高校优秀青年创新人才培育项目(LYM10081);广州市科技和信息化局应用基础研究计划项目(2010Y1-C641)资助~~

摘　　要：在规划图框架下,定义了动作图,并进一步扩展为时态动作图,使之能体现处理具有时间资源约束的时态规划问题中的时态信息.在此基础上,提出一种对时态信息进行表示与管理并且能够进行时态约束推理的时态一致性赋值方法,利用约束可满足问题(CSP)技术对时序约束进行表示和处理,包括过滤、约减及时态信息的一致性检验,使时态推理技术能更好地应用于时态规划的求解过程中.最后,给出一个基于时态规划图的遗传规划算法GP-td,通过对国际智能规划大赛提供的Satellite规划领域问题进行实验.结果表明:该方法能够有效地提高大规模时态规划问题的求解效率和求解成功率.This paper describes a CSP （Constraint Satisfaction Problems） conceptual model for making time explicit under the temporal action graph, and proposes a new temporal constraint reasoning techniques to handle durative action during the construction of a plan, for many real planning problems often require the planning goals can be satisfied in shorter time, and the execution of planning solution must take the time into account in most real-world applications. Our main contributions consist of. By the general CSP techniques, present some methods to manage temporal information associated with facts and actions in a temporal plan for filtering the domains and constraints, and for the constraints consistency checking; Present a genetic algorithm GP-td to solve temporal planning problem under the framework of the planning graph. All the ideas in this paper are fully implemented and integrated in our algorithm GP-td. Finally, the effectiveness of the techniques is demonstrated on the domain called Satellite benchmarks of International Planning Competitions （IPC）. The results show that these techniques can efficiently solve large temporal planning problems and lead to a greater improvement in planning performance.

关 键 词：时态动作图 时态推理 CSP技术 一致性时态赋值 遗传规划算法. 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]