Efficient collision-free path-planning of multiple mobile robots system using efficient artificial

Jun-HaoLiang,Ching-HungLee⇑DepartmentofMechanicalEngineering,NationalChungHsingUniversity,Taichung402,Taiwan,ROCarticleinfoabstract

Thispaperaimstoproposeanoveldesignapproachforon-linepathplanningofthemultiplemobilerobotssystemwithfreecollision.Basedontheartificialbeecolony(ABC)algorithm,weproposeanefficientartificialbeecolony(EABC)algorithmforsolvingtheon-linepathplanningofmultiplemobilerobotsbychoosingtheproperobjectivefunctionfortarget,obstacles,androbotscollisionavoidance.TheproposedEABCalgorithmenhancestheperformancebyusingeliteindividualsforpreservinggoodevolution,thesolutionsharingprovidesaproperdirectionforsearching,theinstantupdatestrategyprovidesthenewestinformationofsolution.Bytheproposedapproach,thenextpositionsofeachrobotaredesigned.Thus,themobilesrobotscantraveltothedesignedtargetswithoutcollision.Finally,simulationresultsofillustrationexamplesareintroducedtoshowtheeffectivenessandperformanceoftheproposedapproach.Ó2014ElsevierLtd.Allrightsreserved.Articlehistory:Received16July2014Receivedinrevisedform4September2014Accepted21September2014Availableonline14October2014Keywords:MultiplemobilerobotsPathplanningArtificialbeecolonyalgorithmInstantupdateOptimizationCollisionavoidance1.IntroductionManyresearchesareconductedformultiplemobilerobotssys-temsincemultiplerobotscanimprovetheworkingcapabilityandperformance.Thetaskofthepathplanningistoguidethemobilerobotstowardthegoalwithoutcollisionwithobstaclesandotherrobots.Designofafastandefficientmethodisoneoftheimportantproblemsformultiplemobilerobots.Recently,therehavebeenmanyinterestingresearchworkintheliteratureforpathplanningofmobilerobots[1,3,4–16,26–32,35].Manyliteraturesindicatedswarmintelligencetechniquesareamongthemethodsthathaverecentlyreceivedconsiderableinterestintheareaofmobilerobotpathplanning[6,7,9,14,27].Asabove,pathplanningisanimpor-tantissueformultiplemobilerobotssystemnavigation,especiallyon-linepathplanningapproach.Inthispaper,weconsidertheon-linepathplanningproblemformultiplemobilerobotssystem,whichisthetaskofdetermininganoptimalpathfromtheinitialpositiontothetargetwhileavoidingcollisionbetweenrobotsandobstacles.Basedontheartificialbeecolony(ABC)algorithm,weproposeanefficientmethodforsolvingtheon-linepathplan-ningbychoosingtheproperobjectivefunctionfortarget,obstacles,androbotscollisionavoidance.TheABCalgorithmisanewpopulation-basedalgorithmwhichhastheadvantagesoffindingglobaloptimizationsolution,being⇑Correspondingauthor.E-mailaddress:chleenchu@dragon.nchu.edu.tw(C.-H.Lee).http://dx.doi.org/10.1016/j.advengsoft.2014.09.0060965-9978/Ó2014ElsevierLtd.Allrightsreserved.simpleandflexible,andusingveryfewcontrolparameters[2,17–21].TheABCalgorithmhasbeenappliedtomanyreal-worldapplications,e.g.,functionoptimization,real-parameteroptimiza-tion,digitalfilterdesign,clustering,neuralnetworktraining[2,17–21,34].AlthoughtheABCalgorithmbenefitstotheafore-mentionedadvantages,ithassomethingdisadvantagesofaccuracyoftheoptimalvalueandlowconvergencespeed.Herein,wepro-posetheefficientartificialbeecolony(EABC)algorithmtoimprovetheperformanceofoptimization.TheproposedEABCalgorithmenhancestheperformancebyusingeliteindividualsforpreservinggoodevolution,thesolutionsharingprovidesaproperdirectionforsearching,theinstantupdatestrategyprovidesthenewestinfor-mationofsolution.Inthispaper,theon-linepathplanningmethodformultiplemobilerobotssystemwithoutcollisionwithobstaclesandotherrobotsisdevelopedusingtheproposedEABCalgorithm.Thistaskcanbetransferredasanoptimizationproblemwithhybridobjectivefunction,i.e.,theproposedEABCwithhybridizationofobjectivefunctionsfordistancesbetweengoal,otherrobots,andobstaclesareadoptedtoon-lineplanthepathofeachmobilerobot.Thismethodresultsoptimalpathsofmobilesrobotstowardtothegoalandwithoutcollisionintravelperiod.Simulationresultsofillustrationexamplesareshowntodemonstratetheeffectivenessandperformanceoftheproposedapproach.Therestofthepaperisasfollows:Section2introducesproblemformulationforpathplanningofmultiplemobilerobots.Theon-linepathplanningdesignusingEABCisintroducedinSection3.48J.-H.Liang,C.-H.Lee/AdvancesinEngineeringSoftware79(2015)47–56Simulationresultsofillustrationexamplesanddiscussionarepre-sentedinSection4.Finally,conclusionisgiven.2.On-linepathplanningstrategydesignofmultiplemobilerobotsMultiplemobilerobotsusuallyoperateinthesameenviron-mentformanysituations.Thus,pathplanningproblembecomesanimportantissueformultiplemobilerobotssystem[3,7,11,14,27,29,30].Theoff-linemethodisadoptedusuallyforthecaseinwhichtheenvironmentisexactlyknown,andtheon-linepathplanningisusedforunknownenvironment.Inthispaper,theon-linecollision-freepathplanningstrategyformultiplemobilerobotssystemisdevelopedbyusingtheproposedEABCalgorithmwithhybridobjectivefunctions.2.1.ProblemdescriptionAtfirst,weintroducetheenvironmentofon-linepathplanningstrategyformultiplemobilerobotssystemshowninFig.1.ThedesigngoalistodeterminethecorrespondingoptimalpathforobstacleGoaleachmobilerobotsuchthatthemobilerobotsmovefromthecor-respondinginitialpositionstothetarget‘‘Goal’’withoutanycolli-sionswithobstaclesandotherrobots.Fig.2showstheillustrationofEABC-basedapproachformultiplemobilerobotssystem.Detaileddescriptionwillbeintroducedasfollows.TheproposedEABCalgorithmisusedtochoosetheoptimallocalpositionfornextpositionintheneighborhoodofeachmobilerobot.Herein,eachmobilerobot’sstateinthecurrenttimeinstantisdefinedby(xci,yci,hci),i=1,2,...,p,wherepdenotesnumberofrobots.Inthispaper,theoptimizationproblemfornextpositionisevaluatedbythreevalues:objectivevalueforGoal,objectivevalueforobstaclesavoidance,andobjectivevalueforrobotsavoid-ance.Thatis,thenextplannedpositions(xri,yri)forithrobotisdesigned,wherethesubscriptrdenotestheplannedpositionbyEABC,anditalsoplaytheroleofreferencetrajectoryfortrackingcontrolofrobotsinthecurrenttimeinstant.Inaddition,thederiv-󰀂󰀃riÀyciinganglesarecalculatedbyhri¼tanÀ1y.Subsequently,thexriÀxcitrackingcontrolofeachmobilerobotcanbesolvedbytheresultsof[22–25],i.e.,trackingcontrollergeneratessuitablecontrolaction/signals(ddianddhi)suchthatallmobilerobotsmovetothenextplannedstates(xri,yri,hri),i=1,2,...,p.2.2.Collision-freepathplanningbylocalnavigationHerein,theon-linepathplanningofmultiplemobilerobotsisregardedasanoptimizationproblemforsearchinglocaloptimalpositionstepbystep.Theoptimizationconsidersthedistancesbetweengoal,obstacles,andothermobilesfordesigningthenextpositionandcollisions.Theswarmintelligencetechniqueshaverecentlyreceivedconsiderableinterestintheareaofmobilerobotpathplanning.Herein,weusetheproposedEABCalgorithmtofindtheoptimalpathfornextposition.Thenexttargetpositionissearchedintheneighborhoodwithapre-selectedradiusrofthecurrentpositionshownvirtualmobilerobotsinFig.3.FromFig.3,eachrobotusesitsownEABCalgorithmtofindtheoptimalsolutionfornextposition.Thecurrentpositionofmobilerobotisdenotedby(xc,yc)andthevirtualmobilerobotposition(xi,yi),i=1,2,...,PS,wherePSisthechosennumberofvirtualrobots,i.e.,populationnumber.Itpresentstheindividualsforminimizingtheobjectivefunction,whereddenotesthechangingdistance,dxdenotesthechangingdistanceinhorizontal,dydenotestheobstacleobstacleRobot 1obstacleRobot 2Robot 3obstacleRobot PRobot 4Fig.1.Environmentillustrationofon-linepathplanningstrategyformultiplemobilerobotssystem.Fig.2.TheillustrationofEABC-basedapproachformultiplemobilerobotssystem.J.-H.Liang,C.-H.Lee/AdvancesinEngineeringSoftware79(2015)47–5649GoalLocal Navigation region for mobile robot iInitial positionFig.3.Illustrationoflocalnavigationregion(fivevirtualmobilerobotsforsearching).changingdistanceinvertical,Dhdenotesthechangingangle.Then,themobilerobotsfinditsoptimalpathfromsomeinitiallocationstotarget‘‘Goal’’andavoidcollisionwithobstaclesandotherrobots.AsshowninFig.3,thepopulationsize(numberofvirtualrobots)isfiveandthefifthrobotperformsthesmallestobjectivevalue(theoptimalsolutioninthecurrentinstant),i.e.,theoptimalsolutionofnextposition.Therefore,theEABCalgorithmforon-linepathplanningwithlowerandupperboundsisformulatedintheformoffunctiong1(Á)impliestominimizethedistancebetweenvirtualmobilerobotandGoal.Theoptimalindividualischosentobethenextpositionforithrobotincurrentlocation(xc,yc)forlocalnavi-gationarea.Thatis,g1(Á)hastheabilityofderivingthemobilerobottoachievetheGoalstepbystep.(2)ObjectivefunctionforobstaclesavoidanceTheobjectivevalueforobstaclesavoidanceprovidesdistanceinformationbetweenrobotsandobstaclesdefinedasMingðXiÞsubjecttoXi2S;S¼fXi¼ðxi;yiÞjjjXiÀXcjj6rg;ð1Þ(gj2ðXiÞ¼0;kXiÀObsjk1Àd1obs󰀄󰀄󰀄XiÀObsj󰀄>dobs;󰀄󰀄;󰀄XiÀObsj󰀄6dobs;j¼1;2;...;qj¼1;2;...;qð5Þwhereristheradiusofsearchingarea,||Á||denotestheEuclid-eandistanceoperator,andg(Xi)istheobjectivefunctionthatismin-imized.Notethattheradiusrcanbeselectedaccordingtothemobilerobot’smaximumspeed.Subsequently,wegeneratepopula-tioninthesearchingareadefinedas:xi¼xcþ/ÁrÁcosðhÞyi¼ycþ/ÁrÁsinðhÞð2Þwherehisrandomvaluebetween[0,2p],/isarandomvaluebetween[0,1].Thehybridobjectivefunctionintroducedasbelow.2.3.HybridobjectivefunctionInthisphase,weintroducetheusedhybridobjectivefunctionforEABCalgorithm.Theobjectivefunctiondependsonthreerules:reachtoGoal,avoidcollisionswithobstacles,andavoidcollisionswithotherrobots.Astheresultsofliterature[9,14,27],theobjec-tivefunctionforoptimizingtherobots’pathisdefinedaswhereXidenotesthepositionoftheithindividual(orithvirtualrobot),Obsjdenotesthecenterofjthobstacle,dobsdenotessecurityvaluebetweenrobotsandobstacles.Herein,dobscanbechosenbytheradiusofobstaclesandaddsomesecurityvalue,qdenotesnum-berofobstacles.Herein,ourpurposeistominimizetheobjectivefunctiong2(Á).Inordertoavoidcollisionwithobstacles,theshortestdistancebetweenmobilerobotsandobstaclesshouldbelargerthanthesecurityvaluedobs.WhenthevirtualmobilerobotXiisclosetotheobstaclej,g2(Á)resultsanonzerovalue,otherwisezeroobjectivevalueisobtained.Finally,theobjectivevalueofavoidingtheobsta-Pjclesisg2ðXiÞ¼qj¼1g2ðXiÞforlocalnavigation.(3)ObjectivefunctionforrobotsavoidanceSimilartog2(Á)theobjectivevalueforrobotsavoidanceprovidesthedistanceinformationaboutdistancebetweenotherrobotsisdefinedasgðXiÞ¼c1g1ðXiÞþc2g2ðXiÞþc3g3ðXiÞwherecidenotespositiveweightingvaluessatisfyinguserdesign.(1)ObjectivefunctionforgoalP3i¼1ið3Þ(gj3ðXiÞ¼0;kXiÀXcjk1c¼1forÀd1robot󰀄󰀄󰀄XiÀXcj󰀄>drobot;󰀄󰀄;󰀄XiÀXcj󰀄6drobot;j¼1;2;...;pj¼1;2;...;pð6ÞTheobjectivevalueforGoalprovidesthedistancetoGoalwhereXidenotesthepositionoftheithindividual(orithvirtualrobot),Xcjdenotesthejthactualrobotposition.drobotdenotestheg1ðXiÞ¼kXiÀGoalkð4ÞwhereGoaldenotesgoalposition,Xidenotesthepositionoftheithindividual(orithvirtualrobot).Herein,minimizetheobjectivesecurityvaluebetweenrobots.Functiongj3ðXiÞillustratestheavoidanceofcollisionbetweenvirtualrobotXiandjthactualrobotXcj.Inordertoavoidcollisionwithrobots,theshortestdistancebetweenmobilerobotsandotherrobotsshouldbegreaterthan50J.-H.Liang,C.-H.Lee/AdvancesinEngineeringSoftware79(2015)47–56theselectedsecurityvalue.ThecorrespondingobjectivevalueofavoidancerobotscollisionforvirtualrobotXiisobtainedbyg3ðXiÞ¼Ppgjj¼13ðXiÞ.Asabove,thecorrespondingobjectivevalueofvirtualrobotiiscalculatebyEq.(3)andthepositionofvirtualroboti(xri,yri)havingsmallestobjectivevalueisselectedtobethenexttargetpositionforithmobilerobot.Remarks:(a)Theproposedapproachcanbeappliedfordynamicenviron-ment(movingobstaclesavoidance)iftheobstaclesareregardsastheotherrobotsforithvirtualrobot,i.e.,Obsj=Xcj.Ontheotherhand,thevirtualrobotXiconsidersotherrobotsasmovingobstacles,wheretheobstaclepositioniscon-stantlychanging.(b)Theoptimizationofobjectivefunctiong1canbereplacedbyg1ðXiÞ¼kXiÀGoalikwhenthetargetsofmobilerobotsaredifferent,whereGoalidenotesthetargetofithmobilerobot.(c)Otheroptimizationalgorithmcanbeadoptedforthepro-posedon-linepathplanningstrategybyusingthehybridobjectivefunction.Herein,weintroducetheEABCalgorithmtoimplement.3.Efficientartificialbeecolony(EABC)algorithmTheartificialbeecolony(ABC)algorithmwasproposedforreal-parameteroptimizationwhichsimulatestheforagingbehaviorofbeecolony[2,18–21].Itconsistsofthreekindsofbees,employedbees,onlookerbees,andscoutbees.ThispaperintroducesthemodificationsofABCtoimprovetheperformanceofoptimization,includeselite,solutionsharing,instantupdate,andpopulationadjustmentstrategies.ThecomparisonofperformancebetweentraditionalABCandEABChasbeenintroducedin[27].Astheabovedescription,wehereadoptEABCalgorithmwithhybridobjectivefunctiontotreattheoptimizationforon-linepathplanningofmul-tiplemobilerobots.TheEABCalgorithmforoptimizationproblemwithboundsisintheformof(1),wheretheparameterdimensionistwoandeachindividual(orbee)Xirepresentstheithsolutionagent.Inaddition,theflowchartoftheEABCalgorithmisshowninFig.4.Therearefourmajoroperationsforminimizingtheobjec-tivefunction,i.e.,onlookerbeeswithsolutionsharingstrategy,employedbeeswithsolutionsharingstrategy,scoutbees,andpop-ulationadjustment.Herein,weadopttheinstantupdateandsolu-tionsharingstrategiestoenhancetheperformanceoftheEABCalgorithm.Thecorrespondingpseudo-codeoftheproposedEABCalgorithmisgivenbelow:InitializepopulationDoEvaluationofpopulationRankingofpopulation(classifyasonlookerbeesandemployedbees)ProducenewsolutionsbyonlookerbeeswithsolutionsharingProducenewsolutionsbyemployedbeeswithsolutionsharingProducenewrandomsolutionbyscoutbees(theabandonedsolutionisreplaced)UpdatethepopulationsizebypopulationadjustmentUntilstopcriterionismetMoredetailsareintroducedasfollows:(1)InitializationIntheEABCalgorithm,eachindividualXrepresentsasolutionagentandinitialindividualisrandomlychosenfromthecircleregion(localnavigationregioninFig.3).StartInitializationEvaluation & RankingOnlooker Bees Phasei=iSelection+1Noi=Posolution sharingYesOnlooker bees with Employed Bees Phasei=iSelection+1Noi=Psolution sharingsYesEmployed bees with Scout BeesPopulation AdjustmentNoStop Criterion YesEnd0Fig.4.FlowchartoftheproposedEABCalgorithm.(2)EvaluationandrankingThisphaseevaluatesthecorrespondingperformanceofeachindividualcalculates,i.e.,objectivefunctionvalues.Accordingtog(Xi),thefitnessvalueisdefinedasfðXiÞ¼11þgðX;¼1;2;...;PS:ð7ÞiÞiInaddition,thefollowingprobabilityvalueisdefinedforonlookerbeesoperationP¼PfðXiÞVðXiÞPS;i¼1;2;...;PS:ð8Þi¼1fðXiÞSubsequently,allindividualsarerankedandindexed.Finally,theindividualhavingleastobjectivevalueisdefinedasthecurrentbestindividualXbest,i.e.,Xbest={Xi|ming(Xi),Xi2S}.(3)OnlookerbeeswithsolutionsharingHerein,wechoosethehalfbetterpopulationasonlookerbees,i.e.,thepopulationsizeofonlookerbeesPOisPS/2ifPSisevenor(PS+1)/2ifPSisodd,i=1,2,...,PO.Toenhancetheconvergence,thesolutionsharingstrategyisadoptedinthisoperation,thatis,theinformationofthecurrentbestindividualXbestisprovidedtobeapartofsearchingdirection,i.e.,thetrialindividualisVi¼Xiþ/1ðXkÀXiÞþ/2ðXbestÀXiÞð9Þwhere/1and/2arerandomvectorbetween[À1,1]and[0,1],respectively,andkisselectedbyroulettewheelapproachaccordingtoPV(Xi),k–i,toenhancetheevolution.J.-H.Liang,C.-H.Lee/AdvancesinEngineeringSoftware79(2015)47–5651(4)EmployedbeeswithsolutionsharingTheremainedindividualswithlowerfitnessvaluearesettobeemployedbees,i.e.,thepopulationsizeofonlookerbeesPEisPS/2ifPSisevenor(PSÀ1)/2ifPSisodd,i=(PO+1),(PO+2),...,PS.Thedifferentbetweenemployedbeesandonlookerbeesisthediffer-entialvectorcomposedofrandomlyselectedindividualXkandeachindividualXi.Herein,wealsoadoptsolutionsharingstrategytoenhancetheconvergence.ThecorrespondingupdatelawisVi¼Xiþ/1ðXkÀXiÞþ/2ðXbestÀXiÞð10Þwhere/1and/2arerandomvectorbetween[À1,1]and[0,1],respectively,andk2{1,2,...,PS}andk–i.NotethattheselectionofXkhastherandompropertyandthetrialvectormayhavebetterevolutionwhentheonlookerbeeisselected.(5)InstantupdateembeddedselectionNotethattheonlookerbeesandemployedphasesoperateselectioninstantlywhenthenewtrialsolutionisgenerated,asshowninFig.4.Selectionisageneralusedtechniqueforpresent-ingthe&betteroffspring,theoperationisXViifgðViÞ6gðXiÞi¼Xiotherwiseð11ÞwhereVidenotesthetrialindividualinevolutionprocess.Thecur-rentbestindividualXbestisalsoupdatedineachselectionoperation,i.e.,Xbest¼&XiifgðXiÞ6gðXbestÞXbestotherwiseð12ÞHerein,weupdatetheeachindividualandbestindividualinstanta-neously,notuntilallindividualshavebeenoperated.Afteranewindividualbeenproduced,eachindividualXiandthecurrentbestindividualsXbestwouldbeupdatedinstantly.Therefore,wecanpro-videthenewestinformationforthenextindividualinsearchingprocess.Theusedselectionandinstantupdatemethodisintro-ducedasfollows.Theterminationconditionisallindividualshavebeendone.Thismodificationwillenhancetheperformanceofconvergence.Pseudo-codeofinstantupdateembeddedselectionforonlookerphaseFori=1:POProducenewsolutionbyVi¼Xiþ/1ðXkÀXiÞþ/2ðXbestÀXiÞIfg(Vi)6g(Xi)Xi=Vi;g(Xi)=g(Vi);Ifg(Vi)6g(Xbest)Xbest=Xi;EndEnd(6)ScoutbeesThescoutbeescarryoutarandomsearchtodiscovernewfoodsource.Wewithdrawtheworstindividualandgeneratethenewindividualasscoutbeerandomly,i.e.,Xnew¼LBþ/2ÂðUBÀLBÞð13Þwhere/3israndomvaluebetween[0,1].(7)PopulationadjustmentForsolvingtheoptimizationproblem,thereisnogeneralmethodtodecidehowmanyindividualsaresuitable.Havingmoreindividualscanextendthesearchingspaceandincreasetheprobabilityoffindingtheglobaloptimum,butitalsospendsmuchtimeineachgeneration[12].Therefore,thepopulationsize(denotedPS)isoftenchoiceaccordingtousers’experience.Herein,amethodtoadjustthepopulationsizeaccordingthecurrentevolutionstatusisintroduced.Thepopulationsizewillbeincreasedordecreasedaccordingtofollowingconditions,individualcombinationbysim-ilaritymeasurement,andevaluationofevolution.Wesetminimapopulationsizetobetwoandamaximumpopulationsizeisalsopredefinedtoavoidunlimitedincreaseofpopulation.Detailspseudo-codeofpopulationadjustmentisintroducedasfollows.Pseudo-codeofpopulationadjustmentBeginRemoveredundantindividualsbysimilarityexamination(Eq.(14))UpdatePSIfcd>ciandPS>2%goodevolutionPS=PSÀ(cdÀci);IfPS<2PS=2;EndRemovetheabandonedindividualselseifcdTestfunctions[33].

FunctionP2f1ðxÞ¼Di¼1xiQPDf2ðxÞ¼i¼1jxijÀDi¼1jxij󰀃2PD󰀂Pif3ðxÞ¼i¼1j¼1xjf4ðxÞ¼maxfjxij;16i6DgÀÁPÀ122f5ðxÞ¼Di¼1½100xiþ1ÀxiþðxiÀ1Þ󰀅PDf6ðxÞ¼i¼1ðbxiþ0:5cÞ2P4f7ðxÞ¼Di¼1ixiþrandom½0;1ÞPDf8ðxÞ¼i¼1½x2iÀcosð2pxiÞþ10Þ󰀅 !qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiPD21f9ðxÞ¼À20expÀ0:2Di¼1xi󰀂P󰀃D1ÀexpDi¼1cosð2pxiÞþ20þexpð1Þ󰀂󰀃PD2QDxiffi1pf10ðxÞ¼4000þ1i¼1xiÀi¼1cosinPDÀ12f11ðxÞ¼0:1sinð3px1Þþi¼1ðxiÀ1Þ2½1þsin2ð3pxiþ1Þ󰀅PþðxDÀ1Þ2½1þsin2ð2pxDÞ󰀅gþDi¼1uðxi;5;100;4Þ8mxi>aThecomparisonresultofdifferentalgorithmsforD=10in1000generation.Testfunctionsf1f2f3f4f5f6f7f8f9f10f11f12MeanRuntimeMeanRuntimeMeanRuntimeMeanRuntimeMeanRuntimeMeanRuntimeResultsRuntimeMeanRuntimeMeanRuntimeMeanRuntimeMeanRuntimeMeanRuntime(s)(s)(s)(s)(s)(s)(s)(s)(s)(s)(s)(s)EABC6.94Â10À160.851.49Â10À90.953.01Â10À150.815.73Â10À60.934.22Â10À30.691.17Â10À170.90.331.01.84Â10À60.801.25Â10À80.893.96Â10À21.484.18Â10À151.640.9984.04ABC5.62Â10À60.942.26Â10À50.947.65Â10À50.921.140.975.210.903.28Â10À110.900.621.90.590.921.60Â10À30.940.130.965.34Â10À101.410.9982.78PSO5.43Â10À60.242.310.261.67Â10À60.251.160.2748.110.243.22Â10À90.240.360.3023.480.250.910.270.250.285.50Â10À30.483.261.12GA713.490.535.720.553.65Â1030.5435.040.559.75Â1040.53457.420.530.420.6021.960.549.380.565.810.560.210.7722.861.4053obstacles.Onerobotisinitializedatposition(0,0)andfindsthepathtoGoal(3,3)andavoidstheobstaclesintravelperiod.There-fore,theweightingvaluesaresetas(c1,c2,c3)=(0.5,0.5,0).Thestopconditionisthesameasaboveexample.Fig.7introducesthesimulationresults,Fig.7(a)showstheplannedtrajectoryfrom(0,0)to(3,3)withoutcollisionwithobstacles,thecircledenotestheplannedmobilerobot.Theconcentriccirclesshowtheobstacleavoidanceareas,theinnercircledenotestheobstacles,andtheoutercircledenotesthesecurityareaofobstacles.Herein,thesecu-rityradiusesofobstaclesare0.25m,3m,0.35m.WecanobservethatthemobilerobotcanmovetoGoalsuccessfullywithoutcolli-sionswithobstacles.ThecorrespondingobjectivevalueisshowninFig.7(b),wefindthatwhilethemobilerobotavoidscollisionwithobstacles,therearesomevariantofobjectivevalue(seeFig.7(b)),andtheobjectivevalueisminimizedwhenthemobilerobotmovingtoGoal.4.2.3.Example3:Illustrationofthehybridizationofobjectivefunctionsg1(Á)andg3(Á)Herein,tworobotsfrominitialpositions(0,0),(2,2)movingtothecorrespondingGoals(2,2),(0,0)isintroducedtoexaminetheobjectivefunctionrespecttorobotavoidance.TotesttheabilityofmovingtoGoalandrobotsavoidance,theweightingvaluesaresetas(c1,c2,c3)=(0.5,0,0.5).Thestopconditionisthesameasabove.SimulationresultsareshowninFig.8.Fig.8(a)istheplannedtra-jectoriesoftworobotsbyEABCalgorithmwithhybridizationofg1(Á)andg3(Á).WecanobservethattwomobilerobotscanmovetoGoalsandavoidcollisionswithotherrobot.Fig.8(b)introducesthedistancebetweentwomobilerobots.Wecanobservethatthedistancevaluebetweentwomobilerobotsislargerthanthesecu-rityofrobotsintravelperiod(inthiscase,thesecurityofrobotsissettingas0.25m).32.5Goal,showninFig.6(b).ThisillustratestheabilityoftheEABCalgorithmwithg1(Á).4.2.2.Example2:Illustrationofthehybridizationofobjectivefunctionsg1andg2Thisexperimentisintroducedtoillustratetheeffectivenessofobjectivefunctionsg1(Á)andg2(Á),i.e.,reachtoGoalandavoiding2.521.5(a)Goal(b) Objective value2.521.510.5y (m)10.50-0.5-0.5Initialposition00.511.52002468101214161820x (m)Time Step Fig.6.SimulationresultsofExample1,(a)plannedtrajectoryusingEABCalgorithmand(b)thecorrespondingobjectivevalue.32.5(a)Obstacles2.5Goal(b)2Objective value2y (m)1.510.50-0.5-0.5Initialposition1.5obstacleavoidanceregion10.500.511.522.530051015202530x (m)Time step Fig.7.SimulationresultsofExample2,(a)theplannedtrajectoryusingEABCalgorithm;(b)thecorrespondingobjectivevaluevariation.54J.-H.Liang,C.-H.Lee/AdvancesinEngineeringSoftware79(2015)47–562.521.5(a)3Goal(b)2.5Robot 1Initialposition210.50GoalInitialpositionRobot 2Distance00.511.522.5y (m)1.510.50-0.5-0.502468101214161820x (m)Time step Fig.8.SimulationresultsofExample3,(a)theplannedtrajectoryusingEABCalgorithmand(b)thedistancebetweentwomobilerobots.2.5(a)InitialpositionRobot 3ObstaclesInitialposition21.5Robot 2Robot 4y (m)10.5InitialpositionGoal0Robot 1Robot 5-0.5-0.5Initialposition00.511.5Initialposition22.5x (m)Objective value(b)10.50Robot10123456789Objective valueTime step 0.40.20Robot 20123456789Objective valueTime step10.50Robot 30123456789Objective valueTime step 10.50Robot 40123456789Objective valueTime step 10.50Robot 50123456789Time step Fig.9.SimulationresultsofExample4,(a)theplannedtrajectoriesusingEABCalgorithm;(b)Thecorrespondingobjectivevaluevariation.J.-H.Liang,C.-H.Lee/AdvancesinEngineeringSoftware79(2015)47–5655Table3

Comparisonsofabilitybetweenourapproachandotherliteratures.

On-lineOptimizationMultipleValidforapproachapproachrobotsdynamic(shortestpath)environmentLiterature[1]NoNoNoNoLiterature[4]NoYesYesNoLiterature[8]YesYesNoNoLiterature[26]NoYesNoNoLiterature[28]NoYesNoNoLiterature[30]NoYesYesNoLiterature[31]NoNoYesNoLiterature[35]NoNoNoYesOurapproachYesYesYesYes4.2.4.Example4:Illustrationofthehybridizationofobjectivefunctionsg1(Á),g2(Á),andg3(Á)Asabove,weseparatetheobjectivefunctionstoillustratetheeffectivenessofobjectivefunctions.Inthisexample,wecombinetheobjectivefunctionstoexaminetheabilityoflocalsearchingfornextposition,consistsofmovingtoGoal,obstaclesavoidance,androbotsavoidance.Fiverobotsfrominitializedatpositions(0,0),(0,1),(0,2),(2,2),(2,0)andfindthepathtoGoal(1,1),there-fore,theweightingvaluesaresetas(c1,c2,c3)=(0.4,0.3,0.3).Thestopconditionisboththeobjectivevaluesarelessthan0.1.ThesimulationresultsareshowninFig.9.Fig.9(a)showstheplannedtrajectoriesoffiverobotsbyEABCalgorithmwithhybridizationofg1(Á),g2(Á),andg3(Á).Inthetravelperiodofrobots1,4,and5,theyalsoavoidtheobstaclesandthenmovetoGoal.Wecanalsoobservethatrobot2stopatGoalandotherfourrobotsstoparoundtheGoalduetothesecurityofrobots.Herein,thesecurityofrobotsissettingas0.22m.ThecorrespondinghybridobjectivevaluesoffiverobotsareshowninFig.9(b),wecanobservethatallobjectivevaluesareminimizedwhenthemobilerobotsmovingaroundtheGoal.Forthisillustrationexample,weplannedthefivemobilerobotstrajectoriessuccessfullyanditisfeasibleoflocalsearchingfornextpositionbyEABCalgorithm.Finally,toillustrateabilityandeffectivenessofourapproachforon-linepathplanningofmultiplerobots,asimplecomparisonisintroducedinTable3.Table3showsthattheproposedapproachisvalidfordynamicenvironmentandmultiplemobilerobots.Italsohastheabilityofon-lineperformanceandfindingtheshortestpathforeachmobilerobot.5.ConclusionInthispaper,wehaveproposedanon-linecollision-freepathplanningstrategyofmultiplemobilerobotssystemusingthepro-posedEABCalgorithm.TheEABCalgorithmenhancestheperfor-mancebyusingeliteindividualsforpreservinggoodevolution,thesolutionsharingprovidesaproperdirectionforsearching,theinstantupdatestrategyprovidesthenewestinformationofsolution.Itcontainspathplanningfornextposition.First,wesep-aratetheobjectivefunctionstoshowtheabilityofeachobjectivefunction.TheEABCalgorithmhereistofindtheoptimaltrajectorytothegoalforeachmobilerobot.Finally,wecombinepathplan-ningfornextposition.Severalillustratedexampleshavebeenshownthatitisfeasibleinon-linepathplanningofmultiplemobilerobots.Theyalsoshowtheperformanceandeffectivenessofourapproach.AcknowledgementTheauthorswouldliketothankanonymousreviewersfortheirinsightfulcommentsandvaluablesuggestions.ThisworkwassupportedinpartbytheNationalScienceCouncilTaiwan,R.O.C.,undercontractsNSC-102-2221-E-005-095-MY2,NSC-102-2221-E-005-061-MY3andNSC-102-2218-E-005-012.References[1]AbiyevR,IbrahimD,ErinB.Navigationofmobilerobotsinthepresenceofobstacles.AdvEngSoftw2010;41:1179–86.[2]AkayB,KarabogaD.Aefficientartificialbeecolonyalgorithmforreal-parameteroptimization.InfSci2012;192(1):120–42.[3]AraiT,PagelloE,ParkerLE.Editorial:advancesinmultiplemobilerobotssystems.IEEETransRobotAutom2002;18(5):655–61.[4]BhattacharjeeP,RakshitP,GoswamiI,KonarA,NagarAK.Multi-robotpath-planningusingartificialbeecolonyoptimizationalgorithm.In:2011Thirdworldcongressonnatureandbiologicallyinspiredcomputing(NaBIC),19–21October;2011.p.219–24.[5]BorensteinJ,KorenY.Real-timeobstacleavoidanceforfastmobilerobots.IEEETransSystManCybern1989;19(5):1179–87.[6]CaiZ,PengZ.Cooperativecoevolutionaryadaptivegeneticalgorithminpathplanningofcooperativemulti-mobilerobotsystems.JIntellRobSyst2002;33(1):61–71.[7]CaoYU,FukunagaAS,KahngAB.Cooperativemobilerobotics:antecedentsanddirections.AutonRobots1997;4:7–27.[8]ChiaSH,SuKL,GuoJH,ChungCY.Antcolonysystembasedmobilerobotpathplanning.In:2010Fourthinternationalconferenceongeneticandevolutionarycomputing(ICGEC),13–15December;2010.p.210–13.[9]ChenX,LiY.Smoothpathplanningofamobilerobotusingstochasticparticleswarmoptimization.In:Intconfonmechatronicsandautomation;2006.p.1722–7.[10]DudekG,JenkinMRM,MiliosE,WilkesD.Ataxonomyformulti-agentrobotics.AutonRobots1996;3(4):375–97.[11]FahimiF,NatarajC,AshrafiuonH.Real-timeobstacleavoidanceformultiplemobilerobots.Robotica2008;27:189–98.[12]HaoB,DaiX.Thecollision-freemotionofrobotwithfuzzyneuralnetwork.In:The2ndintconfonindustrialandinformationsystems;2010.p.2019–222.[13]HwangYK,AhujaN.Pathplanningusingapotentialfieldrepresentation.IEEEIntConfRobotAutom1988;1:648–9.[14]deJongWJ.Developmentofanexperimentalresearchplatformwithmobilerobotsincludinganapplicationofformationcontrol.MasterofScienceinSystemsandControlatDelftUniversityofTechnology;2008.[15]KambhampatiS,DavisL.Multiresolutionpathplanningformobilerobots.IEEETransRobotAutom1986;2(3):135–45.[16]KhatibO.Real-timeobstacleavoidanceformanipulatorsandmobilerobots.In:IEEEIntconfonroboticsandautomation,St.Louis;1985.p.500–505.[17]KangF,LiJ,XuQ.Structuralinverseanalysisbyhybridsimplexartificialbeecolonyalgorithms.ComputStruct2009;87(13–14):861–70.[18]KarabogaD,BasturkB.Artificialbeecolony(ABC)optimizationalgorithmforsolvingconstrainedoptimizationproblems.FoundFuzzyLogicSoftComput2007;4529:789–98.[19]KarabogaD,BasturkB.Ontheperformanceofartificialbeecolony(ABC)algorithm.ApplSoftComput2008;8(1):687–97.[20]KarabogaD,AkayB.Aefficientartificialbeecolony(ABC)algorithmforconstrainedoptimizationproblems.ApplSoftComput2011;11(3):3021–31.[21]KarabogaN.AnewdesignmethodbasedonartificialbeecolonyalgorithmfordigitalIIRfilters.JFranklinInst2009;346(4):328–48.[22]LeeTC,SongKT,LeeCH,TengCC.Trackingcontrolofunicycle-modeledmobilerobotsusingasaturationfeedbackcontroller.In:IEEETransoncontrolsystemsandtechnology,vol.9(2);2001.p.305–18.[23]LeeCH,ChangFK,LeeYC.Animprovedelectromagnetism-likealgorithmforrecurrentneuralfuzzycontrollerdesign.IntJFuzzySyst2010;12(4):280–90.[24]LeeCH,TengCC.ControlofanonlineardynamicsystemviaadaptivesaturationPIDcontrolscheme.IntJFuzzySyst2002;4(4):922–7.[25]LeeCH,ChiuMH.Recurrentneuro-fuzzycontroldesignfortrackingofmobilerobotsviahybridalgorithm.ExpertSystApplJuly2009;36(5):8993–9.[26]LeiL,ShiruQ.Pathplanningforunmannedairvehiclesusinganimprovedartificialbeecolonyalgorithm.In:Chinacontrolconference,Hefei,25–27July;2012.p.2468–91.[27]LiangJH.On-linepathplanningstrategydesignofmultiplemobilerobotssystemusingmodifiedartificialbeecolonyalgorithm.Materthesis,DepartmentofElectricalEngineering,YuanZeUniversity,Taiwan;2012.[28]LiuG,LiT,PengY,HouX.Theantalgorithmforsolvingrobotpathplanningproblem.In:Thirdinternationalconferenceoninformationtechnologyandapplications,2005,ICITA2005,vol.2,4–7July;2005.p.25,27.[29]Lozano-PerezT,WesleyMA.Analgorithmforplanningcollision-freepathsamongpolyhedralobstacles.CommunACM1979;22(10):560–70.[30]SaffariMH,MahjoobMJ.Beecolonyalgorithmforreal-timeoptimalpathplanningofmobilerobots.In:Fifthinternationalconfonsoftcomputing,computingwithwordsandperceptionsinsystemanalysis,decisionandcontrol.2–4September;2009.p.1,4.[31]SahooRR,RakshitP,HaidarMT.Navigationpathplanningofmulti-robotusinghoneybeematingoptimizationalgorithm(HBMO).IntJComputAppl2011;27(11):1–8.[32]YangSX,LuoC.Aneuralnetworkapproachtocompletecoveragepathplanning.IEEETransSystManCybern–BCybern2004;34(1):718–25.56J.-H.Liang,C.-H.Lee/AdvancesinEngineeringSoftware79(2015)47–56[35]ZhuY,ZhangT,SongJ,liX.Anewhybridnavigationalgorithmformobilerobotsinenvironmentswithincompleteknowledge.Knowl-BasedSyst2012;27:302–13.[33]YaoX,LiuY,LinG.Evolutionaryprogrammingmadefaster.IEEETransEvolComput1999;3(2):82.[34]ZhangC,QuyangD,NingJ.Anartificialbeecolonyapproachforclustering.ExpertSystAppl2010;37(7):4761–7.