Viewshed algorithms for strategic positioning of vehicles

Abstract

An important aspect of simulation and autonomous planning of military operations is to find good and realistic posititions for observation and attack. Essential to this is the ability to identify the set of positions from which a target can be observed and where it can be attacked from. In mathematics, a generalization of this notion is referred to as the viewshed. An algorithm for computing the viewshed is therefore an important part of an autonomous system for finding good positions for observation and attack. A range of algorithms exists for finding the viewshed, from slow exact algorithms to fast approximations. In this thesis we consider how to empirically compare the performance of viewshed algorithms and establish a framework for finding the best algorithm for a specific use case. Leveraging this framework we identify a set of algorithms suitable for integration with a planning algorithm on terrain types typically encountered in military land scenarios. Our testing procedure identifies some weaknesses in the R2 algorithm originally described by Ray et. al., and we propose a few modifications which significantly improve its accuracy on typical terrains with little or no cost in terms of speed. Finally, we propose a generalization of the R2 algorithm with anytime behavior which allows us to compute viewsheds with far greater accuracy than R2, but at the expense of increased runningtimes.

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.