文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > An Investigation into Constraint Modeling of Realistic Planning Domains
侵权投诉

An Investigation into Constraint Modeling of Realistic Planning Domains

Constraint Programming provides a natural way to encode combinatorial search problems. AI Planning problems can also be encoded as constraint-based search procedures. We propose an encoding of planning problems as constraint models and infer actions from s

AnInvestigationintoConstraintModelingofRealisticPlanningDomains

DebdeepBanerjee,RalphBecket

NationalICTAustralia

debdeep.banerjee@rsise.anu.edu.au

rafe@csse.unimelb.edu.au

Abstract

ConstraintProgrammingprovidesanaturalwaytoencodecombinatorialsearchproblems.AIPlanningproblemscanalsobeencodedasconstraint-basedsearchprocedures.Weproposeanencodingofplanningproblemsasconstraintmod-elsandinferactionsfromstatetransitions.Thisapproachprovidesasimple,compactencodingoftheplanningprob-lems.Weillustratetheencodinginamanufacturingplanningdomain.

Introduction

ConstraintProgramming(CP)istheprogrammingparadigmthatissaidtobeclosesttotheprogrammingholygrail,i.e.theuserdescribestheproblem(models=variables+vari-ables’domains+constraints)andthecomputersolvesit(solving=search+constraintpropagation).Inconstraintprogrammingproblemsareformulatedasconstraintsatis-factionproblems(CSPs).Itcapturestheproblemdomain’sfeaturesinanaturalandintuitiveway.CPapproacheshavebeenusedinsolvingmanyrealworldcombinatorialsearchproblems.AIPlanningisaproblemwhereaninitialstate,desired(partial)goalstateandasetofoperatordescriptionsaregivenandthetaskistosynthesizeasequenceofactionstotransformtheinitialstateintoagoalstate.Inclassicalplanning,operatorsoractionsareoftendescribedinSTRIPSstyle,usingthreelists:preconditions,anaddlistandadeletelist.Thepreconditionsstatewhichpropositionsmustholdbeforeanoperatorcanbeapplied;theaddanddeletelistsdescribewhichpropositionsbecometrueandwhichbecomefalseafterapplyingtheoperator.

BothConstraintProgrammingandAIPlanningaresearchproblems.Inconstraintprogramming,searchattemptsto ndalabellingofallvariablesconsistentwiththegivencon-straints,optionallywhiletryingtooptimiseforsomeobjec-tivefunction.CPsearchalgorithmstypicallyseparateissuesofvariableselection(choosingwhichvariabletobranchonnext),domainreduction(howtonarrowthedomainofthechosenvariableonasearchbranch),andpropagation(in-ferringnecessarydomainreductionsonothervariablesasaconsequence).Propagationcandramaticallyreducethesearchspace.AIplanningalgorithms,ontheotherhand,

Copyright

c2007,AssociationfortheAdvancementofArti cialIntelligence(doc.guandang.net).Allrightsreserved.

usuallytakeadynamicapproachtoproblemsolvingbyintroducingnewsubgoalsondifferentsearchpaths.Oneweaknessofthisapproachisthatitismuchhardertoper-formeffectivepropagation.InordinaryCP,alldecisionvari-ablesandtheirdomainsarede nedaspartoftheproblemmodel.InordinaryAIplanning,onedoesnotknowinad-vancewhatthedecisionvariablesare(hereweareusing“de-cisionvariable”todenotethestateofsomethingatagiventimeorwhetheraparticularactionistobecarriedoutatagiventime).ACPrepresentationofanAIplanningproblemthereforehastoaddresstheissueofplanlengthfromtheoutset.Therearetwobasicsolutions:iterativedeepening(searchforaplanoflength1,searchforaplanoflength2,...)orplacinganupperboundontheplanlengthand llingtrailingactionstepswith“donothing”actions.

Searchingforaprede nedlengthofplanisknownasboundedlengthplanning.Inmanyrealworldplanningprob-lems,anupperboundonplanlengthcanoftenbefound.In-terestinconstrainttechniquesinAIplanninghasgrowninrecentyears.Usingconstraint-basedsearchforAIPlanninghasshowngoodresults,especiallyinparalleloptimalplan-ningdomains.KautzandSelman(1992;1996) rstpro-posedaSATencodingoftheplanningproblems.Usingtheplanninggraph(Blum&Furst1995)asabasisforencod-ingprovedtobehelpfulasitsigni cantlyreducesthesizeoftheSATrepresentation(Kautz&Selman1999).WhileSATisrestrictedtoBooleanvariables,othershaveextendedtheencodingintomoregeneralCSPbasedframework(Do&Kambhampati2001).Thereareotherapproachesaswell,forinstanceIntegerProgramming(Vossenetal.1999),(vandenBriel&Kambhmpati2005)andConstraintPro-gramming(vanBeek&Chen1999).ThebasicideaistoconvertaSTRIPSstyleplanningproblemintoaformsuitableforconstraint-basedsearchbyencodingtheinitialstates,goalstates,actions,frameaxiomsandmutualexclu-sionrelationsasconstraintsforagivenboundedlengthplan.AdetailedsurveyofapplicationsofconstraintinAIplan-ningisgivenin(Nareyeketal.2005).

Inthispaperweinvestigatehowwecanmodelplanningdomainsintheconstraintmodel.Theconstraintmodel-inglanguagewehaveusedisMiniZinc(Nethercoteetal.2007),asubsetofamorepowerfulconstraintmodelinglan-guageZinc(delaBandaetal.2006)developedaspartoftheG12project(Stuckeyetal.2005).Herewehavemod-

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email