Development of a neighbourhood graph for trafficability analysis

Framgångsrik framkomlighetsanalys kräver användning av många datakällor, t.ex. elevation och markanvändningsdata, i hög upplösning. Detta kräver, i sin tur, stor lagringskapacitet och kan leda till olämpligt långa exekveringstider för att finna bra färdvägar. För att tillåta effektiv representation och sökning i ett aktuellt område av intresse skapas därför en graf där de bästa vägarna mellan två godtyckliga positioner i området kan identifieras. Terrängobjekt, identifierade från laser-radar data, och markanvändningsdata fusioneras för att skapa en sammansatt karta av det aktuella området. För att skapa grafen måste kartan partitioneras i mindre områden som är homogena ur framkomlighetssynvikel. Dessa mindre områden representeras av noder och vägar mellan områden representeras av bågar i grafen. Olika metoder för att partitionera kartan beskrivs och analyseras. Dijkstra´s algoritm kombineras med A*-algoritmen för att hitta de bästa vägarna mellan två positioner i det aktuella området.