https://parrotletsuk.typepad.com/

Cuckoo Search Algorithm for Robot Path Planner in C++

The Cuckoo Search metaheuristic algorithm is my next nature-inspired optimization method which I decided to use for robot path planner purposes.

Cuckoos are remarkable birds, not only for the lovely sound they produce but also for the aggressive way in which they reproduce. While certain Certain species of cuckoos, deposit their eggs in other birds' nests. Additionally, they may choose to destroy other birds’ eggs to improve the probability that their own eggs will hatch. See the below picture depicting dark cuckoos egg among the other bird which will hatch all of them.

wikipedia.com

For the purpose of Computer Science, the Xin-She Yang and Suash Deb pioneered a Cuckoo Search algorithm, which can be modeled by following three rules (reflecting the behavior of cuckoos):

1. Each cuckoo lays one egg at a time and dumps it in a randomly chosen nest.
2. The best nests with high-quality eggs will be carried over to the next generations (in our case iteration).
3. The number of available host nests is fixed. The egg laid by a cuckoo is discovered by the host bird with a probability pa ∈ (0, 1). In this case, the host bird can either get rid of the egg or simply abandon the nest and build a completely new nest.

For the purpose of software deployment rule 1 and 2, I called phase A and rule 3 phase B. Both phases have different functions describing the nest position update. The position of the nest has to be considered as the position of the waypoint for the robot obstacle-free path planner.

I used the Cuckoo optimization method to solve the robot path planner problem for the simple 2D robot. There is one obstacle and the robot searches obstacle-free path between the start and the goal. The optimization method discussed here solves the minimization problem for the objective function (cost function) which I used in one of my previous articles.

For the reasonable value choice of algorithm parameters, I used the extremely interesting book: Nature-Inspired Optimization Algorithms.

The source code for this article in C++ can be found on my GitHub.

Cuckoo Search Algorithm

Part A of the CA algorithm is related highly to the generation of random numbers. It is important to mention that scientists revealed that many animals' and insects’ flight patterns exhibit the usual traits of Lévy flights (random walk). Fruit flies use a succession of straight flight pathways with sharp 90-degree turns to explore their surroundings. This results in a pattern of intermittent scale-free search similar to Lévy flying.
For the CA algorithm, the fly direction and behavior are modeled following the Lévy distribution.
Consider my C++ implementation and consider which random distributions are used.

The position updated can be expressed by the following equation,

where X is a position vector of the nest (robot position). Other parameters are taken from the book I refer to. S — is the step in which the bird flies between turns. U is a distribution that the samples are drawn from a Gaussian normal distribution with a zero mean and a variance of σ².

The second phase, phase B relies on rule 3. The update of each component of the vector (here 2D — XY) can happen if the randomly generated value is lower than Pa probability — the host bird discovers the cuckoo egg. If the condition is successful so the update is performed according to the following equation,

Xd1 and Xd2 are randomly chosen nest positions.

The pseudo-code of the following algorithm can be displayed as follows,

Pseudo-code of Cuckoo Search algorithm (by author)

The objective function of the robot path planner

The cost function that the algorithm is trying to optimize (compute minimum) can be defined as follows,

where,

distance firefly — obstacle,

distance firefly — goal,

K1 and K2 are coefficients taken from the article.

The optimal values of all constants depicted in the above formulas are taken from the article I refer to.

Performance of a discussed algorithm for different parameter setups,

Run 1

Run 2

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.h

Thank you for reading.