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

《时态规划中基于CSP技术的时态约束方法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第35卷第8期2012年8月计算机学报CHINESEJOURNALOFCOMPUTERS时态规划中基于CSP技术的时态约束方法伍丽华2陈蔼祥°姜云飞”•边芮。中山大学软件所广州510275）"（中山大学教学实验中心广州510275）"（广东商学院数学与计算科学学院广州510320）广东商学院公共管理学院广州510320）摘要在规划图框架F，定义了动作图，并进-步扩展为时态动作图，使之能体现处理具有时间资源约束的时态规划何题中的时态信息•住此基础上，提出一种对时态信息进行表示与管理并且能够进行时态约束推理的时态一致性赋值方法，利用约束可满足问题（CSP）

2、技术对时序约束进行表示和处理•包括过滤、约减及时态信息的一致性检验，使时态推理技术能更好地应用于时态规划的求解过程中•最后，给出一个呈于时态规划图的遗传规划算法GP-td,通过对国际智能规划大赛提供的Satellite规划领域问题进行实验.结果表明：该方法能够有效地提高大规模时态规划问题的求解效率和求解成功率.关键词时态动作图；时态推理;CSP技术；一致性时态赋值；遗传规划算法.中图法分类号TP18DOI号：10.3724/SF.J.1016.2012.01759ACSP-BasedApproachforTemporalConstraintsinTem

3、poralPlanningWULi-Hua1K2)CHENAi-Xiang1)>3>JIANGYun-FeinBIANRui4)l)(SoftwareResearchInstituteofSunYat-SenUniversity»Guangzhou510275》2)(Education&ExperimentCenter*SunYat-SenUniversity«Guangzhou510275)3>(SchoolofMathematicsandComputationalScience»GuangdongUniversityofBusinessStudie

4、svGuangzhou510320)(SchoolofPublicManagement*GuangdongUnii>ersityofBusinessStudiesfGuangzhou510320)AbstractThispaperdescribesaCSP(ConstraintSatisfactionProblems)conceptualmodelformakingtimeexplicitunderthetemporalactiongraph,andproposesanewtemporalconstraintreasoningtechniquestoh

5、andledurativeactionduringtheconstructionofaplantformanyrealplanningproblemsoftenrequiretheplanninggoalscanbesatisfiedinshortertime,andtheexecutionofplanningsolutionmusttakethetimeintoaccountinmostreal-worldapplications.Ourmaincontributionsconsistof：BythegeneralCSPtechniquestpre

6、sentsomemethodstomanagetemporalinformationassociatedwithfactsandactionsinatemporalplanforfilteringthedomainsandconstraints♦andfortheconstraintsconsistencychecking；PresentageneticalgorithmGP-tdtosolvetemporalplanningproblemundertheframeworkoftheplanninggraph.Alltheideasinthispape

7、rarefullyimplementedandintegratedinouralgorithmGP-td.Finally♦theeffectivenessofthetechniquesisdemonstratedonthedomaincalledSatellitebenchmarksofInternationalPlanningCompetitions(IPC).Theresultsshowthatthesetechniquescanefficientlysolvelargetemporalplanningproblemsandleadtoagre

8、aterimprovementinplanningperformance.收稿H期,2009-