Matrix-Binary Codes based Genetic Algorithm for path planning of mobile robot

Abstract

The paper presents the new variant of genetic algorithm using the binary codes through matrix for mobile robot navigation (MRN) in static and dynamic environment. The path planning strategy is established using the trace theory as the optimum controller, Sylvester Law of Inertia (SLI) and matrix simulation. The Matrix-Binary Codes based Genetic Algorithm (MGA) transforms the environment from chaos to array. Importantly, the paper proves the SLI by the real and experimental results for the statement “any robotics randomized environment transforms into the array.” Hence the model is presented as pre-optimized robotics by SLI and post-optimized robotics by trace. The simulation result is presented by using MATLAB software and the result obtained by proposed controller is optimal with respect to path and time when compared to other intelligent navigational controller.

Introduction

The artificial intelligence is the study of transformation from the natural decision to manual decision. Now, engineering is influenced by optimization and its frontiers. The optimization based on the nature-based metaheuristic technique is a highly researched topic of today. The paper presents the application of nature inspired Genetic Algorithm (GA) along with Matrix-Binary Codes representation for solving the navigational problem of autonomous robot system especially for dynamic goal and dynamic obstacle problem. It is more efficient and robust than random search algorithm as it does not require extra information about the given problem. This key feature of MGA helps to get solution easily where all other optimization tools cannot handle due to deficiency of continuity and linearity.

Charles Darwin's “Theory of Evolution” becomes a potential tool to establish an intelligent searching algorithm like GA. The selection, crossover, and mutation are the three important pillars of the GA. Selection refers to the regeneration, reproduction and copying the genes. Each individual is selected according to their fitness function and then it is used for generating the new population. The individual having low fitness function eliminated automatically in the process of selection. In crossover process, matching to the pool is the primary objective. Match pool is defined as the relation of the selected best-fit individuals for converting them into well-defined pairs. In the process of mutation, the substitution of the genes with the opposite genes performs to maintain the genetic diversity from one generation of population to the next. It is an evolutionary algorithm developed initially by Bremermann [1] in 1958, but in 1975 Holland [2] gave its actual identity by using it for the first time in the field of computer science. It is the evolutionary computational approach used for the optimization of a selected function for maximization and minimization operation. It follows the biotic process of reproduction and natural selection mechanism to find out the fittest solution. The ability to get global optima and high parallelism make it efficient over the other optimization technique. In 1975, Holland gave the first introduction to GA for optimization problem based on Darwin's theory of survival of fittest. After that, it has been widely adopted in the field of mobile robotics. Shibata et al. [3] have proposed the GA based successful motion planning approach for the static environment in the presence of a polygonal obstacle. Shing et al. [4] demonstrated the mobile robot for real-time path planning in planner terrain by adopting GA-based search strategy. Optimal path length, path smoothness, and obstacle avoidance are the goals of effective path planning strategy proven by the Xia et al. [5] by using GA in an unknown environment. Kang et al. [6] presented the solution to dead end problem of navigation of robot. They modified GA to keep the robot safe from the stuck problem in the complex-crowded environment. Similarly, path planning strategy in presence of moving obstacle is presented by the Shi et al. [7] for unknown environment.

The acceptability of GA has been increasing day by day, and it is also used with many other approaches to get hybrid approach for path planning. Pratihar et al. [8], Hui et al. [9] and Wang et al. [10] have developed the fuzzy-genetic, genetic-neural-fuzzy and genetic-PSO hybrid navigational approach respectively for mobile robot path planning. The successive application of GA for the combinatorial optimization problem is provided by Kala [11]. He developed the multi-robot path planning over local search in limited computational infrastructure. Similarly, multiple goals optimization problems by GA are solved by Liu et al. [12]. Kuyucu et al. [13] improved GA for MRN over large search space to achieve the multi-objective task by using the combination of various mechanisms like genetic transposition inspired seeding, a strongly-typed crossover, and multi-objective optimization. Yang et al. [14] showed the navigation of multiple mobile robots in the dynamic environment. Many researchers made some modification in conventional GA due to its slow convergence rate and lack of cooperation between the population and local optimum. Hong et al. [15] presented the improved version of GA for global path planning of mobile robot. They used the co-evaluation mechanism for cooperation among the population of multiple mobile robots which results in avoidance of collision and gets optimal path during navigation. Carlos et al. [16] demonstrated the new form of GA for traveling salesman problem by considering dynamic target with respect to time. They achieved the goal by using simple prediction method and found the near optimal solution. Karami et al. [17] developed the adaptive genetic algorithm to present effective motion planning in 2D environment. In this work, they replaced the conventional selection operator by the adaptive one which continuously checks the fitness of the individual one and prevents the process from the premature convergence. It results in maintaining the diversity of the population in the solution and gives the quality of the solution.

The proposed work is structured by the genetic algorithm over matrix trace representation is presented in Section 2. Section 3 and Section 4 describes the experimental and simulation analysis in detail respectively. In Section 5, the comparison between experimental and simulation results is shown whereas Section 6 describes the performance of MGA versus the other intelligent controller. Finally, we discuss the conclusion and future scope in Section 7.