Decision-Making in Robotics using Evolutionary Neural Networks

Roboticists around the world have taken a keen interest in finding bio-inspired solutions to problems. A similar intention inspired the development of genetic algorithms to be employed in the field of artificial intelligence (AI).

A genetic algorithm is a procedure to find, generate, or select a heuristic that may find a good solution inspired by the process of natural selection. Genetic algorithms are a subset of a larger group of algorithms known as Evolutionary Algorithms. They work on the principles of evolution: variation, inheritance, selection, and time. Genetic algorithms provide sufficiently good solutions especially when presented with incomplete information or limited computational capabilities. In general, these algorithms are employed on optimization problems.

One way to implement a genetic algorithm on a robotics system is to use it in an artificial neural network being trained to output control signals to an autonomous vehicle. Let’s use this example to understand how genetic algorithms work in general but first let us define an artificial neural network. The goal of the algorithm is to output such signals that take the fastest route while avoiding obstacles.

Final Result (source)

What are Artificial Neural Networks?

Artificial Neural Networks are a type of computer system which are inspired by the way in which human brain cells analyze and process information. Artificial Neural Networks are used in scenarios where it is difficult to solve the problem by using normal statistical techniques or in decision-making processes where it would be impossible for a human to program all the possible scenarios. They have the feature of self-learning, so as new data is available the performance of a given Neural Network increases.

Working Process of Artificial Neural Networks.

Artificial Neural Networks (ANNs) are made of neurons that are analogous to the neurons in the human brain. A neuron in an ANN is represented by the following equation:-

Where f is the activation function, b is the bias, n is the number of neurons in the previous layer x is the connection from each neuron in the previous layer and w is its corresponding value.

In the human brain, when two adjacent neurons are connected to each other through Dendrites and Axon terminals. There is a small gap in between the connections called synapses. When two adjacent neurons are fired the gap reduces and the bond between neurons gets stronger. This process of the bond between neurons getting stronger is the way in which the human brain learns new things.

Human Neuron (source)

In ANNs, the weights represent the strength of the connection between the neurons. There are different techniques to optimize the values of these weights. Backpropagation is mostly used for this task.

Backpropagation is used for training of Neural Network for supervised learning. In backpropagation, we calculate a gradient of the loss function and then try to reduce it by tweaking the weights starting from the output layer. However, we need to have a proper definition of the correct decision to be taken. Another method to optimize the weights of an ANN is to apply a genetic algorithm. Here we can leverage the properties of reinforcement learning and just promote the decisions which are considered to be good and hopefully the network will generate good enough results through an iterative learning process.

Working process of Genetic Algorithms.

Genetic Algorithms are inspired by the process of natural selection in Darwin’s theory of evolution. It works on the principle of “Survival of the fittest”. In the real world, there is a set population and the animals with suitable qualities live long enough to create offspring and transfer their genes down the line.

Genetic Algorithms mainly consist of 3 things:-

1. Selection- Selection is the process of determining the performance of each individual and selecting it for the next generation. The fitness of each individual is calculated based on a predefined metric and the healthiest individuals are selected.

2. Recombination- Recombination is the process to create the next generation. Fit individuals are crossed to create new individuals. This is done using the sexual evolutionary algorithm, the asexual evolutionary algorithm uses mutation to generate the next generation. The healthiest individual from the previous generation is selected for crossover and generates a population for the next generation.

Crossover (source)

3. Mutation- Mutation is done to maintain genetic diversity. This avoids getting stuck at a local maximum. Few parts of the individuals are randomly mutated based on predefined mutation probability.

Mutation (source)

Evolutionary Neural Network uses Genetic algorithms to optimize its weights and biases.

Flowchart of GA (source)

Implementation

Robot Description- The robot is a car that has 5 distance sensors mounted in front of it.

Robot Description (source)

The output from the sensor is the input to the Neural Network. There are five neurons in the firsts layer and two hidden layers and 2 outputs neurons in the final layer. Car accepts 2 inputs: speed and direction. Each neuron uses a tanh activation function.

tanh (source)

tanh was used because it maps the output from -1 to 1. In this scenario, the negative value represents the opposite direction.

Variants of Genetic Algorithms

There are main types of Genetic Algorithms based on how the next generation of individuals is created-

1. Asexual:- In this type, the recombination step of the algorithm is skipped there is no crossover. Fit individuals from the existing generation are mutated to create the new generation.
2. Sexual:- In this type to generate individuals for the new generation we cross two more of the parent individuals from the current generation. These parent individuals are selected based on their fitness scores.

There is a variant of a genetic algorithm known as the S-Adaptive Genetic algorithm. It updates the value of the probability of mutation and probability of cross over as the behavior approaches the target behavior. The idea is to converge to the best solution possible. Initially assuming the behavior is very different from the target behavior, the rate of mutation and crossover is high but as the behavior approaches the target behavior the rate reduces fine-tune the system.

Different ways of implementing the same task

There are a multitude of ways of doing the same task of decision making for avoiding the obstacle and getting to the desired goal: -

1. Naive Approach- Naive approach is to turn in a different direction if the robot encounters an obstacle. Although this approach is okay for hobby projects, it does not produce any useful result in complex systems where the path optimality is necessary.
2. Classical search algorithms- Classical search algorithms such as A* and Dijkstra’s gives out a collision-free path from a given start point to a given endpoint.
3. MP net- MP net stands for Motion Planning network. MP Net uses 2 networks the first network encodes the workspace and feeds it to the second network which then finds a path avoiding obstacles.

Key Results

In 2006, NASA’s spacecraft, ST5, carried an antenna that was designed by a computer design program operating on genetic algorithms to generate the best radiation pattern. The antenna is known as the evolved antenna. In April 2016, Maurice Conti revealed the use of genetic algorithms to optimize the designs of robotic CAD models. Moreover, CAD design softwares such as SOLIDWORKS and Fusion 360 feature topology optimization of CAD models using genetic algorithms.

In our implementation of the algorithm, the model quickly learnt to drive and avoid obstacles i.e it learnt not to collide with the wall. After about 150 generations, the model started to follow racing lines in any given track. Racing lines are the fastest way around the corner. The figure below shows the best and safest path through the track.

Safest path (source)

Path followed by the model, is shown in the figure below

Fastest path (source)

Genetic algorithms are a part of the machine learning domain but do not qualify under the general categorization of supervised and unsupervised learning. Unlike supervised learning, we do not define every aspect of the targeted behavior in genetic algorithms. Unlike unsupervised learning, we do not specify the effect of various parameters on our end result in genetic algorithms.

Applications and current research trends

Genetic algorithms are used in optimization problems to yield better results over generations. They can be applied to various domains in robotics such as control and path planning. Chen and Gao proposed an S-adaptive genetic algorithm¹ in 2019. The method was applied for the path planning of a soccer robot. It was able to yield an obstacle avoidance behavior and better paths in a shorter time than those taken by the common grid, potential field, and visual graph methods. In 2018, a fuzzy controller² was optimized using a genetic algorithm to control the motion and to track the path of an underwater vehicle. A similar approach was taken by Rath and Parhi⁵ to optimize the navigation of a humanoid robot.

Apart from these, genetic algorithms are also used in finding better solutions to np-hardness problems³ such as the traveling salesman problem⁴ (TSP). Genetic algorithms are not being applied to the problem of image segmentation⁶ due to the development of strong classifiers. Many of these classifiers are based on neural networks. With the employment of genetic algorithms, the neural networks can learn the mapping functions for image classification much faster. This makes image segmentation an area of open research to study the training time and classification accuracy for genetic algorithms based image classifiers.

References

1. Chen, X., Gao, P. Path planning and control of soccer robot based on genetic algorithm. J Ambient Intell Human Comput (2019). https://doi.org/10.1007/s12652-019-01635-1
2. Chen, JiaWang, et al. “Research on fuzzy control of path tracking for underwater vehicle based on genetic algorithm optimization.” Ocean Engineering 156 (2018): 217–223.
3. Mohammed, Mazin Abed, et al. “Solving vehicle routing problem by using improved genetic algorithm for optimal solution.” Journal of computational science 21 (2017): 255–262.
4. Wang, Jiquan, et al. “Multi-offspring genetic algorithm and its application to the traveling salesman problem.” Applied Soft Computing 43 (2016): 415–423.
5. Rath, Asita Kumar, et al. “Path optimization for navigation of a humanoid robot using hybridized fuzzy-genetic algorithm.” International Journal of Intelligent Unmanned Systems (2019).
6. G. Lo Bosco, “A genetic algorithm for image segmentation,” Proceedings 11th International Conference on Image Analysis and Processing, Palermo, 2001, pp. 262–266, doi: 10.1109/ICIAP.2001.957019.

Authors

Toyas Dhake

Umang Rastogi