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-
constraint-based modeling, planning support, ...An in-depth investigation of these different ...To secure a realistic schedule the constraints ...
Many realistic domains involve manipulation of ...Instead of modeling a state change by adding and...combining planning with constraint logic programming....
Many realistic domains involve manipulation of ...Instead of modeling a state change by adding and...combining planning with constraint logic programming....
热门文档