A*-algoritmin variantit
Nygård, Ville (2020-12-23)
A*-algoritmin variantit
Nygård, Ville
(23.12.2020)
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe202101222415
https://urn.fi/URN:NBN:fi-fe202101222415
Tiivistelmä
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.
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.