By poruszać się w nieznanym terenie, pojazd autonomiczny, tak jak człowiek, potrzebuje mapy. Mapy wykorzystywane w autonomii są bardziej złożone, niż te wykorzystywane przez ludzi i są nazywane mapami HD (high definition). Najczęściej taka mapa przechowuje kilka poziomów informacji, m. in.:
- siatkę dróg,
- siatkę pasów jezdnych,
- informacje dynamiczne o stanie ruchu,
- informacje o obiektach statycznych jak znaki, słupy, budynki, itp.
- informacje o kształcie terenu.
Dane w mapie HD przechowywanej w pojeździe muszą być na bieżąco aktualizowane. Różne poziomy mapy mogą wymagać różnej częstotliwości aktualizacji danych. W szczególności, zaawansowane systemy autonomii wymagają zapewnienia ciągłej łączności z bazą lub/i innymi pojazdami, tak by była możliwość aktualizacji informacji dynamicznych w mapie.
Kształt terenu zapamiętywany jest w postaci trójwymiarowej chmury punktów. Chmura taka może być zbudowana z wyprzedzeniem przy użyciu pojazdu wyposażonego w precyzyjny lidar, GPS i czujniki inercyjne. Pojazd taki jeździ po mapowanym terenie, rejestrując dane z czujników. Nagrania są wstępnie filtrowane, a następnie chmury punktów z kolejnych klatek nagrania są dopasowywane do siebie, tworząc spójną statyczną chmurę punktów całego terenu. Otrzymana w ten sposób chmura punktów jest ponownie filtrowana, tworząc finalną mapę. Taka mapa jest wykorzystywana do określania pozycji pojazdu na bazie odczytu chmury punktów z lidaru umieszczonego na autonomicznym pojeździe.
Rozwinięciem tej koncepcji są algorytmy z rodziny SLAM (ang. simultaneous localization and mapping). W tym podejściu tworzenie lub aktualizacja chmury punktów mapy następuje na bieżąco na poruszającym się pojeździe. Pojazd startuje posiadając potencjalnie nieaktualną chmurę punktów mapy lub jej całkowity brak. W trakcie ruchu pojazdu napływające dane z czujników są wykorzystywane do określenia pozycji na już zbudowanej części mapy, a następnie są wykorzystywane do aktualizacji chmury punktów mapy. Tak zbudowana mapa może być zniekształcona przez kumulację drobnych błędów z kolejnych dopasowań klatek danych. Dlatego ważnym elementem wielu algorytmów SLAM jest optymalizacja mapy. Popularną metodą optymalizacji jest detekcja pętli, która wykrywa na mapie ponownie odwiedzane miejsca i koryguje geometrię mapy tak, by informacja z przeszłości była spójna z informacją odczytaną w teraźniejszości.