Dinaminiai kelio paieškos algoritmai apjungia euristinės ir plečiamos (angl. incremental) paieškos metodus, sprendžiant eiles panašių paieškos uždavinių tiek žinant visą informaciją apie aplinką, tiek neturint jokios informacijos. Yra trys plečiamą paiešką naudojančių algoritmų klasės. Šiame darbe pateikiama trumpa dinaminių kelio paieškos algoritmų, naudojančių plečiamos paieškos metodus analizė. Pagrindinis darbo tikslas – visų trijų plečiamos paieškos klasių algoritmų, kuriuos naudojant gaunamas optimalus kelio paieškos sprendinys aplinkose, kur perėjimų tarp viršūnių svoriai gali didėti ir mažėti, palyginimas. Algoritmai lyginami trijose skirtingose situacijose: stacionarioje, judėjimo link tikslo (angl. goal – directed) bei judančio taikinio (angl. moving – target). Tyrimo rezultatai parodė, jog A* ir FSA* nepasiekiamų viršūnių kiekiui esant ~16000 yra ~23,6% našesni už GAA* ir trečios plečiamos klasės algoritmus, o pasiekiamumą keičiančių viršūnių kiekiui esant ~8000 – 42,3%. Nepasiekiamų viršūnių kiekiui kintant nuo 1000 iki 16000 trečios plečiamos klasės algoritmai yra vidutiniškai ~58,7% našesni už GAA* ir ~54% našesni už A* ir FSA*. Pasiekiamumą keičiančių viršūnių kiekiui kintant nuo 500 iki 8000 trečios plečiamos klasės algoritmai yra vidutiniškai ~69,3% našesni už GAA* ir ~47,8% našesni už A* ir FSA*. / Dynamic path finding algorithms combine heuristic and incremental search methods to solve a series of similar search tasks in both known and unknown environments. There are three classes of incremental search algorithms. In this document we provide a brief summary of dynamic path finding algorithms, that uses incremental search methods, but its main focus is on comparing main algorithms of all three incremental classes, that are guaranteed to give optimal solution in environment where action costs can increase and decrease over time, and showing their strong and weak sides. The algorithms are compared in three different situations: stationary, goal – directed and moving – target. At the end of the document conclusions are given based on performed work. In this paper, research showed that A* and FSA* are ~23,6% more efficient than GAA* and third incremental class algorithms when the amount of untraversable cells is ~16000 and ~42,3% more efficient when the amount of traversability changing cells is ~8000. When the amount of untraversable cells is between 1000 and 16000, the third incremental class algorithms are ~58,7% more efficient than GAA* and ~54% – than A* and FSA*. When the amount of traversability changing cells is between 500 and 8000, the third incremental class algorithms are ~69,3% more efficient than GAA* and ~47,8% – than A* and FSA*.
| Identifer | oai:union.ndltd.org:LABT_ETD/oai:elaba.lt:LT-eLABa-0001:E.02~2013~D_20130826_105814-41433 |
| Date | 26 August 2013 |
| Creators | Chabibulin, Linar |
| Contributors | Maciulevičius, Stasys, Barauskas, Rimantas, Plėštys, Rimantas, Jankauskas, Kęstutis, Blažauskas, Tomas, Dzemyda, Gintautas, Damaševičius, Robertas, Misevičius, Alfonsas, Ostreika, Armantas, Palubeckis, Gintaras, Kaunas University of Technology |
| Publisher | Lithuanian Academic Libraries Network (LABT), Kaunas University of Technology |
| Source Sets | Lithuanian ETD submission system |
| Language | Lithuanian |
| Detected Language | English |
| Type | Master thesis |
| Format | application/pdf |
| Source | http://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2013~D_20130826_105814-41433 |
| Rights | Unrestricted |
Page generated in 0.0025 seconds