Evolving self-organizing behaviors for a swarm-bot

foraSwarm-bot

MarcoDorigo1,VitoTrianni1,ErolS¸ahin1,ThomasH.Labella1,

RoderichGross1,GianlucaBaldassarre3,StefanoNolfi3,

Jean-LouisDeneubourg2,FrancescoMondada4,DarioFloreano4,LucaM.Gambardella5

IRIDIA-Universit´eLibredeBruxelles,Belgium2

CENOLI-Universit´eLibredeBruxelles,Belgium

3

InstituteofCognitiveSciencesandTechnologies-CNR,Roma,Italy4

ASL-SwissFederalInstituteofTechnology,Lausanne,Switzerland

5

IDSIA,Manno-Lugano,Switzerland

1

Abstract

Swarmroboticsisanemergentfieldofcollectiveroboticsthat,takinginspirationfrominsectsocieties,studiesthedevelopmentofdistributed,robustandefficientgroupsofinteractingrobots.Inthispaper,wein-troduceaswarmroboticsystem,calledaswarm-bot.Aswarm-botisaself-assemblingandself-organizingartifactcomposedofaswarmofs-bots,mobilerobotswiththeabilitytoconnectto/disconnectfromeachother.Thispaperdescribessomeoftheresultsweobtainedwhiletryingtode-velopthecontrolsystemsofaswarm-bot.Inparticular,weaddresstheproblemofsynthesizingcontrollersfortheswarm-botusingArtificialEvo-lution.Wedescribethemotivationbehindthechoiceoftheevolutionaryapproachandweprovideexamplesofitsapplication,detailingtheresultsobtainedindifferenttasks,namelyaggregationandcoordinatedmotion.Weshowhowevolutionisabletoproducesimplebuteffectivesolutions,whichleadtotheemergenceofself-organizationintheswarm-bot.

1Introduction

Swarmroboticsisanovelapproachtothedesignandimplementationofroboticsystems.Thesesystemsarecomposedbyswarmsofrobotstightlyinteractingandcooperatingtoreachtheirgoal.Swarmroboticscanbeconsideredaninstanceofthemoregeneralfieldofcollectiverobotics.Itisinspiredbythesocialinsectmetaphor,andemphasizesaspectslikedecentralizationofthecontrol,limitedcommunicationabilitiesamongrobots,emergenceofglobalbehaviorandrobustness.Inaswarmroboticsystem,althougheachsinglerobotoftheswarmisafullyautonomousrobot,theswarmasawholecansolveproblemsthatthesinglerobotcannotdo,becauseofphysicalconstraintsorlimitedcapabilities.Thedefinitionofthecontrolsystemforaroboticswarmistheproblemwe

1

addressinthispaper.Inparticular,wepresentthechallengeswearefacingandtheresultsobtainedfromtheongoingworkwithintheSWARM-BOTSproject1.

TheaimoftheSWARM-BOTSprojectisthedevelopmentofanewroboticsystem,calledaswarm-bot[16,11].Aswarm-botisdefinedasanartifactcomposedofaswarmofs-bots,mobilerobotswiththeabilitytoconnectto/disconnectfromeachother.Acompanionpaper[12]submittedtothissamespecialissue,discussesthehardwarerealizationofourswarmroboticsystem2.S-botshavesimplesensorsandmotorsandlimitedcomputationalcapabilities.Theirphysicallinksareusedtoassembleintoaswarm-botabletosolveproblemsthatcannotbesolvedbyasingles-bot.

Figure1:Thes-botprototype.Ontherightsideisshowntherigidgripper,whileontherightsidethereistheflexibleone.Grippersallowtophysicallylinktwos-bots.Theupperpartalsoholdsthesensorsandtheelectronics.Itcanrotatewithrespecttothethelowerpartofthebody(thetractionsystem)whichisequippedwithtracksandwheels.

Intheswarm-botformthes-botsareattachedtoeachotherandtheroboticsystemisasinglewholethatcanmoveandreconfigurewhenneeded.Forexample,itmighthavetoassumedifferentshapesinordertogothroughanarrowpassageorovercomeanobstacle.Physicalconnectionsbetweens-botsareimportantforsolvingmanycollectivetasks.Forexample,s-botscanformpullingchainsinanobjectretrievalscenario.Or,inanavigationonroughterrainscenario,physicallinkscanserveassupportiftheswarm-bothastopassoveraholelargerthanasingles-bot,orwhenithastopassthroughasteepconcaveregion.Inotheroccasions,aswarmofunconnecteds-botsmightbemoreefficient,forexample,whensearchingforagoallocationorwhentracinganoptimalpathtoagoal.

Thesearesomeexamplesofthetasksaswarm-botshouldbeabletoperform.

Inthispaper,wefocusourattentioninprovidingthes-botswithtwoimpor-tantcapabilitiesthatareoffundamentalimportanceinmanycooperativetasks.Thesearethecapabilitiestoperformaggregationandtodistributedlycoordinatetheactivitiesofthegroup.Aggregationisofparticularinterestbecauseitisaprerequisiteforthedevelopmentofotherformsofcooperation:forexample,inordertoassembleinaswarm-bot,s-botsshouldfirstbeabletoaggregate.Therefore,theaggregationabilitycanbeconsideredasthepreconditionfortherealizationofothertasksthattheswarm-botisexpectedtobeabletocarryout.Ontheotherhand,theabilitytocoordinatetheactivitiesofthegroupiscrucialfortheeffectivenessofaswarm-bot:forexample,whencarryinganheavyobjectthatasingles-botcannotmove,alls-botsshouldcoordinateandpullorpushinthesamedirection,inordertomaximizetheperformanceoftheswarm-bot.Similarly,whentwoormoreofsuchobjectshavetobetransported,itisdesiredthatthewholegroupofs-botscoordinatesitsactivityfocusingonasingleobjectratherthanhavingsmallandinefficientgroupsattemptingtomovedifferenttargets.Aggregationandcoordinatedactivityarethemainfocusoftheexperimentspresentedinthispaper.

Inthefollowing,weaddresstheproblemofdefiningthecontrolsystemofthes-botsusingArtificialEvolution,andwediscussthemotivationsbehindthischoiceinSection2.InSection3,wepresenttheresultsobtainedevolvingsimpleneuralnetworksfortheaggregationtask.Section4presentsanexampleofthecollectivechoicetask,whereaswarm-botformedbyacollectionofassembleds-botshastoproducecoordinatedmovement.Finally,Section5concludesthepaperwithsomediscussionabouttheproposedapproach.

2ChallengesandMethodologies

Intheprevioussection,wehavepresentedtheswarm-botandsomeexamplesoftasksitshouldbeabletoperform.Eventhoughthisisonlyaroughdescription,itsuggeststhatcontrollingsuchasystemisachallengingproblem.Distributed-ness,robustness,embodiment,localityofsensing,dynamicinteractionsbetweens-botsareaspectsthathavetobetakenintoaccountwhendevelopingacontrolsystemforsuchanartifact.Isitpossibletofindsomebasicprinciplestobefollowedwhenfacingthischallenge?

Apossibleanswerissuggestedbythenotionofself-organization[5].Self-organizationexplainshow,inasystem,globallevelorderemergesfromthenumerouslocalinteractionshappeningamongthelower-levelcomponentsofthesystem.Inotherwords,asystemself-organizesdrivenbyitsowncomponents,whichinteractrelyingonlyonlocalinformation,withoutanyreferencetothesystemasawhole.Aformofself-organizationofparticularinterestforourworkisself-assembling,theself-organizedcreationofstructures.Self-assemblingoccursinawiderangeofnaturalsystemsrangingfromchemistrytobiology,anditcharacterizesthebehaviorofmanysocialinsects(forareview,see[1]).

Socialinsects,andanimalsocietiesingeneral,presentmultipleformsofself-organizationandself-assembling.Insuchsystems,theinteractionsamongindividualsaremadeusingsimplerulesthatrequire:(i)alimitedcognitiveabilityand(ii)alimitedknowledgeoftheenvironment.Fromageneralpointofview,self-organizationemergesfromtheinterplayoftwobasicmechanisms:positiveandnegativefeedback.Forexample,collectivedecisionsoftenresult

3

fromacompetitionamongdifferentsourcesofinformation,whichareampli-fiedthroughdifferentformsofpositivefeedback.Ontheotherhand,negativefeedbackregulatestheamplificationprocess,andoftenarises“automatically”astheresultofthesystem’slimitsorconstraints(e.g.,limitationinfood,intheavailablespace,orinthenumberofindividuals)[5,6,7,8,9,10,15,17,18].

Self-organizationandself-assemblingarefundamentaltotheSWARM-BOTSproject.Infact,s-bots,exploitingonlylocalinformation,shouldbeabletoself-organize,self-assembleandcoordinatetheiractivities.Thus,understandingthemechanismsthatdrivetheemergenceofself-organizationisoffundamentalim-portance.Ifweareabletoreproducethemechanismsobservedinself-organizingsystems,thenwecanusethemtoefficientlycontrolourartificialswarms.

However,designingaself-organizingcontrolsystemfortheswarm-botisnotatrivialtask.Fromanengineeringperspective,thedesignproblemisgenerallydecomposedintotwodifferentphases:(i)thebehaviorofthesystemshouldbedescribedastheresultofinteractionsamongindividualbehaviors,and(ii)theindividualbehaviorsmustbeencodedintocontrollers.Bothphasesarecomplexbecausetheyattempttodecomposeaprocess(theglobalbehaviorortheindividualone)thatemergesfromadynamicalinteractionamongitssub-components(interactionsamongindividualsorbetweenindividualactionsandenvironment).

NolfiandFloreano[13]claimthat,sincetheindividualbehavioristheemer-gentresultoftheinteractionbetweenagentandenvironment,itisdifficulttopredictwhichbehaviorresultsfromagivensetofrules,andwhicharetherulesthatwillcreateagivenbehavior.Similardifficultiesarepresentinthedecom-positionoftheorganizedbehaviorofthewholesystemintointeractionsamongindividualbehaviorsofthesystemcomponents.Here,theunderstandingofthemechanismsthatleadtotheemergenceofself-organizationmusttakeintoac-countthedynamicinteractionsamongindividualcomponentsofthesystemandbetweencomponentsandenvironment.Thus,itisdifficulttopredict,givenasetofindividualbehaviors,whichbehavioratthesystemlevelwillemerge,anditisalsodifficulttodecomposetheemergenceofadesiredglobalbehaviorinsimpleinteractionsamongindividuals.Thedecompositionfromtheglobaltotheindividualbehaviorscouldbesimplifiedbytakinginspirationfromnaturalsystems,likeinsectsocieties,thatcouldteachuswhicharethebasicmecha-nismstobeexploited[4].However,itisnotalwayspossibletotakeinspirationfromnaturalprocesses,becausetheymaydifferfromtheartificialsystemsinmanyimportantaspects(e.g.,thephysicalembodiment,thetypeofpossibleinteractionsbetweenindividualsandsoforth),orbecausetherearenonaturalsystemsthatcanbecomparedtotheartificialone.

Ourworkinghypothesisisthattheseproblemscanbeefficientlysolvedrely-ingonArtificialEvolution[13].Evolutioneliminatestheproblemofdecomposi-tionatboththeleveloffindingthemechanismsthatleadtotheemergentglobalbehaviorandatthelevelofimplementingthosemechanismsinacontrollerforthes-bots.Infact,itreliesontheevaluationofthesystemasawhole,thatis,ontheemergenceofthedesiredglobalbehaviorstartingfromthedefinitionoftheindividualones.Forexample,wewillshowinSection3howtheaggregationproblemcanbesolvedbyverysimpleevolvedstrategies,withouttheneedofdecompositionatanylevel.

Moreover,evolutioncanexploittherichnessofpossiblesolutionsofferedbythedynamicalagent-environmentinteractions[13].Inamulti-agentsystemlike

4

theswarm-bot,thesedynamicaspectsareenrichednotonlybythepresenceofmultipleagents,butalsobythepossiblepresenceofphysicallinksbetweenagents.Generally,theseaspectsaredifficulttobeexploitedbyhanddesign,butthisispossiblerelyingonanevolutionaryprocess.Section4describesanexperimentalsetupwhichexemplifiesthissituation:inthiscase,physicalconnectionsbetweens-botscreatenon-linearitiesthatareatthebasisoftheefficiencyoftheevolvedbehaviors.

3EvolvingAggregationBehaviors

Inthissection,wepresenttheresultsobtainedevolvingneuralcontrollersfortheaggregationtask.Weranasetofevolutionaryexperimentsinwhichagroupofsimulateds-botshadtoaggregateinaclusterformation,withoutrelyingonanyenvironmentalsignal[19].Inthefollowing,wedescribetheexperimentalsetupdefinedfortheevolutionofclusteringbehaviors.Then,theobtainedcontrollersareanalyzedandtheirpropertiesandlimitationsarediscussed.

3.1ExperimentalSetup

Asimplifiedmodelofans-botisusedintheseexperiments,performedinsim-ulationusingVortexTM,arigidbodydynamicssimulator,whichreproducesthedynamics,frictionandcollisionsbetweenphysicalbodies.Ans-bot(seeFigure2)hasacylindricalbody(12cmradius,6cmheight),twomotorizedwheels,avirtualgripperthatallowsittoconnecttoanothers-bot(whenthelatters-botiswithinagrippableareashownintheFigure2awithadottedrectangle),andanomni-directionalspeakerthatcontinuouslyproducesatonethatcanbeearedbyothers-bots.Eachs-botisalsoprovidedwitheightin-fraredproximitysensors,threesoundsensors(directionalmicrophones),threeconnectionsensors,andagrippersensorsimulatingalightbarrieronthegrip-per.Theenvironmentconsistsofasquaredarenasurroundedbywalls.Thesizeofthearenaischosentobe2×2metersanditisfourtimesbiggerthantheperceptualrangeofthes-bots.Infraredsensorsweresimulatedbyusingasamplingtechnique[13].Soundsensorsweresimulatedbyasetofequations[2].

(a)(b)

Figure2:Aschematics-botseenfromthetop.(a)Actuators:motorizedwheels(twograyrectangles),areaofgripping(dottedrectangle),omni-directionalspeaker(blackcircle).(b)Sensors:proximitysensors(blackrectangles),di-rectionalmicrophones(whitecircles),connectionsensors(threeregionsmarkedwithadashedlinearoundthebody),alightbarriersensoronthegripper(dottedrectangle).

5

Theconnectionsensorsareusedtosensewhetherandatwhichpositiononthebody(withinthreedifferentareas,seeFigure2)anothers-bothasbeengripped.Thelightbarriersensordetectswhetheranobjectisgrippable.

Theinitialpopulationconsistsof40randomlygeneratedgenotypestringsthatencodetheconnectionweightsof40correspondingneuralcontrollers.Eachcontrollerisaneuralnetworkwith17sensoryneurons,thatencodethestateofthe16sensorsandabiasunit(i.e.,aunitwhoseactivationstateisalways1.0).Eachsensoryneuronisdirectlyconnectedwith3motorneurons,thatcontrolthespeedofthetwowheelsandthegripper(seeFigure3).Thus,theneuralcontrollerismadeupof17×3=51connections,eachassociatedtoaweightrangingintheinterval[-10,+10]andrepresentedinthegenotypewith8bits.Therefore,thegenotypeiscomposedby51×8=408bits.Eachgenotypeismappedinto5identicalneuralcontrollerscorrespondingtoagroupof5s-bots[2].Thegroupisallowedto“live”for10“epochs”(eachepochconsistsof600cyclesandeachcyclesimulates100msofrealtime).Atthebeginningofeachepochthes-botsareplacedinrandomlyselectedpositionsandorientationswithinthearena.Duringeachcycle,foreachs-bot:(1)theactivationstateofthesensorsissetaccordingtotheabovementionedprocedures;(2)theactivationstateofthethreemotorneuronsiscomputedaccordingtothestandardlogisticfunction;(3)thedesiredspeedofeachwheelissetaccordingtotheactivationstatesofthecorrespondingmotorunitandlinksbetweens-botsareformedorreleasedaccordingtothestateofthemotorcontrollingthegripper,thestateofthegripper(openorclosed)andtherelativepositionofthes-bots.

wheels

gripper

. . .. . .. . .8 proximity3 sound3 connectiongripperbiasFigure3:Theperceptronusedtocontrolans-bot.Theconnectionwightsofthisneuralnetworkareevolvedinasinglegenotype.Thesamenetworkisclonedinalls-botsinvolvedintheexperiments.

Inordertoevolves-botsabletoaggregate,weevaluatethefitnessofagenotypeastheaveragedistanceofthes-botsfromtheircenterofmass.Inparticular,thefitnessFismeasuredaveragingthequalityofclusteringf(t)inatimewindowcorrespondingtothelastW=100cyclesofeachepoch:

F=

1

Thequalityofclusteringiscomputedaccordingtothefollowingequations:

f(t)=

1

n

n󰀂j=1

Xj(t)󰀃,

whereXi(t)isthepositionvectoroftheiths-botattimet.Thedistancedi(t)

isthresholdedtoamaximumof50cminordertohavefitnessvaluesintheinterval[0,1].Inthisexperiments,wearemainlyinterestedinself-organizedaggregation,andnotspecificallyinself-assembling.Forthisreason,thefit-nessfunctiondoesnotencouragetheestablishmentofconnections.However,connectionsmightappearastheyminimizethedistancebetweentwos-bots.

Everygeneration,thebest8genotypesareselected,andeachonegenerates5offspring.Eachoffspringismutatedwithaprobability2/Lofreplacingeachbitwithanewrandomlyselectedvalue,whereListhelengthofthegenotype.Parentsarenotcopiedinthepopulationofthenextgeneration.Theevolu-tionaryprocesslasts100generations.Theexperimentisreplicated10timesbystartingwithdifferentrandomlygeneratedinitialpopulations.

3.2BehavioralAnalysis

Byrunningtheevolutionaryexperiment,weobservedtheemergenceoftwotypeofstrategies:astaticandadynamicclusteringbehavior.Thestaticcluster-ingbehaviorcreatescompactclusterswheres-botsstayclosetoeachotheranddonotchangetheirrelativepositions,asshowninFigure4a.Differently,thedynamicclusteringbehaviorcreatesratherloosebutmovingclusters(seeFig-ure4b).Alltheevolutionaryrunsperformedresultedinabehaviorthatcouldbeclassifiedinoneofthesetwoclasses;inthefollowing,weanalyzethemostrepresentativeofbothclasses3.3.2.1

Staticclusteringbehavior

Theevolvedstaticclusteringbehaviorleadstotheformationofcompactclus-ters,wheres-bots,performingsmallmovesorwhirl,areabletoconstantlymon-itorthepositionoftheirneighbors,inordertostayclosetoeachotherwithoutchangingtheirrelativepositions.

Figure5showstheperformanceachievedduringtheevolutionofastaticclusteringbehavior.Thebestandtheaveragefitnessvaluesofthepopulation

(a)(b)

Figure4:Snapshotsoftheformedaggregate.(a)Staticclusteringbehavior.(b)Dynamicclusteringbehavior.

areplottedforeachgeneration.Itcanbeseenthatagoodbehaviorisdiscoveredquiteearlyintheevolution,anditisthenslowlyrefined.Initially,thes-botswhirlwhentheyareclosetoeachother,maintainingacertaindistanceamongthem.

Weanalyzetheevolvedbehaviorinthreedifferentcases:first,weobservehowans-botexploresthearenainordertosearchforothers-botsorforalreadyformedclusters.Then,weobservehows-botsapproachandreacttothepresenceofanothers-botorofacluster.Figure6(a)showsthetrajectoryofasingles-botinthearena.Thestartingpositionofthes-botismarkedwithacircle.Whennoobjectsarevisible,thes-botmovesalongacirculartrajectory.Whenthes-botgetsclosetothewall,itrotatesclockwise,andrestartsitscircularmovementafterward.Thecirculartrajectory,havingadiameterbiggerthanthesideofthearena,guaranteesthatthes-bot’sexplorationwillnotgetstuckinaninfiniteloopatthecenterofthearena.

Whentwos-botsgetclose,theattractiontosoundsourcesbecomespredom-inant,andthetrajectorieschange:thetwos-botstendtobounceoneagainsttheother,duetotheinterplaybetweenattractionandrepulsionoriginatingfromsoundandinfraredsensorsrespectively(seeFigure6(b)).Thisindicatesthatclustersoftwos-botsareveryunstable.However,duringthetimespent

1.210.8fitness0.60.40.20

bestaverage

0102030405060708090100

generation number

Figure5:Evolutionofthestaticclusteringbehavior:thebestandtheaveragefitnessvaluesofthepopulationareplotted.

8

(a)(b)(c)

Figure6:Staticclusteringbehavior:(a)trajectoryofasingles-bot.Seetextforexplanation;(b)thetrajectoriesoftwos-botsapproachingandbouncingoffafterward;(c)thetrajectoryofans-botapproachinganalreadyformedcluster.closetoeachother,thepaircanattractothers-botswhichcanjointhecluster,increasingitssizeandstability.

Figure6(c)showsthetrajectoryofans-botapproachingaclusteroffours-bots,whicharefixedatthecenterofthearena,constitutingastablesourceofattraction.Oncethefrees-bot“hears”thesoundemittedbytheclustereds-bots,itstopsandstartswhirling.Thiswhirlingbehavioriscausedbythehighintensityofthesoundheard.Whilethes-botiswhirling,itissubjecttoastrongattractiontothesoundsourcesandaweakerrepulsionfromobstacles.Asthes-botgetsclosertothecluster,theintensityofsoundreceivedincreases,untilacertainthresholdisreached.Then,thes-botmovesforward,andjoinsthecluster.

Notethattheperformanceoftheneuralcontrollerwithrespecttothegivenfitnessmeasureismaximizedbythisstrategy:s-botsareincontactwhenclus-tered,thusminimizingthedistancefromtheircenterofmass.Evolutionhasexploitedoneimportantinvariantpresentintheexperimentalsetup:thenum-berofs-bots.Infact,onlyclustersofthreeormores-botsarestable,whichconstitutesthemajorityinagroupoffives-bots.Thisassuresthatasinglesta-bleclusteroffives-botswillalwaysbeformed.Thiskindofstrategyisperfectlytunedforagroupoffives-bots,butitalsosuggeststhatwhenthegroupsizeincreasesitwillbemoredifficulttoobtainasinglecluster,butrathermultiplesmallerclusterswillbeformed.

Inordertoconfirmthishypothesis,weanalyzedthescalabilityoftheclus-teringbehaviorbyevaluatingthefitnessindifferentgroupsizes,rangingfrom2to20s-bots.Foreachsize,thefitnessofthegroupisevaluated100times4.TheresultsplottedinFigure7showthat,asexpected,thebehaviordoesnotscalewellwiththegroupsize.AsshowninFigure6(b),clustersofsizetwoarenotstable,andthisisconfirmedbythelowfitnessshownintheplot.However,itissurprisingtoseethatclustersofsizethreealsohavealowaveragefitness,andthefitnessvaluesvaryfrom0tonearly1.Thisresultcanbeexplainedbythefactthatthedensityofs-botsinthearenaistoolow,thusitislessprobablethattheycanmeetandformastableclusterwithinthelimitedtime.Thisjus-tifiesthehighvarianceinthecorrespondingdata.Sizesfourandfiverepresent

Fitness0.00.20.40.60.81.02468101214161820

Number of Robots

Figure7:Staticclusteringbehavior:Thefitnessevaluationsobtainedfordiffer-entgroupsizesareplotted.Theaveragefitnessisdrawnasathickline.Theboxesshowtheinter-quartilerangeofthedataandthehorizontalbarsinsidetheboxesmarkthemedianvalue.Thewhiskersindicatethedatarangebe-tweenthemostextremedatapointswithin1.5oftheinter-quartilerangefromthebox.Theemptycirclesmarktheoutliers.

theoptimumgroupsize,asexpected.Theperformanceofgroupsofsixs-botsisalsosatisfactory,howeverthevarianceintheperformanceincreasesduetoformationsoftwoclustersofthrees-bots.Then,asthegroupsizeincreases,theperformancedecreases,initiallyaccompaniedbyahighvarianceinthedata,duetomultiplepossiblesituations.Forlargergroupsizes,thevariancedecreases,alongwiththeperformance.Thiscanbeexplainedbytwoobservations:first,thelargerthegroupsizeis,themoresmallclustersareformed.Second,ahigherdensityofs-botscreatesahighintensityofsoundthroughoutthearena,causingallthes-botstowhirlinplace.

Theintensityofsound,asperceivablebyans-botinthearena,createsasoundfieldwhichcanbeusedtogiveanapproximateindicationofthesoundattractionforcesactingonthes-bots.Figure8plotsthechangeinthesoundfieldovertimefor5,10and20s-bots.Inthegroupoffives-bots,asingleclusterisformed,whilemultipleclustersappearedforlargergroupsizes.ThelastrowinFigure8showsthatthehighintensityofsoundinhibitstheexplorationbehaviorofthes-botsandmakesthemjointhenearests-botorcluster.3.2.2

Dynamicclusteringbehavior

Thedynamicclusteringbehaviorcreateslooseaggregates,wheres-botsstayclosetoeachother,butmoveandchangetheirrelativepositions.Inthisway,theclustercanchangeshapeandmoveacrossthearena.Weanalyzeherethemostrepresentativeevolvedbehaviorbelongingtothisclass.

Figure9plotsthebestandtheaveragefitnessofthepopulation.Notethatthefitnessvaluesaresmallerthantheonesachievedinthestaticclusteringbe-haviorevolution.Infact,thebehaviordoesnotminimizethedistancesbetweens-botsandhencetheclustersobtainedarelesscompactthantheonesobtainedwiththestaticclusteringbehavior.

Alsointhiscaseweperformananalysisoftheevolvedbehaviorobserving

10

5 s−bots

10 s−bots

20 s−bots

cycle 0cycle 250cycle 500

Figure8:Staticclusteringbehavior:Snapshotsofthesoundfieldsareshownatthreepointsintime.Eachrowcorrespondstoasimulationofclusteringwithadifferentgroupsize(5,10,and20s-bots,fromtoptobottom).Columnsshowdifferentpointsintime.

theexploringandclusteringcapabilitiesofthes-bots.Figure10(a)showsthetrajectoryofasingles-botduringexploration.Thes-botmovesslowlyandacceleratesnearanobstacle,doingasharpclockwiseturntoavoidthecolli-sion.Acirculartrajectoryisobservedwhenthes-botisfarfromanyobstacles.However,thisisnotasapparentasinthestaticclusteringbehavior.

Figure10(b)showsthetrajectoriesoftwos-botsasademonstrationofthedynamicsoftheinteraction.Whenthes-botssenseeachother,theyapproachandstartmovingtogether,oneleadingandtheotherfollowing.Thissortof“flocking”behaviorcreatesclustersthatarestillabletoexplorethearenaandmergewithothers-botsorclusters.Similarflockingmovementsmightbeob-servedalsoingroupsofthrees-bots,whileforlargerclustersthecontinuouschangeintherelativepositionsamongthes-botsresultsinaslowmovementofthewholeaggregate.Differentlyfromthestaticclusteringbehavior,thisstrat-egypresentsrobustnesswithrespecttotheformationofsub-clusters.Thus,weexpectthat,whenchangingthenumberofs-botsinvolvedintheexperimentthe

1.210.8fitness0.60.40.20

bestaverage

0102030405060708090100

generation number

Figure9:Evolutionofthedynamicclusteringbehavior:thebestandtheaveragefitnessvaluesofthepopulationareplotted.

11

(a)(b)

Figure10:Trajectoriesofthedynamicclusteringbehavior:(a)singles-botexploringtheenvironment;(b)twos-botsapproachingandflockingintheenvi-ronment.Theintermediatepositionsareshowninordertogiveanideaoftherelativepositionsduringflocking.

performancewillgracefullydegrade,andthatwewillobservetheformationofasinglecluster.

Thescalabilityanalysisconfirmsthisexpectationonthedynamicclusteringbehavior.ItisperformedinthesamewayasforthestaticclusteringbehaviorandtheresultsareplottedinFigure11.Theplotsshowthattheperformanceofthegroupdecreasesalmostlinearlywiththegroupsize.Thisdecreaseinperformanceisduetothefactthattheminimumaveragedistancetothecenteroftheclustergrowswiththenumberofs-botsduetotheirphysicalembodiment.

Inthisdynamicclusteringbehavior,therearenounstableclusters.Onthecontrary,clusterscanmoveintheenvironment,eachs-botmaintainingitsaveragedistancefromthecenterofmassandeventuallyformingasingleaggregate.Thebestcaseistheclusteroftwo,mainlybecausethes-botscanstayveryclosetoeachother.Thisanalysisconfirmsthattheevolvedbehavioriswellsuitedfordifferentgroupsizes,assub-clusters,whenformed,cancontinuetheaggregationprocess.

Fitness0.00.20.40.60.81.02468101214161820

Number of Robots

Figure11:Dynamicclusteringbehavior:Thefitnessobtainedfordifferentgroupsizesisplotted.Theaveragefitnessisdrawnasathickline(seealsoFigure7forexplanationofthegraph).

12

5 s−bots

10 s−bots

20 s−bots

cycle 0cycle 250cycle 500

Figure12:Dynamicclusteringbehavior:Snapshotsofthesoundfieldsareshownatthreepointsintime.Eachrowcorrespondstoasimulationofclusteringwithadifferentgroupsize(5,10,and20s-bots,fromtoptobottom).Columnsshowthedifferentpointsintime.

Figure12showsthesnapshotsofsoundfieldsobservedfromthedynamicclusteringbehavior.Itisworthnotingthat,unliketheobservationsmadeonstaticclusteringbehavior,ahighintensityofsoundinthearenaisnotprob-lematicforthemovementofthes-bots.Onthecontrary,itseemstoserveasacommunicationmediumthatguidestheclustering.

Thereadermighthavenotedthat,althoughs-botshavecontrolovertheirgrippers,thesearenotused.Asmentionedbefore,inthepresentedworkweweremainlyinterestedinthestudyofself-organizedaggregation,andnotinself-assembling.Nevertheless,connectionscouldhavebeenestablishedbecausetheyminimizetherelativedistancebetweentwos-botsthusobtaininghighfitnessvalues.Whatwasobserved,however,isthatconnecteds-botswere,inmostcases,unabletomoveinacoordinatedway,makingtheformationofclustersdifficultifpossibleatall.Toeffectivelyaggregateandself-assemble,assembleds-botsshouldbeabletodisplaycoordinatedmovements,whichisthesubjectofthefollowingsection.

4EvolvingCoordinatedMovement

Inthissection,weconsiderancoordinationproblem,inwhichaswarm-botmadeofacollectionofassembleds-botshastodisplaycoordinatedmovements.Here,s-botsstartassembledinaswarm-bot,andtheyhavetosolvetheproblemthattheirwheelsmighthavedifferentinitialdirectionsormightmismatchwhilemoving.Inordertocoordinate,s-botsshouldbeabletocollectivelychooseacommondirectionofmovement,havingaccessonlytolocalinformation.

Evolvingneuralcontrollers,wewereabletofindsimpleandeffectivesolu-tionsthatallows-botstodisplaycoordinatedmovementsindependentlyfromthetopologyoftheswarm-botandofthetypeoflinkwithwhichs-botsareconnected.Moreover,wewillseethatevolveds-botsalsoexhibitobstacleavoidancebehaviors(whenplacedinanenvironmentwithobstacles)andobjectpulling/pushing(whenassembledtooraroundanobject.)

13

4.1ExperimentalSetup

Theswarm-botconsistsoffours-botsassembledinalinearstructure,asshowninFigure13.Differentlyfromthepreviousexperiments,s-botshavethepossibilitytorotatetheirbodywithrespecttotheirwheels5.Eachs-botismodeledbyarectangularchassisprovidedwithtwomotorizedandtwopassivewheelsandacylindricalturretthatisconnectedtothechassisthroughamotorized“hingejoint”thatcanrotatearoundtheverticalaxis.Eachs-bothasaphysicallinkthroughwhichitisattachedtoanothers-botalongtheperimeterofitsturret.Thelinkconsistsofanother“hingejoint”thathasarotationaxisparalleltothehorizontalplaneandisperpendiculartothelineformedbythefours-bots.

Figure13:Fourphysicallylinkeds-botsformingalinearstructure.Foreachs-bot,thecylinderandtheparallelepipedrespectivelyrepresenttheturretandthechassis.Thelargecirclesandsmallspheresrespectivelyrepresentthemotorizedandpassivewheels.Thelinebetweentwos-botsrepresentthelinkbetweenthem.Thewhitelineaboveeachs-botindicatesthedirectionandintensityofthetraction.

Eachs-botisprovidedwithatractionsensor,placedattheturret-chassisjunction,thatreturnsthedirection(i.e.theanglewithrespecttothechassis’orientation)andtheintensityoftheforceoftraction(henceforthcalled“trac-tion”)thattheturretexertsonthechassis(Figure14).Tractioniscausedbythemovementsofboththeconnecteds-botsandthes-bot’schassis.Noticethattheturretofeachs-botphysicallyintegratestheforcesthatareappliedtothes-botbytheothers-bots.Asaconsequence,thetractionsensorprovidesthes-botwithanindicationoftheaveragedirectiontowardwhichtheteamistryingtomoveasawhole.Moreprecisely,itmeasuresthemismatchbetweenthedirectionstowardwhichtheentireteamandthes-bot’schassisaretryingtomove.Theintensityofthetractionmeasuresthesizeofthismismatch.

Eachs-bot’scontrollerisaneuralnetworkwith4sensoryneuronsthatencodethetractionplusonebiasneuron.Thesearedirectlyconnectedwith2motorneuronsthatcontrolthetwomotorizedwheelsandtheturret-chassismotorizedjoint.Thefoursensoryneuronsencodetheintensityofthetractionfromfourdifferentpreferentialorientationswithrespecttothechassis(front,right,backandleft).Foreachsensor,thisintensitydecreaseslinearlywithrespecttotheabsolutedifferencebetweenthesensor’spreferentialorientationandthetraction’sdirection,andis0whenthisdifferenceisbiggerthan90degrees.Theactivationstateofthemotorunitsisnormalizedbetween[-10,+10]andisusedtosetthedesiredspeedofthetwocorrespondingwheelsandtheturret-chassismotor.

Figure14:Tractionforcedetectedbythes-bots’tractionsensor.Thelargeandsmallcirclesrespectivelyrepresenttherightactivewheelandfrontpassivewheel.Thedashedlineandthefullarrowrespectivelyindicatethes-bot’sorientationandthedirectionandintensityofthetraction.Thedashedarrowindicatestheanglebetweenthechassis’orientationandthetraction.

Theconnectionweightsoftheneuralcontrollerofthes-botshavebeenevolved.Theinitialpopulationconsistsof100randomlygeneratedgenotypesthatencodetheconnectionweightsof100correspondingneuralcontrollers.Eachconnectionweightisrepresentedinthegenotypeby8bitsthataretrans-formedinanumberintheinterval[-10,+10].Therefore,thetotallengthofthegenotypeis10×8=80bits.Eachgenotypesencodestheconnectionweightsofateamofidenticalneuralcontrollers.Theteamisallowedto“live”for5epochs,eachlastingT=150cycles.Atthebeginningofeachepochthechassisofthe4s-botsareassignedrandomorientations.The20bestgenotypesofeach

areallowedtoreproducebygenerating5copiesoftheirgenotypegeneration

with3%oftheirbitsreplacedwithanewrandomlyselectedvalue.Theevo-lutionaryprocesslasts100generations.Theexperimentisreplicated10timesbystartingwithdifferentrandomlygeneratedinitialpopulations.Toallowtheswarm-bottomoveasfastandasstraightaspossible,weuseafitnessfunctionFbasedontheeuclideandistancebetweenthecenterofmassoftheteamat

10,75360315Chassis' direction27022518013590450

Fitness0,50,2500255075100Generations050 cycles100150(a)(b)

Figure15:(a)Performanceacross100generations.Thethicklineandthinlinerespectivelyplottheperformanceofthebestteamofeachgenerationandtheaverageperformanceofthepopulation,averagedoverthe10replications.(b)Thegraphshowsthedirection(angle)ofthechassisofthefours-botsin150cycles,startingwithtwodifferentinitialrandomorientations(thickandthinlines,respectively).

15

thebeginningandattheendofeachepoch:

F

=

󰀃X(0)−X(T)󰀃

n󰀂j=1

n

Xj(t),

wherenisthenumberofs-botsinvolvedintheexperiment,Xj(t)aretheco-ordinatesofthejths-botatcyclet,X(t)aretheresultingcoordinatesofthe

centerofmassofthegroup,andDisthemaximumdistancethatasingles-botcancoverinTcyclesbymovingstraightatmaximumspeed(see[3]formoredetails).

4.2ObtainedResults

Figure15ashowshowthefitnessofthepopulation,averagedoverthe10repli-cations,changesacross100generations.Attheendoftheevolution,thebestteamofeachreplicationwastestedfor100epochs,andthecorrespondingaver-ageperformanceisreportedinTable1.Itcanbenoticedthatmostreplicationoftheexperimentsucceededinfindingaverygoodsolution6.

Table1:Averageperformanceofthebestindividualofeachreplication

Replication

0.9470.9430.9310.9230.8390.9340.7650.8600.9460.945

Directobservationofthebehaviorshowsthats-botsstarttopullindifferentdirections,orienttheirchassisinthedirectionwherethemajorityoftheothers-botsarepulling,movestraightalongthisdirectionthatemergesfromthisnegotiation,andcompensatesuccessivemismatchesinorientationthatarisewhilemoving.AsshowninFigure15b,thedirectionthatemergesfromthenegotiationbetweens-botschangesineverytrial.

Theanalysisofhowevolvedindividualsreacttodifferentdirectionandin-tensityofthetractionindicatesthattheydevelopedasimplestrategythatcanbedescribedinthefollowingway:(i)Whenthechassisofthes-botsareorientedtowardthesamedirection,theintensityofthetractionisnullandthes-botsmovestraightwithmaximumspeed.(ii)Whentheintensityofthetractionis

low,thechassisofthes-botsareorientedtowardsimilarbutnon-identicaldirec-tions.Inthiscase,s-botstendtoturntowardtheaveragedirectioninwhichthewholegroupismoving,i.e.,theytendtoturnleftwhenthetractioncomesfromtheleftsideandrightwhenthetractioncomesfromtherightside.(iii)Whentheintensityofthetractionishighandcomesfromthereardirection,thechas-sisofthes-botsareorientedinratherdifferentdirections.Forinstance,threes-botsmightbeorientedtowardNorthandones-botmightbeorientedtowardSouth.Inthiscasethes-botstendtochangetheirdirection.Thes-botsthathavethehighermismatchwithrespecttotherestofthegroupfeelastrongertractionthanothers,andthisassuresthatauniquedirectionfinallyemergesforthewholeteam.Inparticular,intheexamplejustdescribed,thes-botfacingSouthwillchangeitsdirectionmorequicklythantheotherthrees-botsfacingNorth.Notethatinthiscasealls-botswouldfeelatractionfromtherear.Theonlydifferencebetweenthes-botsisthattheindividualorientedtowardsouthfeelsatractionintensitystrongerthantheotherindividuals.Asidefromthisschematicdescription,notethatthenon-linearitiesinhows-botsreacttotractioncomingfromdifferentanglesandofdifferentintensitiesseemtoplayanimportantfunctionalrolethatwearestilltryingtounderstand.

4.3GeneralizationProperties

Asweclaimedabove,evolvedcontrolsystemsdisplayanabilitytoproducecoordinatedmovementsindependentlyfromthenumberofs-bots,thetopologywithwhichtheyareconnected,andthetypeoflinks.Forinstance,bytestingateamof8s-botsconnectedsotoformthestarformationshowninFigure16a,weobservedthattheydisplayanabilitytonegotiateanuniquedirectionandtomovetowardsuchemergentdirectionalsointhiscase(seeFigure16b).

S-botsalsodisplayanabilitytoproducecoordinatedmovementswhenas-sembledbymeansofflexibleinsteadofrigidlinks.Flexiblelinksconsistsoftwosegmentsconnectedbyahingejointthatallowtheconnecteds-botstorotateonthegroundplanealongthemiddlepointofthelink.Bytestingeights-botscon-

nectedbyflexiblelinkssotocreateasnakeformation,weobservedthats-botsabletonegotiateanuniquedirectionandproducecoordinatedmovementalongsuchdirectionalsointhiscase.Atthebeginningofeachtrial,theformationdeformsasaconsequenceofthedifferentorientationofthechassisofthes-bots

36031527022518013590450050 cycles100150(a)

Chassis' direction(b)

Figure16:(a)Eights-botsconnectedbyrigidlinksintoastarformation.(b)Theorientationangleofthechassisofthe8s-botsofastarformation(thickline)andsnakeformation(thinline)in150cycles.

17

butaftersometimeitsettlestoastableconfigurationandacommondirectionalsointhiscase.Giventhatinflexibleassembledstructuresthemotoractionperformedbys-botsmightaffecttheshapeoftheswarm-botratherthanthetractionperceivedbythes-bots,theseresultsseemtoindicatethattheevolvedstrategyisextremelyrobustandallowss-botstocoordinateevenwhentractionsensorsprovideincompleteinformationaboutthemovementsoftheteam.

Furthermore,byplacings-botsinanenvironmentwithobstacles,weob-servedthattheydisplayindividualandcollectiveobstacleavoidancebehaviors.Infact,whenans-botshitsanobstacle,theturretexertsatractiononthechas-sisintheoppositedirectionoftheobstacle.Followingthebump,then,asingles-botturnsandavoidsremainingblockedbytheobstacle.Whenassembled,thetractionresultingfromthebumpistransmittedtotheothers-botsthroughthephysicallinks,lettingthewholegroupreorganizeandchangedirection,thusavoidingtheobstacle.Alsointhiscase,s-botsareabletocollectivelyavoidob-staclesindependentlyofthenumberofassembleds-botsthewayinwhichtheyareconnected,andthetypeoflinks.Figure17showsthebehaviorofasnakeformationconnectedwithflexiblelinksinanarenasurroundedbywallsandincludingfourcylindricalobstacles.Asshowninthefigure,theswarm-botdis-playsanabilitytocoordinateandtocollectivelyavoidwalls.Giventhats-botsareconnectedthroughflexiblelinks,theswarm-bottendstochangeitsshapeduringcoordinationphasesandduringcollisionwithobstacles.However,giventhats-botsalsotendtomaintaintheirdirectionofmovement,theswarm-botdisplaysalsoanabilitytogothroughnarrowpassages,eventuallydeformingitsshapeaccordingtotheconfigurationoftheobstacles.Thiscollectiveobstacleavoidancebehaviorisalsoveryrobust.Infact,manyoftheevolvedbehaviorstestedinasnakeformationnevergotstuckduringlongobservationperiods.Thiscanbeexplainedbyconsideringthatswarm-botsassembledthroughflexi-blelinksaredynamicalsystemsthatkeepchangingshapeuntiltheydisentanglesfromtheobstacles.Bymoving,s-botsalsochangetheirrelativepositionswithrespecttoothers-botssothatthewholeswarm-botalwaysgeneratesnewcon-figurationsandhasanextremelyreachdynamic.

Finally,weobservedthats-botsconnected toanobject,orconnectedso

(a)(b)

Figure17:Eights-botsassembledintoasnake formationdisplayingcollective

obstacleavoidance.(a)Thelightparallelepipeds andthelargecylindersrep- resentwallsandobstacles,respectively.(b)Thesmallgraycirclesrepresent

theinitialpositionandshapeoftheswarm-bots.Thesquareandthelargefull

circlesrepresentthewallsandtheobstacles.Thelinesshowthetrajectoryof

thes-botsduring600cycles.

18

toformaclosedstructurearoundanobject,tendtopull/pushtheobjectinacoordinatedfashion.Figure18ashowsanexampleofeights-botsassembledtoacylindricalobjectthroughrigidlinks.Iftheweightoftheobjectisbelowagiventhreshold,s-botsdisplayanabilitytocoordinateandtodragtheobjecttowardthedirectionthatemergesfromthenegotiationbetweenthem(Figure18b).Thisbehaviorcanbeexplainedbyconsideringthatevolveds-botstendtofollowtheaveragedirectionoftheteambutalsohaveatendencytomaintaintheirdirectionofmovementiftheintensityoftheperceivedtractionisnottoohighandtheangleofthetractiondiffersofabout180degreesfromthedirectionofmovement.Incidentally,thissuggeststhatthistendencytopersevereinmovingtowardthecurrentdirection(whenthetractioncomesfromtheopposite

direction)alsoplaysaroleintheabilitytoproducecoordinatedmovement.

(a)(b)

throughrigidlinks.(b)TracesFigure18:(a)8s-botsconnectedtoanobject

leftbythes-bots(thinlines)andtheobject (boldline)in150cycles.Largeandsmalldottedcirclesrepresenttheinitial(bottom)andfinal(top)positions

ofthes-botsandoftheobject.

5Conclusions

Thispaperintroducedanewroboticconcept,calledaswarm-bot,definedasanartifactcomposedofsimplerautonomousrobots,calleds-bots.Ans-bothaslimitedacting,sensingandcomputationalcapabilities,butcancreatephysicalconnectionswithothers-bots,thusformingaswarm-botthatisabletosolveproblemsthesingleindividualcannotcopewith.Wepresentedinthispapersomeoftheresultsobtainedintheattempttocontrolaswarm-bot.Inparticular,wechosetoexploitArtificialEvolutionforsynthesizingthecontrollersforthes-bots,andforobtainingself-organizationintheroboticsystem.Thesolutionsfoundbyevolutionaresimple,generalandinmanycasetheygeneralizetodifferentenvironmentalsituation.Thisdemonstratesthatevolutionisabletoproduceaself-organizedsystemthatreliesonsimpleandgeneralrules,asystemthatisconsequentlyrobusttoenvironmentalchangesandtothenumberofs-botsinvolvedintheexperiment.

Concerningtheaggregationtask,theobtainedresultsshowedthatevolutionwasabletosynthesizesimplebuteffectivebehaviors.Thiswasdonemainlyexploitingsomeinvariantspresentintheenvironmentandthecomplexinter-actionsamongs-botsandbetweens-botsandtheenvironment.Theevolvedaggregationbehaviorscanbeconsideredself-organized.Basically,theattrac-19

tiontosoundsourcesservesasapositivefeedbackmechanism:thehighertheintensityofsoundperceived,thehighertheattractiontowardthesource,whichisconsequentlyamplified.Ontheotherhand,therepulsionbetweens-botscon-stitutesthenegativefeedbackmechanism:itmakesclustersof2s-botsunstableinthestaticclusteringbehavior,andresultsinthemovementoftheclustersinthedynamicclusteringbehavior.Thedynamicstrategyscaleswiththenumberofs-botsbecauseitdoesnotstronglyrelyonenvironmentalinvariants,butismerelyaresultofadynamicinteractionbetweenthes-bots,whichmakesitmorerobusttoenvironmentalchanges.

Inthesecondsetofexperiments,wedescribedhowcoordinatedmovementscanbeperformedbyagroupofsimulateds-botsthatarephysicallyconnectedtoformaswarm-bot.Weshowedthattheproblemcanbesolvedinarathersimpleandeffectiveway,byprovidingthes-botswithatractionsensorandbyevolvingtheneuralcontrollers.Theevolvedstrategyexploitsthefactthatthebodyofaswarm-botphysicallyintegratestheeffectsofthemovementsofthesingles-bots.Thetractionsensorallows-botstodetecttheresultofthisintegration.Inthisway,theproblemofproducingcoordinatedmovementscanbeeasilysolved.Infact,thesesensorsallows-botstohavedirectaccesstoglobalinformationaboutwhattheentiregroupisdoing.

Wealsoshowedhowneuralcontrollersareabletogeneralizeinratherdif-ferentcircumstances,eveniftheywereevolvedforaparticularcase,thatis,fortheabilitytoproducecoordinatedmovementinaswarm-botoffours-botsformingalinearstructure.Wehaveobservedthat(i)evolvedcontrollerspro-ducecoordinatedmovementsinswarm-botswithvaryingsize,topology,andtypeoflinks;(ii)theydisplayindividualandcollectiveobstacleavoidancewhenplacedinanenvironmentwithobstacles;(iii)theyspontaneouslyproduceob-jectpushing/pullingbehaviorwhens-botsareassembledtooraroundagivenobject.Theseresultssuggestthatthisstrategymightconstituteabasicfunc-tionalitythat,complementedwithappropriateadditionalfunctions,mightallowswarm-botstodisplayalargenumberofinterestingbehaviors.

Thecostoftheevolutionaryapproachistwofold:ononehand,itisnec-essarytoidentifyinitialconditionsthatassureevolvability,i.e.,thepossibilitytoprogressivelysynthesizebettersolutionsstartingfromscratch.Ontheotherhand,artificialevolutionmayrequirelongcomputationtimeanditisoftenun-feasibleonrealrobots.Forthisreason,softwaresimulationsareoftenused.Thesimulationsmustsaveasmuchaspossibletheinterestingfeaturesoftherobot-environmentinteraction.Thus,wechoosetodevelopoursimulationsusingarigidbodydynamicssimulator.Weplaninthefuturetostudytheproblemoftransferringthecontrollersevolvedinsimulationstotherealswarm-bots.

Infuturework,wewouldliketoinvestigatetheemergenceoffunctionalaggregation,forexample,inpreyretrievalorinnavigationonroughterrain.Furthermore,wewouldliketoevolveswarm-botsabletomovetowardagiventargetandtoassembleanddisassembleonthebasisoftheircurrentgoalandoftheenvironmentalconditions.Fromthispointofviewtheresultsreportedinthispaperonindividualandcollectiveobstacleavoidancebehaviorsuggestthattheproblemofcontrollingsingles-botsandteamsofassembleds-botsmightbesolvedwithuniformandsimplecontrolsolutions.Moreover,theresultsreportedinthepaperontheabilitytogeneralizetoratherdifferentsituationssuggestthatcontrolsolutionsmightscaleuptosignificantlycomplexconditions.

20

Acknowledgments

MarcoDorigoacknowledgessupportfromtheBelgianFNRS,ofwhichheisaSeniorResearchAssociate.

TheSWARM-BOTSprojectisfundedbytheFutureandEmergingTech-nologiesprogramme(IST-FET)oftheEuropeanCommunity,undergrantIST-2000-31010.TheinformationprovidedisthesoleresponsibilityoftheauthorsanddoesnotreflecttheCommunity’sopinion.TheCommunityisnotrespon-sibleforanyusethatmightbemadeofdataappearinginthispublication.

TheSwissparticipantstotheprojectaresupportedundergrant01.0012bytheSwissGovernment.

References

[1]C.Anderson,G.Theraulaz,andJ.-L.Deneubourg.Self-assemblagein

insectssocieties.InsectesSociaux,49:99–110,2002.[2]G.Baldassarre,S.Nolfi,andD.Parisi.EvolvingMobileRobotsAble

toDisplayCollectiveBehaviours.InHemelrijkC.K.andBonabeauE.,editors,ProceedingsoftheInternationalWorkshoponSelf-OrganisationandEvolutionofSocialBehaviour,pages11–22,MonteVerit`a,Ascona,Switzerland,September8-13,2002.UniversityofZurich.[3]G.Baldassarre,S.Nolfi,andD.Parisi.Evolutionofcollectivebehaviorin

ateamofphysicallylinkedrobots.InProceedingsofEvoROB2003,Essex,UK,April2003.Toappear.[4]E.Bonabeau,M.Dorigo,andG.Theraulaz.SwarmIntelligence:From

NaturaltoArtificialSystems.OxfordUniversityPress,NewYork,NY,1999.[5]S.Camazine,J.-L.Deneubourg,N.Franks,J.Sneyd,G.Theraulaz,and

E.Bonabeau.Self-OrganizationinBiologicalSystems.PrincetonUniversityPress,Princeton,2001.[6]S.CamazineandJ.Sneyd.Amodelofcollectivenectarsourceselection

byhoneybees:self-organizationthroughsimpleindividualrules.JournalofTheoreticalBiology,149:547–571,1991.[7]S.Camazine,J.Sneyd,M.J.Jenkins,andJ.D.Murray.Amathematical

modelofself-organizedpatternformationthecombsofhoneybeescolonies.JournalofTheoreticalBiology,1:295–311,1990.[8]J.-L.DeneubourgandS.Goss.Collectivepatternsanddecisionmaking.

EthologyEcologyEvolution,pages295–311,1989.[9]C.Detrain.Fieldstudyonforagingbythepolymorphicantspeciespheidole

pallidula.InsectesSociaux,37(4):315–332,1990.[10]T.D.Fitzgerald.Thetentcaterpillars.CornellUniversityPress,Ithaca,

NewYork,1995.

21

[11]F.Mondada,G.C.Pettinaro,I.Kwee,A.Guignard,L.Gambardella,

D.Floreano,S.Nolfi,J.-L.Deneubourg,andM.Dorigo.SWARM-BOT:Aswarmofautonomousmobilerobotswithself-assemblingcapabilities.InHemelrijkC.K.andBonabeauE.,editors,ProceedingsoftheInterna-tionalWorkshoponSelf-organisationandEvolutionofSocialBehaviour,pages307–312,MonteVerit`a,Ascona,Switzerland,September8-13,2002.UniversityofZurich.[12]F.Mondada,G.C.Pettinaro,A.Guignard,I.V.Kwee,D.Floreano,J.-L.

Deneubourg,S.Nolfi,L.M.Gambardella,andM.Dorigo.SWARM-BOT:anewdistributedroboticconcept.submittedtoAutonomousRobots,SpecialIssueonSwarmRobotics,2003.[13]S.NolfiandD.Floreano.EvolutionaryRobotics:TheBiology,Intelligence,

andTechnologyofSelf-OrganizingMachines.MITPress/BradfordBooks,Cambridge,MA,USA,2000.[14]G.C.Pettinaro,I.W.Kwee,L.M.Gambardella,F.Mondada,D.Floreano,

S.Nolfi,J.-L.Deneubourg,andM.Dorigo.Swarmrobotics:Adifferentapproachtoservicerobotics.InProceedingsofthe33rdInternationalSym-posiumonRobotics,Stockholm,Sweden,October7-112002.InternationalFederationofRobotics.[15]F.Saffre,R.Furey,BKraft,andJ.L.Deneubourg.Collectivedecision-makinginsocialspyders:Dragline-mediatedamplificationprocessactsasarecruitingmechanism.JournalofTheoreticalBiology,198:507–517,1999.[16]E.S¸ahin,T.H.Labella,V.Trianni,J.-L.Deneubourg,P.Rasse,D.Flore-ano,L.M.Gambardella,F.Mondada,S.Nolfi,andM.Dorigo.SWARM-BOTS:Patternformationinaswarmofself-assemblingmobilerobots.In

A.ElKamel,K.Mellouli,andP.Borne,editors,ProceedingsoftheIEEEInternationalConferenceonSystems,ManandCybernetics,Hammamet,Tunisia,October6-9,2002.Piscataway,NJ:IEEEPress.[17]T.D.Seeley.TheWisdomofHive,pages277–290.HarvardUniversity

Press,Cambridge,1995.[18]T.D.Seeley,S.Camazine,andJ.Sneyd.Collectivedecision-makingin

honeybees:howcolonieschooseamongnectarsource.BehavioralEcologyandSociobiology,28:277–290,1991.[19]V.Trianni,R.Gross,T.H.Labella,E.S¸ahin,P.Rasse,J.-L.Deneubourg,

andM.Dorigo.EvolvingAggregationBehaviorsinaSwarmofRobots.TechnicalReportTR/IRIDIA/2003-07,IRIDIA-Universit´eLibredeBrux-elles,Belgium,February2003.

22