Mobil eszközön történő útvonalmeghatározás ingyenes földrajzi adatok felhasználásával Összefoglaló. A mobil eszközökön történő útvonalmeghatározás jelenleg korlátozottan valósítható meg, köszönhetően a limitált erőforrásoknak (memória, processzor teljesítmény). Másrészt, a mai napig kizárólag a gazdaságilag erős országoknak volt lehetőségük megoldást keresni erre a problémára a földrajzi adatok feldolgozásának magas ára miatt. A cikkben szereplő megoldás a hierarchikus útvonal-keresés és a kétirányú A* algoritmus kombinációja. Az osztrák utcatérképekkel végzett tesztek alatt 10-szer gyorsabb eredményt produkált, mint a Dijkstra algoritmus. Az alapvető adatszerkezet a földrajzi adatok mobil eszközön történő tárolására egy négyágú fa (quad-tree). A felhasznált földrajzi adatok az OpenStreetMap (OSM) - 2004-ben indult - projektből származnak, amely ingyenesen felhasználható geográfiai adatokat nyújt.
kulcsszavak: Útvonal-kereső keretrendszer, Gyorsító eljárások, Mobil rendszerek
1. Bevezető Az okostelefonok eladása a 2010-es évre rendkívül megnőtt. Az új generációban már 2 magos processzor, Bluetooth, GPS és mobil operációs rendszer (Android, IOS, W7 Mobile) található. Ezen konfigurációk már egyaránt alkalmasak „on-board”, illetve „offboard” útvonal-meghatározásra. Az „on-board” módszer előnye, hogy az összes térkép a telefonon kap helyet. A program ebben az esetben nem jár egyéb költséggel, ellentétben a külföldi használattal járó magas roaming díjjal, ami az „off-board” megoldás hátulütője. Az „on-board” hátránya, hogy drágák a beépítésre kerülő térképek. Az OpenStreetMap (OSM), a földrajzi adatok fő szolgáltatója megoldja a fent említett problémát. Az OSM projekt 2004-ben indult azzal a céllal, hogy összegyűjtse az ingyenes földrajzi adatokat és felépítsen azokból egy világtérképet. Azonban ezek a nyers adatok közvetlenül nem használhatók fel útvonal-keresésre, ráadásul a mobil eszközöknek túl nagyméretűek is. Ebben a tanulmányban egy hatékony megoldást írnak le a mobil eszközön történő útvonal-keresés problémájára, amely a hierarchikus útvonal-meghatározás és a kétirányú A* algoritmus kombinációja. A hierarchikus útvonal-keresés egy megközelítése
a legrövidebb utak meghatározásának egy hierarchikus rendszerben, például a négyágú fa (quad-tree) adatszerkezetet használva alap adatstruktúrának. A kétirányú A* algoritmus két ellentétes irányú A* algoritmus egyidejű futtatásával határozza meg a legrövidebb utat. Az alkalmazás, amely ezt a módszert implementálta az osztrák utcatérképeken végzett tesztek alkalmával 10-szer gyorsabb eredményt produkált, mint az általános Dijkstra implementáció. (A térkép adatokat az OSM-ből véve.) Az OpenStreetMap-ből származó adatok használata előtt szükség van egy előfeldolgozó folyamatra, melynek részletes ismertetője a 2. részben olvasható. A folyamat lényege a nyers információból olyan adatszerkezet létrehozása, amely alkalmas a korlátozott erőforrással rendelkező mobil eszközökön végzett útvonal-keresésre. A 3. bekezdésben bemutatják a hierarchikus útvonal-meghatározás és a kétirányú A* algoritmus működési feltételeit és ismertetik a komplett megoldás alapötletét, amely a gyors kétirányú útvonal számítás hierarchikus útvonal-kereséssel történő gyorsítása. A 4. fejezet az algoritmus részletes leírása. Az 5. részben szemléltetik a különböző alkalmazások mobil és asztali eszközön végzett tesztjeinek eredményét. Felhasználták az eljárást néhány hosszú útvonal kiszámítására és feljegyezték a kapott eredményeket.
2. Az OSM adatok előfeldolgozása Az OpenStreetMap városi adatai mostanra meglehetősen pontosak lettek. A vidéki földrajzi adatok jelenleg hiányosak, de e tanulmány esetében ez jelentéktelen probléma. Az OSM adatok tartalmaznak csomópontokat, utakat, kapcsolatokat és tulajdonságokat.
(Fig. 1.a ábra) Ezen adatok túl gazdagok és nehezen használhatók útvonal-kereséshez. Az előfeldolgozó célja egy gráf struktúra létrehozása.
(Fig.1.a ábrán látható adatokból a Fig. 1.b ábrán látható struktúra létrehozása)
Az előfeldolgozás után kapott irányított gráf mindössze csúcsokból és súlyozott élekből áll. A csúcsok az útkereszteződéseket és a végpontokat, az élek pedig az ezek között lévő kapcsolatokat jelentik. A generálás a következő lépésekből áll: - Utcák feldolgozása - Az OSM adatokban az élek út címkékkel vannak jelölve. - A kereszteződések azonosítása - Minden csúcs, amit legalább 2-szer érint út, kereszteződés. - A kereszteződések közötti távolságok kiszámítása - Két kereszteződés távolságán a köztük fekvő összes csúcs távolságainak összegét értjük. - Az élek és csúcsok számának csökkentése - Egy csúcs, melynek csak 2 éle van, törölhető. Az élek attribútumait össze kell vonni. A gráf most már felhasználható útkeresésre, de még mindig túl nagyméretű egy okostelefon memóriájának, ezért fel kell darabolni. A szerzők megoldása a gráf szétdarabolására a négyágú fa adatszerkezet felhasználásával a Fig. 2.a ábrán látható.
A gráf első rétege kizárólag az autópályákat tartalmazza. A második réteg négy részre van osztva és megtalálhatóak rajta a főutak is. A harmadik rétegen az összes elérhető út szerepel. A Fig.2.b ábrán látható, hogy az alsó rétegen vannak kereszthivatkozások a felsőbb réteghez, ezáltal minden réteg ismeri a szülőjét, illetve a gyerekeit. Ez az információ nagyon fontos az útvonalak keresésénél, hiszen nem keletkezhet szigorúan éles határ a térkép szektorai között.
3. Az útvonalkereső algoritmus és a gyorsítási technikák Amikor a nyaralási útvonalat tervezik, a sofőrök általában nem a legrövidebb utat keresik, hanem szívesen mennek autópályákon vagy ismert és jó csatlakozással rendelkező utakon. A gyorsító technika – vagyis a hierarchikus útkeresés – felhasználja ezt a megfigyelést alkalmazva az alábbi megközelítést:
-
Megnézi a legközelebbi autópályát Végigmegy az autópályákon úgy, hogy a célhoz a lehető legközelebb érjen Elhagyja az autópályát és megkeresi a célhoz vezető utat az autópálya kijáratától
Ez a szemléletmód látszólag nem a legrövidebb vagy leggyorsabb útvonalat határozza meg, helyette egy jó közelítést számol. Mivel az autópályákat részesíti előnyben, az algoritmus kihagyja a rövidítési lehetőségeket, például keresztül a városon. Másrészt, megkönnyíti a sofőr dolgát elkerülve a szűk belvárosi utcákat. Ezen módszer előfeltétele az úthálózat helyes felépítése és a gráf következetes, teljes címkézése. (például hol van autópálya, főút, stb.) 2002-ben Jagadeesh kifejlesztett egy megközelítést erre a gyorsítási technikára, amelyet „hierarchikus útkeresés”-nek neveznek. Ők a szingapúri földrajzi adatokat alakították kétrétegű hierarchikus struktúrává a legrövidebb utak kereséséhez. Az első réteg csak az autópályákat, míg a második réteg minden utat tartalmazott. Az algoritmus első lépésben kiszámolta a belépési pontok távolságát Dijkstra vagy A* segítségével. Ezen pontok kapcsolatban voltak a fölöttük lévő réteggel. A második lépésben az algoritmus kiszámolta a távolságot a pontok között az első rétegen. A hierarchikus útkeresés meghatározza az utat a kezdő- és célcsúcs közötti kétirányú kereséssel. 2005-ben Goldberg és Harrelson kifejlesztette a kétirányú A* algoritmus egy olyan verzióját, amely ezt a szemléletet követi. Ez a megoldás elindít a kezdőcsúcsból a végcsúcsba, illetve a végcsúcsból a kezdőcsúcsba haladó egyidejű keresést, mely egészen addig fut, amíg közös (aktív) csúcsot nem talál. A legrövidebb út hossza a két csúcs között (ha startcsúcs = s, célcsúcs = t) megadható az alábbi formulával, ahol gv(u) az út költsége az előrehaladó keresésnél, gr(u) pedig az út költsége a visszafelé haladó keresésnél: = gv(u) + gr(u) A számítás addig folyik, amíg a következő feltétel beteljesül: g(u) + h(u) A második egyenlet összehasonlítja az elért legrövidebb utat az aktív pont útköltségének g(u) és a h(u) becsült költség összegével. A legrövidebb utat megkapjuk, ha ez az összeg nagyobb vagy egyenlő, mint a legrövidebb út hossza.
4. Kétirányú hierarchikus útvonal-meghatározás A szerzők a hosszú útvonalak kiszámítására egyesítették a hierarchikus útvonal-keresést és a kétirányú A* algoritmust egy mobil eszközökre készített keretrendszerben. Az utak fontossági sorrendje a következő: mellékút, főút, autóút, autópálya. Első lépésként az algoritmus minden utat figyelembe vesz a pont kis sugarú környezetében, azon kívül azonban nem foglalkozik a mellékutakkal.
Távolabb a ponttól figyelmen kívül hagy minden főutat, aztán az autópályákat, és így tovább. Ez a folyamat látható a Fig. 3. ábrán.
Az Algorithm 1. ábrán látható a megoldás algoritmusa, amely prioritásos sort használ. Első lépésként inicializálja a Qv „ElőreSor”-t, a Qr „VisszaSor”-t, a kezdő- és végpontot és a kereszteződést, továbbá hozzáadja a kezdő- és végpontot a sorokhoz. A fő lépésben az algoritmus kereső ciklusa addig fut, amíg megoldást nem talál, vagy az egyik sor ki nem ürül. A ciklusban az algoritmus úgy dolgozza fel a minimális költségű u csúcsot, hogy kiszámolja az útköltség g(u) és a becsült költség h(u) összegét. A becsült költség a létvonalban mért távolságot jelenti a start- és célállomás között. A következő lépésben a Relax Metódus (Algorithm 2 ábra) következik. A BiStar.RELAX metódus ellenőrzi, vajon tudunk-e javítani a legrövidebb úton v (a cél) felé az eddig megtalált úthoz képest az u csúcson keresztül, és ha igen, módosítja a g[v] tartalmát
ezzel az új útköltséggel.
Az Algorithm 2. ábrán látható, hogy a BiStar.RELAX metódus előtt meghívásra kerül a CheckNode függvény. Ez a függvény valósítja meg a hierarchikus útkeresést. A következő ellenőrzések egyikét végzi el: A lefedett távolság ellenőrzése (DBi*). Ez az eljárás ellenőrzi a távolságot, ahogy a Figure 3. ábrán látható. Ha az út költsége meghalad egy értéket, az algoritmus csak alapvető utakat szúr be. gDist(typ(u,v)) > d[u] + g (u,v). Út típusának ellenőrzése (RTBi*). A függvény igaz értékkel tér vissza, ha az új csúcs típusa nagyobb vagy egyenlő. typ(u) >= typ(u,v) Kereszthivatkozás ellenőrzése. A keresés magasabb rétegre ugrik, ha elérhető kereszthivatkozás. u == crosslink Miután hozzáfűztük az új csúcsot a sorhoz, az Algorithm 1. megismétli ugyanazt a sorozatot visszafelé kereséssel. A következő lépésben a SETCROSSPOINT metódust hívjuk meg, ha az egyik aktív csúcsot már meglátogattuk mindkét irányból. Az utolsó metódus a SHORTESTPATHCROSS visszatér a legrövidebb úttal, amennyiben a feltételek teljesültek.
5. Eredmények Tesztelés céljából először asztali rendszerre készítették el a megoldást. Ebben a lépésben több különböző algoritmus és gyorsítási technika került tesztelésre és elemzésre. A Figure 4a ábra mutatja 4 eltérő út kiszámításának eredményét. A Figure 4b grafikon szemlélteti a számítási eredményeket. A tesztelt algoritmusok a következők: Dijkstra, A*, Kétirányú A*, Távolság Bi*, Út Típus Bi*, a Távolság és Út Típus Bi* kombinációja. Az ábra a hierarchikus útkeresés felgyorsítását mutatja. Az asztali gépen végzett tesztekből látszik, hogy a gyorsítási technika 10-szeresére növelte a keresés hatékonyságát az A* algoritmushoz képest, ráadásul az érintett mellékutak számát 20-szorosára csökkentette. Az asztali teszteket követően egy harmadik generációs Nokia C5 okostelefonon tesztelték az algoritmusokat. A Figure 5a ábrán látható a teszt eredménye.
A mobil eszközön történő tesztelés során a gráf kizárólag autópályákat és főutakat tartalmazott a korlátozottan rendelkezésre álló memória miatt. Az eredmények bizonyították, hogy hosszú útvonalak meghatározására a kétirányú hierarchikus algoritmus a legjobb választás.
6. Következtetés A hierarchikus útvonalkeresés és a kétirányú A* algoritmus kombinációjából álló mobil eszközökre készített keretrendszer egy jó megközelítése a hosszú utak kiszámolásának. Az adatok előfeldolgozása és átalakítása után a földrajzi adatok a megfelelő méretűre mennek össze. Az alapvető adatszerkezet, a négyágú fa, lehetővé teszi az útkereső algoritmusnak a rétegek közötti váltást, ezáltal a keresés nem korlátozódik szigorúan egy térképszektorra. Ezzel az adatszerkezettel kétirányú hierarchikus útvonal meghatározás egyszerre számolhatja az utat minden rétegen. Az útvonal gyorsabban megtalálható, mert az algoritmusnak a csúcspontok korlátozott csoportját kell ellenőriznie egy térképszektorban és a megoldás mindössze egy keresési folyamatot tartalmaz. Ezen kívül, az algoritmus felépítése meglehetősen egyszerű: A keretrendszer mindössze egy kétirányú A* algoritmust, egy négyágú fát és néhány kiegészítést tartalmaz. Ez a megközelítés használható meglévő asztali rendszerekben is legrövidebb utak keresésének felgyorsításához. A rendszer mindössze néhány kiegészítést igényel asztali rendszerekhez, mert azok képesek minden egyszerű gráf adatszerkezettel dolgozni. Az algoritmus önmagából felhasználható különböző területeket alkalmazott programokban, mint a közlekedés irányítása vagy stratégia játékok.
Fordította: Csejtei Dávid (CSDSAAI.ELTE) Fordítás dátuma: 2012.06.22. Eredeti cikk: http://tomx.inf.elte.hu/twiki/pub/Tudas_Labor/2012Summer/Routing.pdf
