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

A CSP-Based Approach for Temporal Constraints in Temporal Planning

在规划图框架下,定义了动作图,并进一步扩展为时态动作图,使之能体现处理具有时间资源约束的时态规划问题中的时态信息.在此基础上,提出一种对时态信息进行表示与管理并且能够进行时态约束推理的时态一致性赋值方法,利用约束可满足问题(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.