Navigation fra a til b uden kollision

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 72202887

Navigation fra a til b uden kollision

At navigere er at kunne finde vej fra a til b, en opgave, der varierer meget i sværhedsgrad alt efter omgivelserne. En navigationsalgoritme skal udlægge en bane bestående af et antal punkter robotten kan følge uden risiko for at støde på forhindringer. Herunder beskrives nogle metoder til navigation i kendte omgivelser. Det er dog et meget stort emne i sig selv, hvorfor navigationsmetoder, der udnytter kort med grid strukturen primært analyseres. Kravene til sådanne navigationsalgoritmer er:

  • Alle baner skal være kollisionsfri
  • Robotten skal nå sit bestemmelsessted hurtigt og sikkert
  • Banerne skal kunne lægges om løbende, når forudsætningerne ændrer sig
  • Robotten skal reagere hurtigt på pludseligt opståede farer

Navigationsalgoritmerne kan opdeles i en række forskellige koncepter:

  • Potentialefunktioner: Navigation efter samme princip som vandet ville løbe - den nærmeste vej. Dette værende mod målet eller væk fra forhindringer
  • Topologisk navigation: Hurtigste vej gennem et antal noder til målet
  • Sampling: tilfældige punkter i kortet vælges og forbindes til målet kan nås

 

Potentiale kort

Denne metode søger at lave ruteplanlægning ved først at give hvert felt i kortet en værdi beregnet af den såkaldte potentialefunktion. Funktionen beregner værdien, ud fra hvilke egenskaber, man ønsker rute planlægningen skal opfylde. Funktionen kunne f.eks. fylde kortet med afstanden til destinationen, for at korteste vej til målet kan findes, eller kombinere denne beregning med afstanden til nærmeste forhindring for at finde en mere kollisionsfri vej. Disse to eksempler uddybes herunder.

Korteste vej til målet (flood-filling)

Den korteste vej til målet findes ved, startende i destinationen, at udfylde nabofelterne med afstanden til dette punkt, medmindre der allerede står en kortere afstand i feltet. Denne metode udbredes over hele kortet som ringe i vandet. Når kortet er udfyldt, kan robotten så navigere mod destinationen, ved hele tiden at bevæge sig mod feltet med den laveste værdi. Metoden virker altså ligesom, hvis robotten var tiltrukket af destinationen. En bane fra start til destination vil komme meget tæt på forhindringerne, for at opnå den korteste vej. Det kan ses lidt ligesom en elastik udspændt mellem de to punkter over et antal forhindringer, og da robotten normalt repræsenteres som et punkt i kortet, vil dette forårsage en kollision. Der er ligeledes en risiko for, at robotten vælger veje, der er for smalle til, at den kan være der, igen med kollision til følge.

En løsning er at udvide samtlige forhindringer, så robotten på denne måde tvinges længere væk fra forhindringerne. Udvides forhindringerne lige meget over det hele, kræver det en ret stor udvidelse for at være sikker på undgå et hjørne. Men på smalle steder vil robotten så måske vurdere, der ikke er plads, selvom den godt kunne være der.

Alternativt skal udvidelsen af forhindringerne modelleres, så hjørnerne udvides ekstra meget, hvilket er ret dyrt at beregne.

Maksimering af afstanden til forhindringerne - en potentialefunktion

Hvis alle forhindringerne var sten, der blev kastet i vandet samtidig, ville ringene i vandet repræsentere de afstande, kortet skal fyldes med for at maksimere afstanden til forhindringerne. Kombineres dette estimat med afstanden til målet, opnås et kort, der både vægter at holde en vis sikkerhedsafstand til forhindringer samt søger en hurtig vej mod målet. For at vælge hvilket felt robotten skal bevæge sig mod næste gang, vægtes de to estimater til et.

Robotten vil udfra dette estimat søge fra store værdier mod mindre i retning mod målet.

Problemet med algoritmen er, at den fra tid til anden vil støde på lokale minimum, hvorfra den ikke aner, i hvilken retning den skal gå. En mulig løsning er at udvælge en tilfældig nabo blandt de nærmeste f.eks. 100 felter og søge videre herfra. Hvis dette ikke hjælper, må man vælge en tilfældig retning og håbe på, at man efter et antal skridt undslipper minimumspunktet.

En anden mulighed er at huske på i hvilke punkter, man har været, og så altid vælge den af de ubesøgtenaboer med den laveste værdi. Det vil ligeledes kunne hjælpe, hvis forhindringerne kun frastøder robotten et mindre antal felter fra forhindringen, så denne kraft kun har virkning et stykke væk. At få denne metode til at fungere korrekt kræver en del finjusteringer.

Topologiske navigationsmetoder

Topologiske kort består som nævnt af noder forbundet af kanter i et netværk. Kanterne indeholder værdier, der f.eks. kunne repræsentere afstanden mellem de to noder. Kortets som regel høje abstraktionsniveau, hvor en node kunne være et gangareal eller et lokale, umuliggør præcis og optimal navigation, men er ideelt til navigation over større afstande. Her kan en kant indeholde simple instrukser til robotten om, hvordan den skal bevæge sig fra node til node.

Det er let at beregne den "korteste'' vej mellem en start node og en destinationsnode med disse egenskaber. Dette gøres lidt på samme måde som flood-filling metoden, startende i destinationen fyldes noderne med et estimat af afstanden til målet. Herefter udføres "relaxation'' for at være sikker på, at estimatet i hver node virkeligt er den mindste afstand (se Dijkstra's algoritme).

Navigationen mellem noderne kan dog også ændre sig ved introduktion af nye forhindringer, hvorfor andre algoritmer må træde til i disse situationer. Dermed kommer vi tilbage til debatten om de metriske mod de topologiske kort, og selvom et rent topologisk kort ikke kan løse hele problemet, kan det høje abstraktionsniveau over kortet afhjælpe kompleksitetsproblemerne ved potentialekortene. Dette er muligt ved at lade hver node repræsentere et metrisk kort, hvori et potentialekort kan genereres.

Sampling metoder

Indenfor styring af specielt robotarme med flere frihedsgrader end den mobile robot, benyttes sampling metoder som f.eks. Probabilistic RoadMap (PRM) metoden. Metoden er ret hurtig, og muliggør navigation over større afstande. Den bygger på den tilfældige udvælgelse af en række punkter i kortet. Punkterne checkes for med sikkerhed at kunne sige om, de ligger et frit sted. Efter at have udvalgt en række "frie'' punkter, der i kortet vil repræsentere noder, findes mulige kanter mellem noderne, hvor disse ikke går gennem forhindringer. Startpositionen og destinationen indsættes ligeledes som noder, og kan en kollisionsfri sti beregnes, returneres denne, hvis ikke, begynder processen forfra med at indsætte punkter, indtil det lykkedes. Metoden danner tit nogle underlige baner, da kun et fåtal af punkterne i kortet undersøges. Et eksempel herpå ses i figuren herunder, hvor en sti fra start til destinationen genereres. Stien kommer tæt på forhindringerne, og bliver vilkårligt kantet.

Sampling af sti fra start til destination, hvor de mørke felter repræsenterer forhindringer. (Højre) Udvælgelse af sti med korteste vej til destinationen, selvom stien på ingen måder er optimal og går vilkårligt tæt på forhindringerne.

Metoden garanterer at finde en vej, hvis den eksisterer, da den sampler til en vej findes. Derfor siges metoden at være sandsynlighedsmæssigt komplet. Der findes et stort antal af forskellige sampling metoder, som bygger på de nævnte principper, og selv om problemerne omkring baner der ligger tæt på forhindringerne, kan løses med indførelsen af sandsynlighedskort, er de generede baner langt fra altid optimale.