Reaaliaikaisista hakualgoritmeista: RTA*, LRTA* ja TBA*

Useilla tekoälyn sovellusaloilla pitää ratkaista hakuongelmia, joissa etsitään graafin solmujen muodostamaa jonoa, joka johtaa ratkaisuun. Graafin solmut voivat vastata esimerkiksi kaupunkeja tieverkossa tai lautapelin eri tiloja, kun pelin siirrot ovat graafin kaaria. Koska useiden sovelluksien kuten pelien karttojen koko kasvaa jatkuvasti, tulee hakualgoritmien ratkaista yhä suurempia ongelmia. Kuitenkin monissa sovelluksissa halutaan vakioajassa osaratkaisuja, joita seuraamalla hakuagentti voi siirtyä reaaliaikaisesti kohti maalitilaa. Reaaliaikaiset hakualgoritmit hakevat reittiä maalitilaan askel kerrallaan ja palauttavat vakioajassa jonkin solmun, johon siirrytään. Tästä syystä ne skaalautuvat luontevasti suurille ongelmille, koska niiden suoritusaika askelta kohti ei riipu tehtävän koosta. Usein reaaliaikaisuus voidaan saavuttaa luopumalla ratkaisun optimaalisuudesta ja joskus algoritmin täydellisyydestä. Tässä tutkielmassa tutkitaan kolmea reaaliaikaista hakualgoritmia: RTA*, LRTA* ja TBA*. Käsitellyt algoritmit ovat heuristisia, eli ne tietävät hakuympäristöstä jotain, millä ratkaisun etäisyyttä voidaan arvioida. Lisäksi esitellään ei-reaaliaikainen hakualgoritmi A*, jota pidetään edellä mainittujen hakualgoritmien perustana. Esitellyissä algoritmeissa havaittiin eroja niiden oppimisessa, laajennusten lukumäärässä, hakuagentin käyttäytymisessä sekä vaatimuksissa hakuympäristöltä.