GilbertPradel
LaboratoireSyst`emesComplexes,Universit´ed’EvryVald’Essonne
CNRSFRE2494
40,rueduPelvoux,CE1455Courcouronnes
91020Evrycedex.FRANCEEmail:gpradel@lsc.univ-evry.fr
Abstract—Thisworkaimsatmodelingasystemwhichallowsauserandmoreparticularyadisabledperson,togiveamissiontoateamofrobotsandtodeterminethewholeprocessleadingtoitsexecution.Thispaperproposesaparticipativemodeltosetupthissystem.Weseparatetheactor:activeelementsubjectedtothestimulus(theuseranditsrequest,forexample),theobjectiveform:objectdesignedinthemindoftheactor,theobject:elementsatisfyingandcorrespondingtothesatisfactionofthestimulus.Inagreementwiththismodel,thesystemisbasedonaseverallevelsdiagramforadesigndirectedtowardsamulti-agentssystem.Inthispaper,wemainlydescribethefourstagesofthemechanismwhichleadtothetrajectorydeterminationoftherobotsgroup.ThesestepsuseaVorono¨ı’sgeneralizedgraphandawavefrontalgorithm.Thecomputationoftheconfigurationspaceforarobotgroupandanadaptationofthegrouptrajectoryallowthegrouptobeformedandreachthefinalposition.
I.INTRODUCTION
Manyapplicationsuchasspaceandunderwaterexploration,operationsindangerousenvironment,servicerobotics,militaryapplications,etc.cancalluponmulti-robotsystems.Thesesystems,althoughfarfromachivement,cancarryoutdifficultoreventasksimpossibletoachievebyasinglerobot.Ateamofrobotsprovidesacertainredundancy,contributestotheachievementofataskinacollaborativewayandshouldbeabletogobeyondwhatcouldbedonebyasinglerobot.Wewilltrytodrawupageneralstateoftheworkintherestrictedfieldofmobileroboticsimplementingoneormorerobotsfortheassistancetodependentpeople.AccordingtoParker[Parker2000]andArai[Araietal.2002],workscanbeclassifiedinthreecategories:
Reconfigurablerobotssystemsalsocalled”CellularRobotsSystems”.Acellularrobotisanauto-organizedrobot-likesystemcomposedofalargenumberofunitscalledcells.Thisideaisinspiredbytheorganizationofalivingsystem.Variousfieldswerestudiedinthisdomain:swarm’sintelligence[BonabeauandTheraulaz2000],”cyclicswarms”[BeniandHackwood1992],CEBOTsystem[FukudaandNakagawa1987].
Trajectoryplanninginthemulti-robotsystemfield:controloftheairtraffic[PremvutiandYuta1989],movementofgroupsofrobotsinforma-tion[Araietal.1989][Wang1989].
FrancoisSaidi
LaboratoireSyst`emesComplexes,Universit´ed’EvryVald’Essonne
CNRSFRE2494
40,rueduPelvoux,CE1455Courcouronnes
91020Evrycedex.FRANCEEmail:saidi@lsc.univ-evry.fr
Architecturesformulti-robotco-operation:AC-TRESS[Asamaetal.1989][SellemandDalgalarrondo1999]resolvesconflictsbetweenrobotsandallocatestasksbycreatingstaffsofrobots.
[BalchandParker2002][SchultzandParker2002][Parkeretal.2002]define7directionsofstudyinmulti-robotsystems:
biologicallyinspiredsystems,
systemswhichstudythecommunications,
systemswhichareinterestedinarchitectures,tasksallo-cationandcontrol,
systemsdirectedtowardslocalization,mappingandex-ploration,
systemsforobjectstransportandhandling,systemsfordisplacementscoordination,
systemsdealingwiththedesignofreconfigurablerobots.SectionIImakesanonexaustivesynthesisofworksinthemulti-robotfield.SectionII-Fpresentsprojectsinconnectionwiththeassistanceforhandicappedordisabledpeople.
Inagreementwiththestudiesontheassistancedevicesforhandicappedpeople,theusermustbeabletotakepartinthecontrolofthesystem,itsmanagementandincertaincasestotakepartinitsdesign.Moreover,theuserwishestohavepermanentlyinformationontheevolutionofthetasksormissionsgiventothesystem.Thesecharacteristicsleadsustoconsiderthesystemdesignasaparticipativesystem.Theseparticipativeaspectswillinvolve:theHuman-Systeminterface(HSI),
therequestinputseenasasetofremoteservicescarriedouteitherinindividualorcollectivewaybytherobots,userinterventionintheconstructionoftherequestsolu-tion,
awaytoactdirectlyontherobotsoronthemissionsceneintheeventofmodification,breakdownorexecutionfailure,
analwaysavailableinformationonthesystemstate.Thesystemdesignwillcalluponseverallevelsofab-straction[Arkinetal.1999],levelsdiscussedinthefollowingsections.Wewillbesuccessivelyinterested:
bythegeneralmodelofdesigninthesectionIII-A,bytheinferenceengine(sectionIII-B)andwiththechoiceoftherobots,
bythedeterminationoftherobot’sgrouppath(sec-tionIII-D).
II.MOBILE
COLLECTIVEROBOTICS
A.Biologicallyinspiredsystems
Mostofmulti-robotsystemsofbiologicalinspirationfollowuponworks[Brooks1986].The”behaviour-based”paradigm(behavioralrobotics)thatheintroducedhasabiologicalsource.[DrogoulandFerber1993]wereinterestedinmodelinginsectsoranimalssocieties(ants,bees,birds,fish...)andreproducedsuccessfullytheirbehaviorsbyobservingsimplelocalrules.[GoldbergandMataric1999]showthepossibilityformulti-robotsystemstocarryoutthecollectivebehaviors.TheAnimatlabapproachconceivessimulatedorrealartificialsystemsnamed”animats”whosebehaviorsexhibitsomeani-malcharacteristics[Ani2002].
Thesestudiesgatheredinarathergeneralclasscalledsystemsusingaswarmtypeco-operationinoppositiontoanotherclassgatheringthesystemsinwhichcommunicationsareintentional,haveacommonpointwhichisnottobesubjectedtoseveretemporalconstraints.
ExperimentsusingthedogAibofromSonyontheloco-motionmechanismshowthatthewalkingcommandsystemobtainedwasmorepowerfulthantheoneprogrammedbytheengineers,andmadethedogwalkfaster.Otherexperimentsimplementingaco-evolutionbetweenspecieswerecarriedoutby[Floreanoetal.1998][Funesetal.1998].Limitsoftheapproachareunderlinedin[MeyerandGuillot2001]whoquotestheattempttoevolvingthenervoussystemofRobokoneko(anartificialcat).
B.Systemsdealingwiththecommunications
Communicationsbetweenthevariousentitiesofamulti-robotsystemareacrucialpoint.Explicitcommunicationisarelationaloperationbetweenanentityandoneormoreothers.Inimplicitcommunication(”throughtheworld”)anentitybroadcastsamessagewhichwillbereceivedbyallothersentities.
Theproblemsinvolvedintheuser-systemcommunicationpartaretackledin[JonesandRock2002]andappliedtotheuseofrobotsteaminthespaceconstructionindustry.Theuserdialogueswithacommunityofagentsthroughaseriesofimplicitandexplicitquestions.Theoperatorplaysasignificantroleinthestockmanagementandtheschedulingoftherobotstasks.Authorsunderlinethedifficultiesto:
establishthestructureandtherangeofthedialogue,createaninfrastructurewhichallowsforthesys-tem/robotstoconductadialoguewiththeuser,
determinethemethodswhichcantakeintoaccountthesubjacentsocialaspectinthiskindofdialogue,
developaninterfacewhichallowstheusertodialoguewiththesystem.
In[Fongetal.2001],authorsrecommendtoadapttheau-tonomyandthehuman-systeminteractiontothesituationand
totheuser.Accordingtotheseauthors,partofthedecision-makingprocess,whichismostofthetimenotstructured,mustremaininthehuman’sdomain,inparticularbecausetherobotsremainverylimitedforthehighlevelperceptivefunctions.Theirapproachtendstotreattherobotnotlikeatoolbutlikeapartner.
C.Systemsdirectedtowardsarchitecturesdesign,tasksallo-cationandcontrol
Problemstackledinthesesystemsare:tasksallocation,tasksplanning,communicationsystemdesign,homogeneityorheterogeneityoftherobots,delegationofauthority,globalcoherenceandlocalactions...In[Iocchietal.2001],multi-robotsystemsareinitiallyshownlikeaparticularcaseofmulti-agentssystemswithspecificconstraintsduetotheimmersionoftheagentsinarealenvironment.
[Rybskietal.2002]presentsasoftwarearchitecturein-tendedforthecontrolofateamofminiaturerobots.Theusedalgorithmtriestodynamicallyallocatetheresourcestotherobotsaccordingtotheirneedsandtotheevolutionofthetaskstheyarecarryingout.Tasksallocationisalsodiscussedin[Mataricetal.2002][GerkeyandMataric2003]whopresentastrategyfortasksallocationbyusingaformofnegotiationtooptimizetheuseoftherobot’sresources.Themulti-robotarchitectureALLIANCE[Parker1998]takesintoaccountthefaultstoleranceaspectandthebreak-downsforthetasksallocation.Thissystemappliestheprob-lemsstudiedindistributedartificialintelligencetocollectivemobilerobotics:
theformulation,thedescription,thedecompositionandtheproblemsallocationamongagroupofintelligentagents,
thecommunicationandtheinteractionbetweentheseagents,
thecoherenceintheactionsoftheagents,
thedetectionandtheresolutionoftheconflicts.
D.Systemsdedicatedtolocalization,cartography,explo-ration,transportandhandlingofobjects
[Burgardetal.2000]considertheproblemofthecollabo-rativeexplorationofanunknownenvironmentbyateamofrobots.Themainchallengeistocoordinatetherobotsactionsinordernottoexploretheenvironmentwhilefollowingthesameway.TheLOSTsystem(LOcalisation-SpaceTrailsforrobotteams)[Vaughanetal.2002]usestrailsoflandmarkstonavigatebetweenvariouspointsofinterest,inthesamewaypheromonestrailsareusedbytheants.[Yamashitaetal.2003]proposeamethodformovementplanningofarobotsteamforthecollectivetransportofanobjectina3Denvironment.Thistaskraisesvariousproblemssuchasobstaclesavoidanceandthestabilityofthetransportedobject.E.Systemsfordisplacementscoordination
Inthefieldofdisplacementscoordinationofthevariousrobotsinsideaformation,themaindirectionsofstudyarethetrajectoriesplanning,thegenerationandthekeepingofthe
formationaswellasthetrafficcontrolsuchastheyaredefinedin[Yuetal.1995].ThesystemMAPS[TewsandWyeth2002]isinterestedinmulti-agentsplanningbygeneratinganabstractrepresentationoftherobotenvironmentseenfromeachrobotspointofviewandisusedforsoccerplayerrobots.
[Dasetal.2002]describeaframeworkfortheco-operativecontrolofarobotsgroup.Simplecontrollersandestimatorsareusedtobuildcomplexsystemsappliedtotheco-operativehandlingandobjecttransportationbyasemi-rigidformation.[TanandXi2004]presentsadistributedalgorithmfortheco-operationandtheredeploymentofanetworkofsensorsembarkedonmobilerobots.Thismodelallowsaformalanalysisoffaultstolerantspace-timefusionofinformationfromthesensors,allowingthedeploymentoftherobotsintheenvironment.Thesystemreconfiguresitselftocoverthemostpossiblespace.
[Spearsetal.2004]introducesaninterestingconceptenti-tled”physicomimetics”whichproposesadecentralizedcontrolmethodforseveralmobilephysicalagents.Theagentsaresubjectedtovirtualforcesandreacttothem.Therobotsareseenasparticlessubjectedtogravitationalandrepulsiveattractions.Thisarticleshowshowonecanorganizetherobotsonalatticewithoutexpensivecalculations.Italsoshowshowthistechniquecanbeusedfortheobstaclesavoidancebymodificationoftheformation.
F.Fieldofassistancesupplyfordependentpeople
Ifthefieldofassistancesupplytodependentpeopleusingmobilerobotics,onerealizesthatinmanyapplications,thishelpisconsideredbyabetterergonomicsoftherobotandathoroughinstrumentationoftherobot(therobotcanbe,forexample,thearmchairofthehandicapped).Withoutbeingexhaustive,onecanmentiontheworksoftheFrenchmulti-disciplinarynationalgroupfortheassistancetohandicappedpeople(IFRATH)inwhichvariousproblemsontheman-machineco-operationandtheco-operationbetweenrobotswerestudied.
InARPHproject[Colleetal.2002]fromtheLSC(ComplexSystemLaboratoryinEvryFrance),themobilerobotequippedwithanarmmanipulatorisintendedtobringanassistancetothehandicappedperson.Thissystemmusthelpthehandi-cappedpersontocarryoutbyhisownsomefunctionsoftheeverydaylife:toseize,collect,carryandmove.Toachieveatask,thepersoncooperateswiththeassistancesystem,eachonebringingherowncompetencesandcapacities.Thiscollaborationhasasmainbenefitthelimitationofthesystemcomplexityandthereforeitscost.Thesystemdoesnotmake”insteadof”butimpliesthepersonatvariousdegreeintherealizationoftherequiredservice.
OtherprojectsarecarriedoutinthisdirectionaswellinFranceasinEurope.ThelaboratoryofAutomaticsandtheAutomatedSystems(LASC)inNancyFrancedevelopsaprototypeofarmchaircalledVAHMmainlyintendedtohelpofthehandicappedpeopleforwhomitisdifficult,orevenimpos-sibletocontrolaconventionalarmchair[Bourhisetal.2001].
Onaconventionalelectricarmchairwereaddedthenecessarysensorsforthenavigationandtheobstaclesavoidanceprocess.Projectsproposingtheimplementationofateamofrobotsforpeople’sassistancearetoourknowledgeveryfew.
Theinterestofthisapproachstaysinitsmulti-domainaspect.Amongthem,onewillpointout:
theinteractionbetweentheuserandthesystem,thestudyofthegroupscreation,
theuseofautomationsuchasitcanbemadebyahuman.
Otherworks,withouthavingforgoaltheassistanceofhandicappedpeople,areinterestedintheaspectsboundto:
thewayinwhichausercandoarequesttothesystem,adevelopmentenvironmentoflow-levelbehaviorsinamulti-robotsystem,
asystemassigningtasksamongasetofautonomousrobots,
theinteractionbetweenauserandamulti-robotsystem.
[Arkinetal.1999]areinterestedinamilitaryorientedap-plicationinwhichtheuser,inthatcasethesoldier,specifiesamissioninahigh-levellanguage.Thismissionisthencompiledthroughseriesoflanguagestooutputaprogramexecutablebyaparticularrobot.
TheRAVE[Dixonetal.1999]projectisinterestedinarealandvirtualenvironmentforanautonomousmulti-robotsystem.Thisenvironmentsimplifiesthedevelopmentofthelow-levelcollectivebehaviors.ROBODIS[SurmannandTheissinger1999]providesanexampleofdecentralizedsystemusinginternetnetworktoconnectvarioussoftwareandhardwareelements.
TheMokSAFsystem[Payneetal.2000]proposesamulti-agentsarchitecturewhichintroducesthreecategoriesofagents.The”providers”agentshaveacertainknow-howandcompe-tences.The”servicerequesters”agentshaveasetofprefer-encesonthedemandsthattheycanaddresstothe”providers”agents.Thelatter”passanannouncement”toproposetheirservices.
Weproposeinthefollowingsectionadesignframeworkforamulti-robotpathplanner.III.PARTICIPATIVE
MULTI-ROBOTSASSISTANCESYSTEM
Themainobjectiveofthisworkistomodelasystemallowingauserandmoreparticularyadisabledperson,togiveamissiontoateamofrobotsandtodeterminethewholeprocessleadingtoitsexecution.
ThemodelingtakesintoaccountthevariouslevelspresentedinthesectionIII-A.Thiswork,inordertoberealizable,hassomelimitsandconstraints:
Experimentstakeplaceonagroupof5compact,lowcost,heterogenousrobotsembarkingonlytheminimumprocessingpowerandafixedpartmanagingtheheavycomputationandtheinformationstorage.
Theenvironmentinwhichmoveandoperatethemobilerobotsisanindoorstructuredenvironment.Moreoverthesytemhasamodeloftheenvironment,i.e.amapofthe
placesincludingalltheobstaclesandobjectstherobotwillinteractwith.
Theuserispartofthesystem;hemay,tovariousdegree,interveneonit,acceptorrejectitsdecisions.Theuserhasathisdisposal:
theknowledgeoftheapartment,robotsandanexternalviewoftheirpossibilities,
anumberofdisplacementanddomesticmissons:–goto,gotowards,return,stop,take,put,–gather,
–bringcloser,moveaway,
–moveanobjectbypushingitorbypullingit,–moveanobjectbycollectingit.areportonthestateofthesystem.
A.Generalmodel
Theparticipativemodelofthissystemisgiveninfigure1.Weconsider,inthisdiagram:
theactor:activeelementsubmittedtothestimulus(theuserandhisrequest,forexample),
theobjectiveform:objectconceived(intheactor’smind,ifthisoneishuman,itcanbedescribedasaprogramiftheactorisacompiler),
theobject:finalstate,elementsatisfyingandcorrespond-ingtothestimulus(itcanbeaprocesswhoseexecutionwillcarryoutthestimulus).
Fig.1.Modelisationofthestep
Thedeductiontransitioniscalleduponaaprioriknowledgerepresentedasrules.Themanufacturingtransitiontransformstheobjectiveforminitsmaterialform:theobject.Thismodelcanbeusedatanylevelfromtherequestleveltotheexecutionlevel.
Thesystemdesigncallsuponseverallevelsofabstraction.Theservicerequiredbytheuserwillhavetobeanalyzedtodecidewhichresourcesarenecessaryandacompletescriptofthescenariomustbebuilt.Thenthescriptwillbesubmittedtotheuserandacceptedornot(inductiontransition:participativemodel).Theselevelsarefoundin[Arkinetal.1999].
Ourapproachispresentedonthefigure2.Thefirstobjectiveformrequiredistheexpressionoftherequest.Thelanguagewhichseemsboththesimplestandthemostconvivialtorepresenttheproposalforamissiontotheuserisaformclosetothenaturallanguage:”therobotRobot
Name”.Theobjectdeductedisthechoiceoftherobots
likelytoactontheconcernedobjectsandontheirrespective
missions.Amongtheconstraintstobetakenintoaccountarethecurrentsituation,theavailability,thetypeofrobots(e.g.arobotequippedwithanarmoracarrierrobot).
UserIndividualserviceland collectiveevmissionsrequestel evitapicitraPIndividualFormationand collectivePath
actions
Tasks allocationon thepath
Fig.2.Modelingoftheapproach
Thesecondlevelwillsetuptheroutesintheenvi-ronmentandwillinferfromthemtheformationsthattheteamofrobotswilladopt.Manufacturingassociatedtothislevelshoulddeterminethekeypoints(byusingforexamplegeneralizedVorono¨ıgraph).Thecollectivebehaviorsdefinedin[GoldbergandMataric1999]aredirectlyassociatedtothevariouspartsoftheroadtofollow.
Thissecondleveldealsalsowithtasksallocations.Theman-ufacturedobjectmustrepresentthecollectiveandindividualtaskswhichareassignedtotherobotsatthebeginningofthemission,withoutprejudgingifthisdistributionwillbeornotmodifiedduringtheexecution.Weimplementedthismodelinsimulationwithintheexistingmulti-robotsdemonstratorARMAGRAintheLSC.Wepresentinthefollowingsectionsthisimplementationinthecaseofthepathplanning.B.Theinferenceengine
Thefirstobjectiveformisobtainedbyusinganinfer-enceenginewithasetofrules.Ourworkisbasedon[Fongetal.2001][AbellaandGorin1999]fortheinputofthemissionbytheuserandthehuman-machineinteractionstudy.Therepresentationofknowledgetakesthedeclar-ativeshapeofJonesin[JonesandRock2002]andusesCLIPS[Aldridgeandal.2002]inferenceengine.
TheformulationoftherequestsinanimperativeformSubject-Verb-Complementwasimplementedforasetofsimplemissions.Theinputoftherequestsisdonebythemeanofagraphicalinterface(figure3)assuggestedin[JonesandRock2002].Themainelementsthattherulesmustcheckare:
theavailabilityoftherobots,
theproximityoftherobotstotheplacewheretheactionmusttakeplace,
thecompetencesoftherobots,inparticularintermofsensors/actuators,
thesemanticconsistency(e.g.onecannottransportcer-taintypeofobjects).
Theusercanbemoreorlesspreciseintheformulationofthemission,neverthelesssomeinformationaremandatory.
Fig.3.User’sinterface
TableIshowsthelinkbetweentheselectedactionandthetypeofargumentrequired:anymissingmandatoryargumentproducesanerror,whichleadstoamessagesignallingthemissingargumentandaskingtheusertobemoreprecise.SomeactionssuchasPUT(tableII)aremoreparticularandneedagroupofspecificrules:theusercanspecifyeithertherobotthattransportsorthecarriedobject.Anotherrulesetallowsthesystemtodeterminethenumberandthefeaturesoftherobotsfortheachievementofthetask.
Action
robots
Arguments
area
Gatherrobotsarea
robottransportableobject
Search
listarea
OptionnalArgument
case1
carriedobject
carriedobject
Fig.5.RealisticindoorFig.6.GeneralizedVorono¨ı’stypeenvironmentfortherobotGraphoftheenvironment
group’spathcomputation
ThegeneralizedVorono¨ıgraph(GVG)intheconfigurationsspace(figure6)istransformedintoanetwork,inwhichnodesrepresentsthejunctionpointsoftheGVG(figures7and8).Thisnetworkiscommontoalltherobotsandshowsallthepossibletrajectoriesforasinglerobotwithouttakingintoaccounttheformationwhichtherobotsgroupwillhavetotake.
Fig.7.TheGVGoverlayedFig.8.Thepathnetwork
onthewavefrontmap
ForeachrobotatrajectoryiscalculatedfromtherobotcurrentpositiontotheGVG.Apathonthenetworktoreachthetargetiscomputed.Thenavigationonthenetworkisdoneusingthewavefrontmapwhichtellswhatdirectiontherobotmusttaketoreachthetarget(figure8).Themergingofthevariousrobotsindividualpath,allowustofindthemeetingspointsaswellasthetrajectoriespartsalongwhosetherobotstravelingroup.Oneachsegmentdefinedpreviously,thesystemselectswhichformationtherobotsgroupwilladopt.Thischoiceisdoneaccordingtoseveralcriteria:
thenumberofrobotstheuser’schoice
thedecisionsystem’schoice
Thefollowingstageconsistsingeneratingthe3Dconfig-urationsspaceforagroupofrobotinformationforeachsegmentofthetrajectoryobtainedpreviously(robotforma-tionshassomeaxesofsymmetrywhichreducestheproblemcomplexity).
Fig.9.
Theconfigurationsspaceforagroupofrobotsinformation
Eachtrajectorysegmentisthendifferenciatedinordertocalculatethespeedvectordirectionatanypointofthepath.Thisoperationaddsathirdco-ordinatetoeachtrajectorypointandallowstopositionthatpathintheconfigurationspaceoftheassociatedformation.Howevereachtrajectorysegmentisonlyvalidforasinglerobotandprobablyincludessomeclasheswithobstacleswhenusedforarobotsgroup.Eachtrajectorysegmentmustbeadjustedtoallowagroupnavigation:
step1:checkingtheconnexityofthetwoendsofthetrajectorysegment,
step2:tuningthetrajectoryinordertoavoidobstacles.Awavefrontalgorithmcheckstheexistenceofapathbetweenthetwoendsofthetrajectory.Thewavefrontalgorithmwasmodifiedinordernottoincrementthedistanceduringthediffusionalongthedimension(dimensionstandfortherotationoftheformation)
Whentheconnexityofthetwoendsisestablishedintheconfigurationsspaceoftheformation(thisonlymeansthataclearpathbetweenthetwoendofthetrajectoryexists),itisstillnecessarytochecktheabsenceofcollisionsbetweenthetrajectorycurveandtheC-obstacles(C-osbstacles:con-figurationsinwhichtheformationcollidesanobstacle).Foreachcollisionzone,thetrajectoryislocallytunedinordertostatisfytotheconstraints.Tuningconsistsinadeformationoftheoriginaltrajectorybyselectingaclearpathbetweenthepointpreceedingtheclashwiththeobstacleandthepointfollowingthatsameclash.Thismethodensurestheleastdeformationbetweentheoriginaltrajectoryandthenewone.ThisdeformationaccordingtothethreedimensionsoftheC-spacecorrespondstotranslationsandrotationsoftheformationintheeuclideanspace.Attheendofthesestagesweobtainasuccessionofsegmentsofindividualandcollectivetrajectories(figure10).
Howeverseveralpointsremainstobestudied:thecreationoftheinitialformation,
themergingbetweenarobotandanalreadyexistingformation,
theoptimizationofthepossiblegatheringzone.If,forexample,twoassemblagepointscorrespondingtotworobotsareveryclose,itismoreadvantageoustomergethemandtocreatedirectlythefinalformationratherthantocreateaninitialformationbeforeincorporating
anewrobot,leadingtoanexpensivemodificationoftheformationofthegroup.
Fig.10.Finalresultshowingtheindividualandcollectivetrajectoriesandthegatheringpoints
IV.CONCLUSION
ANDPROSPECTS
Inthiswork,wepresentaframeworkforamulti-robotspathplannerforgroupnavigation.Thisframeworkallowsapersonandmoreparticularyadisabledpersontogiveamissiontoarobotgroup,andtodeterminethewholeprocessleadingtoitsexecution.
Accordingtosomehypothesesamongwhich:
theindoorstructuredenvironmentisknows,thesmallnumberofrobots,
thecostwhichinfluencesthesystem’sarchitecture,theusermayinterferewiththesystemdecision’s,
Theusercanrequestsomedisplacementmissionsthesys-temisabletoaccomplish.Wemainlyinsistonthesystem’sparticipativeaspectinordertobeacceptedbytheuserinspiteofhislimitations,thisparticipativeaspectimplies:
ahuman-systeminterfacetakingcareofthecommunica-tioninafriendly,clickanddrag,iconbased,high-levellanguage,
theexpressionoftherequestisproposedasasetofremoteservicescarriedoutbyareducednumberofrobots,
thepossibilityofinterveningintheconstructionofthesolutiontotherequest,
awaytoactdirectlyontherobotsandonthemissionsceneintheeventofmodification,breakdownorexecu-tionfailure,
aninformationonthesystemstateisalwaysavailable.
Thesystemmodelingisbasedonaseverallevelsdiagramforadesigndirectedtowardsamulti-agentssystem.Inthispaper,wemainlydescribethemechanismwhichleadstothetrajectorydeterminationoftherobotsgroup.Thisdetermina-tionisdoneinfourstages:
computationofthegeneralizedVorono¨ıgraphintheconfigurationsspaceofasinglerobot,
selectiononthisgraphofthepathforeachrobot,
determinationofregroupingpoints,choiceandvalidationoftheformation,
deformationoftheformation’strajectoryinordertoavoidtheobstacles.
Attheendofthisprocess,thetrajectoryispresentedtotheuser.Ifthelatterisvalidated,itwillthenbecarriedout.Thefollowingstageofourworkistheexecutionofthistrajectorybytherealrobots[PradelandComfaits2002].Inparallel,thetasksallocationconcerningtheactionsthattherobotsmustcarryoutattheendoftheirdisplacementmustbedonebasedontheworkdescribedinthesectionII-C.
REFERENCES
[Ani2002]:2002,FromAnimalstoAnimats7,ProceedingsoftheSeventhInternationalConferenceonSimulationofAdpativeBehavior.B.HallamandD.FloreanoandJ.HallamandG.Hayes,J.A.Meyer,eds.
[AbellaandGorin1999]Abella,A.andA.Gorin:1999,‘ConstructAlgebra:AnalyticalDialogManagement’.In:Proceedingsofthe37thAnnualMeetingoftheAssociationforComputationalLinguistics.
[Aldridgeandal.2002]Aldridge,J.andal.:2002,‘CLIPSVersion6.2CLanguageIntegratedProductionSystems’.
[Araietal.1989]Arai,T.,H.Ogata,andT.Susuki:1989,‘Collisionavoid-anceamongmultiplerobotsusingvirtualinpedance’.In:ProceedingsoftheIEEE/RSJInt.Conf.onIntelligentRobotsandSystems.pp.479–485.[Araietal.2002]Arai,T.,E.Pagello,andL.Parker:2002,‘Editorial:Ad-vancesinmulti-robotsystems’.IEEETransactionsonRoboticsandAutomation18(5),655–6617.
[Arkinetal.1999]Arkin,R.,T.Collins,andY.Endo:1999,‘TacticalMobileRobotMissionSpecificationandExecution’.In:ProceedingsoftheMobileRobotsXIVInternationalConference,Boston,USA.
[Asamaetal.1989]Asama,H.,A.Matsumoto,andY.Ishida:1989,‘Designofanautonomousanddistributedrobotsystem’.In:ProceedingsoftheIEEE/RSJInt.Conf.onIntelligentRobotsandSystems.pp.283–290.
[BalchandParker2002]Balch,T.andL.Parker:2002,Robotteams:Frompolymorphismtodiversity.T.BalchandL.Parker,eds.
[BeniandHackwood1992]Beni,G.andS.Hackwood:1992,‘Stationarywavesincyclicswarms’.In:IEEEInt.Symp.onIntelligentControl.pp.234–242.
[BonabeauandTheraulaz2000]Bonabeau,E.andG.Theraulaz:2000,‘L’intelligenceenessaim’.
[Bourhisetal.2001]Bourhis,G.,O.Horn,O.Habert,andA.Pruski:2001,‘AnAutonomousvehicleforpeoplewithMotorDisabilities’.IEEERoboticsandAutomationMagazine7(1),20–28.
[Brooks1986]Brooks,R.:1986,‘Arobustlayeredcontrolsystemforamobilerobot’.JournalofRoboticsandAutomation2(1),14–237.
[Burgardetal.2000]Burgard,W.,D.Fox,M.Moors,R.Simmons,andS.Thrun:2000,‘CollaborativeMulti-RobotExploration’.In:ProceedingsoftheIEEEInternationalConferenceonRoboticsandAutomation(ICRA),SanFrancisco,USA.
[Colleetal.2002]Colle,E.,Y.Rybarczyk,andP.Hoppenot:2002,‘ARPH:Anassistantrobotfordisabledpeople’.In:IEEEInternationalConferenceonSystems,ManandCybernetics.
[Dasetal.2002]Das,A.,R.Fierro,V.Kumar,J.Ostrowski,J.Spletzer,andC.Taylor:2002,‘Avision-basedformationcontrolframework’.IEEETransactionsonRoboticsandAutomation18(5),813–825.
[Dixonetal.1999]Dixon,K.,J.Dolan,W.Huang,C.Paredis,,andP.Khosla:1999,‘RAVE:ARealandVirtualEnvironmentforMultipleMobileRobotSystem’.In:InternationalConferenceonIntelligentRobotsandSystems(IROS’99),Vol.3.pp.1360–1367.
[DrogoulandFerber1993]Drogoul,A.andJ.Ferber:1993,‘FromTom-ThumbtotheDockers:SomeExperimentswithForagingRobots’.In:FromAnimalstoAnimats2,ProceedingsoftheSecondInternationalConferenceonSimulationofAdpativeBehavior.pp.451–459.
[Floreanoetal.1998]Floreano,D.,S.Nolfi,andF.Mondada:1998,‘Com-petitivecoevolutionaryrobotics:fromtheorytopractice’.In:FromAnimalstoAnimats5,ProceedingsoftheFifthInternationalConferenceonSimulationofAdpativeBehavior.pp.515–524.
[Fongetal.2001]Fong,T.,C.Thorpe,andC.Baur:2001,‘Collaboration,di-alogue,andhuman-robotinteraction’.In:ProceedingsoftheInternationalSymposiumonRoboticsResearch,Lorne,Victora,Australia.
[FukudaandNakagawa1987]Fukuda,T.andS.Nakagawa:1987,‘Ady-namicallyreconfigurableroboticsystem(conceptofasystemandoptimalconfigurations’.In:ProceedingsofIECON’87.pp.588–595.
[Funesetal.1998]Funes,P.,E.Sklar,H.Juillet,andJ.Pollack:1998,‘Ani-malanimatcoevolution:usingtheanimalpopulationasfitnessfunction’.In:FromAnimalstoAnimats5,ProceedingsoftheFifthInternationalConferenceonSimulationofAdpativeBehavior.pp.525–534.
[GerkeyandMataric2003]Gerkey,B.andM.Mataric:2003,‘AFrameworkforStudyingMulti-RobotTaskAllocation’.In:ProceedingsoftheSecondInternationalNavalResearchLaboratoryWorkshoponMulti-RobotSystems.WashingtonD.C.,USA,pp.3367–3373.
[GoldbergandMataric1999]Goldberg,D.andM.Mataric:1999,‘Coor-dinatingMobileRobotGroupBehaviorUsingaModelofInteractionDynamics’.In:AutonomousAgents1999.Seattle,WA,USA,pp.100–107.
[Iocchietal.2001]Iocchi,L.,D.Nardi,andM.Salerno:2001,‘Reactivityanddeliberation:asurveyonmulti-robotsystems’.
[JonesandRock2002]Jones,H.andS.Rock:2002,‘Dialogue-basedHuman-RobotInteractionforSpaceConstructionTeams’.In:Proceedingsofthe2002IEEEAerospaceConference,BigSkyMT,USA.
[Mataricetal.2002]Mataric,M.,G.Sukhatme,andE.Ostergaard:2002,‘Sold!:Auctionmethodsformulti-robotcoordination’.IEEETransactionsonRoboticsandAutomation,specialissueonAdvancesinMulti-RobotSystems5(18),758–786.
[MeyerandGuillot2001]Meyer,J.andA.Guillot:2001,‘Larobotiqueevolutionniste’.
[Parker1998]Parker,L.:1998,‘ALLIANCE:Anarchitectureforfault-tolerantmulti-robotcooperation’.IEEETransactionsonRoboticsandAutomation14(2),220–240.
[Parker2000]Parker,L.:2000,‘Currentstateoftheartindistributedau-tonomousmobilerobotics’.Distributedutonomousroboticssystems18(4),3–12.
[Parkeretal.2002]Parker,L.,G.Bekey,andJ.Barhen:2002,Distributedautonomousrobotisystems,Vol.4.Springer-Verlag.
[Payneetal.2000]Payne,T.,K.Sycara,M.Lewis,T.Lenox,andS.Hahn:2000,‘VaryingtheUserInteractionwithinMulti-AgentSystems’.In:Pro-ceedingsoftheFourthInternationalConferenceonAutonomousAgents,Barcelona,Spain.
[PradelandComfaits2002]Pradel,G.andO.Comfaits:2002,‘Aframeworkforaweb-supervisorycontrolofmobilerobots.Applicationtoanassis-tancesystemfordisabledpersons’.In:10thIEEEInternationalWorkshoponRobotandHumanCommunication,Roman’01.Bordeaux-Paris,France,pp.249–255.
[PremvutiandYuta1989]Premvuti,S.andS.Yuta:1989,‘Considerationsonthecooperationofmultipleautonomousmobilerobots’.In:ProceedingsoftheIEEEInt.WorkshoponIntelligentRobotsandSystems.pp.59–63.[Rybskietal.2002]Rybski,P.,S.Stoeter,M.Gini,D.Hougen,andN.Papanikolopoulos:2002,‘PerformanceofaDistributedRoboticSystemUsingSharedCommunicationChannels’.IEEETransactionsonRoboticsandAutomation18(5),211–225.
[SchultzandParker2002]Schultz,A.andL.Parker:2002,Multi-robotsys-tems:Fromswarmstointelligentautomata.Kluwer.
[SellemandDalgalarrondo1999]Sellem,P.andA.Dalgalarrondo:1999,‘Extensiond’unearchitecturedecontrˆolederobotmobile`aunsyst`emedistribu´ederobots’.
[Spearsetal.2004]Spears,W.,J.Hamann,andR.Heil:2004,‘Distributed,physics-basedcontrolofswarmvehicles’.AutonomousRobots,inpress17(2-3).
[SurmannandTheissinger1999]Surmann,H.andM.Theissinger:1999,‘ROBODIS:Adispatchingsystemformultipleautonomousservicerobots’.In:ProceedingsoftheFSR’99,RoboticsApplicationsfortheNextMillenium,Pittsburgh,USA.pp.168–173.
[TanandXi2004]Tan,J.andN.Xi:2004,‘Peer-to-peermodelfortheareacoverageandcooperativecontrolofmobilesensornetworks’.In:IEEEICRA’04workshoponenvironmentalrobotics.p.toappear.
[TewsandWyeth2002]Tews,A.andG.Wyeth:2002,‘MAPS:Asystemfor
multi-agentscoordination’.AdvancedRobotics,VSP/RoboticsSocietyofJapan14(1),37–50.
[Vaughanetal.2002]Vaughan,R.,K.Stoy,G.Sukhatme,andM.Mataric:2002,‘LOST:Localization-SpaceTrailsforRobotTeams’.IEEETrans-actionsonRoboticsandAutomation18(5),796–812.
[Wang1989]Wang,P.:1989,‘Navigationstrategiesformultipleautonomousmobilerobots’.In:ProceedingsoftheIEEE/RSJInt.Conf.onIntelligentRobotsandSystems.pp.486–493.
[Yamashitaetal.2003]Yamashita,A.,J.Ota,T.Arai,,andH.Asama:2003,‘Motionplanningofmultiplemobilerobotsforcooperativemanipulationandtransportation’.IEEETransactionsonRoboticsandAutomation19(2),223–237.
[Yuetal.1995]Yu,U.,A.Fukunaga,andA.Kahng:1995,‘CooperativeMobileRobotics:AntecedentsandDirections’.TechnicalReport950049.
因篇幅问题不能全部显示，请点此查看更多更全内容