Lokaliseringsmetoder - Lokaliseringsmetoder i kort og omgivelserne

Katarina  Deylami

Jeg er din kontaktperson

Skriv til mig

Indtast venligst et validt navn
Eller dit telefonnummer
Sender besked
Tak for din besked
Vi beklager

På grund af en teknisk fejl kan din henvendelse desværre ikke modtages i øjeblikket. Du er velkommen til at skrive en mail til Send e-mail eller ringe til +45 72 20 28 87.

Lokaliseringsmetoder - Lokaliseringsmetoder i kort og omgivelserne

Præcis lokalisering af robotten i omgivelserne er nødvendigt, både for at kunne navigere præcist, men også for at kunne danne et konsistent kort over omgivelserne. Lokalisering er således en af de vigtigste forhindringer på vejen mod en fuldstændigt autonomt navigerende robot. Moderne positioneringsteknologi benytter sig grundlæggende af fire forskellige teknikker: Trilateration, triangulering, nærhed og bestiknavigation.

Trilateration (positionering vha. afstande)

Trilateration benytter afstanden til et antal objekter til at estimere en position. Hvis afstanden til mindst tre objekter med kendt position kan estimeres, så er det muligt at beregne positionen indenfor den givne målenøjagtighed (se figuren herunder). Kendes et større antal afstande end tre, er det muligt at forbedre estimatet af positionen yderligere.

Et eksempel på trilaterationsprincippet til positionsbestemmelse. Cirklerne angiver den målte afstand (som radius), til objektet der skal positionsbestemmes

Triangulering (positionering vha. vinkler)

På samme måde som det kan lade sig gøre at bestemme positionen udfra tre afstande, er det muligt vha. tre vinkler. Metoden ligner meget trilateration, og de bygger da også på de samme trigonometriske lærersætninger. Det er derfor muligt at kombinere de to metoder. Kendes f.eks. både vinklen og afstanden til bare to punkter, er en positionering mulig, ved at benytte sinus-relationerne på de indsamlede data (se figuren herunder).

Kombineres trilateration med triangulering, er positionsbestemmelse muligt med bare to objekter. Til disse skal vinklerne kendes, samt afstanden mellem objekterne, eller afstandene til positioneringspunktet.

Nærhed

Hvis robotten er i nærheden af et antal objekter, hvis placering er kendt, kan robottens placering estimeres.

Befinder robotten sig således i nærheden af et antal sendere med kort rækkevidde, og kan modtage signalerne, kan robotten bestemme sin position.

Denne metode kræver dog et stort antal sendere for at kunne give et præcist estimat af positionen, da det kun vides om robotten er i nærheden af senderen men ikke hvor tæt.

Bestiknavigation

Bestiknavigation eller deadreckoning fremskriver positionen, og ideen er så, at hvis udgangspunktet er kendt og bevægelsen ligeledes, så må den nuværende position også kunne beregnes. Positionen fremskrives med hjulenes bevægelser. Denne måles med odometriske sensorer, der som regel har en meget høj præcition. Præcitionen falder dog kraftigt med distancen robotten bevæger sig, da følgende faktorer hurtigt giver en større fejl i placeringen:

Et ujævnt underlag, en smule hjulslip, eller en lille usikkerhed omkring den præcise hjulstørrelse og det præcise punkt, hvor hjulet rører underlaget. Dette skyldes, at fejlen akkumulerer. En som udgangspunkt lille fejl på bare et par grader i orienteringen, kan således hurtigt blive til en større positionsfejl efter et par meters bevægelse. Et eksempel på positionering udelukkende på baggrund af odometrimålinger ses på figuren herunder. Denne egenskab gør bestiknavigation specielt følsom overfor fejl i orienteringen, hvorfor præcitionen falder, når robotten manøvrerer for eksempelvis at undgå en forhindring.

Eksempel på akkumulerende estimeringsfejl pga. odometrifejlen. a viser et konsistent kort, mens b viser et kort med en akkumulerende odometrifejl

Eksempel på akkumulerende estimeringsfejl pga. odometrifejlen. a viser et konsistent kort, mens b viser et kort med en akkumulerende odometrifejl.}

Diskussion - hvorfor nøjes med en metode

Bestiknavigation opretholder en ret god præcition over små afstande, men kan ikke benyttes alene, da robotten på længere sigt vil miste orienteringen. I stedet kan metoden kombineres med andre metoder, der korrigerer positionen engang imellem udfra globale parametre såsom placeringen af kendemærker. Således udnyttes bestiksnavigationens høje præcision på små afstande, og de resterende metoder kan med deres konstante position benyttes til at korrigere den akkumulerende fejl. Flere metoder i form af forskellige sensorer kunne evt. kombineres for at forbedre positionsestimatet.

Forskningen på området - et overblik

Det har i mange år været målet for utallige forskningsprojekter, at bygge en fuldstændig autonom mobil robot. Et autonomt mobilt system er opbygget af mange dele. Kortlægning af ukendte dynamiske omgivelser anses som det største problem, i forbindelse med udviklingen af den autonome mobile robot. De seneste år er det til dels lykkedes at skabe softwaren og hardwaren der skal til. En mobil robot kan således bevæge sig rundt i ukendte omgivelser mens den opbygger et kort, beregner sin egen position og navigerer. Dette udføres med udgangspunkt i informationer, der kan indhentes fra omgivelserne (SLAM). De nuværende algoritmer har dog mange begrænsninger, og bygger som regel bl.a. på en antagelse om en statisk verden. Problemstillingen omkring kortlægning af dynamiske omgivelser er i høj grad stadig et åbent forskningsområde. De nuværende algoritmer benytter forskellige metoder til at sortere dynamiske objekter væk som støj, når faste kendemærker skal findes i omgivelserne. De dynamiske objekter optræder således ikke som faste kendemærker i kortene, men kan ikke undtages, når det handler om navigation.

Der er ikke på nuværende tidspunkt nogen kommercielle produkter på markedet, der benytter disse avancerede teknikker. Dette kan bl.a. skyldes at algoritmerne stadig kræver en temmelig stor computerkapacitet for at kunne afvikles. Der er desuden mange teknikker, der løser problemet på hver deres måde. Algoritmernes stabilitet over længere arbejdsperioder og større arbejdsområder er desuden dårligt dokumenteret. Teknikkerne har alle fordele og ulemper, hvilket gør det svært at vælge en frem for en anden. Alle disse mange projekter gør det ligeledes svært at få et overblik over emnet. I de næste delafsnit gennemgås de grundlæggende ideer bag filtrene.

Hvorfor samtidig lokalisering og kortlægning (SLAM)?

Er et kort på forhånd givet, skal robotten stadig vide hvor i omgivelserne den er placeret. Bestemmelsen af placeringen er som nævnt ikke helt nem, selvom odometrimålinger (bestiknavigation) kan indhentes.

Det er derfor nødvendigt at kunne korrigere disse data fra tid til anden. Dette gøres ved at indsamle flere informationer fra omgivelserne. Til dette formål benyttes kendemærker i omgivelserne som f.eks. radiosendere, der benyttes til at beregne robottens position vha. trilateration. En lignende metode kan også benyttes, hvis en laserscanner er til rådighed. Den kan så aflæse reflektionsmærker som kendemærker, og ud fra en aflæsning af både afstand og vinkel beregne positionen. Men når nu laserscanneren alligevel scanner hele området, hvorfor så ikke bruge disse informationer til at generere et kort, i stedet for at have kortet defineret på forhånd? Dette spørgsmål er det grundlæggende bag SLAM ideen.

SLAM - Simultanious Localisation And Mapping dækker over muligheden for at bestemme og udvide et kort mens robotten bevæger sig, og på samme tid lokalisere robotten i dette kort. Det store problem er, at en fejl i enten positionen eller kendemærkerne, kan gøre kortet inkonsistent pga. de statiske afhængighed mellem målingerne. For at konsistente kort og præcise positioner kan genereres, er det nødvendigt at kunne estimere både kortet og positionen på samme tid, da de begge er fejlbehæftede. Udfra en præcis model for præcisionen af sensorerne, der estimerer disse parametre, kan et fælles korrigeret resultat opnås. På denne måde kan kendemærkerne afhjælpe positionsfejl og bestiknavigationensfejl i kendemærkepositionerne. En meget stor grad af præcision er nødvendig, for at kunne opretholde konsistente data. Denne høje præcision er svær at opnå med fejlbehæftede data.

Associering af kendemærker

Dette gælder også genkendelsen af kendemærker. Et problem der i litteraturen er kendt som `data-associeringsproblemet', og dækker over, hvordan et kendemærke identificeres unikt igen og igen.

En lille fejl kommer særligt til udtryk, hvis robotten f.eks. er kørt rundt i gangene på universitetet og efter et stykke tid har fundet en alternativ vej tilbage til et sted, den allerede har været. Hvordan lukkes kortet, og hvordan genkendes et kendemærke, vi allerede har set, unikt igen, hvis kortet ikke er 100% konsistent? Svaret er, at dette kun kan lade sig gøre, hvis sandsynlighedsfordelingerne for alle målepunkter i kortet kendes. Så er det muligt at korrigere hele kortet når et loop lukkes. Problemet besværliggøres yderligere af at det ikke kan afvikles i real-tid. Det er derfor vigtigt, at odometrimålinger og kendetegn i omgivelserne findes så præcist som muligt, for at undgå for store korrektioner. Metoderne til dette varierer meget fra projekt til projekt, hvilket også gælder filtrerings- og kortlægningsmetoderne.

Fortolkning af omgivelserne - et netværk af relationer

Det er nødvendigt kunne fortolke omgivelserne for, at kunne oprette et konsistent kort og præcis positionering. Kendetegnene i omgivelserne fortolkes dog forskelligt alt efter hvilken filtrerings algoritme, der benyttes. Nogle skal bruge de rå aflæsninger fra f.eks. en laserscanner, andre kræver enkelte kendetegn genkendt som et punkt i rummet, mens endnu andre kræver objekter som lofter, vægge osv. Visse implementationer benytter i stedet passive eller aktive kunstige kendemærker, som i eksemplet med reflektionsmærkerne og radiosenderne.

Fælles for disse er ønsket om at give den enkelte algoritme så meget information om placering og orientering som muligt. Både kunstige og naturlige kendetegn kan ikke aflæses helt præcist, og indeholder som regel en større usikkerhed end de enkelte odometrimålinger. Størrelsen på usikkerheden afhænger af hvilken sensor, der benyttes. Usikkerheden og andre karakteristika såsom korrelationen mellem målingerne (statistisk afhængighed) modelleres for de enkelte sensorer i systemet, så en præcis model kan benyttes under filtreringen. Dette gælder også for odometrisensorerne, hvor unøjagtigheden må bestemmes eksperimentielt, og korrelationen er ret høj (akkumulerende fejl).

Antallet af kendemærker kendes som regel ikke på forhånd. Dette stiller krav til filteralgoritmerne om at vedligeholde en dynamisk liste af kendemærker, der er i stand til vokse, når nye kendemærker er tilpas stabile til at indgå i filtreringsprocessen. Filteret benytter det stigende antal kendemærker til at øge kortets præcision. Kortet kan ses som et netværk af relationer, der bliver mere og mere stabilt med antallet af kendemærker (se figuren herunder).

Et netværk af kendemærker med hver deres sandsynlighedsfordeling giver en mere og mere præcis og stabil estimering. En firkant markerer et kendemærke, og en cirkel positionen. Den røde er den virkelige bane mens den sorte er den estimerede.