Title of Publication Encyclopedia of Cognitive Sci

TitleofPublication:EncyclopediaofCognitiveScience.Articletitle:ConstraintSatisfaction.Articlecode:26.Authors:RinaDechterDepartmentofComputerandInformationScienceUniversityofCalifornia,IrvineIrvine,California,USA92717Telephone:[phone]Fax:[phone]E-mail:[e-mail]mentodiMatematicaPuraedApplicataUniversitadiPadovaViaBelzoni7,35131Padova,ItalyTelephone:[phone]Fax:[phone]E-mail:[e-mail]1ConstraintSatisfactionKeywords:Constraints,constraintsatisfaction,constraintpropagation,con-straintprogramming.Contents1Introduction32Constraintpropagation53Constraintsatisfactionassearch74Tractableclasses95Constraintoptimizationandsoftconstraints106Constraintprogramming117Summary13Articledenition:Constraintsareadeclarativeknowledgerepresentationformalismthatallowsforacompactandexpressivemodelingofmanyreal-lifeproblems.Constraintsatisfactionandpropagationtools,aswellasconstraintprogramminglanguages,aresuccessfullyusedtomodel,solve,andreasonaboutmanyclassesofproblems,suchasdesign,diagnosis,scheduling,spatio-temporalreasoning,resourceallocation,conguration,networkoptimization,andgraphicalinterfaces.21IntroductionConstraintsatisfactionproblems.Aconstraintsatisfactionproblem(CSP)consistsofanitesetofvariables,eachassociatedwithadomainofvalues,andasetofconstraints.Eachoftheconstraintisarelation,denedonsomesubsetofthevariables,calleditsscope,denotingtheirlegalcombinationsofvalues.Aswell,constraintscanbedescribedbymathematicalexpressionsorbycomputableprocedures.Solutions.Asolutionisanassignmentofavaluetoeachvariablefromitsdomainsuchthatalltheconstraintsaresatised.Typicalconstraintsatisfactionproblemsaretodeterminewhetherasolutionexists,tondoneorallsolutions,andtondanoptimalsolutionrelativetoagivencostfunction.ExamplesofCSPs.Anexampleofaconstraintsatisfactionproblemisthewell-knownk-colorabilityproblem.Thetaskistocolor,ifpossible,agivengraphwithkcolorsonly,suchthatanytwoadjacentnodeshavedierentcolors.Aconstraintsatisfactionformulationofthisproblemassociatesthenodesofthegraphwithvariables,thepossiblecolorsaretheirdomainsandthenot-equalconstraintsbetweenadjacentnodesaretheconstraintsoftheproblem.Anotherknownconstraintsatisfactionproblemconcernssatisability(SAT),whichisthetaskofndingatruthassignmenttopropositionalvariablessuchthatagivensetofclausesaresatised.Forexample,giventhetwoclauses(A_B_:C);(:A_D),theassignmentoffalsetoA,truetoB,falsetoC,andfalsetoDisasatisfyingtruthvalueassignment.Theconstraintgraph.Thestructureofaconstraintproblemisusuallydepictedbyaconstraintgraphwhosenodesrepresentsthevariables,andanytwonodesareconnectedifthecorrespondingvariablesparticipateinthesameconstraintscope.Inthek-colorabilityformulation,thegraphtobecoloredistheconstraintgraph.IntheSATexampleabove,theconstraintgraphhasAconnectedwithD,andA;BandCareconnectedtoeachother.3Applicationsareas.Constraintproblemshaveprovensuccessfulinmod-elingmundanecognitivetaskssuchasvision,languagecomprehension,de-faultreasoningandabduction,aswellasinapplicationssuchasscheduling,design,diagnosis,andtemporalandspatialreasoning.Thereasonisthatconstraintsallowforanatural,expressiveanddeclarativeformulationofwhathastobesatised,withouttheneedtosayhowithastobesatised.Complexityofconstraint-relatedtasks.Ingeneral,constraintsatis-factiontasks(likendingoneorallsolutions,orthebestsolution)arecom-putationallyintractable(NP-hard).Intuitively,thismean,thatintheworstcaseallthepossiblevariableinstantiationsmayneedtobeconsideredbe-foreasolution(orbestsolution)canbefound.However,therearesometractableclassesofproblemsthatallowforecientsolutionalgorithmsevenintheworst-case.Moreover,alsofornon-tractableclasses,manytechniquesexhibitagoodperformanceinpracticeintheaveragecase.Constraintoptimizationproblems.Constraintprocessingtasksincludenotonlythesatisfactiontask,butalsoconstraintoptimizationproblems.Thisoccurswhenthesolutionsarenotequallypreferred.Thepreferencesamongsolutionscanbeexpressedviaanadditionalcostfunction(alsocalledanobjectivefunction),andthetaskistondabest-costsolutionorarea-sonableapproximationofit.Softconstraints.Thenotionofconstraintoptimizationleadsamoreex-ibleviewofconstraints,whereeachconstraintmayhavealevelofimpor-tance.Inthiscase,wetalkaboutsoftconstraints,whichallowforafaithfulmodelingofmanyapplicationsandcanaccommodateuserpreferencesanduncertaintieswithintheconstraintformalism.TechniquesforsolvingCSPs.Thetechniquesforprocessingconstraintproblemscanberoughlyclassiedintotwomaincategories:searchandcon-sistencyinference(orpropagation).However,suchtechniquescanalsobecombined,and,infact,inpracticeaconstraintprocessingtechniqueusuallycontainsaspectsofbothcategories.Searchalgorithmstraversethespaceofpartialinstantiations,buildingupacompleteinstantiationthatsatisesalltheconstraints,ortheydeterminethattheproblemisinconsistent.In4contrast,consistency-inferencealgorithmsreasonthroughequivalentprob-lems:ateachsteptheymodifythecurrentproblemtomakeitmoreexplicitwithoutloosinganyinformation(thatis,maintainingth