Algorithmic and Architectural optimization techniques in particle filtering for FPGA-Based navigation applications

Abstract

Els filtres de partícules (FPs) són una tipologia de tècniques d'estimació bayesiana basades en simulacions Monte Carlo que es troben entre els sistemes d'estimació que ofereixen millors rendiments i major flexibilitat en la resolució de problemes d’estimació no lineals i no gaussians. No obstant això, aquest millor rendiment i major flexibilitat es contraposa amb la major complexitat computacional del sistema, motiu pel que fins ara la seva aplicació a problemes de temps real ha estat limitada. La majoria de les aplicacions en temps real, en particular en el camp de la robòtica mòbil, com ara el seguiment, la localització i mapatge simultani (SLAM) i la navegació, tenen limitacions en el rendiment, l'àrea, el cost, la flexibilitat i el consum d'energia. La implementació software de FPs en plataformes d’execució seqüencial en aquestes aplicacions és sovint prohibitiu per l’elevat cost computacional. Per tant per aproximar els FPs a aplicacions en temps real és necessària l'acceleració de les operacions de còmput utilitzant plataformes hardware. Donat que la major part de les operacions es poden realitzar de forma independent, el pipeline i el processament en paral·lel poden ser explotats de manera efectiva mitjançant l'ús de hardware apropiat, com ara utilitzant Field Programmable Gate Arrays (FPGAs). La flexibilitat que tenen per introduir la paral·lelització fa que puguin ser emprades en aplicacions de temps real. Amb aquest enfocament, aquesta tesis doctoral s’endinsa en el difícil repte d’atacar la complexitat computacional dels filtres de partícules introduint tècniques d’acceleració hardware i implementació sobre FPGAs, amb l’objectiu d’incrementar el seu rendiment en aplicacions de temps real. Per tal d’implementar filtres de partícules d’alt rendiment en hardware,aquesta tesis ataca la identificació dels colls d’ampolla computacionals en FPs i proposa, dissenya i implementa tècniques d’acceleració hardware per a FPs. Emprant tècniques d’acceleració hardware per a filtres de partícules primer es dissenya i implementa una arquitectura HW/SW per a FPs. Després, es dissenya un processador hardware per a FPs en el que es detallen totes les etapes del FP aplicant-lo a un algorisme de mapatge i localització simultània i implementant-lo sobre FPGA. També es dissenya i implementa un co-processador paral·lel per a un escàner làser emprat en FPs emprant un algorisme de Bresenham. Aquesta proposta hardware ha conduit al desenvolupament del primer prototip totalment hardware (sobre FPGA) per a filtres de partícules emprats en SLAM.

Los filtros de partículas (FPs) son una tipología de técnicas de estimación bayesiana basadas en simulaciones Monte Carlo que se encuentran entre los sistemas de estimación que ofrecen mejores rendimientos y mayor flexibilidad en la resolución de problemas de estimación no lineales y no gausianos . Sin embargo, este mejor rendimiento y mayor flexibilidad se contrapone con la mayor complejidad computacional del sistema, por lo que hasta ahora su aplicación a problemas de tiempo real ha sido limitada. La mayoría de las aplicaciones en tiempo real, en particular en el campo de la robótica móvil, aplicaciones tales como el seguimiento, la localización y mapeo simultáneo (SLAM) y la navegación, tienen limitaciones en el rendimiento, el área, el coste, la flexibilidad y el consumo de energía. La implementación software de FPs en plataformas de ejecución secuencial en estas aplicaciones es a menudo prohibitivo por el elevado coste computacional. Por lo tanto para aproximar los FPs a aplicaciones en tiempo real es necesaria la aceleración de las operaciones de cómputo utilizando plataformas hardware. Dado que la mayor parte de las operaciones se pueden realizar de forma independiente, el pipeline y el procesamiento en paralelo pueden ser explotados de manera efectiva mediante el uso de hardware apropiado, como utilizando Field Programmable Gate Arrays (FPGAs). La flexibilidad que tienen para introducir la paralelización hace que puedan ser utilizadas en aplicaciones de tiempo real. Con este enfoque, esta tesis doctoral se adentra en el difícil reto de atacar la complejidad computacional de los filtros de partículas introduciendo técnicas de aceleración hardware e implementación sobre FPGAs, con el objetivo de incrementar su rendimiento en aplicaciones de tiempo real. Para implementar filtros de partículas de alto rendimiento en hardware, esta tesis ataca la identificación de los cuellos de botella computacionales en FPs y propone, diseña e implementa técnicas de aceleración hardware para FPs. Empleando técnicas de aceleración hardware para filtros de partículas primero se diseña e implementa una arquitectura HW/SW para FPs. Después, se diseña un procesador hardware para FPs en el que se detallan todas las etapas del FP aplicándolo a un algoritmo de mapeo y localización simultánea y implementándose en FPGA. También se diseña e implementa un co-procesador paralelo para un escáner láser empleado en FPs empleando un algoritmo de Bresenham. Esta propuesta hardware ha conducido al desarrollo del primer prototipo totalmente hardware (FPGA) para filtros de partículas empleados en SLAM.

Particle filters (PFs) are a class of Bayesian estimation techniques based on Monte Carlo simulations that are among the estimation frameworks that offer superior performance and flexibility on addressing non-linear and non Gaussian estimation problems. However, such superior performance and flexibility of PFs comes at the cost of higher computational complexity that has so far limited their applications in real time problems. Most real time applications, in particular in the field of mobile robotics, such as tracking, simultaneous localization and mapping (SLAM) and navigation, have constraints on performance, area, cost, flexibility and power consumption. Software implementation of the PFs on sequential platforms for such applications is often prohibitive for real time applications. Thus to make PFs more feasible to such real-time applications, the acceleration of PFs computations using hardware circuitry is essential. As most of the operations in PFs can be performed independently, pipelining and parallel processing can be effectively exploited by use of an appropriate hardware platform, like field programmable gate arrays (FPGA), which offer the flexibility to introduce parallelization and lead to a wide range of applications of PFs in real time systems. Thus the focus of this phD thesis is to address the challenge of to deal with the computational complexity of PFs introducing FPGA hardware acceleration for improving their real-time performance and make its use feasible in these applications. For a high throughput hardware realization of the PFs, some of the issues addressed in this thesis include: the identification in the computational bottlenecks of the PFs and the proposal and design of PF hardware acceleration techniques. Based on the PF hardware acceleration techniques, the design and implementation of a PF HW/SW architecture is presented. In addition, a new approach for full parallelization of the PFs is presented which leads to a distributed particle filtering implementation with simplified parallel architecture. Finally, the design of a fully hardware PF processor is provided where the whole particle filtering steps applied to the SLAM problem are proposed for an implementation on FPGA. As part of the PF processor design, important problems for PF in SLAM are also solved. Also, the design and implementation of a parallel laser scanner as a PF co-processor using a Bresenham line drawing algorithm is realized. The proposed hardware architecture has led to the development of the first fully hardware (FPGA) prototype for the PF applied to the SLAM problem.