Grey Wolf Optimizer for Robot Path Planner in C++
The path planner is a crucial component of robot motion. To design the robot’s route from one point to another, robotic systems employ algorithms (often called intelligent). The basic objective of route planning is to determine a robot’s permissible movements in an environment with obstacles. These movements involve a path from the start point to the target place without collisions with obstacles.
In the following article, I used the Gray Wolf Optimization (GWO) algorithm to solve an online robot path planning problem (collision avoidance).
GWO belongs to the group of metaheuristic algorithms, which can be applied to solve any optimization problems. The term was created from the combination of the word “meta” — meaning “higher level”, and the word “heuristic” — meaning “to search”, which results from the fact that algorithms of this type do not solve any problem directly, and they only provide a way to create the appropriate algorithm.
Before I started with the robot path planner I checked GWO performance by running a simple optimization problem (details later).
Grey Wolf Optimizer
The article is thought to give intuition over the algorithm and depict principles of deployment in C++. For the deployment of the GPO algorithm, I used the formulas depicted in the referred article.
The source code you will find on my GitHub.
The GWO algorithm mimics the social structure and hunting behavior of gray wolves in the wild nature. The four grey wolf groups alpha, beta, delta, and omega make form the hierarchy of leadership. Another intriguing aspect of gray wolves’ social behavior is their approach to collective hunting. The first step in the gray wolves’ approach is for them to locate their prey and then circle it while the alpha wolf is in charge. It is presumable that the alpha, beta, and delta wolves provide greater information about the likely location of prey in the mathematical model of the hunting strategy of gray wolves.
As a result, the GWO algorithm updates the positions of the wolves using the first three best answers (alpha, beta, and delta).
I recommend watching a Youtube film about how the algorithm “works” in nature.
I used a map with one circular obstacle in the robot path planning test. The GWO algorithm was adapted for robot path planners (in this case for a 2D mobile robot). The GWO algorithm looks for the optimal solution of the defined function (cost function), which gives obstacle — free robot path.
The robot position is expressed by the following equations,
The distance between the mobile robot and the obstacle must be kept to the maximum, however, the time constraint, regarding the shortest path has to be also incorporated (the robot has to achieve the target soonest possible).
The cost function optimized by GWO can be depicted as follows,
where,
where the parameter α1 reflects how fast the robot reaches the target Factor α2 controls the distance between the robot and the obstacle. The last one α3 can be considered a smoothing factor to control the robot path smoothness. drObs and drGoal variables are used to calculate the Euclidian distance between the robot and the obstacles and the distance between the robot and the goal, respectively.
The simplified idea of the algorithm has been depicted in the below figure. The implementation in C++ is straightforward.
When we run the GWO, the wolf positions in the algorithm are nothing other than the robot positions in 2D space. The algorithm tries to optimize these positions (in each iteration the position are moved) in order to find the solution: the cost function has to achieve convex optimization (global minimum of the cost value function).
The other important feature of the GWO is the fact that in each iteration the randomly generated position of the robot (wolf) is approximated (moved) in relation to the best position of the robot (wolf — alpha, beta, and delta).
Each of the three positions of the robot (wolf): alpha, beta, and delta provide the minimum value of the cost function in a certain iteration.
Before I started with the robot path planner I checked the performance of GWO by finding the maximum value of the multiplication of two variables in the range (-5, 5). After running 25 iterations the value of the function equals 25, as expected (you find also this program on my GitHub).
Performance of the algorithm. The robot avoids obstacles.
Plotting requires incorporating the header file which has to be in the same folder as your cpp (a file you can clone from my repository).
Your program can be compiled as follows,
//compile
g++ my_prog.cpp -o my_prog -I/usr/include/python3.8 -lpython3.8//
//run
./my_prog
//folder tree
├── my_prog
├── my_prog.cpp
├── matplotlibcpp.hThank you for reading.
