Viewshed algorithms for strategic positioning of vehicles

I simulering og autonom planlegging av militære operasjoner er det viktig å kunne finne gode og realistiske observasjons- og angrepsposisjoner. Essensielt for dette er å kunne identifisere hvor et mål kan observeres fra og hvor det kan angripes fra. En generalisering av slike posisjoner omfattes av begrepet viewshed fra matematikk. Algoritmer for å finne viewshedet er derfor en viktig del av et autonomt system for å finne gode observasjons- og angrepsposisjoner. Det finnes en rekke algoritmer for å finne viewshedet, fra trege men eksakte algoritmer til raske tilnærmingsalgoritmer. I denne oppgaven undersøker vi hvordan man kan empirisk vurdere ytelsen til viewshedalgoritmer, og etablerer et rammeverk for hvordan man bør velge algoritme til en gitt anvendelse. Dette rammeverket anvender vi for å finne et utvalg algoritmer som egner seg til bruk i planlegging på typiske terrengtyper fra militære landscenarioer. Testprosedyren vår avdekker noen svakheter i R2-algoritmen opprinnelig beskrevet av Ray et. al., og vi foreslår noen endringer til algoritmen som gir betydelig høyere nøyaktighet på typiske terreng med liten eller ingen økning i kjøretid. Til slutt foreslår vi en avbrytbar generalisering av R2-algoritmen som gjør det mulig beregne viewshed med langt høyere nøyaktighet enn R2, i bytte med økt kjøretid.