Fast algebraic methods for interval constraint pro

FastAlgebraicMethodsforIntervalConstraintProblemsPeterB.LadkinUniversitatBielefeldTechnischeFakultatPostfach100131D-33501Bielefeld,[e-mail]rbornCenterforParallelComputingFurstenallee7D-33095Paderborn,[e-mail]21August1996AninvitedpapertoappearintheAnnalsofMathematicsandArticialIntelligenceAbstractWedescribeaneectivegenericmethodforsolvingconstraintproblems,basedonTarski’srelationalgebra,usingpath-consistencyasapruningtechnique.Weinvestigatetheperformanceofthismethodonintervalconstraintproblems.Timeperformanceisaectedstronglybythepath-consistencycalculations,whichinvolvethecalculationofcompositionsofrelations.Weinvestigatevariousmethodsoftuningcompositioncalculations,andalsopath-consistencycomputations.Spaceperformanceisaectedbythebranchingfactorduringsearch.Reducingthisbranchingfactordependsontheexistenceof‘nice’subclassesoftheconstraintdomain.Finally,wesurveythestatisticsofconsistencypropertiesofintervalconstraintproblems.Problemsofupto500variablesmaybesolvedinexpectedcubictime.Evidenceispresentedthatthe‘phasetransition’occursintherange6n:c15,wherenisthenumberofvariables,andcistheratioofnon-trivialconstraintstopossibleconstraints.1IntroductionConstraintsatisfactionproblems,orCSPs[Mac87]areaformoflogicprogramming(seeSection2),andareusuallysolvedbyvarioustunedsearchmethodsthroughtuplesofvalues(e.g.[Gus89]).Intervalconstraintsformaparticularclassofconstraintproblemsthatprimafaciemaynotbesolvedusingthesemethods,sincethedomainsoftherelationsareinnite.IntervalconstraintproblemsarefoundinplanningandschedulinginAI,andsolvingsuchproblemsisessentialforthemixedqualitative-quantitativeproblemsstudiedin[KL91].Allenoriginallyshowedhowtousesearch-pruningtechniquesbasedonpath-consistency,performedassymboliccomputationswiththeconstraintrelationsthemselvesratherthanontuplesofvalues[All83],andlaterresearchhasbuiltonthisinsight(e.g.[Lad90]containsasurveyofworkto1989,andsee[vB92]formorerecentwork).LadkinandMadduxshowedthattherelationalgebraofTarskiisanappropriatemath-ematicalcontextinwhichtorepresentandsolvebinaryconstraintproblems[LM88,LM94].AnalgebraofrelationsisasetofbinaryrelationsclosedundertheBooleanoperations(i.e.formingaBooleanalgebra),withtheadditionaloperationsofcompositionandconverse,andThispaperisanextendedversionof[LR93],includingresultstodate.1containinganidentityrelation(analgebraicidentityelementforthecompositionoperation).Alltheseoperationsareusedinconstraintsatisfactiontechniquesforbinaryconstraints.Sections2and3areanintroductiontothissymbolicapproachtoconstraintsatisfactionproblems.Everynitealgebraofrelationscontainsacollectionofminimalnon-emptyre-lations,calledatomsoratomicrelations,suchthateveryrelationinthealgebramaybeexpressedasasumofatoms.Wepresentageneralalgorithmarchitectureinwhichconstraintproblemsovervariousdomainsmaybesolvedsymbolically(Figure12).Ourdesignreliesonhighly-prunedsearch,andissuitableforNP-hardconstraintproblemsinwhichsearchisacomponentofasolutionalgorithm.Path-consistencypreprocessingisused,followedbyasearchwhichinvolvespath-consistencypruningateachchoicepoint.OurdesignmaybeusedwhenthereisaclassofconstraintrelationsCsuchthat(a)thecompositiontableformembersofCmaybestoredandaccessedeciently;(b)thereisanecient1methodforsolvingproblemswhoseconstraintsareallinC;(c)allconstraintrelationsintheproblemdomainmayberepresentedasunionsofmembersofC.Thelastcondition(c)entailsthattheatomicrelationsaremembersofC,andsoifconditions(a)and(b)holdfortheatomicrelations,theyformtheminimalclassCforwhich(a)-(c)hold.Ouralgorithmtakesasinputaconstraintprobleminthedomain,andreturnsamorerestrictedprobleminwhichallconstraintsarerelationsinCthatarepotentiallytighterthantheoriginals.OnemaythenapplytheC-constraint-solver(condition(b))tocompletethesolution.AlthoughC=atomicrelationswillworkifanyclassCdoes,itispreferabletochooseclassCaslargeaspossiblesatisfying(a)-(c),toreducethebranchingfactorinsearchandtoreducethetimetakenincalculationsofcompositions(seebelow).Intervalconstraintproblemstthisparadigm,asdovariousspatialreasoningmethods(seeRecentRelatedWorkbelow).SolvingintervalconstraintproblemsisNP-complete[VKvB89,Mad94],sosomesearchmustbeexpectedinasolutionalgorithm(unlessP=NP).Thereare13atoms(atomicrelations)intheIntervalAlgebra,givingacompositiontableof169entries(144entriesareactuallyusedsinceoneoftheatomsisanidentityforcomposition);andproblemswithatomicconstraintsmaybesolveddeterministicallyinquadratictime.ThereisalsoalargerclassCwith187members,namelythepointisablerelations,fulllingconditions(a){(c)(seeSection2foradenitionofpointisable).HencewecancompareperformanceofthealgorithmdesignwithC=atomswiththatofC=pointisables.Thepointisablerelationswereintroducedindependentlyin[LM88]andin[vBC89].Aquadratictimealgorithmforsolvingintervalproblemswitheitheratomicconstraintsorpointisableconstraintsmaybederivedfrom[vB90].NebelandBurckertdiscoveredthemaximalsubclassfulllingconditions(a){(c),calledtheORD-Hornrelations[NB95].Thereare868ORD-Ho