Néhány algoritmus az abszolút GPS-helymeghatározás területérõl

Takács Bence, doktorandusz

bence@agt.bme.hu

BME Általános és Felsõgeodézia Tanszék

2001. augusztus

Az elmúlt évtizedben az USA Védelmi Minisztériuma által üzemeltetett NAVSTAR-GPS elnevezésû globális helymeghatározó rendszer a navigáció legfõbb eszközévé vált. A rendszert katonai célokra fejlesztették, de számos polgári célra is felhasználható. Alapelve: a helymeghatározás ismertlen mennyiségei ismert helyzetû mûholdakra végzett távolságmérések alapján vezethetõk le. A helymeghatározás egy egyenletrendszer megoldását jelenti, az egyes egyenletek a mûholdak ismert koordinátái, a mért mûhold-vevõ távolságok és a vevõ ismeretlen koordinátái között teremtenek kapcsolatot. Az ismeretlenek (a vevõ három térbeli koordinátája és a vevõ órájának igazítatlansága) egyértelmû meghatározásához legalább négy mûholdra végzett egyidejû távolságmérésre van szükség. A mûholdgeometria sajátos következménye, hogy általában több mint négy mûhold egyidejû mérése lehetséges, így az elkerülhetetlen mérési hibák miatt a helymeghatározás egyenletrendszere ellentmondásokhoz vezet. Az ellentmondások megszüntetésének hagyományos módszere a legkisebb négyzetek (LN) módszerén alapuló kiegyenlítés, amelynek elvi alapjait Gauss dolgozta ki. A módszert azóta a geodéziában (és természetesen sok más mûszaki tudományterületen) számos feladat megoldásához alkalmazzák.
A tanulmány a GPS méréseket és a vevõ-, valamint a mûholdkoordinátákat tartalmazó egyenlerendszer megoldásának néhány módszerét mutatja be: (1) az ún. "direkt" módszereket, ahol az ismeretlenek értéke zárt képletek segítségével kiszámítható; (2) a "hagyományos" LN módszert; (3) az ún. rekurzív kiegyenlítés módszerét, amely tulajdonképpen a Kalman-szûrés összefüggésein alapul.

Bevezetés

Elemi geometriai feladat: a síkon két ismert helyzetû ponttól adott távolságra lévõ harmadik pont helye két kör metszéspontjaként adódik. Az ismeretlen P, az ismert A és B pontok síkkoordinátái, illetve a megmért t_AP és t_BP távolságok alapján a következõ egyenletrendszer írható fel:

/1/

Ugyanezt a feladatot a térben is megfogalmazhatjuk, a helymeghatározás egyenletrendszere az /1/ egyenletrendszerbõl értelemszerûen következik:

/2/

Ez a GPS-szel történõ helymeghatározás geometriai alapelve. A mûholdakat az ismert A, B, C pontokba képzeljük, a t_AP, t_BP, t_CP távolságokat a meghatározni kívánt P pontban lévõ vevõ méri.

A távolság meghatározásakor a vevõ a mûhold rádiójelének futási idejét méri meg. Az eredmény csak akkor lesz a valódi távolság, ha a mûholdak atomórája és a földi vevõ egyzserûbb kivitelû órája pontosan szinkronizált. Ez a gyakorlatban nem valósítható meg, ezért be kell vezessünk egy negyedik ismeretlent: a vevõ órahibáját, azaz a vevõ órája által "mutatott" idõ eltérését az ún. GPS-rendszeridõtõl. A helymeghatározás egyenletrendszere tehát a következõ alakú:

/3/

ahol

Xⁱ, Yⁱ, Zⁱaz i-edik mûhold ismert térbeli derékszögû koordinátái
PR_iaz i-edik mûholdra végzett távolságmérés eredménye
x, y, z                  a vevõ ismeretlen térbeli derékszögû koordinátái
Cr                          a vevõ órahibájának hatása (az idõeltérés és a hullám terjedési sebesség szorzata)
n                          az észlelt mûholdak száma

Megjegyezzük, hogy a /3/ egyenletrendszer bal oldalán álló pszeudótávolságokat korrigálni kell a légkör jelkésleltetõ hatásával, illetve a mûholdak órájának igazítatlanságával, a jobb oldalon lévõ mûholdkoordinátákat pedig a Föld forgásának hatásával. A korrekciók megtalálhatók a legtöbb GPS kézikönyvben.

A /3/ egyenletrendszer gyakorlati megoldása több nehézséggel jár: (1): az egyenletek száma általában nagyobb, mint az ismeretlenek száma, vagyis az elkerülhetetlen mérési gibák miatt az egyenletrendszer ellentmondásokat tartalmaz; (2): az egyenletek nem lineárisak, a linearizáláshoz szükség van az ismeretlen vevõkoordináták elõzetes értékére, vagyis (3): a megoldást iterációval kapjuk meg. A /3/ megoldásának több módszere ismert, a következõkben ezeket foglaljuk össze.

Az egyenletrendszer "direkt" megoldása n = 4 esetén

A vizsgált esetek közül ez a legegyszerûbb, hiszen az egyenletrendszer nem tartalmaz ellentmondásokat. Több módszer is ismert [Kleusberg, 1994, Grafarend & Shan, 1996, Leva, 1996], ezek közül Kleusberg módszerét mutatjuk be röviden.

Az elsõ lépésben vonjuk ki az elsõ egyenletet a három további egyenletbõl, ezzel az ismeretlen mennyiségek számát négyrõl háromra csökkentettük (a referencia-mûholdat zérus indexszel jelöltük). A következõ egyenéetrendszert kapjuk:

/4/

ahol

a pszeudótávolságok különbsége (1. ábra)

A három egyenlet geometriailag egy-egy hiberbólikus felületet jelent, ezek metszéspontja adja a vevõ lehetséges helyzetét. A megoldás további lépései vektoralgebrai összefüggések alkalmazásán alapulnak, a levezetés megtalálható [Klesuberg, 1994]-ben, vagy [Strang & Borre, 1997]-ben. A megoldás lépéseit az 1. táblázat tartalmazza. A számítás végeredménye a referencia (az ábrán 0-val jelöltük) mûholdról a vevõre mutató egységvektor (e^1,2) és a vektor hossza (s^1,2). általában a /3/ egyenletrendszernek két megoldása létezik, ezek közül a "helyes" kiválasztása elõzetes koordináták figyelembe vételével lehetséges. A geometria függvényében a következõ lehetõségek szigorú vizsgálata szükséges:

a két egységvektor (e¹ és e²) különbözõ és mindkét távolság (s¹ és s²) pozitív: a helyes eredmény kiválasztása elõzetes koordináták alapján szükséges
a két egységvektor (e¹ és e²) különbözõ, de az egyik távolság negatív: csak a pozitív távolsághoz tartozó megoldás elégíti ki a /3/ egyenletrendszert, ezért ez a helyes
az 1. táblázatban jelölt F¹ és F² két egységvektor párhuzamos: ebben az esetben a Kleusberg algoritmusnak végtelen sok megoldása létezik. Tapasztalaltaim szerint ez igen gyakori eset. Ha a két F vektor nem teljesen, csak közel párhuzamos, már akkor is elfajul a megoldás.
a két egységvektor (e¹ és e²) ugyanaz, ilyenkor nem kapunk egyértelmû megodlást.

1. táblázat A Kleusberg-algoritmus (az alsó indexek nem a vektorok elemeit jelölik, hanem az egyes vektorok meg megkülönböztetésére szolgálnak)

A Kleusberg módszer nagy elõnye, hogy zárt képletekkel néhány lépésben adja a megoldást, hátránya viszont, hogy csak négy mérés esetén alkalmazható. További hátránya, hogy érzékeny a mûholdgeometriára. A gyakorlatban általában több távolságot mérünk és a lehetséges négyes konfigurációk közül a legkedvezõbb kiválasztása a mûholdgeometria szigorú vizsgálata alapján történik. Ez azonban körülményessé teszi a gyakorlati alkalmazást. Ha n a mérések száma, akkor a lehetséges négyes kombinációk száma:

Ha például n=8 mûholdat mérünk, akkor 70 négyes kombináció létezik, de ha már 12, akkor 495 négyes kombinációt kell megvizsgálni. A kedvezõtlen tulajdonságok miatt véleményem szerint ennek a módszernek inkább elvi, mint gyakorlati jelentõsége van.

1. ábra Kleusberg algoritmus geometriai mennyiségei

Az egyenletrendszer "direkt" megoldása n => 4 esetén

Ezt a módszert elõször Bancroft publikálta [Bancroft, 1985]. A fölös méréseket az egyenletek linearizálása nélkül, a LN módszerének elve alapján lehet figyelembe venni. A /3/ egyenletrendszer alkalmas átrendezésével, felhasználva a "Lorentz inner product" fogalmát, egy egyismeretlenes másodfokú egyenletet kapunk. A módszer elõnye, hogy nincs szükség elõzetes vevõkoordinátákra, hátránya viszont, hogy mátrixinvertálást tartalmaz. A "Lorentz inner product" számítása a következõ összefüggés alapján elehetséges:

/5/

Az algoritmus lépéseit a 2. táblázat tartalmazza:

2. táblázat Bancroft-algoritmus

Az egyenletrendszer megoldása a normálmátrix invertálásával

A legkisebb négyzetek módszerének alapgondolata a következõ: (1) ha valamely mennyiségek meghatározására méréseket végzünk, és a mérések száma nagyobb, mint amennyi a megoldáshoz feltétlenül szükséges, akkor az elkerülhetetlen mérési hibák miatt a mérések ellentmondanak egymásnak; (2) az ellentmondásokat ún. kiegyenlítéssel szüntetjük meg úgy, hogy minden méréshez egy-egy javítást rendelünk; (3) a végtelen sok javítási rendszer közül azt választjuk, amelyben a javítások a legkisebbek; (4) ha a mérések pontossága (ún. súlya) különbözõ, a keresett javítási rendszerben a javítások négyzetének súlyozott összege a lehetõ legkisebb (innen a módszer elnevezése), a javítások keresett rendszerét tehát matematikai módszerrel, szélsõérték keresésével határozhatjuk meg.

A /3/ egyenletrendszer a mért pszeudótávolságok és a helymeghatározás ismeretlen mennyiségei között teremt nemlineáris kapcsolatot. Ahhoz, hogy az ismeretleneket a hagyományos kiegyenlítõ számítás összefüggéseivel meg tudjuk határozni, a /3/ egyenletet jolbb oldalát liearizálni kell. Ehhez a vevõ és a mûhold geometriai távolságát kifejezõ összefüggést Taylor-sorba fejtjük, majd a magasabb fokszámú tagokat elhanyagoljuk. A linearizált egyenlet [Husti et al, 2000]:

/6/

ahol
            x₀, y₀, z₀                  a vevõ elõzetes térbeli derékszögû koordinátái
            az elõzetes koordináták javítása
    a geometriai távolság közelítõ értéke, amely a vevõ közelítõ koordinátáinak ismeretében számítható

Az így levezetett lineáris ún. közvetítõ egyenletrendszer mátrixos alakban a következõ:

részletesen:

/7/

Az ismeretlen mennyiségek a következõ összefüggéssel határozhatók meg [Detrekõi, 1991]:

/8/

ahol a kiegyenlítõ számítás elnevezéseit használva:
A - alakmátrix, l - tisztatagvektor, P - a mérések súlymátrixa, N - normálmátrix, az ún. normálegyenletrendszer együtthatómátrixa.

Összefoglalva a normálmátrix invertálásának módszerét: (1) a szükségesnél több mérés alapján optimális becslést ad; (2) a /3/ egyenlet linearizálásához az ismeretlen vevõkoordináták elõzetes értéke szükséges; (3) a megoldás során egy 4x4 méretû mátrixot kell invertálni; (4) az egyes mérések közötti korreláció figyelembe vehetõ.

Az egyenletrendszer megoldása Kalman-szûréssel

A Kalman szûrési technika elsõsorban dinamikus rendszerek állapotának becslésére alkalmas módszer, melynek elvi alapja az elõzõekben ismertetett LN módszeréhez kapcsolódik. A Kalman-szûrés számos alkalmazását dolgozták ki a teljesség igénye nélkül: a navigáció, a geodézia, a jármûkövetés (repülõgépek, ûrhajók, rakéták irányítása), a geológia, az óceánográfia területén [Takács, 2000]. A következõkben ezek közül egy olyan alkalmazást mutatunk be, amely a /7/ egyenletrendszer megoldásának hatékony módszere. Ezt a módszert rekurzív kiegyenlítésnek szokás nevezni. A módszer nagy elõnye, hogy a mátrixmûveletek lépésekre bontásával a számítási igény lényegesen csökkenthetõ, sõt az invertálásra nincs is szükség. A /7/ egyenletrendszer esetében ez nem jelent lényeges különbséget, hiszen a mai számítóeszközöknek a /8/ alatti mátrixmûveletek elvégzése nem okoz nehézséget. Ugyanakkor az alábbiakban ismertetett módszer a kiegyenlítõ számítás területén lényegesen nagyobb egyenletrendszerek megoldásában is általánosan alkalmazható. A Kalman-szûrés másik fontos elõnye, hogy a durva hibák szûrése lényegesen hatékonyabb, mint a "hagyományos" LN módszere esetén.

A Kalman-szûrés összefüggései megtalálhatók pl. [Brown & Hwang, 1992]-ben. A módszer alapgondolata a következõ: a rendszer álalpotát leíró mennyiségeket (navigáció esetén pl. a koordinátákat és a sebességeket) az állapotvektor tartalmazza, melynek becslését minden egyes idõpontban az állapotvektor elõzõ értékének és az aktuális mérésekbõl levezethetõ értékének optimális súlyozásával határozunk meg.

A /8/ alatti ún. normálegyenlet megoldható a Kalman-szûrés összefüggéseinek alkalmazásával. Induljunk ki a /7/ alatti egyenletrendszerbõl. Jelölje az A alakmátrix i-edik sorát a h^t vektor, a négy ismeretlent tartalmazó vektort (állapotvektort) továbbra is x vektor. A /7/ alatti egyenletrendszer megoldásához a következõ iterációs lépésekre van szükség (3. táblázat):

3. táblázat A Kalman-szûrés alapösszefüggései

Az iterációs lépések elõtt az ismeretlenek értékét zérusnak tekinthetjük (vagyis nem kell elõzetes koordinátákkal rendelkeznünk), ugyanakkor a P mátrixot célszerû igen nagy számokkal feltölteni. Megjegyezzük, hogy az utolsó iterációs lépés után a P mátrix a normálmátrix inverzévé váilk.

A Kalman szûrés további elõnye, hogy az egyes idõpontokhoz tartozó helyzet-adatok simíthatók (emiatt jogos a módszer elnevezésében a szûrés kifejezés). Ez egyszerûen úgy valósíható meg, hogy az ismeretlenek (x) és kovarianciamátrixuk (P) elõzetes értéke az elõzõ idõpontban mehgatározott értéket veszik fel. Egész pontosan, az elõzetes P kovarianciamátrixot az elõzõ epochában mehgatározott mátrix és egy predikciós tapasztalati tényezõ összegeként szokás felvenni. Ez a tapasztalati tényezõ tulajdonképpen a futó átlagolás hosszával analóg mennyiség. A módszer továbbá burkoltan azt is tartalmazza, hogy ha valamelyik idõpontban négynél kevesebb mûholdat észlelünk (mozgó vevõ esetén ez igen gyakori), akkor a módszer eehhez az idõponthoz is ad helyzet-adatot.

Összefoglalás

A mûholdas helymeghatározás legalapvetõbb feladata a vevõ ismeretlen koordinátáinak meghatározása ismert helyzetû mûholdra végzett távolságmérésekbõl. Ebben a cikkben néhány módszer ismertetésekor elsõsorban a különbözõ algoritmusok bemutatására törekedtünk.

Mivel az egyenletek száma általában nagyobb a megoldáshoz feltétlenül szükségesnél, az elkerülhetetlen mérési hibák miatt az egyenletrendszer ellentmondásokkal terhelt. Bizonyos algoritmusok (Kleusberg) nem alkalmasak az ellentmondások feloldására, ezért ezek csak közelítõ értékek számítására alkalmasak. A Kleusberg algoritmus elõnye viszont, hogy nagyon egyszerû és gyors. Az ellentmondások megszüntetésének hagyományos eszköze a legkisebb négyzetek módszere, ennek alkalmazására a cikkben három különbözõ lehetõséget mutattunk be. Az elsõ a normálmátrix invertálásán alapul, ez a kiegyenlítõ számítás klasszikus módszere. Két hátrányát említjük: az egyenleteket linearizálni kell, illetve hatékony mátrixinvertálási technikát igényel. A Bancroft-algoritmus néven ismert módszer az elõbbi, míg a Kalman-szûrés az utóbbi nehézséget küszöböli ki.

A Kalman-szûrésen alapuló módszernek számos kedvezõ tulajdonsága van: nem kell bonyolult mátrixmûveleteket végezni (gyors), az egymás után következõ epochák simítása egyszerû (emiatt nevezik szûrésnek) és a durva hibák hatására alig érzékeny (robosztus).

Irodalomjegyzék

Bancroft, S. (1985): An algebraic solution of the GPS Equations. IEEE Transaction on Aerospace and Electronic Systems, Vol. AES-21, No. 6, pp. 56-59

Brown R. G. & P. Y. C. Hwang (1992): Introduction to Random Signals and Applied Kalman Filtering, John Wiley & Sons. Inc., New York, Chichester, Brisbane, Toronto, Singapure

Detrekõi Á. (1991): Kiegyenlítõ számítások. Tankönyvkiadó, Budapest

Grafarend E. W. & J. Shan (1996): A closed-form solution of the nonlinear pseudo-ranging eqations (GPS). Artifical Satellites, Planetary Geodesy No. 28., Vol. 31., No. 3., pp. 133-147.

Husti Gy., Ádám J., Bányai L., Borza T., Busics Gy., Krauter A. (2000): Globális helymeghatározó rendszer (bevezetés)

Kleusberg, A. (1994): Die direkte Lösung des raumlichen Hyberbelschnitts. Zeitschrift für Vermessungswesen, Vol. 119., No. 4., pp. 188-192.

Krauter A. (1999): Role of the Geometry in GPS Positioning. Periodica Politechnica Civ. Eng., Vol. 43., No. 1., pp. 45-53.

Leva, j. L. (1996): An alternative Closed-Form Solution to the GPS Pseudorange Eqations. IEEE Transaction on Aerospace and Electronic Systems, Vol. 32, No. 4, pp. 1430-1439.

Strang G. & K. Borre (1997): Linear Algebra, Geodesy and GPS, Wellesly-Cambridge Press.

Takács B. (2000): Kalman-szûrõ a korszerû helymeghatározásban. Magyar Távközlés, Vol. 11., No. 8., pp. 8-10.