Navigationskortet

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.

Navigationskortet

Det er nødvendigt at kunne generere et konsistent kort indeholdende samtlige forhindringer i nærheden, for at kunne navigere sikkert. Et godt kort skal have følgende egenskaber:

  • Alle forhindringer skal repræsenteres.
  • Det skal være muligt at estimere afstande over kortet.
  • Dynamiske objekter skal repræsenteres og fjernes igen når de bevæger sig.
  • Det skal være muligt at generere en bane (trajectory) over kortet til navigation (så optimal som muligt).
  • Kortet skal være konsistent.

Alle disse krav kan imødekommes med metriske gitterkort. Men med topologiske kort, bestående af knuder og kanter, kan væsentlige forbedringer opnås.

Kortets repræsentation

Historisk set er der to måder at lave et kort på. Enten repræsenteres det topologisk eller metrisk, som vist på figuren herunder. Det topologiske kort søger at nå et højere abstraktionsniveau vha. en kompakt repræsentation. Et kort består således af en liste af væsentlige steder forbundet af kanter, der indeholder de nødvendige informationer, for at kunne navigere mellem stederne på listen. Det metriske kort indeholder i stedet kun geometriske informationer. Grænsen mellem de to typer er dog ret svævende, da de topologiske implementationer, vi i dag ser fungere, næsten alle er afhængige af geometriske oplysninger. Fordele og ulemper ved de to repræsentationer opremses herunder:

Det Metriske kort:

  • + Sensordata kan repræsenteres direkte og med alle oplysninger.
  • + Let at bruge data fra flere forskellige sensorer i kortet.
  • + Mange muligheder for at navigere, f.eks. generering af korteste sti.
  • - Kræver meget plads da højere opløsning kræves end af det topologiske kort.
  • - Følsom overfor sensor fejl såsom akkumulerende odometrifejl.
  • - Sværere at overskue da abstraktionsniveauet er lavere.

Det Topologiske kort:

  • + Mindre følsom overfor fejl i sensor-dataen.
  • + Højere abstraktionsniveau er mere brugervenligt.
  • + Mere kompakt repræsentation.
  • - Sværere at generere direkte fra sensordata.
  • - Ingen præcis navigation mulig.
  • - Det højere abstraktion gør det sværere at benytte direkte i computerprogrammet

 

Henholdsvis det metriske og det topologiske kort, hvor bogstaverne markerer væsentlige steder i kortet.

Gitterkortlægning

Gitter kortlægning er inspireret af billedrepræsentationen, men hvor hver pixel i billedmatricen repræsenterer en farve, repræsenterer hver pixel i kortet en sandsynlighed. Denne metriske opbygning er den mest brugte metode til kortlægning i SLAM applikationer. I Elfes implementation fra 1989 (*1), indeholder hver celle således sit eget uafhængige stochastiske estimat af sandsynligheden for, at cellen er optaget. Navigationssoftwaren kan dermed bestemme en sti gennem et antal punkter med lav sandsynlighed for at ramme en forhindring. Denne implementering giver desuden rig mulighed for at kombinere input fra en række forskellige sensorer i opbygningen af et kort over omgivelserne. Hver sensor opbygger således et lokalt sandsynlighedskort over en scanning. Dette kort opdaterer så det globale kort, og det samme gør kort fra andre sensorer. Sensorer med forskellig karakteristik, styrker og svagheder kan altså supplere hinanden til et mere komplet kort.

Gitterkort, hvor de sorte pletter er forhindringer og felterne markeret med gråt er felter, der er helt eller delvist optaget af forhindringer og derfor ikke må besøges.

Matematikken bag metoden

Udledningen af de sandsynlighedsberegninger, der ligger til grund for kortet, ligner af gode grunde meget beregningerne bag kort og positionsestimeringen. For én celle i kortet m(x,y) og målingerne z(1),...,z(t) beregnes sandsynligheden for at cellen er optaget vha. bayes regel. Det antages ligeledes, at kortet er statisk og alle målinger uafhængige, da disse antagelser gør det muligt at beregne et estimat i real-tid. Logaritmen til alle udtryk (den såkaldt log-odds form) kan beregnes, da de logaritmiske regneregler letter beregningsbyrden.

Initialiseringsværdien for felterne i kortet sættes som regel til en værdi på ca. 0.5. Det er desuden nødvendigt at beskrive sensorerne i systemet med en sensormodellen der giver en sandsynlighedsfordeling for en række felter. Sandsynligheden for at et enkelt felt er optaget eller ej kan udledes ud fra denne.

Kort til små embeddede applikationer

Til embeddede applikationer bliver Elfes algoritme alt for krævende, både når det gælder hukommelse og beregningstid. Derfor udviklede Borenstein et al. i 1991 en simplificeret udgave (*2). Denne algoritme lægger helt simpelt en eksperimentielt bestemt størrelse til, hvis et felt iflg. en sensor er optaget, og trækker en anden værdi fra, hvis ikke, helt uden brug af sensormodeller. Grundideen er, at sensorerne alligevel er så upræcise, at det ikke kan betale sig at opretholde præcise modeller, hvilket også forsvarer et grovere masket kort. Metoden hedder Histogrammic In-Motion Mapping (HIMM) og er med succes blevet anvendt i en række applikationer, hvor små embeddede systemer skulle styre en mobil robot (se bl.a. (*3)).

Metoden repræsenterer altså ikke korrekte sandsynligheder, men i stedet nogle mindre præcise "pseudosandsynligheder'' der stadig gør kortet brugbart i forhold til navigation. Ulempen er, at når de korrekte sandsynligheder ikke opretholdes, er det ikke muligt at foretage datafiltrering direkte på baggrund af kortet og på denne måde supplere f.eks. et Kalman filter med yderligere korrektion. De metriske kort benyttes dog sjældent i praksis til at foretage denne supplerende datafiltrering.

Topologiske kort og kombinationer af de to typer

De topologiske kort står som nævnt sjældent alene. De kombineres næsten altid af en vis mængde geometrisk data. Det topologiske korts fordele kan dog stadig opnås i kombination med et metrisk. Specielt i forbindelse med korrektion af cykliske baner i omgivelserne, viser topologiske kort deres styrke. Duckett et al. (*4) benytter f.eks. en topologisk node som abstraktion for et lokalt metrisk gitterkort. Dette giver mulighed for at udnytte nogle af det topologiske korts fordele, såsom den lave følsomhed over for fejl, og det højere abstraktionsniveau. Ved større fejl som f.eks. forekommer ved lukning af cykliske baner, korrigeres nodernes placering således hurtigt vha. en relaxation algoritme. Relaxation virker ved, at noderne er forbundet med en slags "fjeder'', der for at minimere energien, skal sørge for at forbindelsen mellem noderne, er den, som robotten har målt.

Forsøg på at generere noget, der ligner rent topologiske kort, findes bl.a. i Dedeoglu et al.'s inkrementalalgoritme (*5). Algoritmen starter med at processere sensordata for at detektere genkendelige scenerier såsom korridorer, t-kryds, hjørner osv.. Detekteres f.eks. et hjørne, indsættes dette som en node i kortet.

Micarelli et al. (*6) benytter samme overordnede princip. Her benyttes wavelet transformationen bare til at konstruere et histogram, der beskriver, hvor der er forhindringer i synsfeltet. Dette histogram kan så sammenlignes med på forhånd givne histogrammer af korridorer, hjørner osv.

Diskussion af kortlægningsalgoritmer

Et gitterkort er i sig selv ret tungt, og giver ikke mange muligheder, for at kortet f.eks. kunne være i stand til at korrigere fejl genereret af cykliske baner.

Det ville dog stadig være rart, at kunne beholde gitterkortets fordele såsom bedre ruteplanlægning og sensorintegration. Dette er alle fordele som Duckett et al. (*4) opretholder i deres implementation. Her udføres sensorintegration og ruteplanlægning stadig i de lokale gitterkort, mens cykliske baner korrigeres i det overordnede topologiske. Dedeoglu et al. (*5) Micarelli et al. (*6) går skridtet videre og dropper helt de lokale gitter kort, hvorfor de mister muligheden for præcis navigation, men opnår et mere kompakt kort med et højere abstraktionsniveau. De seneste års stigende brug af topologiske kort kunne tyde på, at de åbenlyse fordele i endnu højere grad vil kunne udnyttes i fremtiden. Kombinationer f.eks. med flere kort på forskellige abstraktionsniveauer kunne være en naturlig efterfølger til metoderne beskrevet ovenfor. For, hvorfor ikke både opretholde et komplet metrisk kort og på samme tid et overordnet topologisk, som det Dedeoglu et al. benytter sig af. Med et sådant levnes både mulighed for at korrigere cykliske baner, have let sensorintegration og på samme tid lave optimal ruteplanlægning.

Referencer:

(*1) A. Elfes. using occupancy grids for mobile robot perception and navigation. Computer 22(6), pp. 249-265, 1989.

(*2) J. Borenstein and Y. Korez. Histogrammic in-motion mapping for mobile robot obstacle avoidance. IEEE Journal of Robotics and Automation, Vol.7, No.4, pp. 534-539, 1991.

(*3) P. P´erez og J. E. Sim´o F. Blanes, G. Benet. Map building in an autinomous robot using infrared sensors. A Proceedings volume from the 4th IFAC Sympsium, pp.263-268, Argentina, 2000, 2000.

(*4) S. Marsland, J. Shapiro and T. Duckett. Fast, on-line learning of globally consistent maps. Kluwer Academic Publishers - Autonomous Robots 12 (2002), 2002.

(*5) M. J. Mataric og G. S. Sukhatme G. Dedeoglu. Incremental, on-line topological map building with a mobile robot. 1999.

(*6) L. Sciavicco og G. Ulivi A. Micarelli, S Panzieri. Landmark recognition in indoor navigation by fuzzy maps and cbr. Springer-Verlag: RAMSETE, LNCIS, pp. 227-250, 2001, 2001.