[en] 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.

[es] 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.