Högskolan i Skövde

Incremental Phi* och Field D* är vägplaneringsalgoritmer som uppfyller två egenskaper. Den första är att deras vägar kan korsa en miljö i vilken vinkel som helst. Den andra är att de i en okänd miljö kan planera om sina vägar snabbt ifall de stöter på ett hinder. Detta kan vara användbart i realtidsstrategispel. Detta arbete testar därför deras förmåga att skapa korta vägar och att planera om vägar snabbt för att ta reda på deras styrkor och svagheter. Utöver detta testas också deras tider i den första sökningen de gör när miljön är outforskad samt i de fall där algoritmerna har visat sig ha svagheter, vilket är i tomma miljöer och i återvändsgränder. Resultatet är att Incremental Phi* hittar kortare vägar och planerar om vägar snabbare. Den får också kortare tider i en tom miljö, medan Field D* får bättre tider i den första sökningen och i återvändsgränder.