Soft concurrent constraint programming

SoftConcurrentConstraintProgrammingStefanoBistarelliIstitutodiInformaticaeTelematica,C.N.R.,Pisa,ItalyDipartimentodiScienze,Universit´adegliStudi“G.D’Annunzio”,Pescara,italyandUgoMontanariDipartimentodiInformatica,Universit`adiPisa,ItalyandFrancescaRossiDipartimentodiMatematicaPuraedApplicata,Universit`adiPadova,Italy.Softconstraintsextendclassicalconstraintstorepresentmultipleconsistencylevels,andthusprovideawaytoexpresspreferences,fuzziness,anduncertainty.Whiletherearemanysoftconstraintsolvingformalisms,evendistributedones,bynowthereseemstobenoconcurrentprogrammingframeworkwheresoftconstraintscanbehandled.Inthispaperweshowhowtheclassicalconcurrentconstraint(cc)programmingframeworkcanworkwithsoftconstraints,andwealsoproposeanextensionofcclanguageswhichcanusesoftconstraintstopruneanddirectthesearchforasolution.Webelievethatthisnewprogrammingparadigm,calledsoftcc(scc),canbealsoveryusefulinmanyweb-relatedscenarios.Infact,thelanguagelevelallowswebagentstoexpresstheirinteractionandnegotiationprotocols,andalsotoposttheirrequestsintermsofpreferences,andtheunderlyingsoftconstraintsolvercanfindanagreementamongtheagentseveniftheirrequestsareincompatible.CategoriesandSubjectDescriptors:D.1.3[ProgrammingTechniques]:ConcurrentProgram-ming—Distributedprogramming;D.3.1[ProgrammingLanguages]:FormalDefinitionsandTheory—Semantics;Syntax;D.3.2[ProgrammingLanguages]:LanguageClassifications—Concurrent,distributed,andparallellanguages;Constraintandlogiclanguages;D.3.3[Pro-grammingLanguages]:LanguageConstructsandFeatures—Concurrentprogrammingstruc-tures;Constraints;F.3.2[LogicsandMeaningsofPrograms]:SemanticsofProgrammingLanguages—OperationalsemanticsGeneralTerms:LanguagesAdditionalKeyWordsandPhrases:constraints,softconstraints,concurrentconstraintprogram-ming1.INTRODUCTIONTheconcurrentconstraint(cc)paradigm[Saraswat1993]isaveryinterestingcom-putationalframeworkwhichmergestogetherconstraintsolvingandconcurrency.ResearchsupportedinpartbytheItalianMIURProjectscometa,coverandnapoliandbyASIprojectARISCOM.Permissiontomakedigital/hardcopyofallorpartofthismaterialwithoutfeeforpersonalorclassroomuseprovidedthatthecopiesarenotmadeordistributedforprofitorcommercialadvantage,theACMcopyright/servernotice,thetitleofthepublication,anditsdateappear,andnoticeisgiventhatcopyingisbypermissionoftheACM,Inc.Tocopyotherwise,torepublish,topostonservers,ortoredistributetolistsrequirespriorspecificpermissionand/orafee.c2004ACM1529-3785/2004/0700-0001$5.00ACMTransactionsonComputationalLogic,Vol.V,No.N,June2004,Pages1–27.2·StefanoBistarellietal.Themainideaistochooseaconstraintsystemanduseconstraintstomodelcom-municationandsynchronizationamongconcurrentagents.Untilnow,constraintsinccwerecrisp,inthesensethattheycouldonlybesat-isfiedorviolated.Recently,theclassicalideaofcrispconstraintshasbeenshowntobetooweaktorepresentrealproblemsandabigefforthasbeendonetowardtheuseofsoftconstraints[FreuderandWallace1992;Duboisetal.1993;Rut-tkay1994;FargierandLang1993;Schiexetal.1995;Bistarellietal.1997;2001;Bistarelli2001],whichcanhavemorethanonelevelofconsistency.Manyreal-lifesituationsare,infact,easilydescribedviaconstraintsabletostatethenecessaryrequirementsoftheproblems.However,usuallysuchrequirementsarenothard,andcouldbemorefaithfullyrepresentedaspreferences,whichshouldpreferablybesatisfiedbutnotnecessarily.Also,inreallife,weareoftenchallengedwithover-constrainedproblems,whichdonothaveanysolution,andthisalsoleadstotheuseofpreferencesoringeneralofsoftconstraintsratherthanclassicalconstraints.Generallyspeaking,asoftconstraintisjustaclassicalconstraintplusawaytoassociate,eithertotheentireconstraintortoeachassignmentofitsvariables,acertainelement,whichisusuallyinterpretedasalevelofpreferenceorimportance.Suchlevelsareusuallyordered,andtheorderreflectstheideathatsomelevelsarebetterthanothers.Moreover,onehasalsotosay,viasuitablecombinationopera-tors,howtoobtainthelevelofpreferenceofaglobalsolutionfromthepreferencesintheconstraints.Manyformalismshavebeendevelopedtodescribeoneormoreclassesofsoftconstraints.ForinstanceconsiderfuzzyCSPs[Duboisetal.1993;Ruttkay1994],wherecrispconstraintsareextendedwithalevelofpreferencerepresentedbyarealnumberbetween0and1,orprobabilisticCSPs[FargierandLang1993],wheretheprobabilitytobeintherealproblemisassignedtoeachconstraint.Someotherexamplesarepartial[FreuderandWallace1992]orvaluedCSPs[Schiexetal.1995],whereapreferenceisassignedtoeachconstraint,inordertosatisfyasmanyconstraintsaspossible,andthushandlealsooverconstrainedproblems.Wethinkthatmanynetwork-relatedproblemcouldberepresentedandsolvedbyusingsoftconstraints.Moreover,thepossibilitytouseaconcurrentlanguageontopofasoftconstraintsystem,couldleadtothebirthofnewprotocolswithanembeddedconstraintsatisfactionandoptimizationframework.Inparticular,theconstraintscouldberelatedtoaquantitytobemini-mized/maximizedbuttheycouldalsosatisfypolicyrequirementsgivenforperfor-manceoradministrativereasons.ThisleadstochangetheideaofQoSinroutingandtospeakofconstraint-basedrouting[Awducheetal.1999;Clark1989;JainandSun2000;C