Path Optimization for Mobile Robot Using Genetic Algorithm

International Research Journal of Engineering and Technology (IRJET) e ISSN: 2395 0056

Volume: 09 Issue: 06 | Jun 2022 www.irjet.net p ISSN: 2395 0072

Path Optimization for Mobile Robot Using Genetic Algorithm

1,2,3

Abstract – This study presents the concept of using the Genetic Algorithm approach to resolve the mobile robot path planning problem in a static environment with predictable terrain. We present our initial Idea for using genetic algorithms to assist a controllable mobile robot to hunt out an optimal path between a starting and ending point in an exceedingly grid environment. The two problems that occur in an exceedingly very mobile robot's path planning are finding the shortest path and a collision free path. These should be achieved during a static environment ofobstacles. This work is different from other works within the aspect of stationing the obstacles and running the genetic algorithm with user input iterations. This work ensures that the goal position is the global minimum path of the total potential. During this work, anytime the obstacles keep changing the positions. This work is finished in an environment that's modeled inspace time and collision free path by a variation of the Genetic algorithm. A genetic algorithm is capable of competing with every other learning algorithm in terms of accuracy and high performance. Because the number of iterations keeps on increasing, the algorithm draws the shortest andcollision free path. When the obstacles, the initial and destination points, so the number of iterations are set the ultimate wordresult that's the shortest and collision free path is acquired.

Key Words: Path Planning, Genetic Algorithm, Mobile Robot, Static Environment, Optimization.

1. INTRODUCTION

Robots are being introduced into practically every sector throughout the planet to attain error free and optimum results. Every one of the challenges preventing mankind from deploying robots for transportation services is their mobilityandnavigation,robots,unlikehumans,areunable to form optimal path planning without training. This researchpaperintendstoworkoutthemosteffectivethanks tosolvingtheproblemofpathnavigation.

Thegoalofrobotpathplanningistofindapaththathasa reasonable chance of leading from a starting point to a destination point without colliding with any obstacles. However, this navigation challenge has multiple tough phases that have to be overcome, like obstacle avoidance, location identification, and so on. A reliable and efficient navigation system must be ready to identify the robot's presentlocation,avoidcollisions,anddeterminea pathto the destination. As a result, the mobile robot navigation problemcouldbeacomplicatedchallenge,andseveralother sorts of research are performed, yielding a considerable

***

numberofsolutions[1][2].Efficiency,safety,andaccuracyare three important considerations when it involves robot navigationchallenges.Thealgorithm'sefficiencyisregarded ascrucial becauseofoneof theprimaryconsiderations in locating the destination in a short period. As a result, avoidingsuperfluousstepsorbeingstuckinlocalminimum positionsbytherobotshouldleadtoanhonestcourse.

A perfect approach should also avoid all known barriers. Anotherkeyaspectof thealgorithmisitssafety.Oncethe optimal collision free path has been identified, the robot mustfollowthepre definedpathprecisely.Thekeyscopeof thepath findingproblemisanxiousexpeditiouslyandsafety considerations. Lots of efforts are made to beat these two criticaldifficulties[3] .

Variousconventionalmethods,likecelldecomposition,road maps,andpotentialfields,aredevelopedtounravelthetrail planningproblem[4][5].Thebulkofthosesolutionswasbuilt around the concept of spatial arrangement[5]. These approaches demonstrate an absence of adaptation and robustness.Tohandletheshortcomingsofthoseapproaches, researchers investigated a spread of alternatives. For complex and ill behaved optimization problems, Genetic Algorithmsareconsideredoneofthemostrobustmethods available [6] .

A Genetic Algorithm could be a prominent approach that seeks the optimum solution from a group of alternatives. Consider through points as genes in an exceeding chromosome, which will provide a variety of various possibilitiesonagridmapofpathways.Duringthissituation, the trail distances created by each chromosome are considered a fitness measure for that chromosome. An answerpathmaycrossanobstructioninsomeinstances.If theobstructionisformedsortofarectangle,suchrandom solutions are easily removed by putting in place a straightforwardequationbetweentheroadformedbytwo through points and therefore the obstacle. To address the problem of determining robot path planning in a static environment with predictable topography and known obstacles, this paper used the Genetic Algorithm. We presentedasimplifiedfitnessfunctionthatcreatesuseofthe traillength.Theproposedstudyexaminedtheevolutionary process'sperformancewithvaryingnumbersofobstaclesat variouspositionsontheterrain.Apreliminarytestsuggests thattheproposedmethodiseffectiveandefficientindealing withawiderangeoftasksinstaticenvironments.

International Research Journal of Engineering and Technology (IRJET) e ISSN: 2395 0056

Volume: 09 Issue: 06 | Jun 2022 www.irjet.net p ISSN: 2395 0072

2. LITERATURE REVIEW

Table -1: Aliteraturereviewofthereferences

S. No AUTHOR & YEAR TECHNIQUES/ METHODS RESULTS

1 C.Alexopoulos& P.M.Griffin1992[7]

2 MargritBetke& LeonidGurvits 1997[8]

3 S.S.Ge&Y.J.Cui 2000[4]

V*graphalgorithm,E* graph Algorithm

Navigationoflandmarks,map algorithms,localizationof mobilerobots,robotics, triangulation.

GNRONproblem,Newrepulsive potentialfunction,apotential field.

Usedtwoalgorithmsformobilerobot path planning. In the presence of stationaryobstacles,wecancompute theshortesttimecollision freepathfor mobilerobots.

Intermsoflandmarks,thealgorithmis linear. It gives a position estimation that is very close to how the robot is actuallypositioned.However,thereare errorsinsomeofthelengths.

They used the GNRON algorithm in order to ensure the robot would not collidewiththegoalduringitsjourney using the topic of mobile robot path planning to determine the distance betweentherobotandthegoal.

FUTURE SCOPE

4 YonrongHu&Simon X.Yang2004[9]

Geneticalgorithm

Thegeneticalgorithmusedhereuses gridsandcoordinatestorepresentthe environmentwhenplanningapathfor a mobile robot. In addition to providing good solutions from infeasible solutions, a genetic algorithmisdevelopedwiththeuseof anefficientmethod.

when domain knowledge is used in thegeneticalgorithm,a more viable solution will be given for the initial population of the future study. This is more desirable in thefuture.

5 IsmailAL Taharwa, AlaaShetha& MohammedAl Weshah2008[10]

Pathplanning,genetic algorithm,robotics.

Inthecaseofamobilerobotworking in a static environment, the paper describesusingageneticalgorithmfor path planning and also exposed the performanceofevolutionaryprocesses withdifferentsizesofpopulationand different types of tasks in the static environment.

6 MichaelBrand&Xiao HuaYu2013[1]

Glowwarmswarm optimization,robotpath planning,Fireflyalgorithm.

Inbothstaticanddynamicrobotparks, firefly algorithm approaches are employed to determine the shortest path in the two dimensional workspace without colliding with otherobjects.

Theparametersofthis algorithm may be further explored in futureworks,including the minimum number of fireflies needed for real time implementation.

International Research Journal of Engineering and Technology (IRJET) e ISSN: 2395 0056

Volume: 09 Issue: 06 | Jun 2022 www.irjet.net p ISSN: 2395 0072

7 NadiaAdnanShiltagh &LanaDalawrJalal 2013[3]

8 RajatKumarPanda& B.B.Choudhury 2015[6]

Globalpathplanning,mobile robotswithintelligence,genetic algorithmswithmodification, optimalpath.

Mobilerobot,pathplanning, GeneticAlgorithm

9 XuewuWang,Lika Xue,YixinYan&Xing shengGu2017[5]

Anantcolonyalgorithmusedin weldingrobots,co operative traveling,particleswarm optimizationalgorithm

Through the application of the Modified Genetic Algorithm (MGA), a path planning algorithm for mobile robotsisexploredinthisstudy.

Throughout the paper, we will examine the design of a battery operated mobile robot and its path planning.

In this optimization problem, finding the shortest path length is the objective, while avoiding obstacles is theconstraint.Afteroptimization,the shortest collision free path was obtained.Theglobalweldingcollision free path planning was optimized usingtheparticleswarmoptimization algorithm.

10 ChaymaaLamini,Said Benhlim&AliElbekri 2018[11]

11 HyeokSooLee& JongpilJeong2021[2]

Geneticalgorithm,path planning,crossover operator,navigation,mobile robot.

Warehouseenvironment, Reinforcementlearning,mobile robotpath optimization.

Thisarticleproposesafitnessfunction for the genetic algorithm, which minimizes the number of turns required in reaching the goal, which will help optimize the energy consumptionoftherobot.

This reviewed the use of reinforcement learning as a path optimizationtechniqueinawarehouse environment. By avoiding inventory pads, they were able to find the optimalpathtothetargetposition.



First, create a grid graph within the search environment(Figure3).Asaresult,therobotwilltravel during a step pattern on the proposed grid,asit wouldintherealworld.



Second,we wantto reset the obstacles within the environment(Theobstacleswemodifyvaryfromtime totime).

Figure -1: Validationofinputs

3. RESEARCH METHODOLOGY

Theseproceduresweretakenintoconsiderationwhenusing Genetic Algorithms to resolvethe trialplanning challenge. Theseare:

Thenwewouldliketospecifythestartingandendingpoint for the trail to be drawn by using the parameters start x, start y, end x, end y(start x, start y indicates theplace to beginandendx,endyindicatesendingpoint)(Figure4).The iterationvaluesshouldbespecifiedonlyinnumbers/digits format.Theobstaclesaresetthencomestheinitialpointand goalpointsetting.Finally,theiterationsandnumberofruns are set. The setpoints are validated(Figure1). The robot performsthefunctionoffindingthepathtothegoalwithin thegridenvironmentbyemployingageneticalgorithm.Asa

© 2022, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal | Page2527

International Research Journal of Engineering and Technology (IRJET) e ISSN: 2395 0056

Volume: 09 Issue: 06 | Jun 2022 www.irjet.net p ISSN: 2395 0072

result, after the evaluation draws the best path planning collision free.

rankedasapopulation.ItiscrucialtothesuccessofGAsfor fitnessevaluationtoprovideinformationonhowgoodeach candidateis.Itiscommontogeneratetheinitialpopulation randomly.Fitnessevaluation,selection,andreproductionare thethreestepsofevolutionfromonegenerationtothenext

3.2. Path planning

The purpose of mobile robot path planning isto go lookingoutapaththatconnectsthisandtargetpositions.The pathshould be as short as possible, the smoothness ofthe pathshould match the mobile robot's dynamics, andthe pathshouldbesecurefromcollisions

4. RESULTS AND DISCUSSIONS

Figure 2:Flowchartfortheproposedmethodologies

3.1. Genetic algorithm

Foramobilerobot,thepaperusesaGeneticAlgorithmfora global path that guides it to this goal. Using a genetic algorithm, the robot can learn the most effective path to followinaparticularenvironment.Anenvironmentcanbea two dimensionalworkspacewherethetargetislocated,and obstaclesmustbeavoidedifthebestpathistobefound.

Createdagridgraphwithinthesearchenvironment(Figure 3).Asaresult,therobotwilltravelduringasteppatternon theproposedgrid,evenasitmightintherealworld.Inthe aspect of stationing the obstacles and running the genetic algorithm with user input iterations, this work is made differently where static obstacles are stationed but reset obstacles(Figure 4) will change the positions of the obstacles. Assures that the goal position is the globally minimumpathtowardsthefullpotential.Duringthiswork, anytimetheobstacleskeepchangingthepositions.

Figure 3:Mapforpathplanning

Generic algorithms maintain a pool of candidates, and the binary strings used to encode each candidate solution are called chromosomes. It has been determined that binary coding is the most effective method. Using the fitness evaluationfunction,agroupofchromosomesisanalyzedand

Figure 4:Settingsource,obstacles,anddestinationpoints

To evaluate the system performance many tests weredispensedby varying the GA's parameters. The simplestperformance was achieved withthe subsequentparametersstartingat(x,y) >(1,1),endingat (x,y) >(20,10)(Figure6),thetotalnumberofrunswas1 and the total no of iterations was 500 and (x, y) > (1,1), endingat(x,y) >(10,10)(Figure5),thetotalnumberofruns was 5 and the total no of iterations was 500. Overall,the simplestpath wasnot toguide the robotin severalways, starting at different initial locations & with distinct goal

2022, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal |

International Research Journal of Engineering and Technology (IRJET) e ISSN: 2395 0056

Volume: 09 Issue: 06 | Jun 2022 www.irjet.net p ISSN: 2395 0072

points.To inducethe most effectiveshortest pathand therefore thecollision free path the iterations should be more. Figure 5 and Figure 6 are two cases. Figure 5 is ascenariowherethegoalpointisamongtheobstaclesand therefore thepath drawn betweenthe actualpoints. Secondly,Figure6isascenariowherethegoalpointisafter theendingofobstaclesi.e.,theplacetobeginthex axis,y axis,andendingpointofthex axis,y axis,andthereforethe path drawn between these points. As may be verified by Figure5andFigure6,therobottendstomaneuvertowards the placement of the goal, traveling consistently with a minimumdistancedirectionbetweenthestartingandalso arrivalpositions.

5. CONCLUSION

Figure 5:Pathplanningforscenario1

The results obtained showed that the utilization of the GeneticAlgorithmforthemobilerobotproducedextremely smooth path planning. The robot usually travels and successfully finds the varied goal points from distinct startingpointsandenvironmentsandattheidenticaltime avoidsobstacles.Becausethenumberofiterationsincreases, therobotwilltakeyoutotheshortestdistance,byreducing the number of turns in its path to realizing the goal. The resultsprovethattheproposedGeneticalgorithmmethod findstheoptimalpath.Thetypicalnoofrunvaluesandalso thecommoniterationnumbersoftheproposedmethodare more optimal compared to other methods. To induce accurateresultswhilesettingthepointsonthex axisandy axistrueduringthiswork ishandled in suchthesimplest waythatnon numericalcharacterscannotbetakenasinput ifdothatthesystemwarnstheusersayingthatthiscan'tbe givenasaninputtolineinitialandgoalpoints,Thishandling of non numerical characters is additionally through with otherinputvalues.Thealgorithmduringthisworkdoesn't useinformationaboutthemotionofthemobilerobot:the historyofpositionestimates,thecommandsthatmakethe robotmove,andalsotheuncertaintiesinthesecommands. The Genetic Algorithms complexity is O(g(nm + nm + n)) with g the number of generations, n the population size(obstacles), and m the scale of the mutants(possible ways).Hence,thecomplexityofthegeneticalgorithminthis work is on the order of O(gnm)). Future research can undergotheperformanceofGeneticalgorithmsinadynamic environment. Another future direction is to test the effectiveness of Genetic Algorithms with physical robots duringareal worldapplication Thisworkhaslimitations, where the points given are static and obstacles, are generatedrandomlybytheprogramsoinfuturescopewe areabletomanuallyoruseacursortopickthepointsand shapesoftheobstaclesonthemap.

6. REFERENCES

[1] M. Brand, X. H. Yu, “Autonomous Robot Path Optimization Using Firefly Algorithm”, Proceedings of the2013InternationalConferenceonMachineLearning andCybernetics,Tianjin,14 17July2013.

[2] H.S.LeeandJ.Jeong,“MobileRobotPathOptimization TechniqueBasedonReinforcementLearningAlgorithm inWarehouseEnvironment”,Appl.Sci.2021.

Figure -6:Pathplanningforscenario2

[3] N.A.ShiltaghandL.D.Jalal,“PathPlanningofIntelligent Mobile Robot Using Modified Genetic Algorithm”, InternationalJournalofSoftComputingandEngineering (IJSCE)ISSN:2231 2307,Volume 3,Issue 2,May2013.

[4] S.S.GeandY.J.Cui,“NewPotentialFunctionsforMobile RobotPathPlanning”,IEEEtransactionsonroboticsand automation,vol.16,no.5,October2000.

International Research Journal of Engineering and Technology (IRJET) e ISSN: 2395 0056

[5] X. Wang, L. Xue, Y. Yan, and X. Gu, “Welding Robot Collision FreePathOptimization”,Appl.Sci.:8February 2017.

[6] R. K. Panda and B. B. Choudhury, “An Effective Path Planning of Mobile Robot Using Genetic Algorithm”, IEEE International Conference on Computational Intelligence&CommunicationTechnology,2015.

[7] C. Alexopoulos and P. M. Griffin, “Path Planning for a MobileRobot”,IEEEtransactionsonsystems,man,and cybernetics,vol.22,no.2,March/April1992.

[8] 8.M. Betke and L. Gurvits, “Mobile Robot Localization Using Landmark”, IEEE transactions on robotics and automation,vol.13,no.2,April1997.

[9] Y. Hu and S. X. Yang, "A Knowledge Based Genetic A1gorithm for Path Planning of a Mobile Robot", Proceedingsofthe2004IEEEInternationalConference onRobotics8AutomationNewOrleansLAApril2004.[

[10] 10.I.AL Taharwa,A.Sheta,andM.Al Weshah,“AMobile RobotPathPlanningUsingGeneticAlgorithminStatic Environment”,JournalofComputerScience4(4):341 344,2008.

[11] 11. C. Laminia, S. Benhlimab, A. Elbekria,b, “Genetic Algorithm Based Approach for Autonomous Mobile Robot Path Planning,” The First International ConferenceOnIntelligentComputinginDataSciences, 2018.

Volume: 09 Issue: 06 | Jun 2022 www.irjet.net p ISSN: 2395 0072 © 2022, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal