Monte Carlo lokalisering

Monte Carlo-lokalisering ( MCL ), även känd som partikelfilterlokalisering , är en algoritm för robotar att lokalisera med hjälp av ett partikelfilter . Med en karta över miljön uppskattar algoritmen positionen och orienteringen för en robot när den rör sig och känner av miljön. Algoritmen använder ett partikelfilter för att representera fördelningen av sannolika tillstånd, där varje partikel representerar ett möjligt tillstånd, dvs en hypotes om var roboten är. Algoritmen börjar vanligtvis med en enhetlig slumpmässig fördelning av partiklar över konfigurationsutrymmet, vilket betyder att roboten inte har någon information om var den är och antar att den är lika sannolikt att vara var som helst i rymden. Närhelst roboten rör sig, flyttar den partiklarna för att förutsäga dess nya tillstånd efter rörelsen. Närhelst roboten känner av något, omsamplas partiklarna baserat på rekursiv Bayesiansk uppskattning, dvs hur väl de faktiska avkända data korrelerar med det förutsagda tillståndet. I slutändan bör partiklarna konvergera mot robotens faktiska position.

Grundläggande beskrivning

Tänk på en robot med en intern karta över dess miljö. När roboten rör sig måste den veta var den är på kartan. Att bestämma dess placering och rotation (mer allmänt, posen ) med hjälp av dess sensorobservationer kallas robotlokalisering .

Eftersom roboten kanske inte alltid beter sig på ett perfekt förutsägbart sätt genererar den många slumpmässiga gissningar om var den kommer att vara härnäst. Dessa gissningar är kända som partiklar. Varje partikel innehåller en fullständig beskrivning av ett möjligt framtida tillstånd. När roboten observerar miljön kastar den bort partiklar som inte överensstämmer med denna observation, och genererar fler partiklar nära de som verkar konsekventa. I slutändan konvergerar förhoppningsvis de flesta partiklar till där roboten faktiskt är.

Statens representation

Robotens tillstånd beror på applikation och design. Tillståndet för en typisk 2D-robot kan till exempel bestå av en tuppel $(x,y,\theta )$ för position $x,y$$,$ och orientering $\displaystyle \theta }$ . För en robotarm med 10 leder kan det vara en tuppel som innehåller vinkeln vid varje led: $(\theta _{1},\theta _{2 },...,\theta _{10})$ .

Tron , som är robotens uppskattning av dess nuvarande tillstånd, är en sannolikhetstäthetsfunktion fördelad över tillståndsrummet. I MCL-algoritmen representeras tron ​​vid en tidpunkt $t$ av en uppsättning $M$ -partiklar $X_{t}=\lbrace x_{t}^{[1]},x_{t}^{[2]},\ldots ,x_{t}^{[M]}\rbrace$ . Varje partikel innehåller ett tillstånd, och kan därmed betraktas som en hypotes om robotens tillstånd. Regioner i tillståndsutrymmet med många partiklar motsvarar en större sannolikhet att roboten kommer att finnas där — och regioner med få partiklar är osannolikt där roboten är.

Algoritmen antar Markov-egenskapen att det aktuella tillståndets sannolikhetsfördelning endast beror på det tidigare tillståndet (och inte några före det), dvs. $X_{t}$ beror endast på $X_ {t-1}$ . Detta fungerar bara om miljön är statisk och inte förändras med tiden . Vid start har roboten vanligtvis ingen information om sin nuvarande ställning så partiklarna är jämnt fördelade över konfigurationsutrymmet .

Översikt

Givet en karta över miljön är målet med algoritmen att roboten ska bestämma sin ställning i miljön.

Vid varje gång $t$ tar algoritmen som indata den tidigare övertygelsen ${ \displaystyle X_{t-1}=\lbrace x_{t-1}^{[1]},x_{t-1}^{[2]},\ldots ,x_{t-1}^{[M ]}\rbrace }$ , ett aktiveringskommando $u_{t}$ och data som tas emot från sensorer $z_{t}$ ; och algoritmen matar ut den nya tron $X_{t}$ .

    
            
           
            Algoritm MCL ${\displaystyle (X_{t-1},u_{t},z_{t})} :$ X $\displaystyle {\ stapel {X_{t}}}=X_{t}=\emptyset }$ för $m=1$ till $M$ : $x_{t}^ {[m]}=$ motion_update $(u_{t},x_{t-1}^{[m]})$${ \displaystyle w_{t}^{[m]}=}$ sensor_update $(z_{t},x_{t}^{[m]})$${\bar {X_{t}}}={\bar {X_{t}}}+\langle x_{t}^{ [m]},w_{t}^{[m]}\rangle$ endfor för $m=1$ till $M$ : rita $x_{t }^{[m]}$ från ${\bar {X_{t}}}$ med sannolikhet $\propto w_{t}^{[m]}$$X_{t}=X_{t}+x_{t}^{[m]}$ slutför retur $X_{t}$

Exempel för 1D-robot

En robot färdas längs en endimensionell korridor, beväpnad med en sensor som bara kan se om det finns en dörr (vänster) eller om det inte finns någon dörr (höger).

Betrakta en robot i en endimensionell cirkulär korridor med tre identiska dörrar, med hjälp av en sensor som returnerar antingen sant eller falskt beroende på om det finns en dörr.

$t=0$
Algoritmen initieras med en enhetlig fördelning av partiklar. Roboten anser sig vara lika sannolikt att vara var som helst i rymden längs korridoren, även om den fysiskt befinner sig vid den första dörren.	Sensoruppdatering : roboten upptäcker en dörr . Den tilldelar en vikt till var och en av partiklarna. De partiklar som sannolikt ger denna sensoravläsning får en högre vikt.	Omsampling : roboten genererar en uppsättning nya partiklar, där de flesta genereras kring de tidigare partiklarna med mer vikt. Den tror nu att den är vid en av de tre dörrarna.

$t=1$
Rörelseuppdatering : roboten rör sig en bit åt höger. Alla partiklar rör sig också rätt, och en del brus appliceras. Roboten befinner sig fysiskt mellan den andra och tredje dörren.	Sensoruppdatering : roboten upptäcker ingen dörr . Den tilldelar en vikt till var och en av partiklarna. De partiklar som sannolikt ger denna sensoravläsning får en högre vikt.	Omsampling : roboten genererar en uppsättning nya partiklar, där de flesta genereras kring de tidigare partiklarna med mer vikt. Den tror nu att den är på en av två platser.

$t=2$
Rörelseuppdatering : roboten rör sig en bit åt vänster. Alla partiklar rör sig också åt vänster, och en del brus appliceras. Roboten befinner sig fysiskt vid den andra dörren.	Sensoruppdatering : roboten upptäcker en dörr . Den tilldelar en vikt till var och en av partiklarna. De partiklar som sannolikt ger denna sensoravläsning får en högre vikt.	Omsampling : roboten genererar en uppsättning nya partiklar, där de flesta genereras kring de tidigare partiklarna med mer vikt. Roboten har framgångsrikt lokaliserat sig.

I slutet av de tre iterationerna konvergeras de flesta av partiklarna till robotens faktiska position enligt önskemål.

Rörelseuppdatering

Tro efter att ha flyttat flera steg för en 2D-robot med en typisk rörelsemodell utan avkänning .

Under rörelseuppdateringen förutsäger roboten sin nya plats baserat på det givna manöverkommandot genom att applicera den simulerade rörelsen på var och en av partiklarna. Till exempel, om en robot rör sig framåt, rör sig alla partiklar framåt i sina egna riktningar oavsett vilken väg de pekar. Om en robot roterar 90 grader medurs roterar alla partiklar 90 grader medurs, oavsett var de befinner sig. Men i den verkliga världen är inget manöverdon perfekt: de kan överskrida eller underskrida den önskade mängden rörelse. När en robot försöker köra i en rak linje, kröker den oundvikligen åt den ena eller andra sidan på grund av små skillnader i hjulradie. Därför måste rörelsemodellen kompensera för brus. Oundvikligen divergerar partiklarna under rörelseuppdateringen som en konsekvens. Detta förväntas eftersom en robot blir mindre säker på sin position om den rör sig i blindo utan att känna av omgivningen.

Sensoruppdatering

När roboten känner av sin miljö uppdaterar den sina partiklar för att mer exakt återspegla var den är. För varje partikel beräknar roboten sannolikheten för att den, om den hade varit i partikelns tillstånd, skulle uppfatta vad dess sensorer faktiskt har känt av. Den tilldelar en vikt $w_{t}^{[i]}$ för varje partikel som är proportionell mot nämnda sannolikhet. Sedan drar den slumpmässigt $M$ nya partiklar från den tidigare tron, med sannolikhet proportionell mot $w_{t}^{[i]}$ . Partiklar som överensstämmer med sensoravläsningar är mer benägna att väljas (möjligen mer än en gång) och partiklar som inte överensstämmer med sensoravläsningar plockas sällan. Som sådan konvergerar partiklar mot en bättre uppskattning av robotens tillstånd. Detta förväntas eftersom en robot blir allt säkrare på sin position när den känner av sin omgivning.

Egenskaper

Icke-parametrisitet

Partikelfiltret som är centralt för MCL kan approximera flera olika typer av sannolikhetsfördelningar , eftersom det är en icke-parametrisk representation . Vissa andra Bayesianska lokaliseringsalgoritmer, såsom Kalman-filtret (och varianter, det utökade Kalman-filtret och det oparfymerade Kalman-filtret ), antar att robotens tro är nära att vara en Gauss-fördelning och fungerar inte bra i situationer där tron ​​är multimodal . Till exempel kan en robot i en lång korridor med många liknande dörrar komma fram till en tro som har en topp för varje dörr, men roboten kan inte urskilja vilken dörr den befinner sig vid. I sådana situationer kan partikelfiltret ge bättre prestanda än parametriska filter.

En annan icke-parametrisk metod för Markov-lokalisering är den rutnätsbaserade lokaliseringen, som använder ett histogram för att representera trosfördelningen. Jämfört med det rutnätsbaserade tillvägagångssättet är Monte Carlo-lokaliseringen mer exakt eftersom tillståndet som representeras i prover inte är diskretiserat.

Beräkningskrav

Partikelfiltrets tidskomplexitet är linjär med avseende på antalet partiklar. Naturligtvis, ju fler partiklar, desto bättre noggrannhet, så det finns en kompromiss mellan hastighet och noggrannhet och det är önskvärt att hitta ett optimalt värde på $M$ . En strategi för att välja $M$ är att kontinuerligt generera ytterligare partiklar tills nästa kommandopar $u_{t}$ och sensoravläsningen $z_{t}$ har anlänt. På så sätt erhålls största möjliga antal partiklar utan att det hindrar funktionen hos resten av roboten. Som sådan är implementeringen anpassningsbar till tillgängliga beräkningsresurser: ju snabbare processorn är, desto fler partiklar kan genereras och därför desto mer exakt är algoritmen.

Jämfört med rutnätsbaserad Markov-lokalisering har Monte Carlo-lokalisering minskat minnesanvändningen eftersom minnesanvändningen bara beror på antalet partiklar och inte skalas med storleken på kartan, och kan integrera mätningar med en mycket högre frekvens.

Algoritmen kan förbättras med hjälp av KLD-sampling , som beskrivs nedan, som anpassar antalet partiklar som ska användas baserat på hur säker roboten är på sin position.

Partikelberövande

En nackdel med den naiva implementeringen av Monte Carlo-lokalisering uppstår i ett scenario där en robot sitter på ett ställe och upprepade gånger känner av miljön utan att röra sig. Antag att alla partiklarna konvergerar mot ett felaktigt tillstånd, eller om en ockult hand tar upp roboten och flyttar den till en ny plats efter att partiklarna redan har konvergerat. Eftersom partiklar långt borta från det konvergerade tillståndet sällan väljs ut för nästa iteration, blir de knappare vid varje iteration tills de försvinner helt. Vid denna tidpunkt kan algoritmen inte återställas. Detta problem är mer sannolikt att uppstå för ett litet antal partiklar, t.ex. ${\displaystyle M\leq 50} ,$ och när partiklarna sprids över ett stort tillståndsutrymme. Faktum är att vilken partikelfilteralgoritm som helst kan av misstag kasta alla partiklar nära korrekt tillstånd under omsamplingssteget.

Ett sätt att lindra detta problem är att slumpmässigt lägga till extra partiklar vid varje iteration. Detta motsvarar att anta att roboten när som helst har en liten sannolikhet att bli kidnappad till en slumpmässig position på kartan, vilket orsakar en bråkdel av slumpmässiga tillstånd i rörelsemodellen. Genom att garantera att inget område på kartan är helt berövat partiklar, är algoritmen nu robust mot partikelberövande.

Varianter

Den ursprungliga Monte Carlo-lokaliseringsalgoritmen är ganska enkel. Flera varianter av algoritmen har föreslagits, som åtgärdar dess brister eller anpassar den för att vara mer effektiv i vissa situationer.

KLD-provtagning

Monte Carlo-lokalisering kan förbättras genom att ta prov på partiklarna på ett adaptivt sätt baserat på en feluppskattning med användning av Kullback–Leibler-divergensen (KLD). Inledningsvis är det nödvändigt att använda en stor $M$ på grund av behovet av att täcka hela kartan med en jämnt slumpmässig fördelning av partiklar. Men när partiklarna har konvergerat runt samma plats är det beräkningsmässigt slösaktigt att upprätthålla en så stor provstorlek.

beräknas en provstorlek ${\displaystyle M_{x}} .$ Sampelstorleken $M_{x}$ beräknas så att, med sannolikheten ${\displaystyle 1-\delta } ,$ felet mellan den sanna bakre och den provbaserade approximationen är mindre än ${\ displaystyle \epsilon }$ . Variablerna $\delta$ och $\epsilon$ är fasta parametrar.

Huvudidén är att skapa ett rutnät (ett histogram) överlagrat på tillståndsutrymmet. Varje fack i histogrammet är initialt tomt. Vid varje iteration dras en ny partikel från den tidigare (vägda) partikeluppsättningen med sannolikhet proportionell mot dess vikt. Istället för omsamplingen som görs i klassisk MCL, drar KLD-samplingsalgoritmen partiklar från den tidigare, viktade, partikeluppsättningen och tillämpar rörelse- och sensoruppdateringarna innan partikeln placeras i sin behållare. Algoritmen håller reda på antalet icke-tomma fack, $k$ . Om en partikel infogas i en tidigare tom behållare, räknas värdet på ${\displaystyle M_{x}} om, vilket ökar mestadels linjärt i$$k$ . Detta upprepas tills provstorleken $M$ är densamma som $M_{x}$ .

Det är lätt att se KLD–sampling tar bort redundanta partiklar från partikeluppsättningen, genom att bara öka $M_{x}$ när en ny plats (bin) har fyllts. I praktiken överträffar KLD-sampling konsekvent och konvergerar snabbare än klassisk MCL.