FASTmap: A Multi-Layer Sliding Gridmap for Arbitrary Types

Abstract

This report presents the Fixed Area Sliding Template map (FASTmap), a versatile and efficient C++ mapping framework for storing arbitrary and heterogeneous data types in a sliding grid map. The framework was first developed to map the surroundings of autonomous vehicles as these are often equipped with a diverse suite of sensors gathering heterogeneous measurements from the local environment. Gathering this information in a common data structure can provide an autonomy system with a situational awareness of the local environment. This further enables the autonomy system to adapt its behavior to the terrain or evaluate autonomous task and sensor performance. After its initial conception, FASTmap has been generalized into a framework supporting various mapping applications, but autonomous vehicles is still considered the main application. A large part of the core functionality is therefore dedicated to moving the map as efficiently as possible without compromising the flexibility to store general types. As such the map is designed to be frequently moved by using internal circular buffers to achieve real time repositioning of data for maps of appropriate sizes and resolutions. The main focus of the report is to give an introduction to FASTmap suited for new users. To this end the report contains the necessary theory, code snippets and examples to start developing a mapping application. Relevant navigation theory is presented in detail as this subject is tightly coupled with mapping. Especially the interchangeability of grid maps and tangent reference frames is stressed as an important relation. A complete list of the current application programming interface functions, with elaborating comments, is also included as a reference for mapping application developers. In addition to the user-oriented introduction to the framework, more advanced topics like performance benchmarking and maximum error calculations are discussed in the later chapters. First FASTmap is compared to another similar mapping framework called Gridmap, and it is concluded that FASTmap is more versatile because the choice of data types and memory layout can be specified by the user. Then runtimes for common and frequently used functionality for both maps are compared and examples indicate similar performance for similar map sizes. The results are however not conclusive because of insufficient randomization of the experimental setup, and this is suggested as a topic for a dedicated work. Finally a function for the maximum position error introduced by map movement on the Earth ellipsoid is derived. This error is concluded to be neglectable compared to the error introduced by the grid resolution in most practical cases.

Denne rapporten presenterer Fixed Area Sliding Template map (FASTmap), et fleksibelt og effektivt C++-rammeverk for lagring av arbitrære og heterogene datatyper i et bevegelig rutenett. Rammeverket ble først utviklet for å kartlegge omgivelsene til autonome fartøy, siden disse ofte er utstyrt med et variert utvalg sensorer som innhenter heterogene målinger fra det lokale miljøet. Samling av denne informasjonen i en felles datastruktur kan gi et autonomisystem en forståelse av situasjonen og det lokale miljøet. Autonomisystemet kan videre bruke denne forståelsen til å tilpasse oppførselen sin til terrenget eller evaluere autonom oppgave- og sensorytelse. Den originale versjonen av FASTmap har senere blitt generalisert til et generelt rammeverk som støtter mange forskjellige kartapplikasjoner, men autonome fartøyer regnes fremdeles som hovedanvendelsen. En stor del av kjernefunksjonaliteten er derfor dedikert til å flyttet kartet så effektivt som mulig uten å miste fleksibiliteten til å lagre generelle typer. Kartet er derfor designet for å flyttes ofte ved å bruke interne ringbuffere til å reposisjonere data i sanntid for kart av realistiske størrelser og oppløsninger. Hovedfokuset i denne rapporten er å gi en introduksjon til FASTmap tilpasset nye brukere. Rapporten inneholder derfor nødvendig teori, kodeutsnitt og eksempler for å starte utvikling av en kartleggingsapplikasjon. Relevant navigasjonsteori er presentert i detalj siden dette fagfeltet er tett integrert med kartlegging. Det er lagt spesiell vekt på likheten mellom rutenett og tangente referanserammer. En komplett liste over de nåværende programmeringsgrensesnittfunksjonene, med forklaringer, er også inkludert som en referanse for kartapplikasjonsutviklere. I tillegg til den mer brukerorienterte introduksjonen til rammeverket, blir mer avanserte temaer som ytelsesevaluering og utregning av maksimal feil diskutert i de senere kapitlene. Først blir FASTmap sammenlignet med et annet lignende kartrammeverk kalt Gridmap, og det blir konkludert at FASTmap er mer fleksibelt siden datatyper og struktureringen av minne spesifiseres av brukeren. Deretter blir kjøretidene til felles og hyppig brukt funksjonalitet for begge kart sammenlignet, og kjøretidseksempler indikerer sammenlignbar ytelse for lignende kartstørrelser. Resultatene er derimot ikke nok til å konkludere siden testene ikke ble utført i et tilstrekkelig randomisert miljø, og det anbefales å jobbe videre med dette i et dedikert arbeid. Til slutt blir det utledet en funksjon for den maksimale posisjonsfeilen introdusert ved flytting av kartet på jordellipsoiden. Denne feilen blir konstatert neglisjerbar i forhold til feilen introdusert av rutenettsoppløsningen for de fleste praktiske formål.