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

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