En optimal stigfinnare för fordon i verklighetsbaserade digitala terrängkartor


av

F. Markus Jönsson


Institutionen för Numerisk Analys och Datalogi,
Kungliga Tekniska Högskolan, Stockholm, (p)1997

Referat (in English)

Detta arbete beskriver en algoritm för att finna den snabbaste stigen för ett fordon att färdas mellan två punkter i en digital terrängkarta, undvikande eventuella hinder på vägen. Det kan även finnas en, eller flera, ’fiender’ i terrängen som bör undvikas när så är möjligt. Mer specifikt består terränkartan av ett 2D höjdraster och ett terrängklassraster. Det finns även vägar i form av vektordata. Fordonets hastighet är en funktion av terräng- och vägtyp. Underlaget får ej heller luta för mycket. Fiender undviks genom att hålla sig utanför deras siktfält. De generalla resulataten i arbetet bör dock vara tillämpbara på allt från stora GIS system till enklare spel för hemdatorer.

Ansatsen som görs i detta arbete är att reducera problemet till grafproblemet ’lägsta kostnadsstig’ med en associerad kostnadsfunktion på grafens kanter. Kända grafalgoritmer kan sedan användas för att lösa grafproblemet exakt. För att vara användbart på vanliga persondatorer behövs en enkel progressiv metod för riktigt stora grafer (grafer med många miljoner noder) som ger approximativa lösningar med rimlig tids och minnesförbrukning.


Fortsättning... (finns bara på engelska)