FPGA Implementation of Genetic Algorithm for UAV Real-Time Path Planning

@article{citeulike:2988282, abstract = {Abstract\ \ The main objective of an Unmanned-Aerial-Vehicle (UAV) is to provide an operator with services from its payload. Currently, to get these UAV services, one extra human operator is required to navigate the UAV. Many techniques have been investigated to increase UAV navigation autonomy at the Path Planning level. The most challenging aspect of this task is the re-planning requirement, which comes from the fact that UAVs are called upon to fly in unknown environments. One technique that out performs the others in path planning is the Genetic Algorithm (GA) method because of its capacity to explore the solution space while preserving the best solutions already found. However, because the GA tends to be slow due to its iterative process that involves many candidate solutions, the approach has not been actively pursued for real time systems. This paper presents the research that we have done to improve the GA computation time in order to obtain a path planning generator that can recompile a path in real-time, as unforeseen events are met by the UAV. The paper details how we achieved parallelism with a Field Programmable Gate Array (FPGA) implementation of the GA. Our FPGA implementation not only results in an excellent autonomous path planner, but it also provides the design foundations of a hardware chip that could be added to an UAV platform.}, author = {Allaire, Fran\c{c}ois and Tarbouchi, Mohamed and Labont\'{e}, Gilles and Fusina, Giovanni }, citeulike-article-id = {2988282}, doi = {http://dx.doi.org/10.1007/s10846-008-9276-8}, journal = {Journal of Intelligent and Robotic Systems}, keywords = {evolutionary-computation, genetic-algorithm, hardware, metaheuristic, path, planning, robot}, posted-at = {2008-07-11 14:32:42}, priority = {2}, title = {FPGA Implementation of Genetic Algorithm for UAV Real-Time Path Planning}, url = {http://dx.doi.org/10.1007/s10846-008-9276-8} }

TY - JOUR ID - citeulike:2988282 L3 - citeulike-article-id:2988282 N2 - Abstract  The main objective of an Unmanned-Aerial-Vehicle (UAV) is to provide an operator with services from its payload. Currently, to get these UAV services, one extra human operator is required to navigate the UAV. Many techniques have been investigated to increase UAV navigation autonomy at the Path Planning level. The most challenging aspect of this task is the re-planning requirement, which comes from the fact that UAVs are called upon to fly in unknown environments. One technique that out performs the others in path planning is the Genetic Algorithm (GA) method because of its capacity to explore the solution space while preserving the best solutions already found. However, because the GA tends to be slow due to its iterative process that involves many candidate solutions, the approach has not been actively pursued for real time systems. This paper presents the research that we have done to improve the GA computation time in order to obtain a path planning generator that can recompile a path in real-time, as unforeseen events are met by the UAV. The paper details how we achieved parallelism with a Field Programmable Gate Array (FPGA) implementation of the GA. Our FPGA implementation not only results in an excellent autonomous path planner, but it also provides the design foundations of a hardware chip that could be added to an UAV platform. JF - Journal of Intelligent and Robotic Systems TI - FPGA Implementation of Genetic Algorithm for UAV Real-Time Path Planning KW - evolutionary-computation KW - genetic-algorithm KW - hardware KW - metaheuristic KW - path KW - planning KW - robot AU - Allaire, François AU - Tarbouchi, Mohamed AU - Labonté, Gilles AU - Fusina, Giovanni UR - http://dx.doi.org/10.1007/s10846-008-9276-8 ER -