Robot Path Planning with GOA Optimization
Robot Path Planning with GOA Optimization
net/publication/376582239
CITATIONS READS
0 218
2 authors:
All content following this page was uploaded by Tohid Yousefi on 16 December 2023.
Abstract – In the world of mobile robots, figuring out the best path is a big deal. Robots use specific plans
to move from one point to another. The main aim of path planning is to find safe moves for the robot in
places full of obstacles. These moves create a smooth, collision-free path from where the robot starts to its
target. There are many ways to solve this path problem, but they're not perfect yet. Recently, researchers
have turned to smart methods, called meta-heuristic methods, to solve these problems. In our study, we
tried out the particle swarm optimization algorithm (PSO) and the grasshopper optimization algorithm
(GOA). Looking at the results, we found that PSO had a best cost value of 7.5558, and GOA had a best
cost value of 7.5421. This shows how good the grasshopper optimization algorithm is at path planning
and how effective these meta-heuristic methods can be.
Keywords – Grasshopper Optimization Algorithm, Meta-heuristic algorithms, Optimization, Particle Swam Optimization,
Robot Path Planning
106
suitable trajectory involves a sequence of actions, given conditions by minimizing costs or
navigating the robot from the starting point to the maximizing utility. These conditions, leading to the
target through intermediate states. Decisions in maximum or minimum value of a function, are
path planning algorithms are based on current state referred to as optimizations [19].
information and criteria like the shortest distance Optimization is the process of identifying the
measured using Euclidean distance computation. most optimal solution from a set of possibilities. It
While there may be multiple paths, some situations is both a mathematical assessment indicating the
may lack a feasible route. The optimal path is quality of a solution and a method that models a
ideally the shortest, obstacle-free, and takes the problem as an objective function, systematically
least time to reach the goal, considering motion exploring potential solutions to find the best one
constraints like nonholonomic conditions in [20, 21].
underactuated systems. Path planning proves to be As illustrated in the equation below, the
a versatile tool in robotics, offering solutions to a conventional representation of an optimization
variety of real-world problems [16]. problem typically revolves around minimizing the
Today, we are at the peak of progress in the field objective function [22]:
of robotics, and every day new robots with various 𝑚𝑖𝑛 𝑓(𝑥) ∶ 𝑥
applications enter the labor market. One of these
𝑔𝑗 (𝑥) ≥ 0, 𝑗 = {1,2, … , 𝐽}
new systems is mobile robotic systems. which ∈ 𝑅 𝑛 𝑠. 𝑡 {
allows us to do many logistic tasks automatically. ℎ𝑘 (𝑥) = 0, 𝑘 = {1,2, … , 𝐾}
These types of robots need to know their position
(𝐿) (𝑢)
relative to the target position to successfully 𝑥𝑖 ≤ 𝑥𝑖 ≤ 𝑥𝑖 𝑖 = {1,2, … , 𝑛}
navigate. In addition, they should consider the
dangers and obstacles of the surrounding where 𝑓(𝑥) is the optimized function, 𝑔𝑗 (𝑥) is j
environment and adjust their actions to maximize inequality constraints and ℎ𝑘 (𝑥) represents K
the chances of reaching the destination [17]. equality constraints.
The robot path planning problem is a challenging
optimization task commonly addressed using meta- C. Meta-Heuristic Algorithms
heuristic algorithms. The goal is for the mobile Meta-heuristic algorithms mark a notable
robot to reach its target from the starting point via departure from historical heuristic methods,
the shortest path without encountering obstacles. introducing a more systematic and innovative
The problem involves factors like start and target approach to problem-solving. While traditional
positions, obstacle size, shape, number, and zone heuristics often relied on intuition and accidental
boundaries. The objective function for path discoveries, meta-heuristics demonstrate
planning is crucial in defining the optimization widespread success by drawing inspiration from
criteria. Here is the mathematical expression natural events like biological systems and physical
representing the objective function for planning the processes. This shift represents an evolution in
path of a robot [18]: problem-solving, embracing strategic algorithms
inspired by real-world processes for increased
𝑗 = 𝑚𝑖𝑛 𝑄 (1 + 𝛽𝑉) efficiency and adaptability [5, 23].
Meta-heuristics offer an effective means of
Here, 𝛽 stands for the violation coefficient (fixed finding practical solutions to complex problems
at 100), V represents the violation cost, and Q within a reasonable timeframe through trial and
indicates the overall distance between the starting error. Their primary objective is to identify well-
and target points. practiced solutions within an acceptable time scale
[5]. These methods enable efficient exploration of
B. Optimization solution spaces, striking a balance between
Optimization is a crucial aspect across numerous effectiveness and practical time constraints.
applications in engineering and industry, aiming to
minimize costs, energy consumption, or maximize D. Particle Swarm Optimization
profits, output, performance, and efficiency. The The particle swarm optimization is a
objective is to achieve the best outcomes under computational method introduced by Kennedy and
107
Eberhart in 1995 [6]. Since its inception, various global and local search, enhancing the performance
adaptations have been created to address practical of particle swarm optimization [26].
optimization problems [24]. This algorithm
E. Grasshopper Optimization Algorithm
operates as a swarm-based search, with each entity
referred to as a particle. Employed to tackle Grasshoppers pose a significant threat to
optimization challenges, the method involves agriculture, affecting product quality and causing
iteratively adjusting particle velocities based on damage [28]. Their life cycle involves two stages:
combined information and calculating new nymph and adulthood. The nymph stage reflects
positions in each dimension. These particles small, slow movements akin to optimization
continuously navigate a multidimensional search extraction, while adulthood involves sudden, long
space, aiming to achieve equilibrium, optimal steps resembling exploration in optimization
solutions, or surpass computational constraints. algorithms. The Grasshopper Optimization
Figure 1 illustrates the overall flowchart of the Algorithm, introduced in 2017, mimics
particle swarm optimization algorithm [25]. grasshopper swarming behaviors in natural search
processes [7]. This algorithm, categorized as a
swarming algorithm, is inspired by the collective
movement of grasshoppers [29]. Figure 2 displays
the flowchart illustrating the Grasshopper
Optimization Algorithm [7].
IV. RESULTS
In this section of our research, we analyze the
outcomes achieved by employing the PSO and
GOA algorithms for resolving the robot path
planning issue.
Figure 3 shows an example of how a robot plans Fig. 4 The best solution obtained by the particle swarm
its path. In a 6x6 area, there are three round optimization algorithm
obstacles with different sizes. The yellow square is
In Figure 4, there's a clear demonstration that the
where the robot starts, and the green star is where it
PSO algorithm successfully navigated through the
wants to go. We use PSO and GOA algorithms to
planned obstacle, ultimately reaching the
solve this problem and compare the results to see
designated goal.
which one works best.
110
used to solve such problems and find an optimal Instrumentation & Information Systems (EIIS), pp.
solution for them. 1-4, 2017. pp. 1-4, 2017.
[9] Lyu D., Chen Z., Cai Z., and Piao S., "Robot path
In this article, we took on the challenge of robot planning by leveraging the graph-encoded Floyd
path planning using two different methods: Particle algorithm," Future Generation Computer Systems,
Swarm Optimization (PSO) and the Grasshopper vol. 122, no. pp. 204-208, 2021.
Optimization Algorithm (GOA). Both were trying [10] Li H., Zhao T., and Dian S., "Forward search
to find the shortest path. Our results showed that optimization and subgoal-based hybrid path
planning to shorten and smooth global path for
with PSO, we got a best cost value of 7.5558. On mobile robots," Knowledge-Based Systems, vol. no.
the other hand, GOA did a bit better with a best pp. 110034, 2022.
cost value of 7.5421. Looking at these results, it's [11] Bae H., Kim G., Kim J., Qian D., and Lee S., "Multi-
clear that the GOA method is better at handling the robot path planning method using reinforcement
tricky parts of robot path planning. learning," Applied sciences, vol. 9, no. 15, pp. 3057,
2019.
In this article, our main aim is to get the best [12] Ni J., Zhang Z., Su B., Fan X., and Liang W., "A bio-
results for planning robot paths using the inspired neural network based PSO method for robot
grasshopper optimization algorithm. In the future, path planning," 2017 13th International Conference
researchers can explore solving the robot path on Natural Computation, Fuzzy Systems and
planning puzzle using other smart algorithms like Knowledge Discovery (ICNC-FSKD), pp. 234-238,
2017. pp. 234-238, 2017.
MOPSO, MOGOA, SPEA-II, and MODE. This [13] Shareef A. and Al-Darraji S., "Grasshopper optimization
way, we can see how the results compare and algorithm based path planning for autonomous
maybe make the model even better. Also, trying mobile robot," Bulletin of Electrical Engineering
out our method on different sets of data will help and Informatics, vol. 11, no. 6, pp. 3551-3561,
us see how well it works for various situations. 2022.
[14] Qin Y.-Q., Sun D.-B., Li N., and Cen Y.-G., "Path
planning for mobile robot using the particle swarm
optimization with mutation operator," Proceedings
REFERENCES
of 2004 international conference on machine
[1] Koubaa A., Bennaceur H., Chaari I., Trigui S., Ammar learning and cybernetics (IEEE Cat. No. 04EX826),
A., Sriti M.-F., Alajlan M., Cheikhrouhou O., Javed pp. 2473-2478, 2004. pp. 2473-2478, 2004.
Y., and Koubaa A., "Introduction to mobile robot [15] Siegwart R., Nourbakhsh I.R., and Scaramuzza D.,
path planning," Robot path planning and Introduction to autonomous mobile robots, MIT
cooperation: foundations, algorithms and press, 2011.
experimentations, vol. no. pp. 3-12, 2018. [16] Klancar G., Zdesar A., Blazic S., and Skrjanc I.,
[2] Alexopoulos C. and Griffin P.M., "Path planning for a Wheeled mobile robotics: from fundamentals
mobile robot," IEEE Transactions on systems, man, towards autonomous systems, Butterworth-
and cybernetics, vol. 22, no. 2, pp. 318-322, 1992. Heinemann, 2017.
[3] Sariff N. and Buniyamin N., "An overview of [17] Koubaa A., Bennaceur H., Chaari I., Trigui S., Ammar
autonomous mobile robot path planning algorithms," A., Sriti M.-F., Alajlan M., Cheikhrouhou O., and
2006 4th student conference on research and Javed Y., Introduction to mobile robot path
development, pp. 183-188, 2006. pp. 183-188, 2006. planning, Springer, 2018.
[4] Panda M., Das B., Subudhi B., and Pati B.B., "A [18] Xue Y. and Sun J.-Q., "Solving the path planning
comprehensive review of path planning algorithms problem in mobile robotics with the multi-objective
for autonomous underwater vehicles," International evolutionary algorithm," Applied sciences, vol. 8,
Journal of Automation and Computing, vol. 17, no. no. 9, pp. 1425, 2018.
3, pp. 321-352, 2020. [19] Hussain K., Mohd Salleh M.N., Cheng S., and Shi Y.,
[5] Yang X.-S., Nature-inspired metaheuristic algorithms, "Metaheuristic research: a comprehensive survey,"
Luniver press, 2010. Artificial intelligence review, vol. 52, no. pp. 2191-
[6] Kennedy J. and Eberhart R., "Particle swarm 2233, 2019.
optimization," Proceedings of ICNN'95- [20] Burke E.K., Burke E.K., Kendall G., and Kendall G.,
international conference on neural networks, pp. Search methodologies: introductory tutorials in
1942-1948, 1995. pp. 1942-1948, 1995. optimization and decision support techniques,
[7] Saremi S., Mirjalili S., and Lewis A., "Grasshopper Springer, 2014.
optimisation algorithm: theory and application," [21] Yousefi T. and Aktaş Ö., "New hybrid segmentation
Advances in Engineering Software, vol. 105, no. pp. algorithm: UNet-GOA," PeerJ Computer Science,
30-47, 2017. vol. 9, no. pp. e1499, 2023.
[8] Yongxiang Z. and Lei Z., "Improvement and application [22] Sengupta R.N., Gupta A., and Dutta J., Decision
of heuristic search in multi-robot path planning," sciences: theory and practice, Crc Press, 2016.
2017 First International Conference on Electronics
111
[23] Koziel S. and Yang X.-S., Computational optimization,
methods and algorithms, Springer, 2011.
[24] Li C., Yang S., and Nguyen T.T., "A self-learning
particle swarm optimizer for global optimization
problems," IEEE Transactions on Systems, Man,
and Cybernetics, Part B (Cybernetics), vol. 42, no.
3, pp. 627-646, 2011.
[25] Wang D., Tan D., and Liu L., "Particle swarm
optimization algorithm: an overview," Soft
computing, vol. 22, no. 2, pp. 387-408, 2018.
[26] Tran B., Xue B., and Zhang M., "Overview of particle
swarm optimisation for feature selection in
classification," Asia-Pacific conference on simulated
evolution and learning, pp. 605-617, 2014. pp. 605-
617, 2014.
[27] Shi Y. and Eberhart R., "A modified particle swarm
optimizer," 1998 IEEE international conference on
evolutionary computation proceedings. IEEE world
congress on computational intelligence (Cat. No.
98TH8360), pp. 69-73, 1998. pp. 69-73, 1998.
[28] Ewees A.A., Abd Elaziz M., Alameer Z., Ye H., and
Jianhua Z., "Improving multilayer perceptron neural
network using chaotic grasshopper optimization
algorithm to forecast iron ore price volatility,"
Resources Policy, vol. 65, no. pp. 101555, 2020.
[29] Beni G. and Wang J., Swarm intelligence in cellular
robotic systems, Springer, Berlin, 1993.
[30] Doğan L. and Yüzgeç U., "Robot path planning using
gray wolf optimizer," Proceedings-International
Conference on Advanced Technologies, Computer
Engineering and Science (ICATCES’18), pp. 2018.
pp. 2018.
112