Fast and robust interface generation for ubiquitous applications

FastAndRobustInterfaceGenerationfor

UbiquitousApplications

KrzysztofGajos,DavidChristianson,RaphaelHoffmann,TalShaked,Kiera

Henning,JingJingLong,andDanielS.Weld

UniversityofWashington

Seattle,WA,USA

{kgajos,dbc1,raphelh,tshaked,kierah,jingjing,weld}@cs.washington.edu

http://www.cs.washington.edu/ai/supple/

Abstract.WepresentSupple,anoveltoolkitwhichautomaticallygen-eratesinterfacesforubiquitousapplications.Designersneedonlyspec-ifydeclarativemodelsoftheinterfaceanddesiredhardwaredeviceandSuppleusesdecision-theoreticoptimizationtoautomaticallygenerateaconcreterenderingforthatdevice.Thispaperprovidesanoverviewofoursystemanddescribeskeyextensionsthatbarredthepreviousver-sion(reportedin[3])frompracticalapplication.Specifically,wedescribeafunctionalmodelinglanguagecapableofrepresentingcomplexappli-cations.Weproposeanewadaptationstrategy,splitinterfaces,whichspeedsaccesstocommoninterfacefeatureswithoutdisorientingtheuser.WepresentacustomizationfacilitythatallowsdesignersandenduserstooverrideSupple’sautomaticrenderingdecisions.Wedescribeadis-tributedarchitecturewhichenablescomputationally-impoverishedde-vicestobenefitfromSuppleinterfaces.Finally,wepresentexperimentsandapreliminaryuser-studythatdemonstratethepracticalityofourapproach.

1Introduction

Thegrowthofmobileandubiquitouscomputinghascausedincreaseddepen-danceondigitallyencodedinformationandhasincreasedusers’expectationsofbeingabletoaccess,createandmanipulatedigitalcontentinavarietyofsitua-tions.Asaresultusersfrequentlyrelyondevicesotherthandesktopcomputersfortheirdigitalneeds.Thesedevicesincludemobilephones,PDAs,tabletcom-puters,touchpanels,andincreasinglywall-sizeddisplaysoperatedbyfingerorlaserpointing.Thesedevicesnotonlydifferintheirscreensizeandresolution;theyalsosupportverydiversekindsofinputdevicesandmodesofinteraction.Thesetrendsputanenormouspressureonsoftwaredeveloperstomaketheirproductsavailableforalargenumberofplatforms.Whilethelogicoftheap-plicationmayoftentransfereasilyacrossdifferentplatforms,theuserinterfacestypicallyhavetobedesignedandimplementedfromscratch.Ofcourse,inter-facedesignisalwaystime-consuming,butthereareseveralaspectsofubiquitousapplicationsthatareespeciallychallenging:1)Newkindsofdevicesenterthe

1

2

marketatarapidpace.2)Sinceubiquitouscomputingisayoungfield,thereisasmallertrackrecordofsuccessfulinterfacedesignsandincreasedneedforiter-ativeprototyping.3)Inubiquitouscomputingnewfunctionalityoftenemergesfrominteractionsofspontaneouslyaggregateddevicesandservices[10].

ThispaperdescribesSupple,afastandefficientUItoolkitforubiquitousapplicationswhichaddressestheseissuesbyautomaticallygeneratingaperson-alizedinterfaceforawiderangeofhardwareplatforms.Wearguethatsuchatoolkitshouldsatisfythefiverequirementslistedbelow.

–Easy:Thetoolkitshouldsupportrapidprototypingandbeeasyforapplica-tiondeveloperstouse.Section2explainshowSupple’shigh-levelinterfacerepresentationspeedsdevelopment,andTable2inSection6detailsthecodecomplexityoftheexamplesinthispaper.

–Capable:Thetoolkitshouldhandlecomplexinterfacesandrichdatatypes.Section2describesourexpandedmodelinglanguage,andTable3demon-stratesthatSupplecanrenderreasonablycomplexinterfacesveryquickly.–Adaptive:Generatedinterfacesshouldpossessadaptationandcustomiza-tionfeaturestomakeconvenientoperationbyuserswithwidelyvaryingactivities,stylesandpreferences.However,automatedchangestoaninter-facemustminimizethechanceofuserdisorientation.Section3introducesanovelinterface-adaptationmechanismcalledsplitinterfacesanddescribesapreliminaryuserstudysuggestinguseracceptance.Section4presentsacomplementarycustomizationcapability,whichallowsuserstotailoranySuppleinterfacetotheirdesiresaswellastoundounwantedadaptations.–Portable:Asingleinterfacespecificationshouldenablerenderingthatin-terfaceoneverysupportedhardwareplatform,includingdeviceswhicharecomputationallyimpoverishedandwhichmaynothavenetworkconnectiv-ity.Section2explainshowSuppletakesadevicedescriptionasinputandusesadecision-theoreticoptimizationalgorithmtorenderaninterfacespecif-icallytailoredtothecapabilitiesandconstraintsofthathardwareplatform.Section5describesourdistributedarchitectureandcachinginfrastructure,whichsupportsremoterenderingandwirelessoperation.Section6providespreliminaryperformancedataforoursystem.

–Extensible:Itshouldbeeasytoextendthesetofhardwaredevicessup-portedbythetoolkit.ThemostdifficultaspectofgettingSuppletogenerateinterfacesforanewhardwareplatformisspecifyingthecostmodel[3]forthatdevice’sinteractionmodes.Inthepast,thiswasindeedalaboriouspro-cess,butwehaverecentlydevelopedapreference-elicitationmethodologyandmachine-learningalgorithmwhichquicklygeneratesthesecostmodels.Spaceprecludesadescriptionofourtechnique,butsee[4]fordetailsandexperimentsshowingitsefficacy.

ThenextsectionsummarizesSupple’srenderingalgorithmanddescribesitsextendedmodelinglanguagewhichnowsupportsmorecomplexapplicationsanddatatypesrequiredbyubiquitousapplications.Section3explainsSupple’snovelmethodofsupportingdynamicimprovementstotheUIinamannerwhichdoesn’tdisorienttheuser;apreliminaryuser-studyvalidatestheapproach.Sec-tion4presentsamechanismtoallowadesignertooverridedecisionsmadeby

3

{ , , }Power:boolVolume:X-Bass:boolStereo: { , , , }Tuner:{ , , , }<nilFreq:Seek>>:nil->nilBand:{ , }Mode:Reverse:boolDolby:boolTape:{ , }CD:{ , }{ , }Repeat:boolRandom:boolPlay:nil->nil{ , }Disc:Pause:nil->nilTrack:{ , , , , , }<-Play:nil->nilPlay->:nil->nilStop:nil->nilPause:nil->nilFwd:nil->nilRev:nil->nil{ , , }Stop:nil->nilFig.1.Graphicalrepresentationofthefunctionalspecificationforastereocontroller.Forclarity,differentpartsofthespecificationaregroupedwithgrayshading.

Fig.2.Threetabviewsofthestereospecification,renderedforaPDA.

theautomaticrenderingengine.Section5describesthedistributedarchitecture,whichenablesSuppletorunoncomputationallyimpoverishedplatformssuchasPDAs.Section6presentsexperimentalresults,whichconfirmSupple’sfit-nessasatoolkitforubiquitousapplications.Weendthepaperwithadiscussionofrelatedandfutureresearch.

2OverviewofSupple

Suppletakesthreeinputs:afunctionalspecificationoftheinterface,adevicemodelandausermodel.Thefunctionalspecificationdefinesthetypesofdatathatneedtobeexchangedbetweentheuserandtheapplication(e.g.Figure1).Thedevicemodeldescribeswhichwidgetsareavailableonthedeviceandpro-videsacostfunction,whichestimatestheusereffortrequiredtomanipulatethesewidgetswiththeinteractionmethodssupportedbythedevice.Finally,auser’stypicalactivitiesaremodeledwithadevice-andrendering-independentusertrace.Supple’srenderingalgorithmcombinesconstraintpropagationwithbranch-and-boundsearch,guidedbyanadmissibleheuristic.

4

Fig.3.Aninterfaceutilizingimagesandclickablemaps.

Inthissection,wedescribeSupple’sfunctionalspecificationlanguage,brieflydiscussitsoptimization-basedrenderingalgorithmandprovideanoverviewofitsimplementation,focusingonaspectsnotelucidatedin[3].

2.1FunctionalSpecificationLanguageforInterfaceModeling

Theinterfaceelementsincludedinthefunctionalspecificationcorrespondtounitsofinformationthatneedtobeconveyedviatheinterfacebetweentheuserandthecontrolledapplianceorapplication.Eachelementisdefinedintermsofitstype.Thereareseveralclassesoftypes:

Primitivetypesincludethecommonbasicdatatypessuchasintegers,floats,stringsandbooleans.Asanexample,thepowerswitchforthestereosys-temisrepresentedasaBooleaninthespecificationofFigure1.Theprimitivetypesalsoincludeseveralmorespecializedconstructsthatoftenbenefitfromspecialhandlingbyuserinterfacessuchasdates,times,imagesandclickablemaps.TheselasttwotypesareillustratedinaconcreteinterfaceshowninFig-ure3,whereausercanpointatdifferentofficesonabuildingmap,causingtheoccupant’simagetobedisplayed.

Containertypes,formallyrepresentedas{τ1,τ2,...,τn},areusedtocre-ategroups(orrecords)ofsimplerelements.Forexample,alloftheinteriornodes(e.g.,Tuner,Tape,CD,Stereoortheunnamedintermediatenodes)inthespec-ificationtreeinFigure1areinstancesofthecontainertype.

Constrainedtypes:󰀅τ,Cτ󰀆denotesaconstrainedtype,whereτisanyprimitiveorcontainertypeandCτisasetofconstraintsoverthevaluesofthistype.Inthestereoexample,thevolumeisdefinedasanintegertypewhosevaluesareconstrainedtoliebetween0and10.IntheemailclientshowninFigure4(a)thelistofemailfoldersshownontheleftisrepresentedasaStringwhosevaluesareconstrainedtobethenamesofthefoldersinthecurrentlyselectedemailaccount(noteherethattheconstraintsonthelegalvaluesofanelementcanchangedynamicallyatruntimee.g.,whennewfoldersarecreated).Inmost

5

Fig.4.AnemailclientthatusesSuppletorenderitsuserinterface.(a)Themainview.(b)Theconfigurationpane.

caseselementsoftheconstrainedtypearerenderedasadiscreteselectionwidget(list,combobox,etc)exceptfornumberrangeswherecontinuousselectorssuchasslidersmaybeused.

Constraintscanalsobespecifiedforcontainertypes.Forexample,considerthelistofavailableemailaccountsintheemailexampleofFigure4(b).Eachaccountismodeledasaninstanceofthecontainertype.Yettheuserwantsnotonlytoseethesettingsofasingleaccount,butshealsowantstoselectdifferentaccountstoview.Thus,wemodeltheinterfaceelementrepresentingthecurrentaccountasacontainerobjectwhosedomainofvaluesisrestrictedtoallregisteredemailaccountsforthatuser.WhenSupplerendersthiscontainer,itallowstheusertoselectwhichaccounttoview,andalsodisplaysthataccount’ssettings.Whenenoughscreenspaceisavailable,Supplewillrenderboththeselectionmechanismandthedetailsofthecontentside-by-side,asinFigure4(b).Whenspaceisscarce,Supplewillshowjustthelistofavailableaccounts;inordertoviewtheircontents,theusermustdouble-clickonanelementinthelist,orclicktheexplicit“Details”button.

Whilethisapproachmakesmodelingeasy,itassumesthatalltheobjectsinacontainer’sdomainareofexactlythesametype.Inpractice,thisisnot

6

Fig.5.AsimpleclientforAmazonWebServices.(a)Searchresultswithapaneshowingpropertiesofaselectedobject—onlythosepropertieswhicharecommontoallitemsareshownthere,butthe“MoreDetails”buttonbringsupamorespecializedviewforeachitem.(b)Detailedviewforabook.(c)Detailedviewforadigitalcamera.

alwaysthecase.Forexample,considerFigure5’sinterfacetoAmazonWebServices.Itemsreturnedbysearchmaycomefromanyofseveralcategories,eachofwhichcanhavedifferentattributes.Books,forexample,havetitlesandauthorswhilemanyotheritemsdonot.Toalleviatethisproblem,Suppleallowstheelementsofacontaineroftypeτtobeasubtypeτ󰀁ofτ.1Insuchsituations,ifspacepermits,Supplerendersalltheattributesofthecommonancestortypeτstatically,nexttothechoiceelement(Figure5(a)).Anytimeaspecializedobjectisselectedbytheuser,anotherbuttonishighlighted,alertingtheuserthatmoredetailedinformationisavailable,whichcanbedisplayedinaseparatewindowasinFigures5(b)and(c).

Vectors:elementsoftypevector(󰀅τ,Cτ󰀆)areusedtosupportmultiplese-lection;theydenoteanorderedsequenceofzeroormorevaluesoftypeτ.TheconstraintsCτdefinethesetofvaluesoftypeτthatcanbeselectedfrom.Forexample,thelistofemailsintheemailclient(Figure4(a))isrepresentedasa

1

Asubtypeofacontainertypeiscreatedbyaddingzeroormorenewelements;thesubtypecannotrename,removeorchangetypeoftheelementsdefinedinitsparenttype.

7

Fig.6.Suppleoptimallyusestheavailablespaceandrobustlydegradesthequalityoftherenderedinterfaceifpresentedwithadevicewithasmallerscreensize.Thisfigureshowsthreerenderingsofaclassroomcontrolleronthreedeviceswithprogressivelynarrowerscreens.

vectorofMessageelements,whosevaluesareconstrainedtothemessagesinthecurrentlyselectedfolder;thisallowstheusertoselectandmoveordeleteseveralmessagesatonce.

Actionsaredenotedasτ1→τ2,whereτ1standsforthetypeoftheobjectcontainingparametersoftheaction,whileτ2describesthereturntypei.e.,theinterfacecomponentthatistobedisplayedafterthetypicalexecutionoftheaction.Unliketheothertypeswhichareusedtorepresenttheapplication’sstate,theactiontypeisusedtoinvokethemethods.The“Reply”buttonintherenderingoftheemailclientinterfaceinFigure4(a)isrepresentedasanactionwithanullparametertype(sinceitoperatesonthecurrentmessage)andMessageasthereturntype.TheSearchintheAmazonbrowserexampleinFigure5(a)isanactionwithStringasaparametertypeandanullreturntype.2.2

Algorithm

Unlikepreviousmodel-basedrenderingsystems(e.g.thePersonalUniversalCon-troller[6]),whichusetemplatesorrule-basedapproachestogeneratinguserin-terfaces,Suppleusesdecision-theoretic,combinatorialoptimization.Conceptu-ally,Suppleenumeratesallpossiblewaysoflayingouttheinterfaceandchoosestheonewhichminimizestheuser’sexpectedcostofinteraction.Efficiencyisob-tainedbyusingbranchandboundsearchandanovel,admissibleheuristictoexplorethespaceofcandidaterenderings;fullconstraintpropagationisusedtomaximizethepruningeffectofviolatedconstraints.Severalvariationsonthealgorithmareempiricallyevaluatedin[3].

Supple’suseofacostfunctiontoguidethechoiceofrenderinghasseveraladvantages.Unlikearulesetthatneedstobecreatedbyhand,thecostfunctioncanbequicklyconstructedautomaticallyfromdesigner’sresponsestoexamplesofconcreterenderingsofdifferentinterfaces[4].Furthermore,optimizationisrelativelyrobust,flexiblyhandlingtradeoffsandinteractionsbetweenchoicesindifferentpartsoftheinterface.Incontrast,rule-basedsystemsarefragilebecausesmallchangestodeviceconstraints(e.g.,displaysize)mayrequirea

8

SUPPLEmethod callsmessagesUser ModelSUPPLE SolverDevice ModelApplication or ApplianceDisplay DeviceApplication State and LogicInterface ModelWidget ProxiesConcrete WidgetsFig.7.Supple’simplementation:Theinterfacemodelexposesthestatevariablesandmethodsthatshouldbecomeaccessiblethroughtheinterface.Thewidgetproxiesgen-eratedbythedevicemodelareassignedtointerfacemodelelementsbySupple’sop-timizationalgorithm.

majorchangetotherendering.ArulederivationwhichworkswellononePDAmightfailwhenusedwithaslightlysmallerscreen,sincethecandidateinterfacemightnolongerfit.Conversely,arule-basedsystemwilllikelyfailtoexploitanincreaseinscreensize(ordecreaseininterfacecomplexity)byusingmoreconvenientbutlargerwidgets.Incontrast,Supple’ssearchalgorithmalwaysselectsaninterfacethatisoptimal(withrespecttothecostfunction)foragiveninterfaceanddevicespecification.Figure6illustrateshowSupplerobustlydegradesthequalityofthegenerateduserinterfacesasitispresentedwithdeviceswithprogressivelynarrowerscreens.

2.3Implementation

SuppleiswritteninJavaandisdesignedtointegrateeasilywithexistingappli-cationcode—especiallywithapplicationswhosestateismaintainedinbeans—insuchcasesSuppleautomaticallymaintainstwo-wayconsistencybetweentheinterfaceandapplicationstates.CommunicationbetweenSupple’simple-mentationcomponentsisillustratedinFigure7.UserinterfacesarespecifiedbycreatingUIobjectsforeachpropertyormethodtobeexposedthroughtheinterface.Whenaskedtogenerateaconcreteuserinterface,Suppleproceedsinthefollowingway:

1.Thedevicemodelisengagedtogenerateasetofcandidatewidgetproxies,serializableobjectsthatarecapableofgeneratingaconcretewidget,foreachelementoftheinterfacemodel.

2.Usingcombinatorialsearch,Supplegeneratesthebestassignmentofwidgetproxiestointerfacemodelelementsandestablishestheconnectionsbetweenthem.Ifnecessary,theproxiesmaynowbeserializedforcachingortransporttocomputationally-impoverisheddevices.

3.Thewidgetproxiesaretriggeredtogenerateaconcreteuserinterfaceonthefinaldisplaydevice.Formostapplications,newwindowsordialogboxes(orequivalentelementsonotherplatforms)needtobedisplayedatrun-time.Supplerendersthemdynamicallyasneeded.

9

3AutomaticAdaptationwithoutDisorientation

Automaticallygeneratinginterfacesontheflyopensupthepossibilityofincor-poratingknowledgeabouttheuserandhistasksintothedesignoftheconcreteinterface.OurinitialpaperonSuppleexplainedhowanalysisofausertraceenabledthesystemtoautomaticallyadaptaninterfacetoagivenuser’sworkhabitsbyfullyreplacingonerenderingwithanother[3].Thisapproach,however,couldresultindramaticchangestotheinterfaceandconsequentlydisorienttheuser.Inthissection,wecomparealternativedesignsforadaptiveinterfacesinanexploratoryuserstudy;wethendescribeourimplementationofsplitinterfaces,atechniquewhichreconcilesadaptivitywithpredictability.3.1

ExploratoryUserStudy

Forourstudy,wecomparedfourinterfaces:twotraditionalandtwoadaptivesiblings.Oneofthetraditionalinterfacesorganizedoperationshierarchically,andtheotheruseda“flat”structure,inwhichoperationsarealwaysvisible.Becausethesestructureshavedifferentstrengthsandweaknesses,weconsidereddifferentadaptationmethodsineachcase.

Ahierarchicalinterfaceoffersclearorganization,butmakescertainopera-tionshardertoaccess,soweemployadaptationinanefforttospeedaccesstocommonlyusedfunctionality.Following[13,16,2]weadvocateageneralizationofsplitmenuswhichwecallsplitinterfaces(Figure8(b)).Wepartitionaninter-faceintostaticanddynamicsections.Thestaticportionalwaysmaintainsthesameorganization,whilethedynamicportiondisplaysspeedywaystoinvokecommonlyusedfunctionsthatmightbeotherwisehardtoaccess.NotethatincontrasttoSearsandShneiderman[13],whoremovedrecentlyuseditemsfromtheiroriginallocationswhenorderingthemnearthehead,weproposeduplicatingfunctionalitywhenplacingitinthedynamicportionoftheinterface.

Aflatinterfaceorganizationmakeseveryoperationready-at-hand,butmaypromotesomanyoperations,thattheresultconfusestheuser.Thus,weuseadaptationinanefforttofacilitatenavigation,directingtheusertocommonlyusedoptions.Specifically,wedevelopthenotionofalteredprominence,dynam-icallyhighlightingcommonlyusedkeys(Figure8(d)).

Ourhypothesiswasthatthesplitinterfacewouldbemoreuniversallyac-cepted,becausetheoriginal(static)portionoftheinterfaceisneverchanged,maintainingasenseofusercontrol.Weexpectedalteredprominencetobemorecontroversial,becauseadaptionmodifiestheinterfaceinwaysthatuserscan’tignore.

Forourexperimentaldomain,wechoseagraphingcalculatorapplication,becausemosttasksrequirenumerousinteractionswithclickableUIelements.Thisprovidesacopiousstreamofuser-activitydata,allowingforrelativelyfastadaptation.Weenrolled16usersfromapopulationofgraduatestudentsandstaffintheDepartmentofComputerScience&EngineeringattheUniversityofWashington.Halftheuserswereassignedtothehierarchical/splitinterfaceandhalftoflat/alteredprominence.Weaskedeachusertocompletetwosetsof18formulaentrytasks.Usersenteredonesetofformulaeinanadaptiveinterface

10

(a)(b)(c)(d)

Fig.8.The(handcrafted)interfacesusedinourpreliminaryuserstudy:(a)astaticinterfacethatrequiresuserstousehierarchicalpull-downmenustoaccessadvancedfunctions,(b)splitinterface—anadaptiveversionofthehierarchicalinterfaceinwhichfamiliesofthemostfrequentlyaccessedfunctionsareaddedtothe(previouslyempty)“dynamic”areainthemiddleoftheinterface,(c)astatic,flatinterfacewitheverybuttonpresentatalltimes(d)alteredprominence—anadaptiveversionoftheflatinterface,whichhighlightsthetwomostrecentlyusedfamiliesofbuttons.(Theparenthesisandthexvariablearehighlightedatalltimes.)

andtheotherinastaticUI.Toneutralizelearningeffects,halftheusersstartedwiththeadaptiveinterface,whiletheotherhalffirstusedthestaticUI.Usersreportedtheirsubjectiveexperienceontwoquestionnaires.

Duetothemoderatesamplesize,mostofourresultswerenotstatisticallysignificant.Onaverage,thesubjectscompletedthetasksfasterusingtheadap-tiveinterfaces.Thespeedupwasverysmallforthesplitinterface,butnoticeablefortheinterfacewithalteredprominence.Furthermore,whencomparedtothecorrespondingstaticinterface,theerrorrateincreasedforthesplitinterface,butdecreasedslightlyforalteredprominence.

Thesubjectivecommentsweremoresurprising.Usersconsideredalteredprominencetobeintuitive,butdeemedthesplitinterfacetobeslightlylessintu-itivethanitsstaticalternative.Interestingly,however,usersexpressedastrongandnearly-universalpreferenceforthesplitinterfacewhencomparedwithitsstaticversion(thisresultwasstatisticallysignificantwithp<0.02).Incon-trast,therewasnostatisticallysignificantpreferenceforalteredprominenceintheflatinterface;infact,someusersexpressedastrongdislikeforthatmethodofadaptationclaimingthatitcausedthemtogetdisorientedeverytimethehighlightingchanged.

11

(a)(b)(c)

Fig.9.Intheoriginalprintdialogbox(a)ittakesfourmouseclickstoselectlandscapeprinting:detailsbutton,featurestab(b),landscapevalueandthenaclicktodismissthepop-upwindow.(c)showstheinterfaceafterautomaticallyadaptationbySupplegivenfrequentusermanipulationofdocumentorientation;theadaptedinterfaceisidenticaltotheonein(a)exceptfortheCommonActivitiessectionthatisusedtorenderalternativemeansofaccessingfrequentlyusedbuthardtoaccessfunctionalityfromtheoriginalinterface.

Inbothcases,theinterfaceadaptedatarapidpace:severaltimesduringthecourseofa10–15minute-longsession.Webelievethatbothadaptationstrategieswouldhavehadmoreimpactiftheywereperformedataslowerpace,givingtheuserachancetonoticeandtakefulladvantageofthem.Inaddition,theprominencemightbetterhavebeenalteredmoregradually,sothatthechangeswereimperceptibleandhencenotadistraction.3.2

AdaptationinSUPPLE

Sinceourstudyindicatedthatusersstronglyfavoredsplitinterfaces,weadoptedthismethodinSupple.Figure9showsanexamplewhere,inresponsetoapar-ticularusertracethatrepeatedlyused“Landscape”printing,Supplehasauto-maticallypopulatedthe“CommonActivities”areaofthetop-levelprintdialogboxwithaone-clickshortcuttothisorientation.Supple’ssplitinterfacesgen-erallyworkwelloninterfacesthatinvolvenavigatingamongdifferentwindowsortabpanes(orcards/pagesoncellphonesandpagesontheWeb).

Renderingasplitinterfaceiscomputationallyharderthanrenderinganin-terfacewhereeachpieceoffunctionalityexistsinexactlyoneplace.Inadditiontofindingthebestassignmentofwidgetstointerfaceelements,Supplenowmustalsodecidewhatamountofspacetosetasideforthedynamiccontent,whatfunctionalitytorepresentinthedynamicarea,andhowtorenderit(du-

12

plicatedfunctionalityneednotberenderedexactlyasitwasintheinterface’sstaticpart).

Ideally,Suppleshouldduplicatefunctionalitywiththehighestexpectedutil-ity(i.e.,favoringtheproductofaccesslikelihoodandthedifficultyofnavigationwiththestaticinterface).Note,however,thatthepresenceofadynamicshort-cutforanelementEwilllikelyreducethechancethatauserwillnavigatetoEthroughthestaticinterface.Thisinturnmaycauseadifferentrenderingtobepreferableforthestaticpart.Thusthechoiceofstaticanddynamicaspectsinteract,andchoosingtheoptimalstaticinterfacerequiresconsideringthedis-tributionoverpossibledynamiccontent.Sincethiscomputationisintractable,weuseasimpleapproximation—firstchoosingastaticrenderinginisolation,thengreedilyaddingthebestdynamicshortcutsinturn.WedefinetheutilityofaparticularsetofduplicatedFunctionalityforaparticularconcreteInterfaceandausagetraceas:

utility(duplicatedFunctionality|concreteInterface,trace)=

expectedEffort(concreteInterface|trace)

–expectedEffort(concreteInterface+duplicatedFunctionality|trace)TocomputeexpectedEffort,Supplesimulatesuseoftheinterfacebyre-playingthetraceofpastinteractionsthroughahypothesizedinterfaceandes-timatingthetotal”effort”required.Theusagetracesarerecordedintermsofthefunctionalityaccessedandarestoredinarendering-independentmanner.Fordesktopinterfaces,thenumberofmouseclicks(forchangingtabs,openingnewwindows,dismissingthem,etc)isusedastheapproximationofthetotaleffort.OnWAPcellphones,thenumberofbuttonpressesisusedasthemetric.Incaseswherethefunctionalitythattheuserwantstoaccesshasbeendupli-catedinseveralpartsoftheinterface,Suppleassumesthattheuserwillusethemostconvenientcopyofthefunctionality.Whilethismodelofexpectedeffortisimperfect,ourinitialexperiencesuggeststhatitisagoodapproximationforevaluatingthepotentialutilityofduplicatedfunctionality.

Intheory,asystemmightcalculatetheoptimalpercentageofspacetoallo-catetothedynamicandstaticpartsofaninterface,respectively.Unfortunately,aprincipledapproachtothisoptimizationiscomputationallyprohibitive.Asaresult,Suppleignoresthisdecisionandonlyincludesareafordynamiccontentifauserexplicitlyrequestsitorifthebestavailablerenderingdoesnotfillallavailablespace.Table1summarizesthealgorithmthatSuppleusesforselect-ingwhichinterfaceelementstodisplayinthe“CommonActivities”areaofeachinterfaceview:2

4OverridingAutomatedRenderingDecisions

Supple’scommittmenttocompletely-autonomousrenderinghindersacceptancewithusersasitoriginallyprovidednomeansforeitherdesignersortheenduserstocontrolthepresentationororganizationofthefinalconcreteinterfaces.In

2

AviewisaunitofauserinterfacesuchasawindowonadesktopcomputeroracardinaWMLdocument.

13

selectCommonActivities(interfaceModel,concreteInterface,trace)1.initializeduplicatedFunctionality

2.whilethereisstillaviewwithspaceforduplicatedfunctionality3.currentBestUtility←0

4.currentBestCandidate←null

5.foreachviewinconcreteInterfacethathasspaceforduplicatedfunctionality6.foreachelementininterfaceModel7.temp←duplicatedFunctionality+duplicateelementintoview8.ifutility(temp|concreteInterface,trace)>currentBestUtility9.thencurrentBestCandidate←duplicateelementintoview10.if(currentBestCandidate!=null)11.thenduplicatedFunctionality←duplicatedFunctionality+currentBestCandidate12.elsereturnduplicatedFunctionality13.returnduplicatedFunctionality

Table1.Supple’salgorithmforselectingelementstobedisplayedinthe“Com-monActivities”areaofeachinterfaceview.

Login: { , } -> { , }Login: { , } -> { , }LoginUser

Name

bob

User:{ , }Host:{ , }

......

customization

plan

User:{ , }Host:{ , }

......

device model& user model

PasswordHost

Port

1023Login

Name:stringPassword:passwordName:stringPort:integer

Name:stringdefault: bob

Password:password

Port:integerwidget: spinner

functional specificationcustomized specification

Fig.10.Supple’scustomizationarchitecture.Theuser’scustomizationactionsarerecordedinacustomizationplan.Thenexttimetheinterfaceisrendered(possiblyinadifferentlysizedwindoworonadifferentdevice)theplanisusedtotransformthefunctionalspecificationintoacustomizedspecificationwhichisthenrenderedusingdecision-theoreticoptimizationasbefore.TheinterfaceshowninthisfigureisforasmallFTPclient.

ordertoencourageadoption(andsatisfyrequirementsofeaseandadaptivity),wedevisedaconvenientwaytooverrideoptimization-basedchoices.Suppleincludesacomprehensivecustomizationfacilitythatallowsadesignerorendusertomakeexplicitchangestoaninterface:rearrangingelements,duplicatingfunctionality,removingelements,andconstrainingthechoiceofwidgetsusedtorenderanypartofthefunctionalspecification.Operationissimpleonawindowsandmouseplatform—onesimplyright-clickstheinterfaceelement(primitivewidgetorcontainer)andoptionsarerevealed.Duplicationandrearrangementarespecifiedwithdraganddrop.

Combiningexplicitcustomizationwithoptimization-basedrenderingrequiresamajorchangetotheoriginalSupplearchitecture(Figure10).Supplerecordsacompletehistoryoftheuser’scustomizationoperationsinacustomizationplan.Renderinganinterfaceproceedsintwophases.First,Suppleappliestheplantothefunctionalspecificationinordertocreateagraphcalledacustomized

14

specification.Inthesecondphase,Suppleappliesdecision-theoreticoptimiza-tion(describedinSection2)tothedevicemodel,usermodel,andcustomizedspecificationtorendertheinterface.

Thefunctionalandcustomizedspecificationsmayhaveverydifferentstruc-tures,e.g.,thecustomizationspecificationmayomit,duplicateormovefunc-tionality;itmayalsocontainconstraintsonthesetofwidgetswhichmaybeusedtorendercertainelements.

Notethatthecustomizationplancanbeappliedtoanyfunctionalspecifica-tion,includingonesthattheuser(andSupple)havenotyetseen;italsomaybeappliedwhenrenderinganinterfaceonanoveldevice(however,constraintsrequiringspecificwidgetsmaynotbesatisfiable).ExplicitlyrepresentingthecustomizationplanalsoallowsSuppletosupportaflexibleundosystemwhichencouragesuserstoexperimentwithalternativeinterfaces.

5HandlingComputationally-ImpoverishedDevices

Asrequiredbytheportabilityandextensibilityrequirements,Supplesupportsthemajormodesofoperationrequiredbyubiquitouscomputing.Insomesitua-tions,userswillwanttoaccessapplicationsontheirdesktopcomputers(PCs).Itisalsolikelythatuserswillwanttousetheirdesktopcomputerstoaccessappli-cationsrunningonaremoteserverorappliance.Finally,mobileusersmaywanttoaccesseitherlocalorremoteapplicationsusingcomputationally-impoverisheddevicessuchasPDAsandcellphones.ThesescenariosrequirethatSupplebeabletopresentinterfacesondevicesotherthanthoseexecutingapplicationlogic.Furthermore,ourmeasurementsshowthatSuppleoptimization-basedren-deringcantakeupto40secondstorenderaninterfaceonaPDAsuchasaDellAximv50x.ThuswerequirethatSupplebeabletoutilizearemoterenderingservice(werefertoitasthesolverserver)toacceleratetherenderingprocess,whenevernetworkconnectivityisavailable.Figure11illustratesdifferentmodesofoperationsupportedbySupple.Inordertoenabledisconnectedoperationandtosavepower,aggressivecachingofrenderingresultsisalsosupported.IntheremainderofthissectionwesummarizeSupple’sdistributedarchitecture.Beingabletorenderinterfacesforremoteapplicationisacommonfeatureoftoday’sinterfacegenerationsystems,likethepreviouslymentionedPersonalUniversalController[5]andtheUbiquitousInteractor[7].However,thecompu-tationalcomplexityofourdecision-theoreticrenderingalgorithmcreateuniquechallengesforthedistributionofoursystem.

Supplenaturallysupportsdistributionoftheapplicationandtheinterface,whenitsXML-basedsyntaxisusedtodescribethefunctionalspecification.Wehavealsoimplementedadistributedframework,basedonJavaRMI,thatachievesthesameresultwhentheprogramaticinterfaceisused.Suppleauto-maticallychoseslocalorremotebindingsdependingontheconfiguration,andtheapplicationprogrammerneednotbeawarethatdistributedoperationisinvolved.

15

PCApplicationApplianceApplicationPDAApplicationApplianceApplicationPCDisplaySolverDisplaySolverDisplayPCSolverPDADisplayPCSolver(a)(b)(c)(d)Fig.11.Suppleallowstheapplication,solverserver,andinterfacetorunondifferentdevices;thefollowingmodesofoperationarecommon:(a)AnapplicationrunningonaPCisdisplayedonthesamemachine—theuserinterfaceisrenderedlocally.(b)AremoteapplicationisdisplayedonaPC—theuserinterfaceisrenderedonthePC.(c)AnapplicationrunningonaPDAisdisplayedonthatsamePDA—aremoteservermaybeusedforfasterrenderingofaninterfacewhichisthencached.(d)AremoteapplicationisdisplayedonaPDA—againaremoteservermaybeusedtoquicklyfillthecachewiththerequiredinterfaces.

CurrentlytheremotesolverservercanonlybeinvokedusingJavaRMI,becauseourdevicemodelisnotfullydeclarative.3Inthefuture,however,weplantoimplementthesolverserverasawebservice.

Asabootstrappingmeasure,wehaveimplementedalocaldiscoverymecha-nismbasedonMulticastDNS(baseprotocolforApple’sBonjour)sothatdis-playdevicescaneasilydetectavailableapplicationsandsolverserversintheirenvironments.Developersarefreetoreplaceitwithwhateverlocalorglobaldiscoverymechanismismostappropriatefortheirdeploymentenvironment.

6QuantitativeEvaluation

InthisSection,weevaluateSupple’sversatility,quantifythecomplexityofinterfacespecifications,reportontherenderingtimefordifferentdevices,andmeasurethesizeofmessagestransmitedduringdistributedoperation.Addition-ally,Section3.1describedouruserstudywhichevaluatedthesplitinterfaceandalteredprominenceadaptationmethods.

WedemonstrateSupple’sversatilitybyexhibitingthewiderangeofdif-ferenttypesofinterfacesithasgenerated.Earlierinthepaper,wepresentedastereocontroller(Figure2),afullyfunctionalemailclient(Figure4),anin-terfacetoAmazonwebservices(Figure5),amap-basedinterface(Figure3),acontrollerforclassroomequipement(Figure6),andanadaptiveprintdialogbox(Figure9).ThewidediversityoftheseapplicationsdemonstratesSuppleiscapableofhandlingcomplexinterfacesandrichdatatypes(i.e.,thecapabilityrequirement).

3

Boththefactorscomprisingcostfunctionsandtheelementsofthewidgetfactoryaredescribedprocedurally.Asaresult,appropriateclassdefinitionsmayneedtobesubmittedtogetherwitharenderingrequest.

16

PrintDialogMapAmazonEmailStereoClassroomLinesofcode117475947513373Table2.LinesofcodeusedtoconstructandmanagetheuserinterfacesfortheapplicationspresentedthroughoutthispaperandfortheClassroomcontrollerfrom[3].

PrintDialogPC0.31sPDA(local)—PDA(remote)—MapAmazonEmailStereoClassroom0.25s1.2s0.21s1.5s0.55s———40s29s———3.1s2.5sTable3.Timerequiredtorenderuserinterfacesondifferentplatforms.Thethree

conditionsincludeinterfacesbeingrenderedlocallyonadesktopcomputer(PC)andinterfacesrenderedonaPDAeitherlocallyoronaremotesolverserverrunningonadesktopcomputer.Inthelastcasethetimesincludethecommunicationoverhead.

Comparisonsofthecodequantityorcomplexityamongdifferentapproachesareoftencontroversial.Yet,wefeelitisusefultoreportontheamountofcode4devotedtothedescriptionandmanagementoftheuserinterfaceforalltheexamplesreportedinthispaper(e.g.,asaproxyforeasyofuserequirement).ThesenumbersarereportedinTable2andarefortheprogrammatic(asopposedtotheXML-based)encodingoftheinterfaces.

Inserviceoftheextensibilityrequirement,Table3reportstherenderingtimesfordifferentinterfacesanddifferentplatforms.Forinterfacesrunningonadesktopcomputer,thegenerationtimessupportfullyinteractiveoperation.PDAuserscanalsoexperiencefastinterfacegenerationtimesiftheyhavenetworkaccesstoaremotesolver.EvendisconnectedPDAusersarenotpreventedfromusingSupplebuttheymayhavetoendureasubstantialwait(e.g.,upto40s)thefirsttimeanygiveninterfaceisrendered.Futurerenderingsareinstantaneous,becauseofthecachingmechanism.

Wehavealsomeasuredthesizesofthemessagesthatneedtobeexchangedinordertoinvokearemotesolver.Thefunctionalspecificationsizesvaryfrom4.8kBto11.5kBwhiletherenderedsolutionsareallsmallerthan3.6kB.Thesesizesmakeasolverserveranoption,notonlyonWiFinetworks,butalsoonslowerBluetoothor3Gcellphoneconnections.

7RelatedWork

Researchershaveinvestigatedmodel-baseduserinterfacesystemsincludingau-tomaticinterfacegenerationformanyyears,yieldingimpressivesystems[15].Unfortunately,noneofthepriorworkmeetsourfiverequirements.ProjectsliketheUIML[1],XIML[11]ortheUbiquitousInteractor[7]provideadevice-independentwayofrepresentingvariousaspectsoftheuserinterfacebutulti-4

NumberswerecalculatedusingtheMetricspluginforEclipseavailableatmetrics.sourceforge.net.

17

matelyallrequirethattheapplicationdesignerspecifyhowabstractelementsbemappedtoconcretewidgetsonvarioustargetplatforms.

ThePersonalUniversalController(PUC)[5]comesclosertomeetingourrequirementsasitprovidesadomain-independentlanguageforabstractlyde-scribinguserinterfacesintermsoftheirfunctionalityanditprovidesasetofrenderingalgorithmsforasmallnumberofdifferentplatforms.Thissystem,however,isintendedmainlyforrenderinginterfacesforappliancesasareplace-mentfortraditionalremotecontrols.Itsrule-basedrenderingalgorithmsreliesonspecificdomainknowledgeandmakesitinflexibleeventothechangesinthescreensizeofthedeviceitrunson.XWeb[8],isevenfurtherlimitedbythefactthatleafwidgetsarepre-specifiedandonlytheirlayoutischosendynamically.

8Conclusions

ThispaperpresentsSupple—anautomaticuserinterfacegenerationtoolkitthatsupportsrapidprototypinganddeploymentofubiquitousapplicationsacrossdifferentplatforms.Wemakethefollowingcontributionsthatturnedaresearchprototypeintoapracticalandpowerfultool:

–Weprovideadetaileddescriptionofthefunctionalspecificationlanguageformodelinguserinterfacesandweextenditwiththreenewclassesoffea-tures:explicitsupportforsubtyping;newtypesforrepresentingimages,maplocationsandvectors;andthealternativesspecificationelementsthatgivethedesignersgreatercontroloverdifferentsubsetsoffunctionalitytobepresentedondifferentclassesofdevices.

–Wedescribeanewadaptationstrategy,termedsplitinterfacesthatprovidesthebenefitsofallowingusersfastaccesstofrequentlyusedfunctionalitywithoutneedlesslydisorientingthem.Thischangerequiredafundamentalextensiontoourrenderingalgorithm,enablingittohandlefunctionalspec-ificationswhicharedirectedacyclicgraphsnottrees.

–Wesupportexplicitcustomizationactions,whichallowsbothusersandthedesignerstochangethestructureoftheinterfaceortooverrideSupple’sautomaticrenderingchoices.

–Weuseadistributedarchitecture,thatenablesuserinterfacestobepre-sentedonremotedevice;italsoallowsimpoverisheddeviceswithnetworkconnectivitytouseremoteinterfacesolverserversforfasterrenderingoftheinterfaces.Ourarchitecturealsosupportscachingofthepreviouslyrenderedinterfacesforfasterpresentationanddisconnectedoperation.

–OurevaluationdemonstratesthefeasibilityofthepracticaldeploymentofSupple.Ouruserstudy(Section3.1)supportsthesplitinterfacesasaneffectiveandnon-distractingmethodtoadaptinterfacestouser’stasks.SupplesatisfiesthefivedesideratalistedinSection1andisapromisingplatformforubiquitousinterfaces.InordertofullyevaluateSupple’simpact,wearereleasingitasanopensourcetoolkitforpublicuse.

Inthefutureweplantoextendthespecificationlanguagetoallowdraganddropoperationsonplatformsthatprovidethatcapabilityandtosupportmorecomplexmap-basedinteractionswhereadditionalinteractiveobjectscan

18

beoverlaidoverthemap.Finally,following[12],weplantoextendSuppletoworkwithmultiplemodalities,includingspeech.

AcknowledgmentsWethankDonPatterson,MichaelCafarellaandtheanony-mousreviewersforcommentsontheearlierversionsofthemanuscript.ThisresearchissupportedbyNSFgrantIIS-0307906,ONRgrantN00014-02-1-0932andbyDARPAprojectCALOthroughSRIgrantnumber03-000225.

References

1.M.Abrams,C.Phanouriou,A.L.Batongbacal,S.M.Williams,andJ.E.Shuster.UIML:Anappliance-independentxmluserinterfacelanguage.WWW8/ComputerNetworks,31(11-16):1695–1708,1999.

2.L.FindlaterandJ.McGrenere.Acomparisonofstatic,adaptive,andadaptablemenus.InProceedingsofACMCHI2004,pages89–96,2004.

3.K.GajosandD.S.Weld.Supple:automaticallygeneratinguserinterfaces.InIUI’04,Funchal,Madeira,Portugal,2004.ACMPress.

4.K.GajosandD.S.Weld.Preferenceelicitationforinterfaceoptimization.InProceedingsofUIST2005,Seattle,WA,USA,2005.

5.J.Nichols,B.Myers,M.Higgins,J.Hughes,T.Harris,R.Rosenfeld,andM.Pignol.Generatingremotecontrolinterfacesforcomplexappliances.InProceedingsofUIST’02,Paris,France,2002.

6.J.Nichols,B.A.Myers,M.Higgins,J.Hughes,T.K.Harris,R.Rosenfeld,andM.Pignol.Generatingremotecontrolinterfacesforcomplexappliances.InUIST’02,Paris,France,2002.

7.S.Nylander,M.Bylund,andA.Waern.Theubiquitousinteractor-deviceinde-pendentaccesstomobileservices.InCADUI’2004,Funchal,Portugal,2004.

8.D.R.Olsen,S.Jefferies,T.Nielsen,W.Moyes,andP.Fredrickson.Cross-modalinteractionusingXWeb.InUIST’00,pages191–200,SanDiego,California,UnitedStates,2000.ACMPress.

9.M.PerkowitzandO.Etzioni.Towardsadaptivewebsites:Conceptualframeworkandcasestudy.ArtificialIntelligence,118:245–276,2000.

10.S.Ponnekanti,B.Lee,A.Fox,P.Hanrahan,andT.Winograd.ICrafter:Aservice

frameworkforubiquitouscomputingenvironments.InProceedingsofUbicomp2001,pages56–75,2001.

11.A.PuertaandJ.Eisenstein.XIML:Auniversallanguageforuserinterfaces,2002.

unpublishedpaperavailableathttp://www.ximl.org/.

12.D.Reitter,E.Panttaja,andF.Cummins.UIonthefly:Generatingamultimodal

userinterface.InHLT/NAACL-04,2004.

13.A.SearsandB.Shneiderman.Splitmenus:effectivelyusingselectionfrequencyto

organizemenus.ACMTrans.Comput.-Hum.Interact.,1(1):27–51,1994.

14.B.SmythandP.Cotter.Personalizedadaptivenavigationformobileportals.In

ProceedingsofECAI/PAIS’02,Lyons,France,2002.

15.P.Szekely.Retrospectiveandchallengesformodel-basedinterfacedevelopment.

InF.BodartandJ.Vanderdonckt,editors,Design,SpecificationandVerificationofInteractiveSystems’96,pages1–27,Wien,1996.Springer-Verlag.

16.D.S.Weld,C.Anderson,P.Domingos,O.Etzioni,K.Gajos,T.Lau,andS.Wolf-man.Automaticallypersonalizinguserinterfaces.InIJCAI03,Acapulco,Mexico,August2003.