A PErsonalized Tourist INformation Advisor is presented,

USINGALOGICPROGRAMMINGAPPROACH

PanagiotisStamatopoulosIsamboKaraliConstantinHalatsis

UniversityofAthens,DepartmentofInformatics

Abstract

APErsonalizedTouristINformationAdvisorispresented,calledPETINA,whichisasystemaimingatconstructingtoursthatsatisfyconstraintsspecifiedbytourists.Thesys-temconsultsadatabasewhichcontainsinformationaboutactivities,eventsandsitesthatrefertoGreece.PETINAtakesasinputuserwishesabouttourgenerationexpressedasconstraintsovervisits’propertiesanditsoutputistourssatisfyingtheseconstraints.Theuserwishesmaybestatedusingeitheraformallanguageoragraphicalinterface.Themethodofcomputationappliestoanyproblemdomain,incasetheprobleminvolvescombinatorialsearchingundersomekindsofconstraintsthatcanbeclassifiedintosomewelldefinedcategories.Althoughalogicprogrammingapproachissuitableandvaluablefortheformulationofcombinatorialsearchproblems,conventionalPrologsys-temsfailtocopewiththemefficiently.PETINAhasbeenimplementedintheElipSyslanguage,whichisaparallellogicprogrammingsystemextendedwithvariouspowerfulmechanismstoallowefficientexecution.MostoftheElip-Sys’featureswereprovedtobeindispensableforhandlingthecomplexityoftheencounteredproblems.

Keywords

combinatorialsearch,tourconstruction,parallellogicpro-gramming,constraintsatisfaction,datadrivencomputationIntroduction

Combinatorialsearchproblemsarecomputationallyinten-sive,especiallyiftheyaddressasignificantlylargesearchspace.Unfortunately,nogeneralandefficientalgorithmexiststosolvethem.Manycombinatorialsearchproblems

involveuserdefinedconstraintsovertheirsearchspace,sothestraightforwardandclassicalmethodtocopewiththemistoemploythetraditionalgenerate-and-testmethod.Thedeclarativeformulationofthismethodcanbeachievedinalogicprogrammingenvironment,viatheProloglanguage[3,19].However,duetotheinefficiencyoftheexhaustivesearchofProlog,real-lifeproblemscannotbesolvedinthisbasicframework.

Inthispaper,aspecificcombinatorialsearchproblemispresented.TheapplicationthatexemplifiestheproblemiscalledPETINA[6,7,18],whichisaPErsonalizedTouristINformationAdvisoraboutGreece.Itspurposeistocon-structtoursthatsatisfyconstraintsspecifiedbytourists.Al-thoughPETINAreferstoGreece,thesystemisgenericandcanbeusedasatouristinformationadvisorforanycountry.Aparallellogicprogramminglanguage,ElipSys[1],isusedfortheimplementationofPETINA.ElipSysprovides,apartfromvariouskindsofparallelism,suchasOR-parallelism,AND-parallelismanddata-parallelism,otheradditionalfea-tureswhichareexploitedtoattacktheencounteredprob-lemsandtomaketheapplicationusefulinareal-worlden-vironment.Thesefeaturesconsistoftheintroductionofadatadrivencomputationruleontopoftheusualdepth-firstleft-to-rightexecutionstrategyofPrologandtheincorpora-tionofconstraintsatisfactiontechniquesoverfinitedomainsintothelanguage.AnotherusefulfacilitythatElipSyspro-videsisitsextensionwiththeappropriatetoolswhichfa-cilitatethedevelopmentofgraphicaluserinterfaces.BothPETINAandElipSysweredevelopedinthecontextoftheESPRITIIEDS(EuropeanDeclarativeSystem)projectbytheUniversityofAthensandECRCrespectively.Thepreviousworkinthetourgenerationproblemdomaincomprisestwoprototypes,namelyTIA[11]andTInA[12],whichwereimplementedinthePEPSysparallellogicpro-gramminglanguage[16].AlthoughtheseprototypeshadtodealwithsimilarproblemstotheonesofPETINA,theycannotbeconsideredasreal-lifeapplications,sincetheyaddressedlimitedamountofdata.Moreover,theex-

tendeddatabasestructureandtheadvancedfunctionalityofPETINA,withrespecttotheonesofTIAandTInA,requiremorepowerbytheunderlyingimplementationframeworkthantheoneofPEPSys’parallelexecution.

Inthefollowing,abriefdescriptionoftheElipSyslan-guageisgivenaswellasPETINA’sdatabasestructure,thefunctionalityofthesystem’stourgenerationfacilityandthestructuralspecificationofthewholeapplicationarepre-sented.EmphasisisputonthemethodemployedbytheTourGenerationEngineinconjunctionwiththeexploitedElipSysfeatures.Finally,implementationissuesaredis-cussedandperformancemeasurementsarepresented.

ElipSysLanguage

ElipSys[1]isaparallellogicprogramminglanguage,whichhasbeenextendedtoincorporatevariouspowerfulexecu-tionmechanisms.ThelanguagesupportsOR-parallelism,AND-parallelism,data-parallelism,datadrivencomputa-tion,constraintsatisfactiontechniquesoverfinitedomainsandafacilityforthedevelopmentofuserinterfaces.Elip-SyshasgreatlybenefitedbytheMegalog[2],CHIP[4]andPEPSys[16]projectsofECRC.

OR-parallelismaimsattheconcurrentexplorationofthevariousalternativeclausesthatdefineanElipSysprocedure.Theprogrammerhastodeclare“goodpoints”forefficientOR-parallelexecution.Ifthereareavailableresources,thatisprocessingelements,abranchpointiscreatedwithfer-tilityequaltothenumberofalternativeclauses.

AND-parallelismresultsfromtheconcurrentexecutionoftwogoalsinconjunction.ThisfeatureisnotprovidedbytheElipSysexecutionmodel,neitheritissupportedbytheruntimeenvironmentofthelanguage.Itresidesonlyatthelan-guagelevelandisactuallycompiledintoOR-parallelism.Data-parallelism[8]isakindofparallelismarisingfromtheconcurrenttreatmentoftheelementsofasetofdata.Itissupportedbyvariousbuilt-inpredicates.Ifthereareavailableresources,abranchpointiscreatedwithfertilityequaltothenumberoftheelementsintheset.

Inaddition,ElipSyssupportsadatadrivencomputationrule[15]ontopoftheusualdepth-firstleft-to-rightexecutionstrategyofProlog.Thisrulemodifiesthereductionorderofgoalsaccordingtoinstantiationsofvariablesbydeclaringthateverygoalthatreferstoaspecificpredicatehastobedelayed,ifitsargumentsarenotadequatelyinstantiated.Adelayedgoalisawakenedwhenthedesirabledegreeofinstantiationisachieved.

Constraintsatisfactiontechniquesoverfinitedomains[20]leadtoaprioripruningofthesearchspaceandthus,theyresultinmoreoptimizedexecution.ElipSysprovidesthisfacility[21]byallowingtheprogrammertodefinedomain

variableswhichmayrangeoverintegerintervalsorenu-meratedsetsandtouseasetofbuilt-inconstraintsonthesevariables.Afterstatingtheconstraintsthatdescribeaprob-lem,thegenerationofvaluesforthedomainvariablesmustbetriggered,viatheappropriatebuilt-inpredicates,inor-dertostarttheconstraintpropagationandthepruningofthesearchspace.Inaddition,theconstraintsatisfactionmech-anismofElipSyssupportsasetofhigherorderpredicatesusefulforoptimizationproblems.

Finally,anotherfeatureofElipSysconcernsanobjectori-entedextension,namedPCE[13],whichwasdevelopedindependentlyfromthelanguage.PCEallowstocreateX-windowbaseduserinterfaceseasilyandquickly.Itprovidesasetofbuilt-inclassesand,ingeneral,asmallamountofElipSyscodesufficestoadaptthebuilt-infacilitiestoaparticularapplication.

PETINA’sDatabase

ThePETINAsystemconsultsadatabase,implementedasasetofElipSysfacts,thatcontainsinformationaboutac-tivities,eventsandsites.Activitiesareconsideredtobethetourist’svisitstovariousspots,whileeventsareshowsthatmaybeattended.Inaddition,thesitesrefertothegeographicalentitiesofGreece.

Threedatastructuresaredefinedinthesystem’sdatabase,namelytheactivitytree,theeventtreeandthesitetree.However,themainpartofthedatabaseconsistsoftheac-tivityandeventinstancesaswellasthesiteones.Everyinstanceisidentifiedbyauniquekeyvalue.Theactivityandeventinstancesarelinkedtonodesofthecorrespond-ingtrees.Ontheotherhand,thesiteinstancesthemselvescomposethesitetree.Theactivity,eventandsiteinstancesarecharacterizedbytheirattributes.

Thenodesoftheactivitytreerepresentactivitycategories.Thetreeorganizationisbasedoninteresthierarchyandthenodesofapartofthetreeareconsideredasinterestnodes,intermsofwhichspecificinterestsmaybeexpressed.Ac-tivitycategorieswhoseinstanceshavevariouskindsofin-terestarerepresentedbymorethanonetreenodes,de-notedwiththesamekeywordbutwithdifferentindices.Inthisway,agraphideaisimplementedwithatreestruc-ture.Inordertorefertoanactivitycategoryregardlessoftypeofinterest,avariablemaybeusedinplaceofthein-dex,e.g.representsallthe“museum”nodesoftheactivitytree,i.e.1,2,,

7.

Activityinstancescanbelinkedtomorethanonenodesaccordingtothecategoriestheybelongtoandaccordingtothetypesofinteresttheypresent.Eachtypeofinterestcorrespondstoaninterestnode.Anactivityinstanceislinkedeitherdirectlyorindirectlytoall,andonlythese,interestnodesthatcorrespondtothetypesofinterestit

presents.

Anactivityinstanceischaracterizedbyitsattributes,namelythesite,thedenomination,theduration,thecost,thetimeperiod,thecloseddays,theinterestandthedetail.Theinterestattributeisaspecialoneinthesensethatitcollectsasmanyvaluesasthetypesofinteresttheinstancepresents.

Similarapproacheshavebeenfollowedfortheeventandthesiteinformation.

FunctionalityofPETINA

PETINAtakesasinputuserwishesabouttourgeneration,namedtourgenerationrequests,expressedasconstraintsovervisits’properties.Itsoutputistourssatisfyingtheuser’sconstraints,assetsofactivityinstancesorassetsofeventinstances.Theuserisalsoallowedtoaskforinformationaboutactivities,eventsandsitesviainforma-tionretrievalqueries.Finally,managementofPETINA’sdatabaseissuppliedbythesystemthroughdatabasead-ministrationcommands.Theabovethreekindsofrequestsmaybeexpressedusingaformallanguageclose,however,tonaturallanguage.ThislanguageisdefinedbyaDefiniteClauseGrammar(DCG)[14]whichoffersthepossibilitytohandlecontextsensitivity,transformationoftheinputandprocedurecalls.Moreover,agraphicalinterfaceisprovidedthathelpstheusertoformulatetherequests.Inthiscase,theuserdoesnotneedtoknowanythingaboutPETINA’sformallanguage.

Therestofthissectionisdevotedtothetourgenerationre-questsgivingageneraldescriptionoftheconstraintsofthelanguageandpresentingthefunctionalityofthegraphicalinterface,asfarasthetourgenerationfacilityofthesystemisconcerned.

Therearetwokindsoftoursthatthesystemproduces.Con-sequently,therearetwokindsoftourgenerationrequeststheusermayexpress.Theoneconcernstheactivitytourgenerationandtheothertheeventtourgeneration.Inbothcases,atthebeginningoftherequest,theuserhastogiveatimeconstraintconcerningthetimeperiodwhenthevisitisgoingtotakeplace,inordertoavoidvisitingspotsthatareinactive.Theotherpartoftherequestisasetofactivityconstraintsorasetofeventconstraints.Theanswertoatourgenerationrequestconsistsofthetourswhichsatisfyalltheconstraintsoftherequest.

Atimeconstraintissatisfiedbyatour,ifthetimeperiodattributeofeveryinstancethatbelongstothetourhasanonemptyintersectionwiththevisitperioddefinedinthetimeconstraint.Anexampleofatimeconstraintisthefollowing:

visitperiodis20Jul92-10Sep92

Anactivityoreventconstraintmaybeeithersimpleorcross.Asimpleconstrainthasthegeneralform

for

andissatisfiedbyatourincase

holdsforthe

.

Themaybelocal,global,topologicalorcom-plex.Thelatterinvolvestheoperators“and”,“or”and“not”appliedtothefirstthreekindsofconditions.Localconditionsrefertoeveryinstanceoftheindi-vidually.Theyinvolveanattributeexpression,i.e.eitheranarithmeticexpressionofattributesorasingleattribute.

Globalconditionsrefertotheentire

asawhole.Theyinvolveanaggregatefunction(“sum”,“avg”,“max”,“min”)appliedtoanattributeexpression.Topologicalcon-ditionsrefertothenumberofinstancesinthe.Inthiscase,thekeyword“number”isused.

Asimpleconstraintmaybelocal,globalortopologicalifitsislocal,globalortopologicalrespectively.Incaseacomplexconditionappearsinasimpleconstraint,theconditionistransformedintoconjunctivenormalform.Then,theoriginalconstraintissubstitutedbyoneormoreconstraintswhoseconditionsaretheand-operandsofthenormalform.Ifanand-operandinvolvesonlylocalcondi-tions,thecorrespondingconstraintislocal.Thesameholdsforglobalandtopologicalconditions.Otherwise,ifnosuchclassificationcanbedone,theconstraintiscalledmixed.

Asfarasthe

partofasimpleconstraintiscon-cerned,thisisdefinedintermsofoneormoretreenodes,possiblyrefinedbythesocalledwhere-propertiesbyusingthekeyword“where”.Incaseofanactivityconstraint,anentirecategory(setofactivitynodes)maybereferencedorasingleactivitynodebyusingthe“with”specifier.

Thefollowingareexamplesofsimpleactivityconstraints:1.duration*interest>=600

forplant(localconstraint)2.max(religiousplaceinterest)>=7forbuildingwitharchitecturalplaceinterest(globalconstraint)3.number=1forpicturesquespotwhereinterest>5(topologicalconstraint)4.min(cost)=<300orduration>180forholidayresort(mixedconstraint)Intheordertheyappear,eachofthepreviousconstraintsis

satisfiedbyatourif:

1.Consideringthesubtourofthetourthatcontainstheinstanceswhicharefinallylinkedtoanodeoftheform

,foreveryinstanceinthesubtour,theprod-uctofitsdurationanditsinterestattributesisgreaterthanorequalto600.

2.Consideringthesubtourofthetourthatcontains

theinstanceswhicharefinallylinkedtothenode

2,themaximumvalueofthereligiousplace

interestattributesoftheinstancesinthesubtourisgreaterthanorequalto7.

3.Consideringthesubtourofthetourthatcontainstheinstanceswhicharefinallylinkedtoanodeofthe

form

andhaveinterestattributegreaterthan5,thissubtourcomprisesonly1instance.

4.Consideringthesubtourofthetourthatcontainstheinstanceswhicharefinallylinkedtoanodeoftheform,eithertheminimumvalueofthecostattributesoftheinstancesinthesubtourislessthanorequalto300orforeveryinstanceinthesubtour,itsdurationattributeisgreaterthan180.

Apartfromtheusualcomparisonsoperators,the“in”andbetween”operatorsmaybeusedaswell,whichactuallyintroducecomplexconditions.

Asalreadymentioned,therearecrossconstraintsaswell.Acrossconstrainthasthegeneralform

1

for

1

2

for

2

where1and2areeitheraggregatefunctionsappliedtoattributeexpressionsorthekeyword“number”.Thisconstraintissatisfiedbyatourifthecumulativeprop-erty1of1isrelatedwiththecumulativeproperty2of2viathecomparisonoper-ator.Accordingtothekindofthecumulativeproperties,acrossconstraintmaybeglobalortopological.

Thefollowingareexamplesofcrossactivityconstraints:1.sum(cost)forancienthistory

place=numberfornature(topologicalconstraint)Eachofthepreviousconstraintsissatisfiedbyatourif:1.Consideringthesubtourofthetourthatcontainstheinstanceswhicharefinallylinkedtoanodeoftheform

andthesubtourofthetour

thatcontainstheinstanceswhicharefinallylinkedtoanodeoftheform,the

totalcostoftheinstancesinthefirstsubtourislessthanorequaltothetotalcostoftheinstancesinthesecondsubtour.

2.Consideringthesubtourofthetourthatcontainsthein-stanceswhicharefinallylinkedtoanodeoftheform

andthesubtourof

thetourthatcontainstheinstanceswhicharefinallylinkedtoanodeoftheform,thefirstsub-tourcomprisesmoreinstancesthanthesecondone.

Sincemostusersarenotwillingtolearnanduseafor-mallanguageandinPETINA’scasetheusermaybeevenatourist,agraphicalinterfacehasbeenalsodeveloped,usingthePCEextensionofElipSys,thatprovidesauserfriendlywaytoaccessthesystem.Thisinterfaceisde-signedinsuchawaythattheusercomposestherequestviaapointingdevice(mouse)andwithaminimumuseofthekeyboard.Menusandbuttonsareusedextensively,inordertominimizethepossibilityoferroneousinputs.AsfarasthetourgenerationfacilityofPETINAiscon-cerned,thegraphicalinterfacefirstlyaskstheuseraboutthechoicebetweenactivityoreventtourgeneration.Then,atimeconstraintisrequestedinauserfriendlyway.Next,theinterfaceaskstheusertogiveeitherasimpleoracrosscon-straint.Incaseofasimpleconstraint,thepart

ofitisrequested.Theentryprocedureofthe

partoftheconstraintfollows.Finally,theuserisaskedwhetherhe/shewantstogiveawhere-propertyforthe.Theprocedureforgivinganactivityoreventconstraintac-cordinglyisrepeateduntilnomoreconstraintsaredesiredbytheuser.Inthecaseofcrossconstraints,similarfunc-tionalityisprovidedbytheinterface.

PETINA’sStructuralSpecification

PETINAisaclearlymodularizedsystem.ThemodulesitconsistsofaretheUserInterface,theLanguageAnalyzer,theTourGenerationEngine,theInformationRetrievalEn-gineandtheDatabaseAdministrationEngine.TheUserInterfacemoduleisresponsiblefortheuser-systemcommu-nication.IttakesasinputagraphicallystatedrequestandproducesthecorrespondingsentenceofPETINA’sformallanguage.TheLanguageAnalyzertransformstheinputre-questexpressedinPETINA’sformallanguageintoaformsuitableforfurtherprocessing.TheTourGenerationEn-gine,themostimportantmoduleofthesystem,generatesactivityandeventtourssatisfyingtheuser’sconstraints.TheInformationRetrievalEnginesuppliestheinformationtheuseraskedfor.Finally,theDatabaseAdministrationEnginemanagesthedatabasecontents.NoneoftheabovemodulesneedsanychangeincaseadifferentcountrythanGreeceistobeconsidered.

TheLanguageAnalyzerisfurtherrefinedintotheTokenizerandtheParser.TheTokenizertransformstheinputrequest

intoalistoftokens.ThislistisrecognizedbytheParser,inordertoproducetheformalrepresentationoftherequest.ThispaperconcentratesontheTourGenerationEngine(TGE)moduleofthesystem,asithasthemostcomplexproblemtosolveandvariousmechanismsarerequired.TheTGEconsistsoftheDomainsCreator,theConfigurator,theDatabaseFilter,theTourGeneratorandtheTourEvalua-tor.Thefunctionalityofthesesubmodulesaswellasthemethodemployedbyeachonearepresentedinthefollow-ingsection.

MethodofComputationinTGE

SomeofthesubmodulesofTGEdealwithextremelycum-bersometasks.TheTourGeneratorinvolvesacombinato-rialsearchproblemoveralargespace.TheConfiguratorhastosolveasystemofequalitiesandinequalities.More-over,theDatabaseFilterhastohandlealargeamountofdata.

Takingintoconsiderationtheabove,amethodologythatsolvesthevariousencounteredproblemsinasystematicwayisemployed.Thismethodologyisageneraloneandcanbeappliedtoallproblemsthatinvolvecombinatorialsearchingunderconstraintsthatfallintothepresentedgen-eralcategories.TheapproachtakenforeverysubmoduleofTGE,ispresentedinthefollowing.

Firstly,theDomainsCreatorpartitionstheactivityoreventtree,dependingonthetypeoftherequest,intodomains.Thispartitioningisbasedonglobalandtopologicalcon-straints,bothsimpleandcross,aswellasonthemixedones,insuchawaythatnotwodomainshavethesamesetofglobal,topologicalormixedconstraintsappliedtothem.Eachdomainisfurtherpartitionedintofinedomains,ac-cordingtothelocalconstraints.ThepartitioningiscarriedoutbytheDomainsCreatorinthefollowingway.Startingfromtherootoftherelevanttree,eitheractivityorevent,allthenodesarevisitedinadepth-firstleft-to-rightfashion.Duringeachvisit,theconstraintsthatapplydirectlytothenodeareconsideredaswellastheoneswhichareinheritedfromtheancestornodes.Thewholesetofconstraintsthatapplytothenodeisthecriterionforembeddingthenodeintoafinedomainand,consequently,intoadomain.TheConfiguratorproducesallpossibleconfigurationsoftherequestedtours.Aconfigurationrepresentsacceptablenum-bersofinstancesperdomaininatoursatisfyingtheuser’sconstraints.Thismodule,takingintoaccountthesimpleandcrosstopologicalconstraints,generatesandsolvesasystemoflinearequalitiesandinequalities.Thesolutionofthesystemisachievedbyexploitingtheconstraintsatisfac-tiontechniquesthatElipSysoffers.Firstly,asetofElipSysdomainvariablesisgenerated,eachonecorrespondingtoadomainandrepresentingtheacceptablenumberofin-stancesfromthisdomainintherequestedtour.Then,for

everytopologicalconstraint,alinearequalityorinequalityisformed,whichisstatedasanElipSysconstraint.Finally,thegenerationofvaluesforthecreateddomainvariablesistriggered,whichleadstothecomputationofthesolutionsofthesystemofthelinearequalitiesandinequalities.Eachsolutioncorrespondstoaconfiguration.

Next,theDatabaseFilterselectstheinstances,eitheractiv-ityorevent,accordingtothetypeoftherequest,thatsat-isfythetimeconstraintandtherelevantlocalconstraints.Thesesinstancesareselectedforeverynoderefinedbyitswhere-propertytobuildtheinstancesofafinedomain.Then,suchsetsarestructuredtoformadomain.Finally,foreverydomain,thelistsofinstancescorrespondingtoitsfinedomainsarecombinedintoasinglelistandanydu-plicateinstancesareremoved,leadingtothecompositionofthefiltereddatabase.Duplicateinstancesmayoccurinthecaseofanactivitytourgenerationrequestduetothemultiplelinksoftheactivityinstanceswiththenodesoftheactivitytree.ParallelismisexploitedintheDatabaseFilter.Moreprecisely,therearethreelevelsofexploita-tion,theconcurrentprocessingofdomains,finedomainsandnodesrefinedbytheirwhere-properties.Parallelexe-cutioniscarriedoutduringthepostprocessingphaseofthefiltereddatabaseaswell.Thekindofparallelismencoun-teredisdata-parallelism.

TheTourGeneratoristhemodulewheretheactualtoursareconstructed.Themethodusedfortheconstructionoftoursistest-and-generateimplementedusingthedelaymecha-nismofElipSys.Foreveryconfiguration,eachoneofthesimpleglobal,crossglobalandmixedconstraintsisstated,thoughitisdelayeduntilthesubtoursitappliestobecomeground.Next,thegenerationofinstancesforeverydomainistriggeredextractingthemfromthefiltereddatabase.Dur-ingthisgeneration,aconstraintisactivatedandcheckedassoonasallthesubtoursitinvolvesbecomefullyinstanti-ated.Thetourthatisbeingbuiltisrejected,ifaconstraintisnotsatisfied.Then,eachtourthatiscomputedispro-cessedinordertoflattenitssubtours,checkforpossibleduplicateelementsthatmightappearindifferentdomainsandlexicographicallysortitselements.Possibleduplicatetoursareremovedfromthewholesetoftours.ThemainsourceofparallelismofthewholesystemexistsintheTourGenerator.Firstly,thereistheparallelprocessingofallconfigurationsandsecondly,theselectionofpossiblein-stancestobuildasubtourforthecorrespondingdomaininparallel.Inbothcases,thekindofparallelismisagaindata-parallelism.Thiskindofparallelismisalsoexploitedinthepostprocessingofthegeneratedtours.

Finally,theTourEvaluatorsortsthetoursproducedbytheTourGeneratorindescendingorderaccordingtotheirav-erageinterest.Inaddition,itreplacesthekeyvaluesoftheinstancesbythecorrespondingdenominations.Thequick-sortalgorithmisused,whichisatypicaldivide-and-conquermethod.Thus,AND-parallelismisexploited,asitfitsper-

fectlyinthiscase.

PerformanceMeasurements

ThefirstimplementationofthetourgenerationfacilityofPETINAwascarriedoutinSepiaProlog[17].SepiaisanadvancedsequentialPrologsystem.Amongthevariousfeaturesitoffers,thedelaymechanismwasusedintheTourGeneratoraswellasintheConfigurator,inordertosolvethesystemofequalitiesandinequalitiesbyatest-and-generatemethod.

ThecurrentimplementationhasbeencarriedoutintheElipSysversion0.3[5].Thesubmoduleswhichinvolveparallelism,namelytheDatabaseFilter,theTourGenera-torandtheTourEvaluator,werealsoimplementedinthePEPSyslanguage[16].PEPSysisaparallellogicpro-gramminglanguagethatsupportsOR-andrestrictedAND-parallelism.Thedata-parallelismfacilityofElipSyswassimulatedbythePEPSysOR-parallelism.TheCOKEpre-processor[9,10],thatallowstomeasurethetheoreticalper-formanceofparallelexecutionofPEPSysprograms,wasused.TheSepia,ElipSysandPEPSys/COKEworkwascarriedoutonSUN3/60workstationsunderSunOS4.1.1.Moreover,theElipSysversionoftheimplementationwastestedonaSequentSymmetrymachine,thesharedmem-orymultiprocessorofECRC.Thus,trueparallelexecutionresultswereobtainedaswell.

Theaboveimplementationsgavetheopportunityforcom-paringvariousprogrammingmethodologies.Theperfor-mancegainbyusingthedelaymechanismofElipSysintheTourGeneratorrangedfrom3:1to5:1,fortypicaltourgenerationrequests.Asfarastheuseoftheconstraintsatis-factiontechniquesisconcerned,adramaticalimprovementwasachievedbytheElipSysimplementationoftheConfig-uratorwithrespecttotheoneinSepia.Inmostcases,theperformancegainwasseveralordersofmagnitude.Finally,asmentionedabove,parallelismwasexploitedinthreesubmodules.Foracomplexrequestpresentedin[18],thespeedupachievedbytheDatabaseFilterwas4011(numberofinferences/executiontime),bytheTourGenerator821andbytheTourEvalua-tor746.TheCOKEtoolwasusedtoobtainthesemeasurements.Thistoolassumesthateachgoalexecutesinonetimeunitandunlimitedresources(processors)areavailable.Thegraphsrepresentingthenumberofprocessesvs.executiontimeforthethreesubmodulesarepresentedinFigures1,2and3.

ItisworthwhilementioningthatthequalityofthegraphthatcorrespondstotheTourGenerator,whichisthemostcomputationallyintensivepartofthesystem,isverygood.Theshapeofthisgraphisflatratherthanpeaky,whichmeansthattheexploitationofparallelisminthissubmoduleispromising.Asfarasthegraphsthatcorrespondtothe

200

sesse150corp fo100 rebmu50N00200400600Execution time

Figure1:DatabaseFiltergraph

2000

sesse1500corp fo1000 rebmu500N00100200300400500Execution time

Figure2:TourGeneratorgraph

othertwosubmodulesareconcerned,theirshapesarenotasgoodastheTourGenerator’sone,but,anywaythesesubmodulesmaycontributetotheoverallaccelerationofthesystem.

UsingtheSymmetryasaplatform,thesystemwastestedonatrueparallelmachine,whichprovidedtheopportunitytocheckthedegreeofrealparallelismexploitation.Inordertogetsequentialresults,ElipSyswasusedwithoneworkerandthevarioussubmodulesofthetourgenerationfacil-ityranseparatelyontherequestintoconsideration.Table1presentsthecorrespondingexecutiontimesinCPUseconds.Inaddition,thetotalexecutiontimewascomputed.Paral-lelexecutionresultswereobtainedfortheDatabaseFilter(DF),theTourGenerator(TG)andtheTourEvaluator(TE)submodules,whereparallelismisexploited,usinganum-beroftwotosixworkers.TheCPUtimes(inseconds)ofthelongestprocessesareshowninTable2foreachoftheprevioussubmodules.TheconstantsumoftheCPUtimesforthesequentialsubmodules(Seq),i.e.Tokenizer,Parser,DomainsCreatorandConfigurator,aswellasthetotalexe-

15

sesseco10

rp fo rebm5

uN00100200300Execution time

Figure3:TourEvaluatorgraph

cutionresults,thatistheoneswhicharerelatedtothewholetourgenerationfacility,arealsoshowninTable2,consid-eringanumberoftwotosixworkers.Finally,Table3presentsthespeedupsachievedfortheparallelsubmodulesaswellasthetotalspeedupsofthewholeexecution.TheseresultsarealsographicallypresentedinFigure4.

1w

Tokenizer8.29Parser4.23DomainsCreator18.61Configurator0.55DatabaseFilter23.87TourGenerator0.57TourEvaluator

1.58Total

597.70

Table1:SequentialexecutionresultsontheSymmetry

2w

3w4w5w6wSeq31.6831.6831.6831.6831.68DF12.508.686.625.534.77TG277.61184.33138.40112.3994.59TE1.241.040.900.800.82Total

323.03

225.73

177.60

150.40

131.86

Table2:ParallelexecutionresultsontheSymmetryTocommentontheabove,thetheoreticallygoodresultsobtainedbytheCOKEtoolwereverifiedbythetruepar-allelexecution.TheTourGenerator,wherethebulkof

2w3w4w5w6wDF1.912.753.614.325.00TG1.952.933.914.815.71TE

1.271.521.761.981.93Total

1.85

2.65

3.37

3.97

4.53

Table3:Speedupsforparallelexecution

7

Linear6Database Filter5

Tour GeneratorTour Evaluator4Total321001234567Number of workers

Figure4:Speedupvs.numberofworkers

thecomputationalloadappears,presentsacurvethatap-proximatessignificantlytheideallinearcurve.Asitwasexpected,theoverallspeedupismainlyaffectedbytheoneoftheTourGenerator,thusthecorrespondingcurveisveryclosetotheidealone.ThereasonwhytheTourEvaluatordoesnotseemtopresentgoodspeedupsisthat,forthespe-cificrequest,thissubmodulehastosortjust13tours.So,parallelismisnothighlyexploitableinthiscase.

ConclusionsandFutureWork

Inthispaper,themostsignificantpartofPETINA,thatistheonewhichcarriesoutitstourgenerationfacility,waspresented.PETINAisaPErsonalizedTouristINforma-tionAdvisorconsultingadatabasethatcontainstouristdataaboutGreece.Thus,bychangingthedatabasethesystemcanbeusedforanycountry.

Theproblemoftourgenerationisacombinatorialsearchone,thusadvancedmechanismsarerequiredtocopewithitefficiently.TheElipSysparallellogicprogramminglan-guageisasuitablevehicleinthisdirection,since,apartfromtheparallelexecution,itoffersthepossibilityofdeclarativeformulationoftheproblemaswellasitprovidesvariousextendedfeatures,suchasdatadrivencomputation,con-straintsatisfactiontechniquesandaplatformfordeveloping

Speedupgraphicalinterfaces.

AlthoughPETINA’stourgenerationproblemaddressesalargesearchspace,itwasshownthatElipSysfeatureshelptoattackthecomplexityofthealgorithmsneeded.Par-allelismwashighlyexploitable,asitwasprovedbythepresentedperformancemeasurements.Moreover,thedatadrivencomputationwasfoundusefulandtheconstraintsat-isfactionfacilitiesofElipSyswerefoundindispensable.Fi-nally,PETINA,asitisareal-lifeapplication,providesagraphicalandfriendlywaytoallowcausaluserstoaccessthesystem,exploitingtheappropriatefacilityofferedbyElipSys.

Aninterestingcharacteristicofthesystemisthatthemethodemployedforthetourconstructionisageneraloneandcanbeappliedtoanyproblemdomainwhichinvolvescombi-natorialsearchingunderconstraintsthatfallintosomewelldefinedcategories.

Theobjectiveofthefutureworkinthetourgenerationfa-cilityofPETINAistoreducetheexecutiontimeoftheTourGeneratorthatpresentsthebulkofthecomputationalload.Moreprecisely,amoreprofitableuseofthedelaymecha-nismofElipSysisenvisaged.Alternatively,theconstraintsatisfactiontechniquesmaybeexploitedintotheTourGen-eratoraswell.

Acknowledgements

TheauthorsexpresstheirthankstoECRCGmbH(Munich,Germany),forprovidingaccesstoitsparallelmachineandtheElipSyslanguage.SpecialthanksaredirectedtoMikeReeveandMichaelRatcliffefromECRC,fortheirencour-agement,guidelines,feedbackandvaluablecommentsdur-ingthedevelopmentofPETINAinthecontextoftheEDSproject.

References

[1]U.Baron,S.Bescos,S.Delgado-Rannauro,P.Heuz´e,

M.Dorochevsky,M.-B.Ib´an˜ez-Espiga,K.Schuerman,M.Ratcliffe,A.V´eron,andJ.Xu.TheElipSyslogicprogramminglanguage.TechnicalReportDPS-81,ECRC,December1990.[2]J.Bocca.Megalog—Aplatformfordeveloping

knowledgebasemanagementsystems.InternalRe-portKB-75,ECRC,October1990.[3]W.ClocksinandC.Mellish.ProgramminginProlog.

SpringerVerlag,NewYork,1981.[4]M.Dincbas,P.vanHentenryck,H.Simonis,A.Ag-goun,T.Graf,andF.Berthier.TheconstraintlogicprogramminglanguageCHIP.InInternationalCon-ferenceonFifthGenerationComputerSystems,pages693–702,1988.

[5]ElipSysUserManualforreleaseversion03,October

1991.

[6]C.Halatsis,M.Katzouraki,M.Hatzopoulos,P.Stam-atopoulos,I.Karali,C.Mourlas,M.Gergatsoulis,andE.Pelecanos.PETINA—Implementationofthetourgeneration.ProjectDeliverableEDS.WP.9E.A006,UniversityofAthens,December1991.[7]C.Halatsis,M.Katzouraki,M.Hatzopoulos,P.Stam-atopoulos,I.Karali,C.Mourlas,M.Gergatsoulis,andE.Pelecanos.PETINA—Performanceeval-uationofthetourgeneration.ProjectDeliverableEDS.WP.9E.A007,UniversityofAthens,December1991.[8]P.Heuz´e.UsingData-ParallelismintheElipSys.In-ternalReportElipSys-003,ECRC,June19.[9]P.Heuz´eandB.Ing.COKE:Usermanual1.0.Internal

report,ECRC,February19.[10]B.Ing.COKE—AnanalysistoolforPEPSyspro-grammes.InternalReport23,ECRC,October1987.[11]B.Ing.Touristinformationadvisor:Acasestudyof

anapplicationinPEPSys.InternalReportPEPSys/15,ECRC,April1987.[12]B.Ing.Touristinformationadvisor—Acasestudy

ofanapplicationinPEPSys—Finalreport.InternalReportPEPSys-32,ECRC,September1988.[13]PCEReferenceManual,October1986.

[14]F.PereiraandD.Warren.Definiteclausegrammars

forlanguageanalysis—Asurveyoftheformalismandacomparisonwithaugmentedtransitionnetworks.ArtificialIntelligence,13(3):231–278,1980.[15]M.Ratcliffe.OntheuseofthedelayinElipSysPro-log.TechnicalReportelipsys/001,ECRC,June19.[16]M.RatcliffeandJ.-C.Syre.Aparallellogicprogram-minglanguageforPEPSys.InInternationalJointCon-ferenceonArtificialIntelligence,pages48–55,1987.[17]Sepia3.0UserManual,June1990.

[18]P.Stamatopoulos,I.Karali,andC.Halatsis.PETINA

—TourgenerationusingtheElipSysinferencesys-tem.InProceedingsofthe1992ACM/SIGAPPSym-posiumonAppliedComputing,volume1,pages320–327,1992.[19]L.SterlingandE.Shapiro.TheArtofProlog.MIT

Press,Cambridge,MA,1986.[20]P.vanHentenryck.ConstraintSatisfactioninLogic

Programming.MITPress,19.[21]J.XuandA.V´eron.Typesandconstraintsinthe

parallellogicprogrammingsystemElipSys.TechnicalReportDPS-105,ECRC,March1991.