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

摘要

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.