A*-algoritmin variantit

Abstract

Yksittäistä agenttia käsitteleviä paras ensin -hakualgoritmeja on käytetty vuosikymmenien ajan ratkaisuina hyvin monentyyppisiin ja monia aloja koskettaviin ongelmiin. Yksi tärkeimmistä on jo vuonna 1968 esitelty A*-algoritmi (lausutaan "A tähti").

Vaikka A* on hyvin laajalti käytetty, tietyissä tilanteissa se on osoittautunut riittämättömäksi. Tämän vuoksi A*:een on esitelty suuri määrä laajennoksia vuosien saatossa. A*:n laajennoksia on jo vuosien ajan kategorisoitu sen mukaan mitä A*:n ongelmia tai puutteita kyseinen laajennos pyrkii korjaamaan. Vaikka kategorioita on löydettävissä kirjallisuudesta lukuisia,tässä tutkielmassa keskitytään neljään kategoriaan. Näitä ovat inkrementaaliset, anytime, reaaliaikaiset sekä any-angle-algoritmit.

Inkrementaaliset algoritmit käyttävät peräkkäisiä keskenään hyvin samankaltaisia hakuja hyväksi seuraavissa hauissa. Anytime-algoritmit kykenevät antamaan toteuttamiskelpoisen arvion reitistä milloin tahansa (paitsi ensimmäisen laskennan aikana). Algoritmin oletetaan kykenevän myös parantamaan reittiä mitä enemmän laskentaan annetaan aikaa. Reaaliaika-algoritmien yhteinen piirre on, että ne kykenevät toimimaan hyvin tarkkojen aikarajojen puitteissa. Any-angle-algoritmit eivät rajoita liikkumista solmujen välillä lainkaan.

Tässä tutkielmassa esitellään ensin yksi algoritmi jokaisesta kategoriasta, D* Lite, ARA*, LSS-LRTA* sekä Field D*. Nämä algoritmit toteutetaan Python-ohjelmointikielellä ja niiden suorituskykyä testataan tuntemattomassa ympäristössä. Tämän jälkeen niiden suorituskykyä testiympäristössä arvioidaan.