Design and implementation of a genetic algorithm IP core on an FPGA for path planning of mobile robots

This paper presents a hardware realization of a genetic algorithm (GA) for the path planning problem of mobile robots on a field programmable gate array (FPGA). A customized GA intellectual property (IP) core was designed and implemented on an FPGA. A Xilinx xupv5-lx110t FPGA device was used as the hardware platform. The proposed GA IP core was applied to a Pioneer 3-DX mobile robot to confirm its path planning performance. For localization tasks, a camera mounted on the ceiling of the laboratory was utilized to receive images and allow the robot to determine its own location and the obstacles in the environment. In this way, procedures of path planning were tested in a real laboratory environment. An impressive time speedup was achieved when compared with its software implementation. Experimental results illustrate the effectiveness of the GA IP core hardware.

PDF

___

[1] Willms AR, Yang SX. An efficient dynamic system for real-time robot-path planning. IEEE T Syst Man Cyb 2006; 36: 755-766.
[2] Tuncer A, Yildirim M. Dynamic path planning of mobile robots with improved genetic algorithm. Comput Electr Eng 2012; 38: 1564-1572.
[3] Manikas TW, Ashenayi K, Wainwright RL. Genetic algorithms for autonomous robot navigation. IEEE Instru Meas Mag 2007; 10: 26-31.
[4] Al-Taharwa I, Sheta A, Al-Weshah M. A mobile robot path planning using genetic algorithm in static environment. J Comput Sci 2008; 4: 341-344.
[5] Deliparaschos KM, Doyamis GC, Tzafestas SG. A parameterised genetic algorithm IP core: FPGA design, implementation and performance evaluation. Int J Electron 2008; 95: 1149-1166.
[6] Fernando PR, Katkoori S, Keymeulen D, Zebulum D, Stoica A. Customizable FPGA IP core implementation of a general-purpose genetic algorithm engine. IEEE T Evolut Comput 2010; 14: 133-149.
[7] Mostafa HE, Khadragi AI, Hanafi YY. Hardware implementation of genetic algorithm on FPGA. In: 21st National Radio Science Conference; 1618 March 2004; Egypt. pp. 1-9.
[8] Tuncer A, Yildirim M, Erkan K. A hybrid implementation of genetic algorithm for path planning of mobile robots on FPGA. In: The 27th International Symposium on Computer and Information Sciences; 34 October 2012; Paris, France. pp. 459-465.
[9] Glette K, Torresen J. A flexible on-chip evolution system implemented on a Xilinx Virtex-II Pro device. In: 6th International Conference on Evolvable Systems; 1214 September 2015; Sitges, Spain. pp. 66-75.
[10] Gomez-Pulido JA, Vega-Rodriguez MA, Sanchez-Perez JM, Priem-Mendes S, Carreira V. Accelerating floatingpoint fitness functions in evolutionary algorithms a FPGA-CPU-GPU performance comparison. Genet Program Evol M 2011; 12: 403-427.
[11] Allaire FCJ, Tarbouchi M, Labont´e G, Fusina G. FPGA implementation of genetic algorithm for UAV real-time path planning. J Intell Robot Syst 2009; 54: 495-510.
[12] Kok J, Gonzalez LF, Kelson N. FPGA implementation of an evolutionary algorithm for autonomous unmanned aerial vehicle on-board path planning. IEEE T Evolut Comput 2013; 17: 272-281.
[13] Hachour O. The proposed genetic FPGA implementation for path planning of autonomous mobile robot. International Journal of Circuits, Systems and Signal Processing 2008; 2: 151-167.
[14] Holland JH. Adaptation in Natural and Artificial Systems. Ann Arbor, MI, USA: University of Michigan Press, 1975.
[15] Tuncer A, Yildirim M. Chromosome coding methods in genetic algorithm for path planning of mobile robots. In: The 26th International Symposium on Computer and Information Sciences; 2628 September 2012; London, UK. pp. 377-383.
[16] Gelenbe E, Liu P, Lain´e J. Genetic algorithms for route discovery. IEEE T Syst Man Cy B 2006; 36: 1247-1254.
[17] Lysecky RL, Vahid F. A study of the speedups and competitiveness of FPGA soft processor cores using dynamic hardware/software partitioning. In: Proceedings of the Design, Automation and Test in Europe Conference and Exhibition; 711 March 2005; Munich, Germany. pp. 18-23.
[18] Xilinx Inc. MicroBlaze Processor Reference Guide EDK 11.4, Xilinx, UG081 (v10.3). San Jose, CA, USA: Xilinx, 2009.
[19] Chen P, Chen R, Chang Y, Shieh L, Malki HA. Hardware implementation for a genetic algorithm. IEEE T Instrum Meas 2008; 57: 699-705.
[20] Serra M, Slater T, Muzio JC, Miller DM. The analysis of one-dimensional linear cellular automata and their aliasing properties. IEEE T Comput Aid D 1990; 9: 767-778.
[21] Scott SD, Samal A, Seth S. HGA: A hardware-based genetic algorithm. In: Proceedings of the Third International ACM Symposium on Field-Programmable Gate Arrays; 1995; California, USA. pp. 53-59.
[22] Wolfram S. Statistical mechanics of cellular automata. Rev Mod Phys 1983; 55: 601-644.
[23] Wolfram S. Universality and complexity in cellular automata. Physica D 1984; 10: 1-35.
[24] Bresenham JE. Algorithm for computer control of a digital plotter. IBM Syst J 1965; 4: 25-30.
[25] Sekanina L. Towards evolvable IP cores for FPGAs. In: Proceedings of the 2003 NASA/DoD Conference on Evolvable Hardware; 911 July 2003; Chicago, IL, USA. pp. 145-154.
[26] Tuncer A, Yildirim M, Erkan K. A motion planning system for mobile robots. Adv Electr Comput En 2012; 12: 57-62.