IOS Press $-Calculus of Bounded Rational Agents Flexible Optimization as Search under Bound

47

$-CalculusofBoundedRationalAgents:FlexibleOptimizationasSearchunderBoundedResourcesinInteractiveSystems

EugeneEberbach

ComputerandInformationScienceDepartmentUniversityofMassachusettsDartmouthNorthDartmouth,MA02747,USAeeberbach@umassd.edu

DiscussionsandcommentsfromPeterWegneronexpressivenessofthe$-calculusareappreciated.ThankstoRichardBrooksforhisparticipationinthe$-calculusresearchatAppliedResearchLab,PennsylvaniaStateUniversity,andMarkLastforexplorationofdataminingapplication.ChrisDuarte,ChristineBuzzellandGeryMartelwereinstrumentalinthedesignandimplementationoftheCCLlanguageforAUVs.CommentsoffourreviewersoftheJournalallowedtoimprovetheoriginalmanuscript.ResearchsupportedinpartbyONRundergrantN00014-03-1-0421.

Addressforcorrespondence:ComputerandInformationScienceDept.,UniversityofMassachusettsDartmouth,285OldWestportRoad,NorthDartmouth,MA02747-2300,USA.

48E.Eberbach/$-CalculusofBoundedRationalAgents

Thatdealswithincompleteinformationandcomplexityduringproblemsolving.Secondly,devel-opinganalgebrawhichexpressescurrentpractices,e.g.,neuralnets,cellularautomata,dynamicprogramming,evolutionarycomputation,ormobileroboticsaslimitingcases,providesatoolforexploringthetheoreticalunderpinningsofthesemethods.Astheresult,hybridmethodscanbenaturallyexpressedanddevelopedusingthealgebra.

Keywords:resourceboundedcomputation,processalgebra,problemsolving,search,complete-ness,optimization,totaloptimization

1.Introduction

Theattempttobuildflexibleandintelligentsystemsworkingindynamicenvironmentswithboundedre-sourcesgivesthehopeofefficientimplementationofreal-timecomplexsystems.Recentlytherehasbeenashiftfromconsiderationofoptimaldecisionsinsimplesearchalgorithmsandgamestoaconsiderationofoptimaldecision-makingprogramsfordynamic,inaccessible,interactive,complexenvironmentsthatareclosertotherealworld.Unfortunately,tobeperfectlyrationalinsuchenvironmentesisimpossiblebecauseofprohibitingdeliberationcomplexity.Resource-boundedcomputationattemptstogracefullytradeoffresultqualityfortheamountoftimeormemoryrequiredtogeneratetheresults.

Theapproachisknownunderavarietyofnames,includingflexiblecomputation[38],anytimealgo-rithms[13],imprecisecomputation[48],design-to-timescheduling[27],decision-theoreticmetareason-ing[70],computationunderboundedresources[39],etc.Aboundedrationalagentisonethatalwaystakestheactionthatisexpectedtooptimizeitsperformancemeasure,giventheperceptsequenceithasseensofarandlimitedresourcesonehas.

Nobodyproposedresource-boundedcomputationasageneralmodelofcomputation.BasedonChurch’s-calculus[12]andMilner’s-calculus[58],weextendprocessalgebraoperatorswithvonNeumann/Morgenstern’scosts/utilities[81].Astheresult,weattempttochangeacomputationalparadigmfromthedesignofagentsachievingone-timegoalstotheagentswhopersistentlyattempttooptimizetheir“happiness”.Ourapproachtoachievinganagent’s“happiness”meansachievingaglobalopti-mum.Technicallyforthatweuseavariantofprocessalgebraextendedwithautility(cost)allowingtheexpressionofboundedoptimizationandmetareasoningininteractivemulti-agentsystems.

Inthispaperatheoryandformalismforresource-boundedcomputationisproposed.Ithasrootsinprocessalgebras[34,56,58,59]andthetheoryofprogramming[79].However,thisisnotan-otherpaperonprocessalgebras,oritsprobabilistic,timed,orstochasticextensions(tolearnmoreonprocessalgebras,thereaderisreferedto[5,67]).Processalgebrasareusedonlyasatooltoexpressresource-boundedcomputation;andresource-boundedcomputation,webelieveiscrucialfordealingwithintractableproblems.DissimilartoTuringmachines,processalgebrasareclosertorealprogramsbyusingprogramming-likeoperators;theyarenaturallyparallelandinteractive.Somevariantsofpro-cessalgebras,likethe-calculus[58]havebuilt-inalimitedadapatbility(i.e.,mobility).Weneededmodelwhichwillbeadaptive,open,naturallyparallelandinteractive,andprocessalgebrasaregoodinthat.Ontheotherhand,theauthor(uptohisbeststateofknowledge)isunawareofprocessalgebraswithbuilt-inperformancemeasures,andwhichallowinfinityinoperators(neededforexpressiveness).Performancemeasuresandinfinityofoperatorsweretwominimalessentialchangesinprocessalgebras.

Thespecificvariantofprocessalgebra-the$-calculus-hasbeendevelopedindependentlyofanytimealgorithmsandinspiredbytheolderCSA(CalculusofSelf-modifiableAlgorithms)[14,15,16].The

E.Eberbach/$-CalculusofBoundedRationalAgents49

$-calculushasbeenproposedin1997andseveralshorterpapersdescribeitspreliminarydesignandapplications[17,18,19,20,21,22,23,24,25,85].Thisisthemostcompletedescriptionofthe$-calculussofar.

Resource-boundedapproachessharethefollowingcharacteristics[]:ElementaryAlgorithmConstructionwithBoundedOptimalAnswer-insteadofbuildingsystems

thatfinda“good”answer,resource-boundedreasoningtechniquestrytofindan“optimal”answer.Thisoptimalityisresource-bounded,i.e.,itdoesnotguaranteemaximalsolutionquality.Composability-itshouldbepossibletodecomposesystemintomodulesintheformofdelibera-tivealgorithms.Deliberativealgorithmsuseacomputationaldecisionprocedure(ofthetypesense-deliberate-act,oritsspecialcasesense-plan-act)toselecttheirnextbase-levelaction.Thiscontrastswithreactivealgorithms(ofthetypesense-act)thatexhibitpurelyreactivebehaviorsasinBrookssubsumptionarchitecture[6].Asthecomplexityofthedomainofoperationincreases,deliberationandplanningbecomeessentialpartsofeffectiveagentconstruction[].Delibera-tivealgorithmsaredividedintointerruptibleandcontractalgorithms.Interruptiblealgorithmsproduceresultsofthequality“advertised”bytheirperformanceprofilesevenwheninterruptedunexpectedly.Contractalgorithms,althoughcapableofproducingresultswhosequalityvarieswithtimeallocation,mustbegivenanagreedupontimeallocationtoproduceresults.PresenceofMeta-LevelControl-systemexecutionmustbemonitoredtomaximizeperformance.

Thiscanbedoneusingeithercontractalgorithms(indomainscharacterizedbyhighpredictabilityofutilitychangeovertime)orinterruptiblealgorithms(indomainscharacterizedbyrapidchangeandahighlevelofuncertainty).PerformanceMeasureandPrediction-shouldfacilitatepredictionofanticipatedqualityimprove-ment.Qualitymeasuresmayincludecompleteness,precision,orcertainty.The$-calculushasallthecharacteristicsofresource-boundedcomputation:

1.Itproposesageneraltheoryforalgorithmconstructionwithprogrammingoperationssuchascom-position,choice,andrecursivedefinition.Operatorsareboundedbyalimitingvalue(cost).Basingresource-boundedcomputationonprocessalgebraisanewidea.Thisextendsanytimealgorithmstodistributed,interactive,andadaptivesystems.Meta-levelmodificationsprobethesearchspaceofpossiblesolutionsflexiblycontrollingcost.2.Composabilityisachievedbybuildingsolutions/expressionsfromsubexpressions.Recursivedef-initionsofsubexpressionsdecomposetoatomicexpressions.Composability/separabilityofcostmeasuresisassumedaswell.Expressioncostsarefunctionsofsubexpressioncosts.Deliberationoccursintheformofselect-examine-executecyclescorrespondingtosense-deliberate-act.Anemptyexaminephaseproducesareactivealgorithm.Short(long)deliberationisnaturalforin-terruptible(contract)algorithms.Interruptiblealgorithmscanbeinterrupteddowntothelevelofatomicexpressions.Interruptibilityiscontrolledattwolevels:choiceofatomicexpressionsandthelengthofthedeliberationphase.

50E.Eberbach/$-CalculusofBoundedRationalAgents

3.Theapproachusesanovelmeta-controlmethod,the-optimization.Executionismonitoredandmodifiedtominimizecost.Solutionsarefoundincrementally.Theymayoptimizeanswerquality,resourcesused,trafficinthenetwork,oracombinationofseveralfactors.Dependingonproblemcomplexity,costfunctionvolatility,andamountofuncertainty,deliberationcanbedoneforstepsoruntiltermination.Optimizationislimitedtoalphabet,asubsetofthecompleteexpressionalphabet.Thisincreasesrun-timeflexibility.

4.Performancemeasuresareuniformlymodeledasutilitiescalledcosts.Costfunctionscanrepresent

uncertainty,time,oravailableresources.Astandardcostfunctionispartofthecalculus,butusersmaydefinetheirowncostfunctions.Predictionofincomplete/uncertaininformation(intimeorspaceresources)takestheformofsilent(invisible)expressionswhosecostcanbeeitherunknownorestimated.

Weconsidertheabilitytooptimizebothsolutionsqualityandthedeliberationcostsasthemostimportantpracticalfeatureofresource-boundedcomputation,neededtotacklehardcomputationalprob-lemsofthereal-world.However,anotherbasicrequirementofanytimealgorithms:themonotonicim-provementinthesenseoftheperformancemeasureineachiterationstep,wedonotconsideras“amust”(pendingthatitsviolationleadstothegoal).Thisallowsalargerclassofsystems,likeevolutionarycomputationorneuralnets,whichveryoftenviolatethemonotonicityrequirements,toincludetosuchwidelyunderstoodresourceboundedcomputation.

Inthispaper,wediscussoptimizationproblemsbysearchandemergingglobaloptimization.Thepaperisorganizedasfollows.InSection2,wedescribethebasicfeaturesofthe$-calculus,andproblemsolvingseenasoptimizatonunderboundedresources.InSection3,syntaxofthe$-calculusandthebe-havioralequivalenceofcostexpressionsarepresented.Section4containstheoperationalcostsemanticsofthecalculusbasedonthenovelmeta-levelcontrolmethod(the-optimization)andtheLabeledTran-sitionSystemswithinferencerulesandstructuralcongruence.Theprocessalgebraapproachnaturallysupportsbuildingprogramsandalgorithms.Atypicallyforprocessalgebra,oursemanticslookforap-proximatelyoptimalprogramsratherthanadequateones.Completeness,optimizationsearchingforthebestqualitysolutions,andtotaloptimizationlookingbothforthebestqualitysolutionsandminimizingsearchcost,aredefined.Theoptimization(totaloptimization)problemsaresolvedinacontextofincom-pleteknowledgeofanagentsituatedinanenvironmentcontainingpossiblymultipleinteractingagents.Necessaryconditionsforachievingglobaloptimizationthroughlocalspatialortemporaloptimizationaregiven.CostfunctionperformancemeasuresarepresentedinSection5.AstandardcostfunctionisdescribedforstronglyandweaklycongruentcostexpressionsinSection5.1.Itcanbeusedtomeasurethequalityofsolutionsandcostsofsearch.Simplecostexpressionsempiricalprofilingdonebycollect-ingstatisticsorreinforcementlearningtechniquesisoutlinedinSection5.2.InSection6,illustratingexamplesspanningmanyareasofAI,computerscienceandoperationresearcharepresentedtoillus-tratethepowerandversatilityofthe$-calculus.Asingleagentsearch(e.g.,A*,tabusearch,simulatedannealing),two-agentsearch(e.g.,minimax,expectiminimax),andmultipleagentsearch(e.g.,dynamicprogramming,evolutionarycomputation,cellularautomata,neuralnets)arepresentedasaspecialcaseofthe$-calculussearch.Applicationstoadaptiveautonomousmobilerobotics,imageprocessing,anddataminingarediscussedinSection7.Section8containsconclusionsandfuturework.

E.Eberbach/$-CalculusofBoundedRationalAgents51

2.The$-Calculus:TheElementaryAlgorithmConstructionwithBoun-dedOptimalAnswer

2.1.The$-CalculusinCapsule

The$-calculus(read:costcalculus)[17,18,19,20,21,22,23,24,25,85]isahigher-orderpolyadicprocessalgebra.Ahigher-ordermeansthatanarbitraryexpression(notonlynamescanbecommuni-catedininteractions).Apolyadic-meansthatawholelistofexpressions,andnotasingleexpression,canbecommunicatedinasingleinteraction(infactourlistsareevenunbounded-enumerablyinfinite).

The$-calculususesutilities,calledcoststoexpressadaptability,optimizationandself-modificationfordynamicandinteractivemulti-agentsystems.Agentsinteractbysendandreceiveprimitives.TheapproachdiffersfromothermodelsbyincludingtimeandresourcecostsasbasiccomponentsexpressingthebehaviortypicalofmanyAIsystems.Auniformmechanismexistsforexpressingcontrol,learning,uncertainty,error,fitness,entropy,interestingness,energy,distance,time,complexity,etc.

Toavoidacombinatorialexplosion,on-lineoptimizationoftenconsidersarestrictedsubsetofagents,andonlyafewstepsofexecution.Inthe$-calculus,self-modificationandcost-optimizationarethedriv-ingforceforproblemsolving,control,andprogramsynthesis.Theinnovativeaspectofthe$-calculusanditspredecessorCSAisthattheyintegrateneuralnetworks,geneticprogramming/algorithms,sym-bolicrule-basedexpertsystems,logic,imperativeandobject-orientedprogrammingintoacommonframework[14].

Theapproachdevelopsageneralmodelfordistributedinteractiveintelligentsystems.Ithasbeende-signedtospecify,investigate,andimplementsystemsexhibitingmeta-computation(e.g.,self-modification)andoptimization,includingexpertsystems,neuralnetworks,evolutionarycomputation,artificiallife,andadaptiveautonomousagents(describedinSections6and7).Theworkisrelatedtoothergeneralmodelsforsequentialandparallelcomputation,including-calculus[12]and-calculus[58,59,60].Thesymbol“$”isusedtostressthat$-calculusisadirectdescendantof-and-calculi;andtheapproachisbasedonstrengthsofitspredecessors,withcostasitsmostimportantaspect1.

The$-calculusleadstoanewprogrammingparadigm:costlanguages,whereeachstatementinthelanguagehasitsassociatedcost,andanewclassofcomputerarchitectures:cost-drivenmachines,wherenextinstructionforexecutionistheinstructionwiththesmallestcost[16,25].

The$-calculusexpressesadaptationasoptimization.Globalbehaviorisoptimizedbyperforminglocaloptimizationofcomponents.“Fuzzy”conceptslikeemergingintelligencearegivenamathemat-icalfoundation.Systemdesignisreducedtofindingappropriateobjectivecostfunctions,optimizationparameters,methods,andalgorithms.Becauselocaloptimizationsareperformed,globaloptimizationisreducedtoacombinationoffeasiblelocaloptimizations.Themainquestioniswhichlocalopti-mizationstoperformandhowtocooperate.Thisisresolvedbymaskingpartsoftheproblem-spacegiving-optimizationproblems,describedinSection4.1.Partsof$-expressionsarereplacedbysilent$-expressions,whichmaskpartoftheproblemspace(eitherspatiallyortemporally).Forobservationbisimilarity/congruence[57],silent$-expressionsareinvisiblewithaneutralcost.Theydonotpar-ticipatedirectlyinoptimization;however,theyparticipateindirectlyandinfluenceresults.Forstrongbisimilarity,silentactions(representingincompletelocalknowledgeofanagent)areinvisible,buttheircostisnotzero.Dependingonthecostestimation,globaloptimizationmayormaynotbesuccessful.

52E.Eberbach/$-CalculusofBoundedRationalAgents

2.2.ProblemSolvingunderBounderResources

Anidealrational(intelligent)agent[69]isonethatalwaystakestheactionthatisexpectedtooptimizeitsperformancemeasure,giventheperceptsequenceithasseensofar.However,itrequiresanunre-alisticassumptionthatanagenthasunlimitedresources(e.g.,infinitespeedofcomputation,orinfinitememory).Unfortunately,mostoftherealproblemsrequiringintelligencearecomputablyundecidableorintractable(eitherunsolvableorexponentiallycomplex),thusperfectoptimizationrequiredforintel-ligenceisoutofthequestion.

Alimited(bounded)rationalagent[69]isonethatalwaystakestheactionthatisexpectedtooptimizeitsperformancemeasure,giventheperceptsequenceithasseensofarandthelimitedresourcesonehas.Aboundedrationalagentsolvesconstraintoptimizationproblems,takingintoaccountboththequalityofasolutionandthecostsofresourcesusedtoobtainit.Boundedoptimalityfitsintuitiveideaofintelligenceandprovidesabridgebetweentheoryandpractice.

Theperformanceofsearchalgorithms(intelligenceofanagent)canbeevaluatedinfourways(seee.g.[69])capturingwhetherasolutionhasbeenfound,itsqualityandtheamountofresourcesusedtofindit.

DEFINITION2.1.Oncompleteness,optimality,searchoptimality,andtotaloptimalityWesaythatthesearchalgorithmis

Completeifitguaranteesreachingaterminalstate/solutionifthereisone.Optimalifthesolutionisfoundwiththeoptimalvalueofitsobjectivefunction.

SearchOptimalifthesolutionisfoundwiththeminimalamountofresourcesused(e.g.,thetimeandspacecomplexity).

TotallyOptimalifthesolutionisfoundbothwiththeoptimalvalueofitsobjectivefunctionandwiththeminimalamountofresourcesused.

DEFINITION2.2.OnproblemsolvingasamultiobjectiveoptimizationproblemGivenanobjectivefunction,whereisanalgorithmspacewithitsinputdomainandcodomaininthesetofrealnumbers,,problem-solvingcanbeconsideredasamultiobjectiveminimizationproblemtofindand,whereareterminalstatesofthealgorithmspace,andareterminalstatesofsuchthat

whereisaproblem-specificobjectivefunction,

anaggregatingfunctioncombiningand.

isasearchalgorithmobjectivefunction,and

is

Withoutlosinggenerality,itissufficienttoconsideronlyminimizationproblems.Anobjectivefunctioncanbeexpandedtomultipleobjectivefuntionsifproblemconsideredhasseveralobjectives.Theaggregatingfunctioncanbearbitrary(e.g.,additive,multiplicative,alinearweightedsum).Theonlyrequirementisthatitcapturesproperlythedependencebetweenseveralobjectives.Inparticular,ifbecomesanidentityfunction,weobtaintheParetooptimality

E.Eberbach/$-CalculusofBoundedRationalAgents53

UsingParetooptimalityissimpler,howeverweloseanexplicitdependencebetweenseveralobjectives(wekeepavectorofobjectivesignoringanypriorities,ontheotherhand,wedonothaveproblemscom-biningobjectivesiftheyaremeasuredindifferent“units”,forexample,anenergyusedandsatisfactionofusers).Forfixedweconsideranoptimizationproblem-lookingforminimumof,andforfixedwelookforminimumofsearchcosts-searchoptimumof.

Objectivefunctionsallowcapturingconvergenceandtheconvergencerateofconstructionofsolu-tionsmuchbetterthansymbolicgoals.Obviouslyeverysymbolicgoal/terminationconditioncanbeexpressedasanobjectivefunction.Forexample,averysimpleobjectivefunctioncanbethefollowing:ifthegoalissatisfiedtheobjectiveissetto1,andifnotto0.Typically,muchmorecomplexobjectivefunctionsareusedtobetterexpressevolutionsofsolutions.

Letdenotesthesetoftotallyoptimalsolutions.Inparticulardenotesthesetofoptimalsolutions,andtheoptimalsearchalgorithms.

Letbeametricspace,whereforeverypairofitselementsthereisassignedtherealnumber

,calleddistance,satisfyingthreeconditions[44]:

1.2.3.

,

Thedistancefunctioncanbedefinedindifferentways,e.g.,astheHammingdistance,Euclideandis-tance,ifsatisfiesterminationconditionandotherwise.Tokeepitindependent

fromrepresentation,andtoallowtocomparedifferentsolvingalgorithms,wewillfixthedistancefunc-tiontotheabsolutevalueofdifferenceoftheobjectivefunctions.Weextendthedefinitionofthedistancefromthepairsofpointstothedistancebetweenapointandthesetofpoints

Inproblemsolving,wewillbeinterestedinthedistancetothesetofoptimalsolutions

,andinparticular,.thedistance

,i.e.,in

DEFINITION2.3.OnsolutionconvergenceForanygivenprobleminstance,itssolutionevolvedinthe

discretetimewillbesaidtobe

convergenttothetotaloptimumiffthereexistssuch

,

thatforevery

,

asymptoticallyconvergenttothetotaloptimumiffforevery,

,forevery

,thereexistssuch

that

convergentwithanerror

every

tothetotaloptimum,where

,

iffthereexistssuch

thatfor

divergent,otherwise.

Ifisfixedtheconvergenceisalgorithmic,otherwiseitisnonalgorithmic.Asymptoticconvergence

isnonalgorithmic.

DEFINITION2.4.OnsolutionconvergencerateTheconvergenceratetothetotaloptimumisdefinedas.

54E.Eberbach/$-CalculusofBoundedRationalAgents

Thecovergenceratedescribestheone-stepperformanceofthealgorithm,wherethepositivecon-vergenceratemeansthatthealgorithmdriftstowardstheoptimumandthenegativeratesignifiesadriftawayfromtheoptimum.Withpositiveconvergencerate,thesearchalgorithmwilltypicallyconvergeorasymptoticallyconvergetotheoptimum.Thebestsearchalgorithmswillhaveahighconvergencerateandasmallnumberofstepstoreachtheoptimum.Inthesimilarway,optimalandsearchoptimalconvergenceandconvergenceratecanbedefined.Ifthesearchalgorithmisprobabilistic,weuseanexpectedvalueofthedistancefunction.

Searchcaninvolvesingleormultipleagents:-singleagent:andalgorithmslikedepth-first,breadth-first,uniformcost,iterativedeepening,A*,

IDA*,SMA*,hillclimbing,simulatedannealing[69,54],-twoagents:usingalgorithmslikeminimax,alpha-beta,expectiminimax[81,69],

-multipleagents:andalgorithmslike-optimization,n-playergames,co-evolutionaryalgorithms,

COllectiveINtelligence[81,54,87].

Formultipleagentssearchcanbecooperative,competitive,orrandom.Incooperativesearchotheragentshelptofindanoptimum,incompetitivesearch-theydistracttoreachanoptimum,andinrandomsearchotheragentsdonotcareabouthelpingordistractingtoreachanoptimum.

Searchalgorithmscanbeonline,whereactionexecutionandcomputationareinterleaved,andof-fline,wherethecompletesolutioniscomputedfirstandexecutedafterwithoutanyperception.Moreinterestingareonlinealgorithms,althoughthemajorityofdevelopedsofarsearchalgorithmsareoffline.

3.The$-CalculusSyntax:Composability

3.1.SimpleandComposite$-Expressions

Letbeasetofterminalscorrespondingtoconstants,variables,datastructures,andzero-argumentfunctions.Theyterminateevaluation.Letbeasetoffunctions,suchasarithmeticoperations,pro-grammingoperations,mathematical/logicalfunctions,userorautomaticallydefinedfunctions.Functionsareexecutedbyevaluation.Terminalsaredataforfunctions.Functionsaredynamic,theyinputtermi-nals,modifythem,andproducenewterminals.Letbeasetofmeta-codeoperatingonterminals,functionsandmodifications(noteself-modification).Meta-codeandcostareuniquefeaturesofthe$-calculus.Meta-codesearchesforminimalcostalgorithmsthatachievethedesiredgoal.Inother

)words,terminalsarezero-order,regularfunctionsarefirstorder,andmeta-code-higher-order(

functions.Theuniformapproachtodata,codeandmeta-codeissimilartosymbolicexpressionsfromLisp.

Throughoutthepaperweuseprefixnotation.Data,functions,andmeta-codearewrittenas,whereisafunction/terminal/modificationnameandisavectorofitsparameters(possiblycountablyinfinite).Sometimes,weomitparameters,andwritesimply.Wealsorefertodata,functions,andmeta-code,allasfunctions.

Letbenamesoversets,and,andeachwithanintegralarity(representingnumberofparameters)foreachterminal,functionandmeta-code.Let

bepredefined(reserved)names.Weassumebasicarithmeticandrelationaloperatorsarepredefinedandavailable,e.g.,,etc.

E.Eberbach/$-CalculusofBoundedRationalAgents55

LetP,Q,R,...rangeoverthe$-expressions(read:costexpressions)andletX,Y,Z,...beprocessvariables.Wewilldistinguishsimple(oratomic)$-expressions,executedinoneindivisiblestep,orconsideredtobeindivisiblebecauseitismoreconvenientfromthepointofauser.$-expressionsreturnothercostexpressionsasaresultoftheirevaluation.Inparticular,theymayreturnnothingaftersuccessfulexecution,ortheymayblockafterafailureinexecution.

Letbeapossiblycountablyinfiniteindexingsetusedtoindexargumentsof$-expressions.Theindexingsetcanbeomittedifitisempty,orthelistofargumentsissmall,orargumentscanbede-ducedfromthecontext.Theindexingsetisapossiblycountablyinfinite,andAll$-calculusoperatorsuseapossiblycountablyinfinite(unbounded)indexingset.TheindexingsetisinfinitetoexpressformalismswithricherbehaviorthanTuringmachines:includingcellularautomata[10],interactionma-chines[82,83],neuralnetworks,andrandomautomatanetworks[28].Thisexpressivepowerisneededtoexpressinteractivedistributedsystems,constructionuniversality,self-reproduction,andevolutionprob-lems.[19]shows$-calculussimulates-calculus,-calculus,interactionmachines,cellularautomata,neuralnetworksandrandomautomatanetworks.

In$-calculuseverythingisacostexpression:agents,environment,communication,interactionlinks,inferenceengines,modifiedstructures,data,code,andmeta-code.$-expressionscanbesimpleorcom-posite.Simple(contract)$-expressionsareconsideredtobeexecutedinoneatomicindivisiblestep.Composite(interruptible)$-expressionsconsistofdistinguishedcomponents(simpleorcompositeones)andcanbeinterrupted.

DEFINITION3.1.The$-calculusThesetof$-calculusprocessexpressionsconsistsofsimple$-expressionsandcomposite$-expressions,andisdefinedbythefollowingsyntax:

::=

cost

sendwithevaluationthroughchannelreceivefromchannelsuppressevaluationof

definedcallofsimple$-expressionwithparameters,anditsoptionalassociateddefinitionwithbodyevaluatedatomically

negationofdefinedcallofsimple$-expression

::=

sequentialcomposition

parallelcompositioncostchoice

adversarychoicegeneralchoice

definedprocesscallwithparameters,anditsassociateddefinition

withbody(normallysuppressed);willforce

evaluationofexactlyonce

56E.Eberbach/$-CalculusofBoundedRationalAgents

Thedetailedexplanationsandexamplesof$-expressionsarepresentedbelow:1.Azero

.

Apredefinedprocesssimplyblocksanddoes(returns)nothing(degenerateprocessorinactionwithblocking);fulfillsfunctionofthelogicalfalse,any$-expressiondifferentthanrepresentstrue.Itisaspecialinstanceofemptychoicesandemptyparallelcomposition,thusitisnotlistedseparatelyinsyntaxdefinition.

2.Asilentprocess.

Unlikezeroitneverblocks,butexecutessilentlyreturningnothing(thusitisconsideredtobeunobservable,i.e.,notvisibleorignoredbytheagent).Althoughnotdirectlyobservable,theeffectsofsilentactionscanbeestimatedbycosts.Inparticular,itcanbeusedtoshutdownapartofthe$-expressionmakingitinvisible(transparent)foragivenagent.Itisaspecialinstanceofanemptysequentialcomposition.3.Acost

.

Costfunctioncalculatesacost(thevalueoftheobjectivefunction)associatedwithandused

forsolutionofoptimizationproblems.Thereturnvalueistypicallydefinedinthedomainofrealnumberswithaddedinfinity.Astandardcostfunctionispredefinedinthe$-calculus,howevertheusercandefineowncostfunctions.

4.Asend

andareceive

.

The$-calculusagentsinteractthroughsend-receivepairsastheessentialprimitivesofthemodel.

Sendandreceivealwaysworkinpairsbyhandshakingmessage-passingcommunicationtypicalforprocessalgebras.Ifsendorreceivecannotfindmatchingelement,theyblock.Bothsendandreceiveshouldusethesamenameofcommunicationlink,calledchannel(here),andeachinsendshouldbematchedbyacorrespondinginreceive.

5.Asuppression

.

Itsuppressesevaluationoftheunderlying$-expression(sameasquoteoperationinLisp).6.Auser-definedsimple$-expressioncall

.

anditsassociatedoptionaldefinition

Theseareuser-definedelementsof,,and,i.e.,possibletoevaluateimmediately.Simplecostexpressionswithnameandparameterswillidentifyatomicactionswhichmaybeper-formedbyaprocess.Thestructureofsimplecostexpressionsisneglected,andtheirbodyisconsideredtobeevaluatedatomicallyinoneindivisiblestep,denotedas.

7.Anegationofuser-definedsimple$-expressioncall

.

anditsassociatedoptionaldefinition

thereisassociateditsuniquenegation

canbeexecutedatthesametime(becauseone

ofthemwillblockanditscosttoexecutewillbeequalto).Ofcourse,isdifferentthan

Foreachuser-definedsimplecostexpression

E.Eberbach/$-CalculusofBoundedRationalAgents57

8.Asequentialcomposition

.

Sequentialcompositionisusedwhen$-expressionsareevaluatedinatextualorder.Thisfunction

meansthatifdoesnotblock,thenisevaluatedfirst,next;otherwiseitblocks.Asequentialcompositionbehaveslikefortheemptysequentialcomposition(forand).

9.Aparallelcomposition

.

Thisfunctionevaluatesallsimultaneouslyanditpicksupasubsetofnon-blockedelementsatrandomforevaluation.Ifallblock,thenparallelcompositionblocks(deadlocks).Theemptyparallelcompositionbehaveslike.

10.Acostchoice

andanadversarychoice

.

Thecostchoiceselectsexactlyonewithminimalcosts,andtheadversarychoiceselectsexactly

onewithmaximalcostsforevaluation.Tiesarebrokenrandomly.Anemptycostchoiceandanemptyadversarychoice(for)reduceto.

11.Ageneralchoice

.

Thegeneralchoiceselectsrandomlyexactlyonegeneralchoicebehaveslike.

whichguard

doesnotblock.Theempty

12.Adefinedprocesscall

,anditsassociatedrecursivedefinition

.

Callanddefinitionencapsulateexpressionsinamorecomplexform(likeprocedureorfunction

definitionsinprogramminglanguages).Inparticular,theyspecifyrecursiveoriterativerepetitionof$-expressions.Thedefinitioncreatesorredefinesatemplateobjectnamed,withformalinputparameters,andwiththebody.Thebodyevaluationbydefaultissuppressed,howeveritcanbeforcedtobeevalautedexactlyoncebyapplyingonceoperator.Thedefinitionisevaluatedbyitsassociatedcall,returningnew(calculated)values.Foracall,theremustbeacurrentuniquedefiningequation,wherethenamesarealldistinct.Thedefinitionbodymaycontainfreevariablenames.Inthecallbehaveslike,wheremeansthesimultaneoussubstitutionofforalloccurrencesofin.Thedefinitionprovidesrecursion,sincemaycontainanyidentifier,evenitself.Ifassociateddefinitiondoesnotexist,andthefunctioncallisnotasimplecostexpression,thenthecallblocks.

Theoperatorsandare-binders,i.e.intheprocessesand

theoccurrencesofinarebound,usingusualrulesforscope.Thefreevariablesofdonotoccurinthescopeofanybinderandaredenotedby.Boundedvariablesaredenotedby.Thealpha-conversionofboundedvariablesisdefinedasusual,andrenaming(orsubstitution),where

isdefinedastheresultofreplacingalloccurrencesofinby,

possiblyapplyingalpha-conversiontoavoidcapture.

EXAMPLE3.2.sendandreceivearesimilartopolyadicinputandoutputprefixesfrom-calculus.The

maindifferenceisthatsendandreceivealwayshavetooccurinpairs,i.e.,theyareblockedifexecutedseparately(in-calculus,thisisequivalenttousetherestrictionoperatorenforcingsimultaneouscom-municationofinputandoutputprefixes).Anotherdifferenceisthatcostcanbeusedtofindwhichpairs

58E.Eberbach/$-CalculusofBoundedRationalAgents

willcommunicate.Wewillshowafewexamplesofsuccessfulsend/receive:

,and

,

Wecaneasilydescribematchingfromproductionrules:assumingthatsystemisinstate(andand)andproductionruleif(and)then(and),weshouldgetstate(andand).In$-calculus,wecanexpressthisasfollows:

afterdoublesend/receive(matching)from

andweget.

EXAMPLE3.3.Sendisaformofcommunicationwhichcanreturnvariouscostexpressions(dependingonthechoiceoftheexpressionsentthroughthechannel).Itisequivalenttosendthroughthenoisychannel.Inoneatomicstepanexpressionisevaluated,sent,andreceivedbycorrespondingreceive.Asuppressedsendcanbeconsideredasaspecialcaseofsendthroughanidealidentitychannel.Forexample,let’sconsidersendthroughchannelchangingvalue1to0intransmittedexpression,i.e.,let’sassumethatevaluatesto0:

Iftousesuppressedsendinsteadofa“regular”send,i.e.,(evaluationofwillbesuppressed,andwillreceivevalueandnot0.UsingLispterminology,suppressedsendsuppressesevaluationoftransmittedexpression(equivalenttothequoteoperatorfromLisp).

Sendcansimulatemanyotheroperators.Forinstance,aclassicalone-pointcrossoverfromevo-lutionarycomputationexchangingandinexpressionsand,assumingthat

,canbesimulatedby

,wherecrossover

functionswapsitsargumentsand.Obviously,sendcansimulatemutation-expressionsareevaluated/mutatedwhensentthroughthechannel.

EXAMPLE3.4.Recursivedefinitionprovidesdataandcodeabstractionmechanism.Inparticular,it

canexpressiterativeconstructs.Forexample,itcansimulatethereplicationoperatorfrom-calculus:

andnextcalling.

Thedefinitiontogetherwithonceoperatorallowstoexpressassignment(evaluationonlyonce),e.g.,incrementationofxby1canbewrittenas.

3.2.BehavioralEquivalenceof$-Expressions:StrongandObservationCongruence

Equivalencerelationsareamathematicaltoolforspecifyingabstractionsbyequivalenceclassesthat

identifyelementsdifferingonlyintheirirrelevantproperties.Observationequivalencespecifiesinterac-tiveabstractionsthatignoreunobservableinnerbehavioranddistinguishesobservablebehavior.Milner[57]examinedstrongandobservationequivalenceforprocessescalledbisimulation,whereinthecaseofstrongequivalence,unobservablebehaviorcouldcausemanysideeffects.Inourcase,unobservablebe-haviorisrepresentedbysilent(invisible)action.Thisisimportanttoexpressincompleteknowledgeofanagentaboutotheragentsandanenvironment.Forobservationequivalence,anagentmaynotbeawarethatotheractionsexist,thusfromitspointofviewitwilltreatsuchactionsasnonexistentand/orhavingneutralcost.Instrongequivalenceinfluenceofinvisibleactionswillbeestimatedbycost.Thisiscrucialtoourapproachofinvestigatinganemergingbehaviorofmultipleagentshavingpartialobservability.

E.Eberbach/$-CalculusofBoundedRationalAgents59

Wedefinestrongandobservationbisimulationandcongruenceinaconventionalmanner(see[57]).Strongbisimulationisthelargestequivalencerelationontheclassof$-expressions,suchthatanytwo$-expressionsiff,forall,

whenever

then

and

.

Twoprocessesarestronglycongruentifftheyarestronglybisimilarinanycontext.

Let

Observationcongruenceanytwo$-expressions

isthelargestequivalencerelationontheclassof$-expressions,suchthatiff,forall,

wheneverthen

and

.

i.e.,eachactionofoneprocessismatchedbyasequenceofactionsofanotherprocesswiththesame

visiblecontent(arebisimilar),and,additionally,eachinitialactionoforismatchedbyatleastoneactionoftheother.

Strongandweak(observation)congruenceequateprocesseswhichpossessthesametransitions(countingornottheinvisibleaction)anddeadlocks.Theydifferintheroleofandrequirementsformatchingoffirstactions.Thesedifferencesareimportant,sinceequivalentprocessesshouldhavethesamecost.ThisisconsistentwiththevonNeumann/Morgenstern’sutilitytheory[81].Atthispoint,wedidnottrytoinventanewdefinitionofbisimulation,butrathertoutilizetheexistingonetoshowtheapplicabilityofthebisimulationconcepttothedecision/utilitytheory.Structuralcongruence(definedanddiscussedinSection4.2)impliesstrongcongruenceimpliesobservationcongruence,i.e.,impliesimplies.

4.The$-CalculusOperationalCostSemantics:Meta-LevelControl

Inthissectionwedefinetheoperationalsemanticsofthe$-calculususingaLabeledTransitionSys-tem(LTS)[61]extendedbythe-searchthatcapturesthedynamicnatureandincompleteknowledgeassociatedwiththeconstructionoftheproblemsolvingtree.TheconventionalLTSassumesthatthecompletederivationtreeispossibletoconstructandthesizeofthetreeisoutsideofitsconsideration.The-searchdescribeshowtheproblemsolvingtreeisexpandedandprunedatthemacro-level,andaLabeledTransitionSystemwithInferenceRulesandStructuralCongruencerecordthesuccessiveactionstobeperformedatthemicro-level.Anewnotionhere,comparedtotraditionaltoolsusedforprocess

-search.However,afterthatweleavetheKeller/Plotkin’sLabeledTransitionSystemalgebras,isthe

withoutchanges-ourgoalatthispointisrathernottoexperimentwithsemanticsandvariousequiva-lencenotions,buttore-use(ifpossible)theexistingprocessalgebratools.Forthesamereason,wewillalsoconsidertheclassicalnotionofbisimulationandcongruence.BothaLabeledTransitionSystemandStructuralCongruencewillbeusedasapartofthesearchtreeprocedure(moreprecisely,toselectsimple$-expressionsforevaluationintheexamineandexecutephases).

Thebasic$-calculussearchmethodusedforproblemsolving,the-optimizationisaverygeneralsearchmethodprovidingmeta-control,andallowingtosimulatemanyothersearchalgorithms,includingA*,minimax,dynamicprogramming,tabusearch,orevolutionaryalgorithms[69].Theproblemsolvingworksiteratively:throughselect,examineandexecutephases.Intheselectphasethetreeofpossible

60E.Eberbach/$-CalculusofBoundedRationalAgents

solutionsisgenerateduptostepsaheadandwide,andagentidentifiesitsalphabetofinterestforoptimization.Thismeansthatthetreeofsolutionsmaybeincompleteinwidthanddepth(todealwithcomplexity).However,incomplete(missing)partsofthetreearemodeledbysilent$-expressions,andtheircostestimated(i.e.,notallinformationislost).Theabovemeansthat-optimizationmaybeifsomeconditionsaresatisfiedtobecompleteandoptimal.Intheexaminephasethetreesofpossiblesolutionsareprunedminimizingcostofsolutions,andintheexecutephaseuptoinstructionsareexecuted.Moreover,becausethe$operatormaycapturenotonlythecostofsolutions,butthecostofresourcesusedtofindasolution,weobtainapowerfultooltoavoidmethodsthataretoocostly,i.e.,the$-calculusdirectlyminimizessearchcost.Thisbasicfeature,inheritedfromanytimealgorithms,isneededtotackledirectlyhardoptimizationproblems,andallowstosolvetotaloptimizationproblems(thebestqualitysolutionswithminimalsearchcosts).

Wewilladdresstheproblemsofcompleteness,optimality,andtotaloptimalityofproblemsolvingsearchformultipleagentsinthe-optimizationperformedbythe$-calculusmeta-control.Theagentsevaluate$-functionsusingvaluesfortherelevantfactors,whichexpressthecurrentphysicalenviron-ment.Threenaturallimitsexisttothisapproach:notallrelevantfactorscanalwaysbeknownwithsufficientcertainty,thephysicalenvironmentissubjecttochange,andthereisalimitwhatcanbecom-putedassumingfinitetimeandmemory.Forthatreason,welimitouroptimization,performingwhatwe

-optimization.Thevariablereferstothelimitedhorizonforoptimization,necessaryduetocallthe

theunpredictabledynamicnatureoftheenvironment.Thevariablereferstoareducedalphabetofin-formation.Noagenteverhasreliableinformationaboutallfactorsthatinfluenceallagentsbehavior.Tocompensateforthis,wemaskfactorswhereinformationisnotavailablefromconsideration;reducingthe

-optimizationtofindthestrategywiththealphabetofvariablesusedbythe$-function.Byusingthe

lowest$-function,meta-systemfindsasatisficingsolution,andsometimestheoptimalone.Thisavoidswastingtimetryingtooptimizebehaviorbeyondtheforeseeablefuture.Italsolimitsconsiderationtothoseissueswhererelevantinformationisavailable.

Thustheoptimizationprovidesaflexibleapproachtolocaland/orglobaloptimizationintimeorspace.Technicallythisisdonebyreplacingpartsof$-expressionswithinvisible$-expressions,whichremovepartoftheworldfromconsideration.Forobservationbisimilarity/congruence,silent$-expressionshaveneutralcost(0forthecrispcostfunction)anddonotparticipatedirectlyinoptimization.Theyareindirectlyanintegralpartof$-expressions,andinfluencetheresults.

4.1.The

-OptimizationSearch

The-searchcanbeusedbothforsingleandmultiplecooperativeorcompetitiveagentsworkingonline()oroffline().The$-calculusprogramsconsistofmultiple$-expressionsforseveralagents.Given:

-analphabetofsimple$-expressionsoftheuniverseconsistingofanenumerablenumberofagents(includinganenvironment),,.Theagentpopulationsizewillbedenotedby.

-analphabetofsimple$-expressionsofthei-thagent,,expression,andoptional(explicit)goals,animplicitdefaultgoalis

-aninitial$-.

-ascopeofdeliberation/interestsofthei-thagent,i.e.,asubsetoftheuniverse’ssimple$-expressionschosenforoptimization.Allelementsofrepresentanenvironmentorirrelevant

E.Eberbach/$-CalculusofBoundedRationalAgents61

partofanagent(s),andwillbecomeinvisible(replacedby),thuseitherignoredorunreachableforagivenagent(makesoptimizationlocalspatially).Expressionsoverwillbetreatedasobservationallycongruent(costofbecomesneutral,e.g.,typicallyequal0).Allexpressionsover

willbetreatedasstronglycongruent-theywillbereplacedbyandalthoughinvisible,

theircostwillbeestimatedusingbestavailableknowledgeofanagent(maytakearbitraryvaluesfromthecostfunctiondomain).

-acostfunctionperformancemeasure(selectedfromthelibraryoruserdefined).Itconsistsoftheproblemspecificcostfunction,asearchalgorithmcostfunction,andanaggregatingfunction.Typically,auserprovidescostofsimple$-expressionsoranagentcanlearnsuchcosts(e.g.,byreinforcementlearning).Theuserselectsordefinesalsohowthecostsofcomposite$-expressionswillbecomputed.Typically,forexample,

,,,

whereistheprobabilitytochoose,andsoon.Thecostofthesearchtreeisthefunctionofitscomponents:costsofnodesandarcs.Thisallowstoexpressboththequalityofprograms(rewards)andsearchcost.

-abranchingfactorofthesearchtree,i.e.,themaximumnumberofgenerated

childrenforaparentnode.Forexample,hillclimbinghas,forbinarytree,and

isashorthandtomeantogenerateallchildren(possiblyinfinitemany).

-representsthedepthofdeliberation,i.e.,thenumberofstepsinthederivation

treeselectedforoptimizationintheexaminephase(decreasingpreventscombinatorialexplo-sion,butcanmakeoptimizationlocalintime).isashorthandtomeantotheendtoreach

meansomittingoptimization(i.e.,theagoal(maynotrequireinfinitenumberofsteps).

emptydeliberation)leadingtoreactivebehaviors.Similarly,abranchingfactorwillleadtoanemptydeliberationtoo.Stepsconsistofmultisetsofsimple$-expressions,i.e.,aparallelexecutionofoneormoresimple$-expressionsconstitutesoneelementarystep.

-thenumberofstepsselectedforexecutionintheexecutephase.For

stepslargerthanwillbeexecutedwithoutoptimizationinreactivemanner.Forexecutionwillbepostponeduntilthegoalwillbereached.

Thedefaultgoalistofindapairof$-expressions,i.e.,anypair

being

whereisaproblem-specificcostfunction,isasearchalgorithmcostfunction,andisan

aggregatingfunctioncombiningand.Thisisthedefaultgoalfortotaloptimizationlookingforthebestsolutionswithminimalsearchcosts.Itisalsopossibletolookfortheoptimalsolutiononly,i.e.,thebestwithminimalvalueof,orthebestsearchalgorithmwithminimalcostsof.

Thedefaultgoalcanbeoverwrittenbyanyotherterminationcondition(intheformofanarbitrary$-expression)likethemaximumnumberofiterations,thelackofprogress,etc.

DEFINITION4.1.The-SearchThe-searchi-thagent

universeofagentpopulationandworkingintimegenerations

,

,fromanenumerable

isacomplex$-expression

62E.Eberbach/$-CalculusofBoundedRationalAgents

(meta-procedure)consistingof,,,,,,,andconstruct-ingsolutions,itsinput,frompredefinedanduserdefinedsimpleandcomplex$-expressions.Forsimplicity,wewillskiptimeandagentindicesinmostcasesifitdoesnotcauseconfusion,andwewillwrite,,,,and.Eachi-thagentperformsthefollowing-searchprocedure

inthetimegenerations:

/*initializeand*/

/*basiccycle:select,examine,execute*/

whereistheselect-examine-executecycleperformingthe-optimizationuntilthegoalissatisfied.

Atthatpoint,theagentre-initializesandworksonanewgoalinthestyleoftheneverendingreactiveprogram:

/*looprecursivedefinition*/

E.Eberbach/$-CalculusofBoundedRationalAgents63

searchtreewiththebranchingfactorandstepsdeep(atmost)overalphabetstartingfromcurrentstate.Intheconstructionofthederivationtreereplace(perhapsbyexchangingmessageswithotheragents)$-expressionshiddenbyinpreviousselectphasetotherealvaluesandlearntheircosts.Intheexpansionreplaceallsimple$-expressionswhichdonotbelongtoby(i.e.hidethem-maketheminvisible-theywillbetreatedasobservationallycongruentwithneutralcost(e.g.,equal0).Replacealso$-expressionswhichareatboundarydepthlargerthan,orbelongingtoby,andestimatetheircosts,i.e.theywillbetreatedasstronglycongruent.

4.ExaminePhase:

Forstrongcongruence,i.e.,actionsbelongingto,useestimatesorprecisevaluesofcostsforhidden(by)$-expressions(theseareexpressionsbelongingtootheragentsoroutsidethedepthorwidthofthesearch).Forobservationcongruence,i.e.,actionsperformedbytheagentbutoutsideofitsinterest,use.

Prunethesearchtreebyselectingpathswithminimalcostincostchoicesandwithmaximalcostinadversarychoices.Tiesarebrokenrandomly.

5.ExecutePhase:

If(offlinesearch)andgoalhasnotbeenreachedintheSelect/ExaminePhase,pickupthemostpromisingleafnodeofthetree(withminimalcost)forexpansion,i.e.,makeitacurrentnodeandreturntoSelectPhase.If(offlinesearch)andgoalhasbeenreachedintheSelect/ExaminePhase,executeoptimaluptothegoalnode.If(onlinesearch),executeoptimaluptoatmoststeps.Ifexecutioninterrupted,and,decreasebythevalueproportionaltotheremainingsteps

decrease.Ifexecutionnotinterruptedincreasepending.Iforif

increase.Ifcostofsearch(costofand)toolargedecreaseand/or,otherwise

-search,includingcostsofsimple$-expressions,,increaseit.Modifyotherparametersof

iftheyhavechanged.

REMARK4.2.SomeRemarksonthe

-Search

Theideal(butunrealistic)situationwouldbeiftheagentworkedwithand,

i.e.,toconsideracompletesearchtreeforeverything.However,inthecomplexdomainsthisisnotpossible,andandhavetobesmall.Alsotheactionsofotheragentsveryoftenareignored.Tocompensateforthat,theestimatesofmissingparts()areused.Alsonon-algorithmicsolutionsofundecidableproblems(notthesubjectofthispaper),requireeithertrulyinfinitesearchtrees(withaninfinitewidthand/ordepth)orwithnon-implementable(oracle-type)subtrees/branches.

The-optimizationisverycloselyrelatedtothenotionoftheUniversalTuringMachine,i.e.,TuringMachineabletosimulateanyotherTuringMachine[77].Notethatinputto-searchcanbeanothersearchalgorithm(havingitsowninput).Insuchaway,the-optimizationcansimulatemanyothersearchalgortihms.Inthephase,infact,anewsearchalgorithmcanbecreated(i.e.,theoldcanbeoverwritten),andbeingcompletelydifferentfromtheoriginal-search.Theoriginal-searchchangesthevaluesofitscontrolparametersmostly,i.e.,,butitcanmodifyalso,,,and$.

E.Eberbach/$-CalculusofBoundedRationalAgents

Notethatallparameters,,,,,andcanevolveinsuccessiveloopiterations.Theyaredefinedasthepartofthephase,andmodified/updatedattheendoftheExecutephase.Notethatinageneral,theyarenotapartofthe$-calculussyntax,becausetheyareassociatedwithaspecificchoiceofthemeta-system:a-optimizationsearch.Foranothermeta-system,differentcontrolparametersarepossible.

Allparametersaremodifiedasthepartof-optimization.Theideaisthesameasself-adaptation

usedtoguideevolutionarysearch[1].Inevolutionarysearch(e.g.,evolutionstrategies)ratherthanrequiringhumanoperatorstosetcontrolparameters,evolutionitselfcanguidethesearchforthebestwaytosearch,i.e.,for,whereisobjectivevalues,isstrategy,anewstrategyisalsosubjecttoevolution,andnewobjectivesare.Notethatfunctionsandformanew-secondlevelofmeta-control.

Inthe$-calculus,anautonomousagentisresponsibleforchangeofthecostfunction,itsatomicactions,whichactionsaremodified-alphabet.Thisshouldbedonebytheagentintheinitialization/re-initializationphase.Simplytheagentshouldknowandhavethechoice,whichactionsitwantstoimprove,whetherisinterestedintakingintoaccountactionsofotheragentsornot,andwhetherisinterestedinsolutionoptimizationonly,ortotaloptimization.However,changesinthedepthofoptimization,depthofexecution,andbranchingfactoraredoneasthepartofthefeedbackfromtheexecutionoftheselect-examine-executeloop.Forexample,ifexecutionisinterrrupted,thenshouldbedecreasedinanappropriateway.Ifcostofsearchbecomestoohigh,thenand/orshouldbedecremented,otherwiseincrementedinthenextiterationoftheloop.Ofcourse,itispossiblethatanagentwillinitializeand/ortowrongvalues,e.g.toinfinity,butafeedbackcontrolfrom-searchwillcorrectthisinefficiency(costofsearchwillbetoohigh)bydecreasing,andcostofsearchislargerforlarger.Asthepriceofdecreasingvalueofandincreasesearchefficiency,wedecreasethechanceoffindingglobaloptimum.However,inspiteofthefinitehorizonofsearch(finitevalues)ifsomeconditionsarefulfilled,agentswillstillbeabletoachieveglobaloptima.Ofcourse,itpaysoff(searchwillbeshorter)iftheguessofvalueiscorrectfromthebeginning.Theinitialchoiceofcanbedonebasedonanestimatedcomplexityproblemtosolve,i.e.,forsimpleproblems,forcomplexproblems,verycomplexproblems,nottimefordeliberationatall:(reactonly).

Althoughtheuseofestimateshassomeanalogieswiththeinformativesearchheuristics(e.g.,Nilsson’sbestpathA*algorithm[33]orIDA*[69]),therearebasicdifferences.Firstly,ithas

donotparticipatebeendevelopedformultipleagents.Secondly,otherconstructorsbesides

activelyinoptimization.Thusnotonlyisanoptimalpathgenerated,buttheoptimalprogram/$-expressionwherenondeterminismhasbeenresolved.Thirdly,themeta-systemforcanexecutewrongchoicesin,becauseitmaynotpostponetheexecutionuntilthewholederivationtreeisfound.Itmayreturntothecorrecttrackeitherbypostponingexecutionorcorrectionafterexecutionofwrongcostchoices.Finally,thecostofsearchmayalsobeoptimized.

Thecaseofisequivalenttoaone-stepdeepderivationtree,andthecaseis

equivalenttoexpandingthederivationtreeuntilgoalexpressionisreached.Thecasecoversreactivesystems,wherethesystemselectsandexecutesthenextactionwithoutdeliberation.Thus

E.Eberbach/$-CalculusofBoundedRationalAgents65

thealgorithmcoversbothlimitingcasesandeverythinginbetween.Wecallthisacostfunctionwherethecostfunctionisevaluatedonceforsteps.

Afterthegoalwithminimumcostisreached,thesystemreinitializesandlooksforanewmini-muminsteadofterminating.Thisisthefeatureofreactivesystemsandagents,ingeneral.The

reinitializationdoesnotneedtostartfromscratch,butmaykeepmemorywhathashappened(likeinPersistentTuringMachines[29]orlikeinInternetserverswhichdonotclearitsglobalstatebecauseanewclientrequestedanewtransaction).

4.2.StructuralCongruence,LabeledTransitionSystemandInferenceRules

Let’snowdefinethenotionsofstructuralcongruenceandLabeledTransitionSystemusedintheexamineandexecutephasesofthe-optimization.

DEFINITION4.3.StructuralcongruenceTwo$-expressionsandinthe$-calculusarestructurallycongruent,written,ifwecantransformoneintotheotherbyusingthefollowingequations:

1.

if

is-convertibleto

,

2.doublesuppressionlawfor:3.abelianmonoidlawsfor

,

,

::

,

,,

4.abelianmonoidlawsfor

,

,

5.lawsfor

:

,

,

,

6.abelianmonoidlawsfor

,

:

,

,

7.lawsfor

,

,

8.distributivelawsfor

and

:

,

,

,

,

,,

9.lawsfor

if

DEFINITION4.4.LabeledTransitionSystemALabeledTransitionSystemtakestheform

whereisasetofstates,isasetofactions(labels)andeachisasubsetof,called

anactionrelationover.Wecallanactionof;inthiscaseissuccessorofandisan-successorof.Forwedefine,andwecallatransitionof;thenisaderivativeofandisat-derivativeof.

66E.Eberbach/$-CalculusofBoundedRationalAgents

Letbesimplecostexpressions,anddenotesimplecostexpressionswithaddedsilentprocess.WedefinetheLTS,whereare$-expressions,arenonemptymultisetsofsimplecostexpressions(including).Theactionrelationsaredefinedtobewiththesmallestcostvalueoftransitionswith

beinganinitialcostexpression,andwhichobeythefollowingrules,inwhichtheactionbelowthelineistobeinferredfromthoseabovetheline:

GIF:

AIF:

in

pairs

and

structuralcongruence

wasdefinedbefore

Theseinferencerulesdescribehow$-expressionswillbeselectedforexecution.Generalchoice

selectsanalternative,whichisnotblocked,atrandom.Theotherchoicesarediscarded.CostchoiceCIFselectsalternativewiththeminimalcost,andanalogouslyadversarychoiceAIFpicksupwiththemaximalcostvalue.

Sequentialcompositionhastwomainforms:foruserdefinedsimple$-expressions,send,costandsilentprocessSEQ1andforreceiveSEQ2.ParallelcompositionPARexecutesamultisetofactionstheydonotblock.Asimpleactionanditsnegationcannotoccurinamultiset.Sendandreceivealwaysoccurinmatchingpairs.AnalternativeruleforPAR,insteadofanypossiblesubset(multiset)ofsimple$-expressionsselectedforexecution,couldselectamaximumsubset,orthesubsetwithminimalcosts.

Structuralcongruencecovers,inparticular,theevaluationoftherecursivefunctioncall,andde-creasesthenumberofinferencerules.

Insteadofseekingthesmallestderivationtree,the$-calculuslooksforthesetoftransitionswithminimalcost.Ifallactionshavethesamecost,thenthederivationtreefoundbythe$-calculuswillbeidenticaltothederivationtreefoundusingthesmallestactionrelation.

E.Eberbach/$-CalculusofBoundedRationalAgents67

EXAMPLE4.5.Toillustratetheoperationalcost(minimalcostactionrelation)semanticscomparedtothetraditional(smallestaction)operationalsemantics,considerthefollowingderivationtree:

Weassumethat

costofthesilentactioniszero

,thusactionhasbeenselected.Wealsoassumethat

,i.e.,thederivationofthetreehasbeenterminated.

Isitpossibletofindanoptimal/totallyoptimal/searchoptimalsolutionusingapproximatecostvaluesinspiteofsomesub-optimaldecisions?Itissometimespossible,dependinghowgoodourcostestimatesare,andwhetherwecountcostofpreviousactionsordisregardthem.Wewillpresentsomeresultson

-optimization.completeness,optimalityandtotaloptimalityofthe

DEFINITION4.6.Locallyfinitegraphsarethegraphswiththefinitebranchingfactorandhavinggoal

statesatthefinitedepth.

LabeledTransitionSystems(LTS)for$-expressions,ingeneral,mayhaveinfinitebranchingfactor(enumerablegeneral,adversary,orcostchoices,parallelcomposition),andthedepthofrecursioncanbeinfinite(enumerablesequentialcomposition).Usuallytoanalyzeorexecuteoperatorsworkingoninfinitenumberofargumentsrequiresinfinitetime(resources).ThuswewillrestrictourconsiderationtolocallyfiniteLTS.

DEFINITION4.7.Forperfectcommunicationanagentlearnsthecorrectcostvalueofsimple$-expressions(costvaluesofforstrongcongruence)afterexpanding“”-nodes.

NotethatsimilarassumptionsaremadeformostconventionalsearchalgorithmslikeA*orminimaxwhereexpandednodesareabletolearncorrectvaluesofcostsofactions.Muchmoredifficultistokeepsuchanassumptionforthe$-calculuswithmultipleagentscommunicatingbymessage-passing,wheretolearncorrectvaluesofcostsofotheragentsrequiressensingbypairssendandreceive(theonlywaytogetinformationaboutanotheragentin$-calculusisbyinteraction).

THEOREM4.8.(ONCOMPLETENESSOFTHE-OPTIMIZATIONSEARCH)ForlocallyfiniteLTS,perfectcommunication,branchingfactor,anddepthofdeliberationthe-optimizationsearchcanbecompletependingthatcostsofactionsareadmissibleand.PROOF.Let’ssetthegoal/terminalstatetotheoptimumof(i.e.,welookforthebestqualitysolution).The-optimizationexpandsall$-expressionnodesuptothedepthinorderofincreasing,thusitmusteventuallyexpandthegoalstate.Anyalgorithmthatdoesnotexpandallnodesinthecontours(formedby$-expressionswiththesamecost)betweentherootandthegoalcontourrunstheriskofmiss-ingtheoptimalsolution.Byadmissibilityrequirementweguaranteethatsearchwillnotbeprematurelyterminated,andoptimalpathswillbeexpanded.Inotherwords,actionspreserveallinformationaboutmissingpartsofthecompletesearchtree,inspiteofand/or.Forexecutionispostponeduntilthegoalisreached(forlocallyfiniteLTSwithperfectcommunication,itwillbereachedinfinitenumberofsteps),andthetreenodescanberememberedtoallowtoexpandremainingnodesifcostestimateswerewrong.For(possiblywrongchoices)areexecuted,thusthesolutionmaynotbeoptimal,i.e.,thegoalmaynotbereached,thussearchmaybeincomplete).

Forinfinitederivationtreesorwhenanagentwillnotbeabletolearncorrectvaluesofcosts,the

-optimizationwillbeincomplete,becauseanagentmaynotreachthegoalatinfinitedepthinthefinitenumberofsteps,andneverwillbesurewhetheritschoicewascorrect.

68E.Eberbach/$-CalculusofBoundedRationalAgents

Wewilldistinguishbetweentemporalandspatialoptimizationusing,,andvaluesascriteria.Becausemeasuresadiscretetimeasthenumberofsteps,thusitcanbethoughtasrepresentingatemporalaspect.Ontheotherhand,(abranchingfactor)and(anoptimizationalphabet)canbethoughtasrepresentingaspatialaspectofoptimization.

DEFINITION4.9.(Ontemporalglobality/localityofthe$-calculusagentsearch)The$-calculus-thagentwillperformatemporallyglobalsearchiff,andatemporallylocalsearchiff.

DEFINITION4.10.(Onspatialglobality/localityofthe$-calculusagentsearch)The$-calculus-thagentwillperformaspatiallyglobalsearchiffand,andaspatiallylocalsearchiff

or.

Notethattherecanbevariouslevelsoftemporallocality-themaximumleveloflocalitywillbe.Notealsothattherecanbevariouslevelsofspatiallocality-themaximumlevelofspatialfor

localitywillbeforor.

Let’sconsideronlyreachablegoalstates,i.e.,suchgoalstatesthatarenodesofthesearchtree.Forunreachablegoalstates,ofcourse,searchcannotbecomplete.

REMARK4.11.Thespatiallyglobalandtemporallyglobal-searchiscompleteforreachablegoalstates.Thejustificationisquitesimple-thiswillbesimplyanexhaustivesearch,andanexhaustivesearchwillallowtoreachanyreachablestate,includingthegoalstates.

Wecanobservethattemporallylocalandspatiallylocal-searchcanbecompletependingthatanincompletetreewillcontainenoughinformationtoapproximatethecompletesearchtree.Thisapprox-imationofthemissingpartofthetreeisdonein$-calculusbyinvisible$-expressionswithestimatedcostsofthemissingpartofthetree.

REMARK4.12.Iftheestimatesofinvisible$-expressionsaresetinsuchawaythatsearchwillnotmissanygoalstate(i.e.,strongcongruencewillbeused),theninspiteoflocality,the-searchwillbecomplete.Thensilent/invisibleactionsapproximatemissingpartsoftheproblem-solvingtree,andnocrucialinformationtoreachthegoalwillbelost.

REMARK4.13.Ifthegoalconditionissetsimplytostopafterafixednumberofiterationsofthe-search,thenthe$-calculussearchbecomesobviouslycomplete.However,anotherpossiblestoppingcriterion-thelackofimprovementofthecostfunctionforseveraliterations-maynotguaranteecom-pletenessunlesssupplementedbymonotonicityrequirement,andperhapsreachingthegoalconditionmaybeachievedininfinitetime,oroscillatearoundanoptimum.

Settingthedefaultgoalconditiontosomethingotherthantheoptimumofthecostfunctionwillresultthatthe$-calculussearchmaybecompletebutnotoptimal.

Thefollowingfourtheoremsdescribetheresultsforoptimizationcaringonlyforthequalityofsolu-tionanddisregardingcostofsearch,i.e.,thei-thagentlooksfortheminimumof.

THEOREM4.14.(ONTEMPORALLYLOCAL&SPATIALLYLOCALOPTIMIZATION)ForlocallyfiniteLTS,perfectcommunication,andadmissiblecostfunction,thetemporallylocal&spatiallylocal-optimizationcanfindanoptimalsolution.

E.Eberbach/$-CalculusofBoundedRationalAgents69

PROOF.Fortemporallylocaloptimizationandforspatiallylocaloptimizationor

.Ifthedepthoftheoptimalsolutionislessthanthentheoptimalsolutionisfoundbyexhaustive

search.Inspiteoffinitevalueof,missingbrancheswilllookmorepromising(byadmissibility)andwillbeexpandedinnextloopiterations.Iftheoptimalsolutionisatthedepthlargerthan,thenassumingthatthemostpromisingnode(thecheapestone)willbeselectedforexpansioninanewiteration,because-optimizationexpandsall$-expressionnodesinorderofincreasing,thusitmusteventuallyexpandtheoptimalgoalstate.If-optimizationreachedanothergoalstatewhichisnotoptimal,itscosthastobelargerthentheestimateofcostofoptimalpath(byadmissibilityassumption).Thusthe-optimizationwilldetectit,andcorrectandexpand.ThisprocessiffinitebylocalfinitenessofLTSassumption.

THEOREM4.15.(ONTEMPORALLYLOCAL&SPATIALLYGLOBALOPTIMIZATION)ForlocallyfiniteLTS,perfectcommunication,andadmissiblecostfunction,thetemporallylocal&spatiallyglobal-optimizationcanfindanoptimalsolution.PROOF.Fortemporallylocaloptimization,andforspatiallyglobaloptimizationand

.Theproofsimilartotheprevioustheorem,butnowbecausetheagentdoesnotneed

toworryaboutexpansionofmissingbranches(approximatedbysilentactions).Theagent’sinterestscoveractionsofallotheragents.Herecrucialistheassumptionaboutperfectcommunication,i.e.,thattheagentisablebycommunicationwithanotheragenttogetthecorrectvalueofanotheragent’ssimple$-expressioncost(hiddenby).

THEOREM4.16.(ONTEMPORALLYGLOBAL&SPATIALLYLOCALOPTIMIZATION)

ForlocallyfiniteLTS,perfectcommunication,andadmissiblecostfunction,thetemporallyglobal&spatiallylocal-optimizationcanfindanoptimalsolution.PROOF.Fortemporallyglobaloptimization,andforspatiallocaloptimizationor

.Herecrucialisthatmissingbrancheswillbeapproximatedbyandbyadmissibilitytheywill

beexpandedinnextloopiterations.

THEOREM4.17.(ONTEMPORALLYGLOBAL&SPATIALLYGLOBALOPTIMIZATION)

ForlocallyfiniteLTS,perfectcommunication,andadmissiblecostfunction,thetemporallyglobal&spatiallyglobal-optimizationcanfindanoptimalsolution.PROOF.Fortemporallyglobaloptimization,andforspatiallyglobaloptimizationand

.Thederivationtreebuiltintheselectphasecontainsthecheapestgoalstate,andtheagentis

interestedinoptimizationofitsownactionsandallotheragentsactions.Onceagain,perfectcommuni-cationiscrucialandbetterinformationcanbereceivedincrementallybyaseriesofinteractions.Trulyagenthasperfectknowlegde,acompletederivationtree,thustheoptimumwillnotbemissed.

Thefollowingnextfourtheoremscovertotaloptimality.Theretheagentisinterestedbothinthebestqualityofthesolutionandtheminimalresourcesusedforitsfinding,i.e,theminimumof

.

THEOREM4.18.(ONTEMPORALLYLOCAL&SPATIALLYLOCALTOTALOPTIMIZATION)

ForlocallyfiniteLTS,perfectcommunication,andadmissiblecostfunction,thetemporallylocal&spatiallylocal-optimizationcanfindatotaloptimalsolution.

70E.Eberbach/$-CalculusofBoundedRationalAgents

PROOF.Theproofwillbesimilarasforlocallyspatialandlocallytemporaloptimization-onlydifferentcostmetricsareused.However,nowbothqualityofsolutionsandsearchcostsaretakenintoaccount,thustotallyoptimalsolutioncanbedifferentfromtheoptimalsolution.

THEOREM4.19.(ONTEMPORALLYLOCAL&SPATIALLYGLOBALTOTALOPTIMIZATION)

ForlocallyfiniteLTS,perfectcommunication,andadmissiblecostfunction,thetemporallylocal&spatiallyglobal-optimizationcanfindatotaloptimalsolution.

THEOREM4.20.(ONTEMPORALLYGLOBAL&SPATIALLYLOCALTOTALOPTIMIZATION)

ForlocallyfiniteLTS,perfectcommunication,andadmissiblecrispcostfunction,thetemporallyglobal&spatiallylocal-optimizationcanfindatotaloptimalsolution.

THEOREM4.21.(ONTEMPORALLYGLOBAL&SPATIALLYGLOBALTOTALOPTIMIZATION)

ForlocallyfiniteLTS,perfectcommunication,andadmissiblecostfunction,thetemporalglobal&spatialglobal-optimizationcanfindatotaloptimalsolution.

Wewillpresentafewsimpleexamplesoflocalandspatialoptimizationforillustration.

EXAMPLE4.22.(GLOBALTEMPORAL&LOCAL/GLOBALSPATIALOPTIMIZATION)

Letusconsiderasimplesystemconsistingofasingleagentsituatedinacertainenvironmentdescribedbythefollowing$-expression:

,andlet’sassumespatiallocaloptimization(representsactions

executedbyanagent,isassumedtobeexecutedbyanenvironment),,

(astandardcostfunctionasdefinedinSection5.1isused),

,andtheimplicitgoalistofindanoptimalsolution.

Intheselectphaseacompletetreeisconstructed(temporalglobaloptimization),andthebestsolutionisfoundintheexaminephasefortheagent:

.Strategy:forlocallyspatialoptimization(istreatedasobservationallycongruentwithcost0)givetoenvironmentachancetoacttoexecuteandnextanagentwillexecute,becausefromtheagent’slocalperspectivethisistheoptimalstrategy.Notethattheenvironmentwillsharethesameinitial$-expression(onlywillbeindifferentplaces).Weassumedanactiveenvironment(performingoptimization),although,moretypicallyanenvironmentwillbepassive:or.

Forgloballyspatialoptimizationperformedbythefirstagentistreatedasstronglybisimilar(fromtheglobalpointofviewtakingintoaccountbothanagentandanenvironment,i.e.).Theagentnowcaresaboutthecostofhiddenby.Ithasto“expand”itbyinteractionwiththeenvironment(eitherbyqueryorsensing).Byperfectcommunicationassumption,itwillbeabletolearnitsrealcost2(frominformationreceivedfromtheenvironment),andtoscheduleforexecutioncheaperbranch.

EXAMPLE4.23.(TEMPORALLYLOCAL&SPATIALLYGLOBALOPTIMIZATION)

Wewillillustratethecasefor,.Letasingleagentbedescribedbythefollowing$-expression:,andlet,(let’smakethesituationclean,i.e.,wedonotcareaboutpartitioningworldintoagentandenvironmentparts)

,butthesystemknowsestimatesonly(strongcongruence).

E.Eberbach/$-CalculusofBoundedRationalAgents71

Intheselectphaseaderivationtreewillbeconstructedonestepdeepandcontinuationrepresentedby:

.Intheexaminephase:willbeselectedforexecution,because.

Thusthesystemintheexecutephasewillmovefromto.Thesystemwillreturntotheselectphase,andnowwillbeselectedforexecutionbecause(the

).system“remembers”historyincostscomputationfor,i.e.

Afterexecutionof,thesystemwilllearnthatitscostis6not4,butthesystemwillstopbecause

.Thesystemfailedtoexploreacheaperchoiceandnext.Notethattherequirement

foradmissibilitywasnotfulfilled,i.e.,costofwasoverestimated.

However,ifcostofwasunderestimated(forinstance,to),thentheproperpathwouldbeexplored.

Therequirementforadmissibilityissometimesdifficulttoenforce.Sameappliestoperfectcommu-nicationortolessextenttotherequirementoffinitenessofthesearchtree.Thuscomputationmaynotreachtheoptimalstate.

,,or,i.e.,inspiteNotealsothatanemergingglobaloptimization(for

ofincrementalexpansionofthederivationtreeorconsideringonlyasubsetofsimple$-expressions)ispossiblependingthatcostfunctionsareadmissible(wedonotoverestimatecostsaboveksteps,ofmissingbranchesb,oroutside),communicationisperfectandderivationtreesarefinitelylocal.

5.CostFunctions:PerformanceMeasureandPrediction

Cost(utility)functionsrepresentauniformcriterionofadaptationandcontrol.Theyhavetheirrootsin

thevonNeumann/Morgenstern’sutilitytheory[81].Themain(butrathertechnical)differencecomparedtotheutilitytheoryisthatweperformuniformlyinthestyleofcontroltheoryminimizationofcostsratherthanmaximization.Intheutilitytheoryandthedecision-theoreticmetareasoning[70]fromgainsaresubtractedcosts,in$-calculusisopposite:fromcostsaresubtractedgains.

Costs/utilitiesmayhavemanypossibleinterpretationsandformulas.Forthisreasonnosingledef-initionisenforcedbythecalculus,Nevertheless,typicalcostsarefunctionsrepresentingtime,money,fitness,error,probability,possibility,belief,complexity,distance,energy,entropy,resources,etc.Costsusingprobabilitiesofcostexpressionsleadtoaprobabilistic$-calculus,thecostsusingthefuzzysetscharacteristicfunction[88]ortheroughsetsmembershipfunction-leadtoafuzzy-logic$-calculusorarough-sets$-calculus.

Costscanbeexplicitorimplicit(endogenouslikeinEchosystem[35]).Explicitcostsmeasurehowwellthesystemperformsinitsenvironment.Implicitcostsfulfillafunctionsimilartoexplicitcosts,withtheenvironmentprovidingfeedback.

Performanceofmultipleagentsortheinfluenceofseveralfactorscanbecombinedinonecostformultiobjectiveoptimization,ortheycanbekeptseparateasavectorofcomponentcosts.Inmultimodaloptimizationwelookformultipleoptimaforagivencostfunction.

Costsmaybepositive,and/ornegative(payoff,gains).Anydomainwherealinearorderisdefinedisfeasible.However,mostcommonlyrealnumbersareused.Normalizedcostsaredefinedonunitinterval.Havingbothpositiveandnegativecostsallowsalloptimizationproblemstobeexpresseduniformlyin$-calculusascostminimization.Insteadtochangethesignofthecostfunction,formaximizationproblemsifthereexistsanupperboundontheobjectivefunctionitisalwayspossibletoconvertittoaminimizationproblembysubtractingfromtheupperboundtheobjectivefunction,andusingtheresult

72E.Eberbach/$-CalculusofBoundedRationalAgents

asacurrentcostfunction.Ifweareinterestedtohaveonlynonnegativecosts,itispossibletoshiftallcoststononnegativevaluesbyaddingtheabsolutevalueofthelowerboundofthecostfunction(pendingthatitexists).

Itisassumedthatcostsdefinedonrealnumbersobeyallaxiomsofutilities,i.e.,orderability,transi-tivity,continuity,substitutability,monotonicity,anddecomposability(seee.g.[69]).Axiomsofutilities,togetherwiththeutilityprincipleandmaximumexpectedutilityprinciple,translateinto$-calculusax-ioms,costprinciple,andminimumexpectedcostprinciple,anddescribetherelationsbetween$-calculuscostchoice,generalchoice,andcostoperators.Inparticular,theyguarantee

Costprinciple:ifandagent’spreferencesobeytheaxiomsofutility,thenthereexistsareal-valued

ifandonlyifispreferredtofunction$thatoperateson$-expressionssuchthat

,andifandonlyiftheagentisindifferentbetweenand.

MinimumExpectedCostprinciple:saysthatthecostforanondeterministicactionwithpossibleoutcomestatesreachedwiththeprobabilityiscompletelydeterminedbyprobabilitiesandcosts(isthesumofprobabilitiesofeachoutcometimesthecostofeachoutcome),andarationalagentshouldchooseanactionthatminimizestheagent’sexpectedcost:.

Tocomputethecost,weusethefollowingprinciple:“thecostoftheproblemconsistingofsubprob-lemsisthefunctionofcostsofsubproblems”,whatiscalledinthetermsoftheutilitytheoryseparabilityofcosts.Thisfunctionmaybedifficulttofind,socostmayalsobeassignedtotheprogramasthewhole.

Letbethesetof$-expressions.Theuserspecifiestheinitialcostsofallsimpleterminals,func-tions,andmodifications(costsofsimplecostexpressions-elementsfrom,and),ortheyarederivedonthebasisofstatisticalprofiling.Theycanbelearnedusingmethodsfromadaptivedynamicprogramming,temporaldifferencelearning,orQ-learning[69],i.e.,costsaredynamicentities.

The$-calculuscanusecostfunctionswhereuncertaintyisexpressedusingprobabilities,fuzzysetsorroughsetsmembershipfunctions.Inparticular,asymptoticcostfunctions(byanalogytoasymptoticcomplexity)canbedefined.

5.1.AStandardCostFunction

Thedomainofthecostfunctionisaproblem-solvingderivationtreeconstructedbythe-optimizationmeta-procedure.ThederivationtreeconsistsofnodesSandedgesE.Bothand$-expressionsformowntrees,wheretreeisresponsibleforgeneration,pruningandevaluationoftreerepresentingaproblemsolution.Toavoidthecomplexitytoanalyzeandsynchronizetwotreesfortotaloptimization,bothtreescanbecompressed/collapsedintoasingletree,wherecanberepresentedasnodes,andasedgesofthecombinedtree,or,alternatively,canformedges,andnodesofthetree.Insuchaway,aproblem-solvingtreewillcapturebothsolutionsandthesearchprocess.The

),thecostfunctionmeasuresthecostscostfunctionmeasuresthequalityofsolutions(costsof

ofsearch(costsof),andaggregatingfunctioncombinescostsofsolutionsandsearch.

Letdefinecostsofnodesandedgesas,where,and(oralternatively,asand,dependingwhetherandhavebeenassociatedwithnodesoredgesofthetree).

E.Eberbach/$-CalculusofBoundedRationalAgents73

Thenthecostoftheproblem-solvingtreescanbedefinedas,i.e.,

ascombiningcostsofthesearchandthesolutionquality

whereisanaggregatingcostfunction,isasearchcostfunction,andistheproblem-specificcostfunction.

Inthispaper,both,,andwilltakethesameuniformformofthestandardcostfunctiondefinedbelow.Inotherwords,bothtrees,edgesandnodeswillformthe$-expressions,andthenitissufficienttodefinehowtocomputethecostsof$-expressions.

becostsofsimplecostexpressions,includingasilentexpression,whereLet

,and.Theyarecontextdependent,i.e.,theydependonstates.In

particular,costofmaydependwhichcostexpressionismadeinvisibleby.Technically,isdefinedontheproblem-solvingtree,consistingofnodesandedgesexpressedby$-expressions,asthefunction

.Thusitissufficienttodefinecostsofmappingthetreetoarealnumber:

$-expressionsP.Notethatthevalueofthecostfunction(oritsestimate)canchangeaftereachloopiteration(evaluationofasimplecostexpression).

Definition5.1.AStandardCostFunctionForevery$-expression

definedasbelow:1.2.

itscost

is

forobservationcongruence

forstrongcongruence

3.

,where

doesnotblock

blocks

74E.Eberbach/$-CalculusofBoundedRationalAgents

for

probabilisticcostfunction

8.

forfor

fuzzysetscostfunction

roughsetscostfunction

whereistheprobabilityofchoiceoftheJ-thmultiset,isafuzzysetmembershipfunctionofchoiceoftheJ-thmultiset,andisaroughsetsmembershipfunctionoftheJ-thmultisetchoice

9.

where

.

Costchoicecalculatescostsastheminimumofcostsofitscomponents.Adversarychoicecostis

definedasthecostofitsmostexpensivecomponent.Generalchoicecosthasbeendefinedastheaveragecomponentcost.Sequentialcompositioncostaddscostsofitscomponents.Parallelcompositioncostselectsanonemptymultisetthatdoesnotblock.Ithasbeendefinedastheaveragecomponentcost.Alternatively,parallelcompositioncouldselectaspecificmultisettobeexecuted,e.g.,themaxiumsubsetthatdoesnotblock(forthemaximumconcurrencysemantics),orthesubsetwiththeminimalcosts(probablythemostinterestingalternative,ontheotherhand,increasingcostsofthe-search).However,boththesealternativeswewillleaveasviablechoicesfortheuserwhocanoverwritethecostofparallelcompositiondefinitionifitispreferable.Costoftherecursive(userdefined)functioncalliscalculatedasthecostofitsbody.Theuserisfreetodefineowncostfunctions.

Forwelldefinedcostfunctions,structurallycongruent,stronlycongruent,andweaklycongruent$-expressionsshouldhavethesamecost,whichisimpliedbythedecision/utilitytheory,i.e.,,

,andshouldimply.Theproofthatthestandardcostfunctioniswell

defined,canbebasedoninductiononthedepthofthederivationtree.Forexample,notethatforcostchoiceandasexpected.Foradversarychoice,anditscostof.Forgeneralchoice,andpendingthatprobabilityofzero/deadlockiszero()whatisareasonableassumption.Similarrequirementswillhavetobeimposedonfuzzysetsorroughsetsmembershipfunctionsingeneralchoiceorparallelcompositionfor-theywillhavetobeequal0forthestandardcostfunctiontobewelldefined.

5.2.CostFunctionProfilingandReinforcementLearning

Thissectiondealswiththebasicproblemofresource-boundedreasoning:howtoderivecostsforsimple

$-expressions.Sincetherearemanypossiblefactorsaffectingtheexecutiontime,theperformanceprofileofsimple$-expressions,inmanycases,hastobedeterminedempiricallyandnotanalytically.

Resource-boundedoptimizationtypicallyassumesthatstatisticsfrompreviousexperimentswithde-liberationproceduresareusedtodevelopprofilesorcostfunctions.Theseprofilesarethenusedastoolsinthemeta-deliberationprocess.

Muchofcomputerscienceisbasedondeductivelyderivingasymptoticmeasuresofalgorithmcom-putationalcomplexitybasedoncharacteristicsofthedatainput.Theyprovideorderofmagnitudeequa-tionsforbest,worst,orpossiblyaveragealgorithmsperformancebasedoninputvolume.Becausethey

E.Eberbach/$-CalculusofBoundedRationalAgents75

capturetherateofgrowth,constantbecomeirrelevantinasymptoticmeasures,sinceatsomepointthevalueofahigherorderfactorwillbegreaterthanalowerorderone;nomatterwhatconstantsareused.Thesemeasuresareusefulfordeterminingalgorithmscalability,butinadequatefordecidingbetweentwospecificalternativeswhereconstantfactorsarerelevant.Inaddition,averagecomplexitymeasuresaregenerallybasedonquestionableassumptionsconcerningthestatisticaldistributionofinputdata,suchasassumingallinputsareequallylikely.

Computationalcomplexityisalmostirrelevantforprofilingcostsofsimple$-expressions.However,itprovidesagoodstartingpoint.Insomecases,deductionalonecanprovideusefulfunctions.Inothercases,especiallywhennoiseisanimportantfactor,deductionisinsufficient.Ifthatisso,empiricaltestingcanbeused.Testingisoftensimulation,whereanumberofrunsarereplicatedwithcontrollablefactorssettofixedvaluesanduncontrollablefactorsgivenrandomvalues.Resultsfromalargenumberoftestsprovidedatapoints,whichcanbeusedtoderivefunctionalapproximations.Derivationoffunctionalapproximationcanbedoneusinganumberofapproaches,includingstatisticalregression,roughsets,andvisualization.The$-functionsfoundshouldbetestedtoverifytheirabilitytoapproximatethedesiredqualitymeasures.Testcouldinvolveeithersimulationsorpreferablyfeedbackfrompreviousrunsofdeliberationmeta-control.

Profilingcanbeusedalsotoderiveformulasforcostsofcompositecostexpressions,Itapproximatesthemifitisnotclearorsufficienttouselibrarycostfunctions.

Costfunctionprofiling/learningcanbedoneusingmethodsfromreinforcementlearning,e.g.Q-learningorTD(TemporalDifference)learning[74,69],however,thisbyitselfcanbeasubjectofanotherpaper.NoteonlythatthedefinitionofthestandardcostfunctionresemblesveryclosethebasicequationforQ-values.Theexpectedutilityinstateperformingaction

where

isrewardforbeinginstate,and

istheprobabilitytoreachstate

fromstatedoing

action.TheQ-valueequationisequivalenttothe$-calculussearchusingonly

(andassumingminimizationandnotmaximization):

,,

and$operators

Theadvantageofreinforcementlearningisthatissufficesforanagentwhoveryoftendoesnotknow

(orisunabletofind)howtomodelotheragentsand/oranenvironment.Thenthecostscanbelearneddirectlyfromrewardsfeedbackinteractions.

6.IllustratingExamplesofBoundedRationalitybySearch

Severalexamplesillustratethe$-calculusasacomputationaltheoryofAIbasedonsearchandoptimiza-tionunderboundedresources.TheseexamplesdescribeAIsearch,evolutionarycomputation,neuralnetworksandartificiallife.Alluseanoptimizationmechanismtotradeoffthesolutionqualityforresourceavailability.Meta-levelcontrolisprovidedbyusingperformancemetrics.Infiniteandfeasi-blesearchspaces,wecanlookforoptimalandtotallyoptimalsolutions.Ininfeasible(infiniteorverylarge)searchspacestheapproachcanimprovesolutionqualityindefinitely,sincenoclearconvergenceconditionsorhaltingcriteriaexist.

76E.Eberbach/$-CalculusofBoundedRationalAgents

6.1.AHeuristicSingleAgentSearch

Asingleagentsearchisbestdescribedintheliterature,andcoversuninformed(weak)methods(andalgorithmslikedepth-first,breadth-first,uniformcost,iterativedeepening),andheuristic(strong)searchmethods(withalgorithmslikeA*,IDA*,tabusearch,SMA*,hillclimbing,simulatedannealing).Heuristicsearchmethodsallowtocutsearchspacecomparedtouninformedmethods.Theyguidethesearchbyestimatingcostofsubpathsfromthecurrentstatetothegoal.Thepowerofpredictionisreallyessentialforintelligentsystems(see,e.g.,[75]).

Probably,thebestknownisA*heuristicsearch(duetoHart,Nilsson,andRaphael,1968,alsocalledthebest-pathsearch[33,63]:itselectsthenodewiththeminimalvalueoftheevaluationfunctionf(n)=g(n)+h(n),whereg(n)givesthepathcostfromthestartnodetonoden,andh(n)istheestimatedcostofthecheapestpathfromntothegoal.A*iscompleteonlocallyfinitegraphs,optimalifcostestimatesareadmissible,withanexponentialtimeandspacesearchcost.TheA*canbesimulatedbythe-searchusing,,,and.Bothoptimalandtotallyoptimalsoutionscanbefound(see,e.g.,[20])

Takingintoaccountsearch(deliberation)costsleadstoboundedrationality,intheformofdirectsearchoptimizationlikeinthe-optimization,orputtingconstraintsonsearchspacelikeinRussell’sSMA*algorithmwithafixedlimitonnodeskeptinmemory(theboundonthespacecost,keepingonlypromisingnodes)[69],orGlover’sTabusearch(keepingthelistofprohibitednodesfromexpansion).Otherpossibilitiestoconstrainsearchspaceistoforgetsearchnodes,andtorememberonlyacurrentpoint,asinhillclimbing(payingpriceofbeingincompleteandnotoptimal),ortoallowrandomlyjumptoforgottenpointslikeinrandom-restarthillclimbing,orsimulatedannealing(bothcompleteandoptimalwithprobability1iftoallowinfinitesearchtime).Theyalleviatethesearchcostbutnotkeeping(asinhillclimbing),oronlykeepingthebestresults(asinrandom-restarthillclimbing)ofthesearchtreeinmemory.

Let’slookinmoredetailstosomeofthosemeta-heuristicsapproaches.Meta-heuristicsthatavoidbeingtrappedinlocalminimahavebeendividedintotwocategoriesmonotonicandnon-monotonic[31,40].Bothmonotonicandnon-monotonicmeta-heuristicsavoidlocalminimabyoccasionallychoosingtomovetoapointinthesearchspacewhichislessattractivethanthecurrentposition.Thesearepointswhere,thevalueoftheobjectivefunctionatpoint,isgreaterthanwhentryingtominimizef.

Monotonicmethodsmakethischoicebasedonthemonotonicallydecreasingvalueofaparameter.Simulatedannealingisprobablythebestknownexampleofthisapproach.Itisanoptimizationmeta-heuristiclooselybasedoncrystalformation,foradetaileddescriptionofsimulatedannealingsee[45].Generally,simulatedannealingchoosesapoint,neighboringthecurrentposition,inthesearchspaceatrandom.Theobjectivefunctionevaluatesthequalityof.Ifislessthan,becomesthecurrentposition.Ifisgreaterthan,becomesfollowingprobabilitydistri-bution.Thismeta-heuristicismonotonic,sincethevalueofdecreasesmonotonicallyaccordingtoacoolingschedule.Theprobabilityofacceptingalowerqualitysolutiondecreasesasthesearchprogresses.

Anothermonotonicmethodisthresholdacceptance,whichusesamonotonicallydecreasingthresh-old.Anycandidatepointisaccepted,aslongas.decreasesmonotonicallyduringthesearch.Monotonicmethodsprovideclearstoppingcriteria,andmeta-levelreasoningisgener-allynotperformed.Elitiststrategiesfromevolutionarycomputationalsobelongtomonotonicmethods.

E.Eberbach/$-CalculusofBoundedRationalAgents77

Non-monotonicmethodsresemblemonotonicmethods,inthatapointmaybeacceptedbythesearchalthough.Theydifferfrommonotonicmethods,inthattheprobabilityofaccep-tancedoesnotdependonamonotonicallydecreasingparametervalue.

Onenon-monotonicheuristicsearchisOldBachelorAcceptance[40].OldBacheloracceptanceisbasedonthresholdacceptance,butmeta-levelreasoningisused.Initssimplestform,thethresholdvariesbasedonrecentexperience.Ifthecandidatepointdoesnotfulfill,isincreasedforthenextiteration.If,isdecremented.Thisprimitivemeta-levelreasoningcausestheheuristictoactlikegradientdescentwhereappropriate,butalsoclimboutoflocalminimaquicklywhenneeded.Additionalmeta-levelreasoninghasbeenaddedbyexplicitlyusingthenumberofiterationsremainingtomodifythethreshold.Ifalargenumberofiterationsremain,thethresholdcanremainlarge.Asprogramterminationapproaches,thethresholddecreasesandthesearchresemblesgradientdescent.

Intermsofthe$-calculus,theOldBachelorAcceptancecanbephrasedas:isacostfunction$,andwemakecostchoicebetweenand:,whereisthecosthistory(thecandidatepointdoesnothavehistory).Ifthenhistoryisincrementedandanewcandidatepointischosen,andifthenthecandidatepointisacceptedandhistoryisdecremented.

AdaptiveMemoryProgrammingisthenameofaclassofmeta-heuristics,whichincludestabusearch.Adaptivememoryprogramisnon-monotonicinthattheprobabilityofacceptingalowerqualitycan-didatepointisindependentofasinglevariable,itisbasedontheobjectivefunctionvaluesfoundatpreviouslyconsideredpoints.

Intabusearch,forexample,alistiskeptofpointsinthesearchspacethathavebeenvisitedmostrecently.Asimpleimplementationmayperformagreedysearchofthesearchspacenotcontainedinthetabulist.Thisapproachavoidsbeingtrappedinlocalminima,butalsoprovidessimplemeta-levelreasoning.Previousresultstosteerthecourseofthealgorithm.Muchattentionhasbeenpaidtofindingtheappropriatelengthforthetabulist.Thelengthofthelistisdeterminedbyresourcelimitations.Theamountofstoragespaceavailablelimitsthelengthofthelist,asdoestheamountoftimeavailabletosearchthelisttodisqualifycandidatepoints.Moresophisticatedvariationsofthisapproachcanbefoundin[30,31,32],includingstrategiesfornon-localsearchesresemblinggeneticalgorithms.

Intermsofthe$-calculus,tabusearchcanbephrasedas:acostchoiceofpossiblecandidateswheresomecandidatesaremaskedbythetabulist.Asimpleimplementationofthetabulistisaddingahistorycomponenttothecostofelementsonthetabulist.Thismakesthemlessattractivethanelementsnoton

makesthemarealtabu.thetabulist.Makingthehistorycomponent

Non-monotonicsearchstrategiesreplacetheparameterwithmeta-levelreasoningforsteeringthesearch.Theyalsofitthecriteriagivenforresourceboundedsystems.Ifthealgorithmretainsthebestresultfoundsofar,thealgorithmsdescribedprovidedboundedoptimalresults.Performancemeasureisbasedonthevalueoftheobjectivefunction.BothAdaptiveMemoryProgrammingandOldBachelorAcceptanceprovidemeta-levelcontrol.InthecaseofOldBachelorAcceptance,thethresholdvariesaccordingtorecentresultsandtheamountoftimeavailable.Inadaptivememoryprogramming,aswithGeneticAlgorithms,resultsofrecentevaluationsoftheobjectivefunctionsteerthesearchforthenextiteration.

Theapplicabilityofasingle-agentsearchalthoughdescribedbestintheliteratureisverylimited.Itallowstoabstractfromdetailsforpayingthepriceofmissinginteraction.Eventhesingleagentissituatedinsomeenvironment,whichleadsnaturallytotwo-agentsystemsandingeneral,tomultipleagentsystems.

78E.Eberbach/$-CalculusofBoundedRationalAgents

MIN

MAX

-3-12-8-2-4-6-14-5-2

Fig:1Aminimaxcompletesearchtree

6.2.ATwo-AgentSearch

Atwo-agentsearchcanbeinterpretedasasinglerationalagenttryingtominimizeitscosts,and,addi-tionally,interactingwithanotheragent(perhaps,takingtheformofanenvironment).Anotheragentcanberationalorprobabilistic.Therationalagentcanbecooperative,i.e.,tryingtohelptominimizethefirstagent’scosts,orcompetitive-thenitwilltrytomaximizecostsofitsopponent.Theprobabilisticagentisneitherhelpingnorfightingthefirstagent.Iteitherdoesnotcareabouttheagent(e.g.,amobilerobotenvironmentwhichis“irrational”or“notcaring”abouthappinessoftheagent),oroscillatesbetweencooperationandcompetitionlikeinthePrisoner’sDilemmaProblem.

Thebestdescribedintheliteratureisthecaseofthetwocompetitiveagents,andalgorithmslikeminimax,alpha-beta,and/orgraphs,andexpectiminimax.ItisbasedonthegametheorydevelopedbyOscarMorgensternandJohnvonNeumannduringWorldWarII[81].Two-agentgamesinclude,forinstance,checkers,chess,Othello,backgammon,tic-tac-toe,andgo.Probably,thebestknownistheminimaxalgorithm,andwewilldescribehowthe$-calculus-optimizationhandlesit.

MinimaxsearchwasproposedbyvonNeumannin1944[81]andusedbyClaudeShannonin1950forchessplayingprogram.Thistwo-playersearchmethodassumesperfectinformationanditcandeterminethebestmoveforaplayer(assumingthattheopponentplaysperfectly)byenumeratingtheentiregametree.Theplayermaximizespayoff,anditsopponentminimizesitinsuccessivemoves.Takingmaximumbytheplayer,andminimumbytheopponentinconsecutivemoves(calledply)goingfromleavestowardstheroot,thebestmovefortheplayermaximizingpayoffisdetermined.Thisiscalledtheminimaxdecision,becauseitmaximizestheutilityundertheassumptionthattheopponentwillplayperfectlytominimizeit.Minimaxiscompleteonlocallyfinitegraphs,withexponentialtimeandquadraticspacesearchcost,andisoptimalunderperfectinformationassumption(bothagentsknowexactlythemovesofitsopponent).

Forillustration,wewillusethesameexampleofminimaxasin[69].“Our”agentperformsmini-mization,anditsopponentmaximization.Thepayoff/goalstatesare,,,,,,,,.Payoffisrepresentedbynegativecosts.

,,

.Bothagentsuseastandardcostfunction,howeverfirstagent

performsminimization(usesacostchoice-minimizingnegativecostmaximizesitspayoff),and

E.Eberbach/$-CalculusofBoundedRationalAgents79

secondagentusesanadversarychoice(bymaximizingnegativecostofthefirstagent,itminimizesfirstagentpayoff).Iftonotcountthemeta-systemitself-the-optimization,tosimulateminimaxweneedonlyfouroperatorsfromthe$-calculus:,,,and$.Forbothagents(optimizeuntilthepayoffsarereached),(executeoneactiononlyafteroptimization).Notethatcooperatingagentsbothwoulduse,i.e.,theywouldminimizecostsinunison.Notealsothatactions/edgesdonothaveanycosts(neutralcosts0),onlynodesgivepayoff(moreprecisely,thegoalnodes).Bothagentssolvetemporallyglobalandspatiallyglobal-optimization(Theorem4.17),whichdoesexactlywhatminimaxdoes,i.e.,itfindsanoptimalmove(weshowthe-optimizationtree):

OPTIMIZATION:Onlyisused,i.e.,-anoptimalmoveislookedfor,thecostsofthemin-imaxsearchareignored.Inotherwordscostsofedgesrepresentingcostsofthe-search,simulatingminimax,areignored.

Thenconsecutivesteps(cycles)ofthe-optimizationdoexactlywhatminimaxsupposedtodo:

0.t=0,initializationphaseTherootiscreatedwithanemptycontinuation,andparametersfortheareselected:,,,standardcostfunctionisused(optimizationonly,andnottotaloptimization),,,...,.isnotthegoalstateandisselectedforexpansionwiththe

,acompleteproblemsolutiontreewillbebuiltintheselectphase.cost0.Because

1.t=1,firstloopiteration,

selectphase

,

,

examinephase

Theoptimalpathis.Thusactionistheoptimalmove().Itison

thepathleadingtostateguaranteeingthebestpayoffatleast-3pendingperfectplayoftheopponent.executephasemoveisexecuted(on-linealgorithm),theopponentisperformingamove,andminimaxalgorithmwouldberepeatednormallyagain,howeverbecausetheplydepthisone-theminimaxisover,andthe-searchiscalledagaintosolveanotherproblem.

Becauseofitstimecomplexity,minimaxisimpractical(intractable)inmostcases.Forrealgames,onlyapartialtreeisconsidered:theutilityfunctionisreplacedbyanevaluationfunction,andthegoalfunctionbythecutofffunction(decreasingvalue).Thealpha-betaalgorithmbypruningsearchtree(decreasingvalue)alleviatesalittletheproblemofthesearchcomplexity,andindirectlyminimizesthesearchcost.

Theresource-boundedapproachofthe$-calculuscansolvesdirectlythetotaloptimizationproblem(minimizingsearchcostsandnegativepaoffsimultaneously).Itaddscostsofactionsandsearchcostdirectly(costofdeliberation).

80E.Eberbach/$-CalculusofBoundedRationalAgents

TOTALOPTIMIZATION:-anoptimalmoveislookedforthatdoesnotexceedthemax-imumtimelimittoanalyzethenextmove.Thisisequivalentthatoperatesonedges,,andonverticesofthetree.Let’sassumethateverymovetakes1unitoftime,andlet’sassumethatminimaxdepth-firstsearchstartsfromtherightbranch.Thenconsecutivesteps(cycles)ofthe-optimizationaresimilarasfortheoptimization(however,theconclusionisdifferent):

0.t=0,initializationphaseTherootiscreatedwithanemptycontinuation

,andparametersfortheareselected:,,,standardcostfunctionisused(totaloptimization),,,...,.isnotthegoalstateandisselectedforexpansionwiththecost0.Because,acompleteproblemsolutiontreewillbebuiltintheselectphase.

1.t=1,firstloopiteration,selectphase

,

,

examinephase

Let’sassumethatthemovesareanalyzedfromrighttotheleft:thefirstsubtree(containing)has

4possiblemovestoanalyze(),thusthecostof.Thesecostsareaddedtothecostofselectingasubtreewithbyanalyzingthenext4possiblemovesgiving

,andforthetheleftbranch.Theacorrectedcostof

optimalpathis,thustheactionistheoptimalmove().Itisonthe

guaranteeingthebesttotalcost2(payoff-2withthecostsofthinking4).pathleadingtostate

Iftoassumethatpayoffshouldbelargerthanthecostsofthinking,wecouldimaginethatafteranalyzingtherightsubtree,a“min”agentwillstoptodoanalysisoftworemainingsubtreestoavoidincreaseofcosts(otherwisethechoiceofselectionofanyof,,orwouldbethesameandequal12).Notethatcostsofremaintobe0,becausecostsof“thinking”oftheminagentarenotthecostsof“thinking”forthemaxagent.executephasemoveisexecuted(on-linealgorithm),theopponentisperformingamove,andminimaxalgorithmwouldberepeatednormallyagain,howeverbecausetheplydepthisone-theminimaxisover,andthe-searchiscalledagaintostarttoworkonanewproblem.

Expectiminimax[69]representstwocompetitiveagentswithelementofchance(e.g.,backgammonwithdicerolls,representinganenvironment).Itrequiresaddingthe5-thoperatorfrom$-calculus:thegeneralchoicewiththecostbeinganexpectedcostofitscomponents(asdefinedinsection5.1forthestandardcostfunction).Wecanthinkaboutthisaspartitioningofsearchspaceinto(minimizingagent1),(maximizingagent2)and(aprobabilisticenvironment).Expectiminimaxleadsina

E.Eberbach/$-CalculusofBoundedRationalAgents81

naturalwaytomorerealisticdomains,whereuncertaintyplaysacentralrole.Forlargesearchspacescuttingoffsearchcanbedonebylimitingthehorizonofsearchtothedepthk.Everythingelseremainswithoutchanges.

6.3.SearchwithMultipleInteractingAgents

Multipleinteractingagentscoverthemostgeneralandinterestingcase,becauseanagentalwaysissitu-atedinsomeenvironmentandveryrarelyisolated.Thusanagenthastointeractbothwithotheragentsandanenvironmentinpresenceofnoiseanduncertainty.Manyapproacheshavebeenproposed,includ-ingthosebasedon

Markovprocesses(e.g.,dynamicprogramming,dynamicbeliefnetworks,dynamicdecisionnet-works).

Evolutionarycomputation(e.g.,geneticalgorithms,evolutionaryprogramming,evolutionstrate-gies,andgeneticprogramming).

Cellularspacemodels(e.g.,cellularautomata,neuralnetworks,automatanetworks,interactionmachines).

Resourceboundedcomputation(e.g.,decision-theoreticmetareasoning,flexiblecomputation,just-in-timecomputing).

Processalgebras(e.g.,the-calculus,the$-calculus)

.

¿Fromtheabove,theapproachesbasedonMarkovprocesses,evolutionarycomputation,andresource-boundedcomputationuseutilities/coststodirectsearchandlearning.Insomeapproaches,likeincellularautomata,automatanetworks,interactionmachines,orthe-calculussearchmaynotbecentraltothemodelandutilities/costsarenotapartofthemodel.Ontheotherhand,cellularspacemodels,evolution-arycomputationandprocessalgebrasdealwithmultipleinteractingagents,whereasMarkovprocessesorresourceboundedcomputation,parallelismrequiresanextensiontoexistingmodels.

Clearly,onlyevolutionarymodels,neuralnets,andthe$-calculusareatthesameparallelwithsearchasacentraldogma,althoughparallelisminevolutionarycomputation,andinsimulatedneuralnetsisusuallyimplicit,andinthe$-calculus-explicit.Wewillbrieflydescribesomeofthoseapproaches,pointingouthowthe$-calculuscouldbeusefulforthem.

6.3.1.MarkovProcessesandDynamicProgrammingasSearch

MarkovprocessesassearchincludeBayesiandecisionnetworks,dynamicprogramming,dynamicbeliefnetworks,anddynamicdecisionnetworks[69].Wewillconcentrateontheoldestandthebestknowndynamicprogramming.

Dynamicprogrammingandthevalueiterationalgorithm,bothproposedbyRichardBellmanin1957,initiatedthemodernapproachtosequentialdecisionproblems[3].Itisonlyapplicableforaccessibleenvironments(theagent’sperceptateachstepidentifiesthestateitisin),andhavingMarkovproperty(thetransitionprobabilitiesfromanygivenstatedependonlyonthecurrentstateandnotonprevious

82E.Eberbach/$-CalculusofBoundedRationalAgents

history).Thebasicideaistocalculatetheutilityofeachstate,andthenusethestateutilitiestoselectanoptimalactionineachstate.ThedifficultpartcalculatingautilityU(state)isthatwedonotknowwhereanactionwilllead.Wecanthinkofasequenceofactionsasgeneratingatreeofpossiblehistories,withthecurrentstateastherootofthetree,andeachpathfromtheroottoaleafrepresentingapossiblehistoryofstates.

Anoptimalaction(policy)iswithmaximalexpectedutilityofoutcomestates:

-adynamicprogrammingequation

whereistheprobabilityofreachingstateifactionistakeninstate,isarewardforbeing

instate,andisautilityofstate.

Thesimplestdynamicprogrammingcontextinvolvesann-stepdecisionproblem,wherethestatesreachedafternstepsareconsideredterminalstatesandhaveknownutilities.

Thesituationissomehowsimilartominimax(orratherexpectiminimax),i.e.,costs/utilitiesareknownonlyafternsteps,andweshouldfillthegapsinsuchawaythatwewilloptimizerewards.Wewillneedalsoonly4operatorsfrom$-calculus(likeinexpectimimax):,andwewilluseastandardcostfunction.Clearly,aclassicaldynamicprogrammingconsidersacaseofasingleagent,thus,-optimizationworkswithand(dependinghowvolatilethecostfunctionis)solvingtemporallyglobalandspatiallyglobaloptimizationproblem:

-adynamicprogrammingequation

DynamicprogrammingforthiscasefulfillsallrequirementsofTheorem4.17,thusiscompleteand

optimal.The$-calculuscouldextenddynamicprogrammingtomultipleagents(byaddingparallelcomposition,andsendandreceiveoperators),andtoattempttominimizecostsofsearchbysolutionofthetotaloptimizationproblem.Thiswouldallowtouseresource-boundedoptimizationasadirectsolutionofthetotaloptimizationproblem.

However,dynamicprogrammingreducesthesearchcomplexityratherindirectlybycuttingthepo-tentiallyverylargeorinfinitedepthofsearchtoafeasiblefinitedepth,andbyusingiterationtoapprox-imatecosts.Inmostofthedecisionproblems,theenvironmenthistoriesarepotentiallyofunboundedlengthbecauseofloops.Thismeansthatthereisnonforwhichtostartthen-stepdynamicprogrammingalgorithm.However,dynamicprogrammingapproximatestheutilitiesofstatestoanydegreeofaccuracyusinganiterativevalue-iterationprocedure:

,-value-iteration

whereistheutilityestimateforstateafteriterations.As,theutilityvalueswillconverge

tostablevaluesgivencertainconditionsontheenvironment.Tostopiterationeitherrootmeansquare(RMS)erroroftheutilityvaluescomparedtothecorrectvalues,orpolicyloss-thedifferencebetweentheexpectedutilityobtainedbyanagentusingthepolicy,comparedwithanagentusingtheoptimalpolicy-isused.

Suchanapproachisequivalenttouseand(assumingoneiterationoncorrespondstooneiterationof-optimization).Ifestimatesofcosts/utilitiesafternstepsareadmissible,thenvalueiterationwouldfindtotallyoptimalsolution(byTheorems4.18-4.21).

E.Eberbach/$-CalculusofBoundedRationalAgents83

6.3.2.EvolutionaryComputationasSearchUnderBoundedResources

Evolutionarycomputation(withitsfourmainsubareasgeneticalgorithms,geneticprogramming,evolu-tionstrategiesandevolutionaryprogramming)canbeunderstoodasaprobabilisticbeamsearchdirectedbyfitness/utilityoptimization.Itisrelatedbothtosimulatedannealingandrandom-restartparallelhillclimbing(smallgeneticchangesthroughmutationandcrossovertoindividualsandusingthebestresult-ingoffsprings).Evolutionarycomputation

isincompleteandnotoptimalinageneralcase,

iscompleteifcrossoverandmutation(orothervariationoperators)allowtoexplorethewholeresultingsearchspace,

isoptimalininfinitegenerationsifcompleteandelitiststrategiesareused(bestindividualspre-served,andusingmetrics:fitnessofthebestindividualfromthebeampopulation),

isnottotallyoptimal,i.e.,computationallyveryexpensive,andmissingmechanismsforcontrolsearchcost(whichwouldallowscalabilityandevolutionon-line,e.g.,forevolutionaryrobotics),missingmechanismsforcontrollength/complexityofsolutions,

fitnessusuallyisnotacomposablefunction(i.e.,fitnessofthesolutionsisnotbuildasthefunctionofitscomponentsfitness.Thisaffectsbothscalabilityandtotaloptimality),

nohints/theoryisprovidedhowtochoosethegenomerepresentationorfitness(aformof“blackart”,i.e.,nostandardization).

Webelievethatthe$-calculuscanbeusefultomitigatesomeoftheseproblems.

search,inparticular,canoffertoevolutionarycomputation.Let’slookwhatthe$-calculusand

Thesearchtreehasnodesoftheform

wherethebeamwidth(populationsize)isfixedto,andeachisdescribedintheformof$-expression(whichcandescribeanarbitrarydatastructureorfunction).Onestepinsearchtreecorre-spondstoonegeneration.Thegenesarealternatedusingthe$-calculussendoperator,whichissogeneral

(anarbitraryfunctioncanbeputthereasthe$-expressionargument)thatitcansimulatecrossovers,mu-tations,orothervariationoperators).Theprobabilisticselectionprocesstrimsthesearchtreeandkeeps(althoughdoesnotneed)thefixedbeamofsearch,andgenescompeteforsurvivalto“fit”tothewidthofthebeam.Astandardizedfitnesstakestheformofthe$-calculusstandardcostfunction,i.e.,abettergenehasalowerstandardizedfitness.Inthe-optimization(i.e.,optimizationisdoneonegenerationahead),and(i.e.,executionoruseofindividualsispostponeduntilsearchistermi-nated).Keepingfixedwidthofsearch,meansthatsomeindividualshavetobeforgotten(andnotethatexactlynot-forgettingindividualsdecidedthatA*orSMA*algorithmswereoptimal).Ontheotherhand,mutation/crossoverallowtojumprandomlytoforgottenornotexploredpartofthesearchtree,whichpotentiallyguaranteesthatthewholesearchtreecanbeexplored(iftoallowinfinitesearchprocess),andglobaloptimumfound.Becausethe$-calculuscostfunctionisseparable,wecancontrolthecomplexity

84E.Eberbach/$-CalculusofBoundedRationalAgents

ofgenes(morecomplex,orlongergeneswillhavehighercosts,thusaslessoptimalwillbesubjecttoextinction).Notethatfitnessinevolutionarycomputationisnormallynotseparable,i.e.fitnessfunctionisdefinedtothegeneasawhole.

Potentially,usingthe-optimizationwecanalsosolvedirectlythetotaloptimizationproblem,whichtakesintoaccountbothsearchcostsandthequalityofgenes.Thisiscrucialforcomplexrealisticdomains,andreal-timeapplications(likeinevolutionaryrobotics),and(besidesthebruteforcetech-nologicalprogress)willallowtouseevolutionarytechniquesonline.Thecurrentindirectapproachofevolutionarycomputationtotacklethesearchcomplexityistokeepthepopulationfixedandtrimmedbyselection.This,ontheotherhand,decreaseschancestofindtheglobaloptimum,becauseitincreasesthenumberofgenerations(length)ofthesearch,i.e.,itmightincreaseinfactsearchcomplexity(wetradeoneresource-memory,foranother-time).Ontheotherhand,keepingmultiplesearchpoints(andnotsinglelikeinA*orSMA*),increaseschancesoffindingglobaloptimum.Theinterplaybetweenthesizeofpopulation(widthofsearch)andtheterminationcondition(lengthofsearch)hasnotbeeninvestigatedinanyextent,andthisasweseecanbecrucialtofindthebestresults.Usually,itisdoneeitherbycheckingafewvalues,ormoreoften,simplystating“let’sassumethepopulationsizeof...”and“terminationconditionis...”.

Let’slooknowinmoredetailstothemeta-controlstructureofevolutionarycomputation-anevolu-tionalgorithm.Anarbitraryevolutionaryalgorithm,whichsubsumesgeneticalgorithms,evolutionaryprogramming,evolutionstrategies,andgeneticprogramming,canbedescribedasthefollowingcom-posite$-expression(noteaverycloseresemblancetothe$-calculus-optimizationmeta-controlpro-cedure):

/*initializepopulationofchromosomes*//*runandfinditscost/fitness*//*basiccycle:select,alter,evaluate*/

/*looprecursivedefinition*/

/*terminationconditionnotsatisfied*/

/*select:selectsurvivingindividualsbasedonfitness*//*alter:applycrossoverandmutation*//*evaluate:runandfinditscost/fitness*//*returnbacktoloop*/

E.Eberbach/$-CalculusofBoundedRationalAgents85

bycopyingchromosomesoralteringthembycrossoverandmutation.Deliberationisalsodirectedbyfitness.Ontheotherhand,onlytheelitistevolutionarycomputationisstrictly“anytime”,i.e.,itmono-tonicallyimprovesfitnessofthebestindividualfromthegenepopulation.Additionally,controllingthesearchcostofoptimization,socrucialforresource-boundedcomputation,atleastnow,isnotcentraltoanevolutionaryapproach.

Finally,letusconsidergeneticprogramming,thesubareaofevolutionarycomputation,whichistheclosestrelatedtothe$-calculusfromallsubareasofevolutionarycomputation,andwhichallowstoex-ploitallharness/operatorsfromthe$-calculus.Geneticprogramming[41]followsthealgorithmgivenabovewithmodifications,,,,anduserspecified,and

86E.Eberbach/$-CalculusofBoundedRationalAgents

withstates

assignedtoeachnode)andcommonfinite-statemachine

(times)andlocaltransitionfunctions

withinputalphabet

,

Theglobalevolution(dynamics)ofacellularautomatonisadiscretedynamicalsystem(self-map)

,whereisasetofconfigurations(totalstates)

Acellularautomatonoperateslocallyasfollows.Acopyofacommonfinitestatemachineoccupieseachvertexofaregulargraph(cellularspace)whichisacell.Synchronously,eachcopyoflooksupitsinputinthestatesofitsneighboringcellsanditsownstate,andthenchangesitsstateaccordingtoitslocaldynamics.Thecellularautomatonperformsitscalculationbyrepeatingtheseatomiclocalrulesapossiblyverylargenumberoftimesforallsitesresultinginanemergentbehavior(globaldynamics)ofthewholesystem.

Inthe$-calculuswesimulateacellularautomatonasfollows:

Eachi-thcopyoffinitestatemachinecalculatesanewvalueofbyevaluatingand

passesitbysendandreceivepairthroughchanneltoanewcallofCA.Thisisdonesynchronouslyforallcells.Thismeansthat$-calculuscansimulateanarbitrarycellularautomaton.

Thereadermayask,whereisthesearchinthisapproach,andwhatistherelationwithresource-boundedcomputation?Firstly,socrucialforCAs,anemergingbehaviorcanbeinterpretedasasearchforafinalstableconfigurationforgiventransitionrules.Thisisnothingelselikethecalculationofthelimitfortheequationabove(leavesofthederivationtree).Secondly,probablyevenmoreimportantforpracticalapplications,thesearchfortransitionsrulesgivenafinalconfiguration/goal.

Bothsearchescanbeinterpretedverysimilarinthe$-calculus.Inageneralcase,thesearchwouldbethroughthespaceofCAs:.AssumingfixedtopologyandfixedinitializationofCA,wecaninterpretthisassearchthroughpossibletransitionrulesof:

wherethenumberofrulesisusuallynotfixed,andonestepinasearchtreecorrespondstoonegenerationofCA.Thetransitionrulesaremodifiedusingthe$-calculussend(notethatsendisusedalsoforpassingnewvaluesoftransitions).Searchcanbecontrolledbyameta-levelintheformofevolutionaryprogramming,orcellularprogrammingwithnonuniformcellularautomata[73]withfitnessasaperformancemeasure,orbytheoptimization.Typicallythesearchcanbedonewithand,andtheuseofastandardcostfunction.Wecanthinkaboutemergingbehaviorthateachcell/agenthasitsowncostfunction,andthequestioniswhatwillbetheglobalcostfunctionofallcells?Thedesign/synthesisproblemwillbeopposite:givenglobalcostfunction,specifycomponentcellcostfunctions.

NotethattypicalforAlifeandcellularautomataproblemsofself-replication,universalcomputationanduniversalconstructioncanbestudiedinthecontextofthe$-calculuswithslightdifference,becausethe$-calculusallowstoexpressmodelshavingricherbehaviorthanTuringmachine,includingcellular

E.Eberbach/$-CalculusofBoundedRationalAgents87

automata[10],-calculus[58,59],interactionmachines[82,83,84],neuralnetworks,andautomatanetworks[28].Inparticular,the$-calculusoperatorsallowingcountablyinfinitenumberofcomponentsmakesthispossible.

Let’slooknowatneuralnetworkssearch.Anartificialneuroncanbedefinedas:

whereistheneuronactivationfunction(usuallyathreshold,piecewise-linear,orsigmoidfunction)

withinputs,weights,andoutput.Thedefinitionallowsrecursion,i.e.canoccurinplaceofoneormoreinputs.Therecursionmayresultinrecurrentdependenciesofinputsonoutputs.

Neuralnetworkstaketheformofthepossiblycountablyinfinitenumberofinterconnectedneuronsasdepictedbelow.

neuralnetwork

...

...

interconnectionnetwork

Fig:2Agenericneuralnetwork

Intermsofthe$-calculusa(recurrent)neuralnetwork

neuronsconnectedbytheinterconnectionnetwork:

isdefinedasapossiblyinfinitesetof

wheretakerealvaluesforcontinuousneuralnetworks,anddiscretefordiscreteneuralnetworks.

Afterreceivingnewvaluesthroughpairssend/receive,aneuralnetworkrepeatsthecyclebycallingitsactivationfunctionsagain.

Thisshowsthatanarbitraryneuralnetworkcanbeexpressedusingthe$-calculus,andthatthecomputationalpowerofthe$-calculusisatleastequaltothatofneuralnets.The$-calculuscansolvethehaltingproblemoftheTuringmachineinthesamewayasneuralnetworkscanduetopossiblyinfinitenumberofneurons[28].

.Typically,itisas-Inageneral,searchisthroughtheenormousspaceofneuralnets:

sumedafixedtopologyofaneuralnet.Thenthesearchisthroughthesmallerspace(butstillpossiblynonenumerable)ofrealordiscreteweights:

88E.Eberbach/$-CalculusofBoundedRationalAgents

wherethenumberofweightsisfixed,i.e.,atypicalbeamsearch,wherenewweight/offspringvaluesreplacecompletelytheoldones.Usuallyasingleneuralnetisthesubjecttoweightmodifications,how-ever,thepopulationofneuralnets,usingevolutionarytechniques,ispossible.ModificationsofweightscanbedirectedlikeinHebbianordeltarules,orrandomlyusingevolutionarytechniques(seee.g.[11]).Acompletesetofweightmodificationscorrespondstoonestepinasearchprocess.Neuralnetworksmodifytheirweights,whichisthebasisofmostneuralnetworklearningalgorithms.Atypicallearningalgorithmmodifiesweightsuntilsomeconvergencecriterionissatisfied.Obviously,thesearchtreesforrealweightsdonotformlocallyfinitegraphs,andthe-optimizationworkswithand

(testinganduseofneuralnetispostponedafterfinishinglearning).Usually,theconvergencecriterionminimizesthecostfunctionintheformoftheclassificationerror.Aneuralnetlearningprocedureformsameta-levelusingminimizationoftheclassificationerrorastheperformancemeasure.Deliberationisdonebyweightmodification.Executionpropagatesnewoutputsignalsandupdatesthecostfunction.Itisunknown,ingeneral,whetheraneuralnetworkwillconvergetotheglobalminimum.Typicallyaneuralnetlearningalgorithmimprovesitsresultswhenitrunsforseveraliterations.Thisisabasicfeatureofresource-boundedcomputation.

Tosummarizeourdiscussionandtostressthepowerofthe$-calculus,in[19]wehaveestablishedthefollowingexpressivenesshierarchy:

,and

denotesTuringmachines,isa-calculus,aresequentialinteractionmachines,multistreaminteractionmachines,cellularautomata,discreteneuralnetworks,

randomautomatanetworks,and$-calculus.where

7.SelectedApplications

Thissectionpresentsthreeselectedapplicationsofthe$-calculusflexibleoptimizationunderboundedresourcesintheareasofadaptiveautonomousmobilerobots,machinevision,anddatamining.

7.1.AdaptiveAutonomousMobileRobots

Adaptiveautonomousagentsinhabitdynamic,unpredictableenvironmentsandattempttosatisfyasetoftime-dependentgoalsusingalimitedsetofresources.IntelligentautonomousagentsaredistributedAIsystemsusuallyconsistingofsimple,non-intelligentlocalcomponents.Theircombinedactivitymayresultinacomplexglobalemergentbehavior.Emergingintelligentbehaviorofautonomousagentsistheresultofadaptation.Itisimportantforadaptationqualitytobeexpressedandmeasuredformally.Thiscanbedonebyusingobjectivefunctionsfordistributedmeta-controlwith(seee.g.[76])orwithout(seee.g.[6])adeliberationphase.AswaspointedbyNilsson[]andZilberstein[]purereactivebehaviorsasadvocatedbyBrooks[6],althoughundoubtedlybetterthannaivesymbolicmodelingof“toyblockworld”examples,cannotsufficetoanalyzeanddesignreal-timecomplexandintelligentbehaviors.Somekindofdeliberationisnecessaryforintelligentagents.However,wehaveatradeoffhowmuchtimecanbespentondeliberation,inordertoreacttimelytodynamicaspectsoftheenvironment.Typicallyforresourceboundedcomputation,the$-calculusallowstotakeintoaccountcostofthemeta-system,i.e.,itiswellequippedtodealwithcostsofdeliberation/planning.

E.Eberbach/$-CalculusofBoundedRationalAgents

Probably,themostappropriateformalmodelstostudyanddesignautonomousagentsare,inorderofincreasingexpressiveness,the-calculus[58,59],interactionmachines[82,83],or(random)automatanetworks[28].Noneofthesedealexplicitlywithadaptationusingboundedresources.The$-calculusdoes.Simulatingautomatanetworksasthemostexpressivemodel,wedemonstratethat$-calculuscandoeverythingtheothermodelscan,whilestillconsideringresource-boundedcomputation.Automatanetworksareageneralizationofcellularautomata,consistingofacellularspaceintheformofanar-bitrarydigraphandanassociatedfamilyoffinite-statemachines.Anarbitraryautomatanetworkcanbeexpressedinthe$-calculussimilartothesimulationofcellularautomatafromSection6.3.3(eachnodewillhaveitsowntransitionrulesandofneighbors,insteadofcommonandfromcellularautomata).Thisshowsthatthe$-calculusisrichenoughtostudythedynamicworldofautonomousagents.

Intermsofthe$-calculus,adaptiveautonomousagentsareaparallelcompositionofcomponentagents

definesthei-thagentwithitsmeta-systemcontrol.Agentistheenvironment.Eachagent

,hasafiniteneighborhooditcommunicateswith,itsowninferenceengine(the-searchprocedure)thatsatisfieslocalgoalsbythe-optimization;anditsowncostfunction.Thismeansthatthecostfunctionforagentsmayconsistofavectorofcomponentcostfunctionsifnocoop-erationisrequired.Theotherextremeisasingleglobalcostfunctionforcooperatingagentstryingtoachieveacommongoal.Itcanbedescribedastheweightedsumoflocalcostfunctions.Eachagentperformseitherlocalorglobal(multiobjective)optimizationdependingontheweightvalues.Costfunc-tionsrepresentfeedback(reward/penalty/sensorysignals)fromtheenvironment.Theyareusedtomodel(estimate)influenceofotheragentsandanenvironmentonagivenagentbehavior.Agentscommunicatewithotheragentsandsenseenvironmentbymessagepassing(the$-calculussendandreceiveoperators).Toavoidacombinatorialexplosionandtodealwithdynamicaspectsoftheworld,on-linedeliberation(optimization)caninvolvearestrictedsubsetofagents,andmanyoronlyafewstepsofexe-cution.Becauseonly“simple”localoptimizationsareperformed,thecomplexityofglobal(perhapsevenintractable)optimizationistransformedtoasetofsimpler(andhopefullyfeasible)localoptimizations.

Therearethreebasicquestionsforautonomousagents:

Howdoesanensembleofagentsproduceintelligentorinterestingoutputinacoordinatedfashion(anemergingglobalbehavior)?

Howtobestdecomposeaglobaljobintothegroupofinteractingagents?

Howtointegratereactive(sense-act)anddeliberative(sense-deliberate-act)behaviors?

Allthreeaspectsarecoveredbythe$-calculus.Thecrucialquestionofproducingintelligentorinter-estingoutput,intermsofthe$-calculus,istransferredtoamoremeasurableproblem:howdoesglobaloptimizationemergefromlocaloptimization?Thisisresolvedbymaskingpartsoftheworldfromthegivenagentina-optimizationproblem.Thisprovidesaflexibleapproachforlocalorglobaloptimiza-tionintimeorspace.Theyreplacepartof$-expressionswithinvisible$-expressions.Dependingonthequalityofcostestimation,communication,theglobaloptimization(emergingglobalbehavior,achievingglobalgoal,avoidingchaoticbehavior)canbeeithersuccessfulornot.Thenecessaryandsufficient

90E.Eberbach/$-CalculusofBoundedRationalAgents

conditionstoachieveglobaloptimization(globaltotaloptimization)byperforminglocaloptimizationsarecoveredbyTheorems4.14to4.21.Formally,wehavethecasethatthesystemconsistsofagents,eachperformingitsownoptimizationonitslocalcostsubexpressiononalphabet,.Thegoalistoobtainaglobaloptimization(ortoreplywhetherglobaloptimizationcanemerge)onalphabet

usinglocaloptimizationson.Weassumethatallagentssharethe

same(global)costfunction$,anddeliberationisspatiallyglobal(i.e.,).Forspatiallylocaloptimization,anagentignoresactionsoutside(byobservationcongruencetheyhaveneutralcost0)andthisaffectstheabilitytoguaranteeemergingglobaloptimizationbylocaloptimizationforanydepthofdeliberationbecausetheagentdoesnotlearncostsofactionsoutside.Thepowerofcorrectesti-mates(guesses)instrongcongruenceisessentialtoguaranteeanemergingglobaloptimization.Costsofinvisibleactionsshouldnotbeoverestimated(admissible),communicationperfect,searchtreefinitelylocal,andagentsshouldlearncostofactionsperformedbyotheragents(i.e.,).

Thesecondproblemdividestheglobaljobamonginteractingagents.Thiscanbedone,forinstance,whenonedesignatedagentsolvestheoptimizationusingaglobalcostexpression.Itpartitionstheglobalcostexpressionintosubexpressionsperformedbyindividualagents,andaddsinteractionsamongagentstosynchronizebehaviorsandexchangeresults.Anagentmayoptimizethecomplexityofanarchitecture,amountofinteractions,timeneededforexecutionanddeliberation.Anotherapproachstartswithatomicelementarybehaviorsusinggeneticprogrammingtechniquestoevolveagentarchitectureandbehaviors.Yetanotherpossibilityusesamatchingmechanism(likeinrule-basedexpertsystemsandemployingthe$-calculussendandreceiveoperators)tofindappropriateactions.

Thethirdproblemintegratesreactiveanddeliberativebehaviors.In$-calculusthisisdonebymod--optimizationproblems.correspondstoreactivebehaviors,andifyingtheparameterforthe

representsdeliberativebehaviors.

Autonomousagentscanbesubdividedintobiological,robotic,artificiallifeandsoftwareagents.TypicalrepresentativesofadaptiveautonomousagentsincludeBrookssubsumptionarchitecture[6],Maesbehaviornetworksandcompetencemodules[51],orMoravecbushrobots[62].Weconcentrateonmobilerobots,theresultsaredirectlyapplicabletoothertypesofagents.

TheOfficeofNavalResearchSAMONprojectatAppliedResearchLab,PennsylvaniaStateUni-versity,StateCollege[66,18]studiedautonomousunderwateragents.AhierarchicalnetworkofAu-tonomousUnderwaterVehicles(AUVs)foradaptiveoceansamplinghasbeendevelopedintheformofthewebbasedtestbedforintegrationanddistributedsimulationofheterogeneousAUVsandmis-sions.TheSAMONprojecthasbeenorganizedasafour-levelhierarchy.AtthetopofthehierarchytherewasaTacticalCoordinatorwhichbyradioinitiatedmissionsthroughorderstoseveralSupervisingAutonomousUnderwaterVehicles(SAUVs).EachAUVestablishedthroughsonarcommunicationthegroupofsubordinatedAUVs.ThegroupofAUVscollectedappropriatedatafromFixedSensorPack-ages(FSPs),distributedovertheregion,andsentdatabacktotheSAUVsandtheTacticalCoordinator.

ASAMONimplementationasdescribedin[66,18]allowedforsomedegreeofflexibility(forin-stance,alostSAUVcouldbereplacedbyAUV,ascheduledbehaviororactioncouldbereplacedbyanewinsertedbehaviororaction),butitdidnotincorporatelearningandevolution.Inotherwords,theAUVcontrollerswerequiteconventional.

Oursuggestion,basedonthe$-calculustheory,wastoincorporateeachagentwithmeta-controlper--optimization.Agents(TC,SAUVs,AUVs,FSPs)couldseeandcommunicateonlywithformingthe

theirneighborsandtheenvironment.Theyworkedinparallelandasynchronously.However,theywereforcedtointeractwitheachother.Unknownfactorsweremaskedbyinvisible.However,eachagent

E.Eberbach/$-CalculusofBoundedRationalAgents91

estimatedcostsofinvisiblecomponents(ifitcaredaboutthem).Eachagent(component)couldhaveadifferentdepthandspanofdeliberation.Forexample,asubmarineattemptingtoavoidcollisionwouldswitchtoreactivebehavior(),whereasaTacticalCoordinatortryingtodesigntheoptimalmissionmightswitchtotoplanacompletemissioninadvance.Thesolutionofthe-optimizationproblemstriedtoconsiderthetimeavailableforthemission,thenumberofavailablevehicles,andtheavailablebatterypowersupply.Becauseprocessallocationandschedulingiscomputationallyhard,andknowledgeoftheTacticalCoordinatorcouldbeincomplete,theTacticalCoordinatorcouldoptimizeonlyafewstepsahead,orperformoptimizationonitshighlevelofabstraction(missions).Supervisingvehiclesperformedoptimizationoftheirlocaltasks,andparts-behaviorswereexecutedandoptimizedbysubordinatedAUVs.Commonglobalcostfunctionandinteractionsallowedforcooperationandachievementoftheglobalgoal.ThisglobalmeasurecouldbeimplementedintheformofthestandardcostfunctionfromSection5.1beingtheweightedsumoftime,energyused,andthenumberofsam-pleslefttocollect.SAMONhierarchyminimizedthetimeneededforthemission,energyused,andthenumberofmeasurementsleft.Flexibleoptimizationdealedwithanunpredictableanddynamiccomplexworld,whileachievingobjectivesinanincrementalandflexiblemanner.Cooperatingagentsminimizedtheir$-functionsinunison,antagonistagentstriedtomaximizecostfunctionsoftheiropponents,theenvironmentwasprobabilistic,i.e.,itcouldinfluenceeachagenteitherway.

ToachieveoneoftheobjectivesoftheSAMONproject,i.e.,thecooperationofheterogeneousvehi-clesfromvariousorganizations,the$-calculushasbeenappliedtoderiveaGeneric-BehaviorMessage-passingLanguageGBML[18]usingsendandreceiveoperatorsforcommunication,andagroupofstandardized(user-definedsimple$-expressionsusingthe$-calculusterminology)elementarybehaviorstailoredtospecificoceanapplication.Thelanguagecouldbealsousedtodesign,monitorandcontrolmissionexecution.ThecontinuationofthisresearchwasthedesignandimplementationoftheCommonControlLanguage(CCL)forthegroupofAUVsatNavalUnderseaWarfareCenter,Newport,andUni-versityofMassachusetts,Dartmouth,andthegeneral-purposeprogramminglanguageCO$T[23,25].

7.2.MachineVision

Machinevisionisparticularlyappropriateforresource-boundedapplications.Mostapplicationsofma-chinevisioninvolveinteractionwiththereal-worldthisbringswithitreal-timeprocessingconstraints.Also,thevolumeofdatatobeprocessedislarge.Forasquareimageofpixelsonaside,eachframe

pixels.Hyper-spectralimagingsystemshavebeenimplementedwhichcollectthousandsofcontains

bandsateachpixellocation[86].Asystemwithbandscontainssamplesineachframe.Ingeneral,theincreaseinthenumberofsamplesmeansbetterresultsarepossible.Unfortunately,italsomeansthatmoretimewillberequiredtoprocesstheimage.Advancesinimaginghardwaretechnology,willrequiremoresophisticatedtechniquesforimageevaluation.

ThepictureinFig.3illustratesatypicalimagingsystem.Radiationisemittedfromalightsourceandtravelsthroughtheatmospherewhichabsorbsandre-emitssomewavelengths.Someofthelightreachestheobjectofinterestandisreflected.Betweentheobjectandthecamera,theatmospherealtersthesignalagain.Theimageofthetargetformedbythecameradependsonseveralfactors:lightsource,atmosphericconditions,object,background,timeofday,andcameraused.Imagingdependsonthecontrastbetweenthetargetanditsbackground.Anefficientsearchstrategydependsonthenoiseintheimage,andbackgroundaswellasontheobject.

92E.Eberbach/$-CalculusofBoundedRationalAgents

Radiation

Source

Observer

Atmosphere

Atmosphere

Object

Fig:3Lightfromthesuntravelsthroughtheatmosphere,isreflectedbythetarget,andtravelsthrough

theatmospheretothecamera.Inthissection,wepresentregistrationofnoisyimagesasanapplicationofresource-boundedcom-putation[7,8,9].Inthisscenariotwosensorsmakeimagesofthesamescene.Thesystemattemptstodeterminethetranslationandrotationwhichmapstheimagefromonesensorontotheotherone.Inwhichcase,thesearchspaceisdefinedbytherelativerotationandtranslationbetweenthetwosensors.

Theobjectivefunctioniscalculatedusingtheerrorcalculatedfromdifferencesbetweenpixelvaluesintheintersectionafterthemappinghasbeenperformed.Thedifferencebetweenindividualpixelvaluesdependsontwofactors:thelackoffitduetoerrorsintheparametervalues,andtheamountofnoiseintheimages.Threedifferentobjectivefunctionshavebeenuseddependingonthetypeofnoisepresentintheimage:Gaussiannoise[7,8,9],uniformnoise,and“saltandpepper”noise.Theexpectedvalueofnoiseintheimageintersectionsiscalculatedandusedtofindthelackoffitcomponentcontainedintheerrorfunction.Anefficientregistrationalgorithmcouldinitiallydeterminethetypeofnoisepresentintheimages,andusethattodeterminetheappropriateobjectivefunction.

Anumberofmeta-heuristicshavebeenusedforsolvingthisproblem:tabusearch,classicalgeneticalgorithms,elitistgeneticalgorithms[8],simulatedannealing[9],andTRUST[2].Resultsfromexperi-mentationshowthatsimulatedannealingandclassicalgeneticalgorithmsconvergeslowlytosub-optimalanswers[7].Tabusearchconvergesquicklytoasub-optimalanswer[8].Elitistgeneticalgorithms[9]andTRUSTconvergetonearglobaloptimalresultsinalimitedamountoftime.

Theseresultsdependonthesearchspaceused.Fortheseexperiments,thesearchspacehadbothperiodicandnon-periodiccomponents.Ifthenon-periodiccomponentsweredominantorthebasinsofattractionnarrowanddeep,itisverylikelythattabusearchandTRUSTwouldbethemostattractiveapproaches.Similarly,thevolumeofnoiseisveryimportant.OnlyelitistGeneticAlgorithmsandTRUSThavebeenfoundtoperformsatisfactorilyinthepresenceoflargeamountsofnoise.Experimentswithsimulatedannealing[7,9]indicateitisparticularlysensitivetonoise.

Thisproblemcannowbephrasedasa$-calculusproblemtotakeadvantageoftheseresults.The$-functionusedischosenasafunctionoftheimagesreadings:

(1)

whereisdefinedasthevaluereturnedbysensor1atpoint,andasthe

readingreturnedbysensor2atpoint.Pointisfoundbyreversingthetranslationand

E.Eberbach/$-CalculusofBoundedRationalAgents93

rotationdefinedbytheparametersbeingtested.Bothandconsistofthesumofactualgrayscalevaluesandnoisevalue.Formoredetailssee[8,9].Thiscostfunctionhasaglobalminimumwherethenon-stochasticportionofthedataprovidestheoptimalanswer,andthestochasticportionofthedataisrepresentedbyaknownstatisticaldistributionovertheentireanswerspace.

Elementarymoves(atomicactionsfromthe$-calculus)consistof3elements:moveimagefromthesecondsensorbyonepixelinx-direction,movebyonepixeliny-direction,androtatebyonedegree.Itisimpossibletofindaclearstoppingcriterionforthisalgorithmsincetheonlywaytobesurethattheglobalminimumforthefitnessfunctionhasbeenfoundisthroughanexhaustivesearchofthesearchspace.Theabovemeansthatpotentiallytheresultsofoursearchimproveifwelongerrunthesearchalgorithm-thedeliberationoftheimageregistrationprocess.Ontheotherhand,let’sassumethattheregistrationofimagesisdoneonline.Wehavealimitedamountoftimetofindanoptimalanswer,andcostofdeliberationmatters.Thustheresultingcostfunctionwillbetheweightedsumofthequalityoftheimageregistration(1)andtime(resources)used.Theelementarymovescanbecombinedse-quentially(bysequentialcompositionoperator),orsearchcanbeexploredinparallelinpopulations(byparallelcompositionoperator).Thedecisionastowhichalternativestoexplorewillberepresentedbycostchoice.Tomeasuresearchcost,weusea$-calculuscrispcostfunction.Let’sassumethateachelementarymovetakesthesameamountoftime.Granularityofmovesinoneiterationcanbecontrolledbythevalueofparameter(depthofdeliberation)translatingandrotatingimageinelementarysteps.

Themeta-controlintheformofa-optimizationwillworkinselect-deliberate-executephases,andwilltrytofindthebestmatchintheminimalnumberofsteps.BasedontheresultsfromSection6we

-searchbothgeneticalgorithmsinclassicandeliteform,aswellastabusearch.cansimulatebythe

Areasonableinitialstrategywouldbeelitistgeneticalgorithmsbasedonourpreviousresearch.Afteranumberofiterations,convergencecanbedetected.OncetheGAconvergestoananswereitherTRUSTortabusearchcanbeusedtoimprovethebestanswerfound.Oncealocalminimumhasbeenreached,iftimeremains,thesystemshouldeitherreverttoanelitistGAapproach,orTRUST.Boundedoptimizationismaintainedandavailabletimeresourcesareutilized.Thismeta-strategycouldbe“hardwired”intothe-search.

Anotherapproachwouldbetoevaluateconcurrentlyseveralmethods:elitistGAs,tabusearch,andTRUSTintheexaminephase,andtoletthemeta-systemtoselectcurrentvalidmethodfortheexecutionphase.Resource-boundedstrategiesusedbythe$-calculusconsiderreal-timeconstraintsanddevelopflexiblemeta-strategies.

7.3.AnytimeFeatureSelectioninDataMining

Alllearningcanbeseenassearchandmemorizingtherepresentationofafunction,e.g.,doingclassi-ficationofobjectslikeininductivelearning.Dataminingtriestoextractusefulknowledge(function

representation)describingasetofdatafromlargedatasets.Dataminingclassificationisbasedonthebasisofobservedexamples,whicharedescribedintermsofafinitenumberofattributescalledherefeatures.

Mostmethodsforlearningrulesordecisiontreesfromexamplesassumethattheattributesusedfordescribingexamplesaresufficientlyrelevanttothelearningproblemathand.Thisassumptiondoesnotalwaysholdinpractice[55].Attributesusedintheexamplesmaynotbedirectlyrelevant,andsomeattributesmaybeirrelevantornonessential.Anattributeisnonessentialisthereisacompleteandconsistentdescriptionoftheclassesorconceptstobelearnedthatdoesnotusethisattribute.Thus,a

94E.Eberbach/$-CalculusofBoundedRationalAgents

nonessentialattributemaybeeitherirrelevantorrelevant,butwillbydefinitionbedispensable.Iftherearemanynonessentialattributesintheinitialdescriptionoftheexamples,thecomplexityofalearningprocessmaysignificantlyincrease.Suchasituationcallsforamethodthatcanefficientlydeterminethemostrelevantattributesforthegivenproblemfromamongallthosegiveninitially.

Largenumberofpotentialfeaturesconstitutesaseriouslyobstacletoefficiencyofmostlearningalgorithms.Suchpopularmethodsask-nearestneighbors,C4.5,andbackpropagationdonotscalewellinthepresenceofmanyfeatures.Moreover,somealgorithmsmaybeconfusedbyirrelevantornoisyattributesandconstructpoorclassifiers.Asuccessfulchoiceoffeaturesprovidedtoaclassifiercanincreaseitsaccuracy,savethecomputationtime,andsimplifyitsresults.Assuminginputfeatures,wecanseefeatureselectionasthesearchprocessthroughpossiblesubsets.Forlarge,brute-forceapproachisoutofquestions.Sincetheprocessoffeatureselectioniscomputationallyintensive,atrade-offbetweenthequalityoftheselectedsubsetandthecomputationtimeisrequired.However,asappearsfrom[49],theexistingmethodsoffeatureselectiondonotconsiderthetrade-offbetweentimeandperformance.In[47,52]anovelanytimealgorithmforfeatureselectionhasbeenpresented,whichgraduallyimprovesthequalityofresultsifmoreresources(computationtime)isavailable.Thealgorithmisinterruptible,i.e.,itcanbestoppedatanytimeandprovideapartialsubsetofselectedfeatures.Thenoveltyoftheapproachisthatitallowscapturingthetrade-offsbetweenthesolutionqualityandthetimesavedand/orcomplexityofclassificationrepresentedbythenumberofinputattributes.Thiscanbecrucialforclassificationalgorithmsworkingwithalargenumberofinputattributes,orwithrealtimeconstraints.

Themethodselectsfeaturesbyconstructinganinformation-theoreticconnectionistnetwork,whichrepresentsinteractionsbetweenthepredicting(input)attributesandtheclassification(target)attributes.Theminimumsetofinputattributesischosenbythealgorithmfromasetofcandidateinputattributes.Usingthe$-calculusterminology,thesearchisthroughtheinformation-theoreticnetworkspace.Ineachnetworkthenumberofhiddenlayersisequaltothenumberofselectedinputattributes.Thesearchisdirectedbythecostfunctionintheformoftheestimatedmutualinformationbetweenthetargetattributeandthesetofinputattributes.Torepresenttheautomatedperceptionofthenetworkquality,anewfuzzy-informationgainFGAINmeasurewasproposed,whichisthefunctionofestimatedconditionalentropyofthetargetattribute,giventhesetofinputattributes,estimatedmutualinformationbetweenthetargetattributeandthesetofinputattributes,significancelevel,andscalingratio.Thusmethodallowstousefewerattributesthantheoptimalclassifieratthepriceofperhapslargerclassificationerrorrate,butfastercompletiontime.

Iftoassumemodificationofthenetworkasanelementarystepinthesearchtree(oneiterationofthealgorithmassumesaddingoneinputattribute),thiscanbeinterpretedas-searchwith,and(testingofthenetworkispostponeduntilterminationcriterionissatisfied).Alphabetisequaltoalphabetofnetworkmodifications.Thesearch,assumingsomeleveloffuzziness,willimprovethequalityofsolutionuntilreachingoptimalvalueofFGAIN.Thetrade-offbetweenthequalitysolutionandthecompletiontimecanbeexpressedasanewmeasure,whereisanormalizedexecutiontime(assumingthatclassificationtimeisbounded).Wecanthinkalsoaboutthesolutionofthetotaloptimizationproblemtakingintoaccountadditionallythesearch

,whereisanormalizedtimeofrunningfeaturecost/time:

selectionalgorithm.

Tostudytheperformanceprofileoftheinformation-theoreticmethodforfeatureselection,thealgo-rithmhasbeenappliedtoseveralbenchmarkdatasets,availablefromtheUCIMachineLearningRepos-E.Eberbach/$-CalculusofBoundedRationalAgents95

itory[4],includingBreast,Chess,Credit,Diabetes,Glass,Heart,andIrisdatasets.TheC4.5algorithm[68]hasbeentrainedoneachdatasettwotimes:beforeandafterfeatureselectionalgorithm.Theer-rorrateofC4.5withoutfeatureselectionwasslightlyhigher(forexample,forDiabetesdataset28.4%against23.3%withfeatureselection;withthetreesize63against23afterfeatureselection).

Otherapplicationsofthe$-calculusincludethedesignandimplementationofthecostlanguageparadigmrepresentatives(e.g.,SEMAL,GBML,CCLorCO$Tlanguages[16,18,23,25]),thedesignandimplementationofevolvablecost-drivenarchitectures(e.g.,CICADAcellulararchitecture),elec-troniccommercemarketbehavioranalysis,predictionandcontrol,DNA-basedagentsandbioinformat-ics,superTuringmodelsofcomputation[21,22,24,85],thedesignandimplementationofhybridexpertsystems,neuralnets,geneticalgorithmsandfuzzysystems,simulationandinvestigationofquantumcomputingandalgorithms.

8.ConclusionsandFutureWork

Thispaperpresentsatheoryforresource-boundedcomputationbasedonprocessalgebrasandtheoryofprogramming.Ourapproachresembles[58](algebraicroots,congruencies,sendandreceivehand-shakingcommunication),[41](terminals,functions,mutation,symbolicexpressionbasedsyntax),and[](performanceprofiles,composabilityofperformancemeasures).Thesesimilaritieswith[58]and[41]differfromotherworksonresource-boundedcomputation.Thispaperconcentratesontheresource-boundedaspectsofthe$-calculus.Theuniqueaspectsofthisapproachare

Proposingresource-boundedcomputationasageneraltheoryofcomputationcomparabletocalculi,andtargetinginteractiveAIapplications.

or

Proposingacomputationaltheoryforhardcomputationalproblems,wherebuilt-inperformancemeasuresallownotonlytoexpresssolutions,buttoprovidethemeanstoincrementallyconstructorimproveexistingsolutions.

Stressingtheabilitytooptimize(butnotnecessarilymonotonically)thequalityofsolutionsto-getherwiththedeliberationcostsasanessentialrequirementforboundedrationality(intelligence).Extensionofperformancemeasuresbeyondtimetoincludeanswerquality,uncertainty,etc.Acompletesetofoperatorstobuildinteractiveprograms.The

-optimizationtodealwithspatialandtemporalconstraintsinaflexibleway.

The$-calculusprovidesanextensionofanytimealgorithmspracticeandtheorybyprovidingtoolsforformalizationandgeneralization.Itrelatesresource-boundedtechniquestomodelsofcomputationlikeTuringmachines,the-calculus,cellularautomataandneuralnetworks.Itprovidesaframeworkforstandardizingperformancemeasuresandmeta-levelcontrol.The-optimizationusinginvisiblecostexpressionstomaskunknownorintractableportionsofthesearchspaceisaninnovativeaspectofourapproach.Itprovidesauniformapproachtorepresentinganddealingwithincompleteanduncertainknowledge.

Algorithmperformanceprofilesareexpressedasgeneral$-expressions.Costprovidesauniformperformancemeasureforalgorithms,data,andmeta-algorithms.Usingasinglevalueforoptimization

96E.Eberbach/$-CalculusofBoundedRationalAgents

meansthattrade-offsbetweenconflictingobjectivesareexpressedexplicitly.Insteadofusingalibraryofperformanceprofilesassociatedwithanytimealgorithmsassuggestedin[],the$-calculusproposestousealibraryofmoregenericcostfunctionsandmeta-systems.Ifappropriate,thesamecostfunctionandmeta-controlcouldbeusedformultipleanytimealgorithms.Auniquemeta-systemisnotnecessaryforeachanytimealgorithm.Userscandecidewhichlibrariessuittheirneeds.Performanceprofileswillgenerallybeproducedbyempiricaltestinginsteadofformalproofs.Currentimplementationislimitedbytheavailabilityofempiricalresearchprovidingperformanceprofiles.

Inthe$-calculus,compilationtechniquesasreferredtoin[]correspondroughlytothecompos-abilityprincipleofcostfunctions.Localcompilationlimitsitsscopetooneprogrammingstructureatatime.Inasimilarway,computationofcostsinthe$-calculusconsidersonlycostsofitsimmediatesub-components.In[]compilationtechniquesarediscussedprimarilyforsequentialcomposition.Somediscussionisgivenforconditionalstructures(generalchoice)andloops(iteration).Otherwaysofcom-bininganytimealgorithms(likeparallelcompositionofalgorithms,recursivedefinitions,pathologicalalgorithmslikethat“run”foreverwithoutimprovement,orflexibleinvisiblealgorithmslike)arenotdiscussed.Apracticaltheoryforalgorithmcompositionneedstodealwithacompletesetofbasicprogrammingconstructs.Thisincludestheserial,parallel,iterativeandrecursiveidioms.Thisistheminimalsetoftransformationsneededforanytimealgorithms.

Inthe$-calculuscontractalgorithmsarereferredtoasatomic$-expressions.Atomic$-expressionscannotbeinterrupted.Theymayhaveastructurethatcanbemodified.However,theusermustbeabletospecifytheircosts.Blockedatomic/contractexpressionswillnotproduceapartialresultandwillhaveaninfinitecost.Thisisconsistentwithcontractalgorithms.Non-atomicexpressionscanbeinterrupted.Atomicandnon-atomicexpressionscanbecomposedinmanyways.Thisisequivalenttointerruptiblealgorithms.Dependinghowweselecttheoptimizationalphabet,thecostincurredbyprocessinterruptioncanbepartofthecostfunctionandsubjecttooptimizationaswell.

Thisapproachisamatterofactiveresearchandanumberofapplicationsareunderdevelopment.Anytheoryforadaptivereal-timesystemsmustprovidetoolsforexpressingtheapplicationdomain.Meta-levelcontrolresemblingthebasicfeaturesofanytimealgorithmsisrequiredaswell.Implementationofthesesystemsshouldallowfortheautomaticdiscoveryofhybridapproachesbasedonempiricalinformation.

The$-calculusprocessalgebraextendedbycosts/utilitiesprovidesanappropriateformalmodelforelementaryalgorithmconstructionwithboundedoptimalanswer.Allprogrammingoperators(built-inanduserdefined)areprovided.Operatorsareboundedbyalimitingvalue(cost).WeshowedthatthismodelisatleastequalinexpressivenesstoInteractionMachinesorRandomAutomataNetworks,i.e.,goingbeyondconventionalTuringMachines,andallowingtocapturebehaviorofdistributedinteractivesystemsboundedbyavailableresources.Thisextendsanytimealgorithmstodistributed,interactivemulti-agentenvironments.In[75],anattempttobuildacomputationaltheoryofAIbasedonpredictionandreinforcementlearninghasbeenpresented.Ourapproachismorecomplete:itisbasedonprocessalgebrasperformingresourceboundedsearch,andspanningtechniquesfromreinforcementlearning,interactivedistributedagents,andmanyothers.

The$-calculusbelongstosuperTuringmodelsofcomputation.i.e.,modelsmoreexpressivethanTuringmachines.However,theexpressivenessofthe$-calculusandnon-algorithmicsolutionsofunde-cidableproblemsarenotaprimarysubjectofthispaper.Formoredetails,thereaderisadvisedtolookto[21,22,24,25].

E.Eberbach/$-CalculusofBoundedRationalAgents97

Itseemsthatinthispaperwetouchedthetipoftheicebergonly.Muchmoreresearchisneeded.Someoftheopentheoreticalproblems,andapplicationsareasforfutureworkarethefollowing:

Investigationofthe$-calculusandprocessalgebrasexpressivenessinrelationtoothermodelsofcomputation,includingothersuperTuringmodelsofcomputation.

Investigationofalgebraiclawsofbisimulationin$-calculuswiththefollowingtwistcomparedtoclassicalprocessalgebras:inthedecisiontheoryitisrathermoreimportantorderingofexpressions(i.e.,aninequality)thantogroupthemintoequivalenceclasses(twoequivalentexpressionshavingthesamecostdonotmakeourlifeeasiertodecidewhichoneispreferredtotheother.Infact,agentscanstarvetodeathifthecomputingofcostswouldbeinefficientorlastforever).Theproofofsoundnessofinferencerulesintheoperationalsemanticsofthe$-calculus.Theproofthatthestandardcostfunctioniswelldefined.

Investigationwhatwouldwegainifformalsemanticsofthe$-calculustobaseonnon-well-foundedsetsandcoinduction(in[84]itwassuggestedthatinteractiveopensystemssemanticsshouldnotusewell-foundedsets,inductionandleastfixedpoints)?

Investigationwhethersimilartochoices,weshouldratherhavethreeparalleloperators:onelikepresentedinthepaper,thesecondselectingsubsetwithminimalcosts,andthethird-withmaximalcosts?

Dealingwithincompleteanduncertainknowledge,e.g.,addingcostfunctionsbasedonDempster-Shafertheoryofevidence,nonmonotoniclogics,e.g.,checkingwhetherprobabilisticmethodsaretrulysuperioroverothermethodstofindoptimalcostsinthepresenceofuncertainty(deFinetti’stheorem[69]).

Standardization(libraries)ofcostfunctions,andmeta-levelcontrol.Doesthereexistaminimalandcompletesetofcostfunctions?

Isacomplexitytheoryjustaspecialcaseofasymptoticcostfunctionmetrics?

Canwedefinebetter,moregeneral(i.e.,notbasedonlotteriesandprobabilities)andconciseaxiomsforcoststhanisprovidedbyutilitytheory(e.g.,likeKolmogorovdidinanelegantwayforprobabilitytheory)?

Theminimalandcompletesetofvariationoperators:doesasolepairsend/receiveoperatorsaspresentedinthepaperformacompletesetofvariationoperators?

Investigationoftechniquesforprofilingandreinforcementlearningofcostfunctions.

Theextensionofthe-optimizationforthedomainofcontinuous(nonenumerable)systems(e.g.,forreal-valueneuralnets).

Amorepreciseinvestigationofthe(,,,,andsoon).

-optimizationself-adaptationofitscontrolparameters

98E.Eberbach/$-CalculusofBoundedRationalAgents

Howtoextendnegationoperatortobeusedwithcomposite(interruptible)costexpressions?Emergingglobalbehavior(globaloptimization)forthecaseofverylargenumberof(massivelyparallel)agents(e.g.,forDNA-basedagentsorquantumcomputingagents).

Therelationofthe$-calculuswithCOIN(COllectiveINtelligence)[87],andinparticular,the$-calculusapproachtoBraess’paradox,theElFarolbarproblem,thetragedyofcommons.Costlanguagesdesignandimplementation.

Thedesignandimplementationofanytimeevolvablerobots.

Thedesignandimplementationofevolvablecost-drivencomputerarchitectures.Electroniccommercemarketbehavioranalysis,predictionandcontrol.

Designandimplementationofhybridexpertsystems,neuralnets,geneticalgorithmsandfuzzysystems.

References

[1]BckT.,FogelD.B.,MichalewiczZ.(eds.),HandbookofEvolutionaryComputation,OxfordUniversity

Press,1997.

[2]BarhenJ.,ProtopepscuV.,ReisterD.(1997)TRUST:ADeterministicAlgorithmforGlobalOptimization,

Science.vol.276,pp.1094-1097.May16,1997.[3]BellmanR.E.,DynamicProgramming,PrincetonUniversityPress,1957.[4]BlakeC.L.,MertzC.J.,UCIRepository

http://www.ics.uci.edu/˜mlearn/MLRepository.html,1998.

of

machine

learning

databeses,

[5]BergstraJ.A.,PonseA.,SmolkaS.A.(eds.),HandbookofProcessAlgebra,NothHolland,Elsevier,2001.[6]BrooksR.A.,ElephantsDon’tPlayChess,inP.Maes(ed.),DesigningAutonomousAgents:Theoryand

PracticefromBiologytoEngineeringandBack,TheMITPress,1994,3-15.[7]BrooksR.R.,ReliableSensorFusionAlgorithms:CalibrationandCostMinimization.Ph.D.Dissertation.

DepartmentofComputerScience,LouisianaStateUniversity,BatonRouge,Louisiana,1996.[8]BrooksR.R.,IyengarS.S.,andChenJ.,AutomaticCorrelationandCalibrationofNoisySensorReadings

usingEliteGeneticAlgorithms,ArtificialIntelligence.vol.18,No.1-2,pp.339-354.July,1996.[9]BrooksR.R.,IyengarS.S.,Multi-SensorFusion:FundamentalsandApplicationswithSoftware,Prentice

HallPTR,UpperSaddleRiver,NJ,1998.[10]BurksA.,EssaysonCellularAutomata,Univ.ofIllinoisPress,1970.

[11]ChellapillaK.,FogelD.B.,AnacondaDefeatsHoyle6-0:ACaseStudyCompetinganEvolvedCheck-ersProgramagainstCommerciallyAvailableSoftware,Proc.2000CongressonEvolutionaryComputationCEC’2000,SanDiego,CA,2000,857-863.[12]ChurchA.,TheCalculiofLambdaConversion,Princeton,N.J.,PrincetonUniversityPress,1941.

[13]DeanT.,BoddyM.,AnAnalysisofTime-DependentPlanning,inProc.SeventhNationalConf.onArtificial

Intelligence,Minneapolis,Minnesota,1988,49-54.

E.Eberbach/$-CalculusofBoundedRationalAgents99

[14]EberbachE.,NeuralNetworksandAdaptiveExpertSystemsintheCSAApproach,Intern.JournalofIntel-ligentSystems,SpecialIssueonArtificialNeuralNetworks,vol.8,no.4,1993,569-602.[15]EberbachE.,CSA:IntheDirectionofGreaterRepresentationalPowerforNeurocomputing,JournalofPar-allelandDistributedComputing,vol.22,no.1,1994,107-112.[16]EberbachE.,SEMAL:ACostLanguageBasedontheCalculusofSelf-modifiableAlgorithms,Intern.Jour-nalofSoftwareEngineeringandKnowledgeEngineering,vol.4,no.3,1994,391-408.[17]EberbachE.,AGenericToolforDistributedAIwithMatchingasMessagePassing,Proc.oftheNinthIEEE

Intern.Conf.onToolswithArtificialIntelligenceTAI’97,NewportBeach,California,1997,11-18.[18]EberbachE.,BrooksR.,PhohaS.,FlexibleOptimizationandEvolutionofUnderwaterAutonomousAgents,

in:NewDirectionsinRoughSets,DataMining,andGranular-SoftComputing,LNAI1711,Springer-Verlag,1999,519-527.[19]EberbachE.,Expressivenessof$-Calculus:WhatMatters?,in:AdvancesinSoftComputing,Proc.ofthe9th

Intern.Symp.onIntelligentInformationSystemsIIS’2000,Bystra,Poland,Physica-Verlag,2000,145-157.[20]EberbachE.,$-CalculusBoundedRationality=ProcessAlgebra+AnytimeAlgorithms,in:(ed.J.C.Misra)

ApplicableMathematics:ItsPerspectivesandChallenges,NarosaPublishingHouse,NewDelhi,Mumbai,Calcutta,2001,213-220.[21]EberbachE.,IsEntscheidungsproblemSolvable?BeyondUndecidabilityofTuringMachinesandItsConse-quenceforComputerScienceandMathematics,in:(ed.J.C.Misra)ComputationalMathematics,ModellingandAlgorithms,NarosaPublishingHouse,NewDelhi,2003,1-32.[22]EberbachE.,WegnerP.,BeyondTuringMachines,TheBulletinoftheEuropeanAssociationforTheoretical

ComputerScience(EATCSBulletin),81,Oct.2003,279-304.[23]EberbachE.,DuarteCh.,BuzzellCh.,MartelG.,APortableLanguageforControlofMultipleAutonomous

VehiclesandDistributedProblemSolving,Proc.ofthe2ndIntern.Conf.onComputationalIntelligence,RoboticsandAutonomousSystemsCIRAS’03,Singapore,Dec.15-18,2003.[24]EberbachE.,GoldinD.,WegnerP.,Turing’sIdeasandModelsofComputation,in:(ed.Ch.Teuscher)Alan

Turing:LifeandLegacyofaGreatThinker,Springer-Verlag,2004,159-194.[25]EberbachE.,EberbachA.,OnDesigningCO$T:ANewApproachandProgrammingEnvironmentforDis-tributedProblemSolvingBasedonEvolutionaryComputationandAnytimeAlgorithms,Proc.2004CongressonEvolutionaryComputationCEC’2004,vol.2,Portland,OR,2004,1836-1843.[26]FogelD.B.,AnIntroductiontoEvolutionaryComputationTutorial,2001CongressonEvolutionaryCompu-tationCEC’2001,Seoul,Korea,2001.[27]GarveyA.,LesserV.,Design-to-TimeReal-TimeScheduling,IEEETransactionsonSystems,Man,and

Cybernetics,23(6),1993,1491-1502.[28]GarzonM.,ModelsofMassiveParallelism:AnalysisofCellularAutomataandNeuralNetworks,Springer-Verlag,1995.[29]GoldinD.,PersistentTuringMachinesasaModelofInteractiveComputation,FoIKS’00,Cottbus,Germany,

2000.[30]GloverF.,GeneticAlgorithmsandScatterSearch:UnexpectedPotentials,StatisticsandComputing,vol.4,

1994,131-140.[31]GloverF.,TabuThresholding:ImprovedSearchbyNonmonotonicTrajectories,ORSAJournalonComput-ing.vol.7,No.4,1995,426-442.

100E.Eberbach/$-CalculusofBoundedRationalAgents

[32]GloverF.,TabuSearchFundaments,TechnicalReport,GraduateSchoolofBusiness,UniversityofColorado,

Boulder,CO,(1995).[33]HartP.E.,NilssonN.J.,RaphaelB.,AFormalBasisfortheHeuristicDeterminationofMinimumCostPaths,

IEEETrans.SSCSSC-4,1968,100-107.[34]HoareC.A.R.,CommunicatingSequentialProcesses,Prentice-Hall,1985.

[35]HollandJ.,AdaptationinNaturalandArtificialSystems,secondedition,TheMITPress,1992.

[36]HookerJ.N.,Needed:AnEmpiricalScienceofAlgorithms,OperationsResearch,vol.42,March-April

1994,201-212.[37]HopcroftJ.E.,MotwaniR.,UllmanJ.D.,IntroductiontoAutomataTheory,Languages,andComputation,

2ndedition,Addison-Wesley,2001.[38]HorvitzE.,ReasoningaboutBeliefsandActionsunderComputationalResourcesConstraints,inProc.ofthe

1987WorkshoponUncertaintyinArtificialIntelligence,Seattle,Washington,1987.[39]HorvitzE.,ZilbersteinS.(eds.),ComputationalTradeoffsunderBoundedResources,ArtificialIntelligence

126,2001,1-196.[40]HuT.C.,KahngA.B.,TsaoC.-W.A.,OldBachelorAcceptance:ANewClassofNon-MonotoneThreshold

AcceptanceMethods,ORSAJournalonComputing.vol.7,No.4,(1995),pp417-425.[41]KozaJ.,“GeneticProgramming:OntheProgrammingofComputersbyMeansofNaturalSelection”,“Ge-neticProgrammingII:AutomaticDiscoveryofReusablePrograms”,“GeneticProgrammingIII:DarvinianInventionandProblemSolving”,TheMITPress,1992,1994,and1999.[42]KozaJ.,AdvancedGeneticProgrammingTutorial,ThirdGeneticProgrammingConf.GP-98,Univ.ofWis-consin,Madison,1998.[43]KumarV.,GramaA.,GuptaA.,KarypisG.,IntroductiontoParallelComputing:DesignandAnalysisof

Algorithms,TheBenjamin/Cummings,1994.[44]KuratowskiK.,IntroductiontoSetTheoryandTopology,PWN,Warsaw,1977.

[45]LaarhovenP.J.M.,AartsE.H.L.,SimulatedAnnealing:TheoryandApplications.D.ReidelPublishingCo.

Dordrecht,Netherlands,(1987).[46]LangtonCh.,ArtificialLife:AnOverview,TheMITPress,1996.

[47]LastM.,KandelA.,MaimonO.,EberbachE.,AnytimeAlgorithmforFeatureSelection,in:(eds.W.Ziarko,

Y.Yao)RoughSetsandCurrentTrendsinComputing,SecondIntern.Conf.onRoughSetsandCurrentTrendsinComputingRSCTC’2000,Banff,Canada,Oct.2000,RevisedPapers,LNAI2005,Springer-Verlag,2001,532-539.[48]LiuJ.W.S.,LinK.J.,ShihW.K.,YuA.C.,ChungJ.Y.,ZhaoW.,AlgorithmsforSchedulingImpreciseCom-putations,IEEEComputer,24,1991,58-68.[49]LiuH.,MotodaH.,FeatureSelectionforKnowledgeDiscoveryandDataMining,KluwerAcademicPub-lishers,1998.[50]LohnJ.,Self-ReplicationSystemsinCellularSpaceModelsTutorial,GeneticProgrammingConference

GP97,StanfordUniversity,1997.[51]MaesP.(ed.),DesigningAutonomousAgents:TheoryandPracticefromBiologytoEngineeringandBack,

TheMITPress,1994.

E.Eberbach/$-CalculusofBoundedRationalAgents101

[52]MaimonO.,LastM.,KnowledgeDiscoveryandDataMining,theInfo-FuzzyNetwork(IFN)Methodology,

Kluwer,2000(inpress).[53]MichalewiczZ.,GeneticAlgorithms+DataStructures=EvolutionPrograms,thirdedition,Springer-Verlag,

1996.[54]MichalewiczZ.,FogelD.B.,HowtoSolveIt:ModernHeuristics,Springer-Verlag,2000.

[55]MichalskiR.S.,BratkoI.,KubatM.,MachineLearningandDataMining:MethodsandApplications,John

Wiley&Sons,1998.[56]MilnerR.,ACalculusofCommunicatingSystems,Lect.NotesinComputerSciencevol.94,Springer-Verlag,

1980.[57]MilnerR.,OperationalandAlgebraicSemanticsofConcurrentProcesses,in:HandbookofTheoretical

ComputerScience,Vol.B:FormalModelsandSemantics,J.VanLeeuwen,ManagingEditor,TheMITPress/Elsevier,1990,1203-1242.[58]MilnerR.,ParrowJ.,WalkerD.,ACalculusofMobileProcesses,I&II,InformationandComputation100,

1992,1-77.[59]MilnerR.,ThePolyadic-Calculus:ATutorial,inF.L.Bauer,W.Brauer(eds.)LogicandAlgebraofSpecifi-cation,Springer-Verlag,1992,203-246.

[60]MilnerR.,ElementsofInteraction,CACM,Jan.1993,vol.36,no.1,78-.

[61]MilnerR.,OperationalandAlgebraicSemanticsofConcurrentProcesses,in:(ed.J.vanLeeuwen)Handbook

ofTheoreticalComputerSciece,Vol.B:FormalModelsandSemantics,ElsevierandTheMITPress,1994,1203-1242.[62]MoravecH.,MindChildren,HarvardUniv.Press,1988.

[63]NilssonN.,ProblemSolvingMethodsinArtificialIntelligence,McGraw-Hill,1971.[]NilssonN.,ArtificialIntelligence:ANewSynthesis,MorganKaufmann,1998.[65]PawlakZ.,RoughSets,Int.J.ComputerandInformationSci.,11,1982,341-356.

[66]PhohaS.,PelusoE.,StadterP.,StoverJ.,GibsonR.,AMobileDistributedNetworkofAutonomousUndersea

Vehicles,Proc.ofthe24thAnnualSymposiumandExhibitionoftheAssociationforUnmannedVehicleSystemsInternational,Baltimore,MD,1997.[67]PlotkinG.,StirlingC.,TofteM.,Proof,Language,andInteraction:EssaysinHonourofRobinMilner,MIT

Press,2000.[68]QuinlanJ.R.,C4.5:ProgramsforMachineLearning,MorganKaufmann,1993.

[69]RussellS.,NorvigP.,ArtificialIntelligence:AModernApproach,Prentice-Hall,1995(2nded.2003).[70]RussellS.,WefaldE.,DotheRightThing:StudiesinLimitedRationality,TheMITPress,1991.

[71]ShannonC.E.,Programmingacomputerforplayingchess,PhilosophicalMagazine,41(4),1950,256-275.[72]SiegelmannH.T.,NeuralNetworksandAnalogComputation:BeyondtheTuringLimit,Birkhauser,1999.[73]SipperM.etal,TheFireflyMachine:OnlineEvolware.InProc.ofIEEEFourthIntern.Conf.onEvolutionary

ComputationICEC’97,1997.[74]SuttonR.S.,BartoA.G.,ReinforcementLearning:AnIntroduction,MITPress,1998.

[75]SuttonR.S.,TowardGroundingKnowledgeinPredictionorTowardaComputationalTheoryofArtificial

Intelligence,aninvitedtalkatCongressonEvolutionaryComputationCEC’2000,SanDiego,July18,2000.

102E.Eberbach/$-CalculusofBoundedRationalAgents

[76]TamK.,LloydJ.,LesperanceY.,LevesqueH.,LinF.,MarcyD.,ReiterR.,JenkinM.,ControllingAu-tonomousRobotswithGOLOG,inProc.oftheTenthAustralianJointConf.onArtificialIntelligenceAI’97,LNAI,Springer-Verlag,1997,1-12.[77]TuringA.,OnComputableNumbers,withanApplicationtotheEntscheidungsproblem,Proc.oftheLondon

MathematicalSociety,ser.2,vol.42,1936-37,230-265;corrections,Ibid,vol.43,1937,544-546.[78]TuringA.,SystemsofLogicbasedonOrdinals,Proc.oftheLondonMathematicalSociety,ser.2,vol.45,

1939,161-228.[79]VanLeeuwenJ,(ed.),HandbookofTheoreticalComputerScience,Vol.AandB,TheMITPress/Elsevier,

1990.[80]VanLeeuwenJ.,WiedermannJ.,TheTuringMachineParadigminContemporaryComputing,2001.[81]VonNeumannJ.,MorgensternO.,TheoryofGamesandEconomicBehavior,PrincetonUniversityPress,

1944.[82]WegnerP.,WhyInteractionisMorePowerfulThanAlgorithms,CACM,May1997,vol.40,no.5,81-91.[83]WegnerP.,InteractiveFoundationsofComputing,TheoreticalComputerScience,192,1998,315-351.[84]WegnerP.,GoldinD.,CoinductiveModelsofFiniteComputingAgents,ElectronicNotesinTheoretical

ComputerScience,vol.19,1999.[85]WegnerP.,EberbachE.,NewModelsofComputation,TheComputerJournal,47(1),TheBritishComputer

Society,OxfordUniversityPress,2004,4-9.[86]WolfeW.L.,IntroductiontoImagingSpectrometers,TutorialText,vol.TT25,SPIEPress,Bellingham,WA,

1997.[87]WolpertD.H.,TumerK.,AnIntroductiontoCollectiveIntelligence,inBradshawJ.M.ed.,Handbookof

AgentTechnology,AAAIPress/MITPress,2000.[88]ZadehL.A.,FuzzySets,InformationandControl,12,1965,338-353.

[]ZilbersteinS.,OperationalRationalitythroughCompilationofAnytimeAlgorithms,Ph.D.Thesis,Univ.of

CaliforniaatBerkeley,1993.