Samtidig lokalisering og kortlægning - Simultaneous localization and mapping

2005 DARPA Grand Challenge -vinder STANLEY udførte SLAM som en del af sit autonome køresystem

Et kort genereret af en SLAM Robot.

Samtidig lokalisering og kortlægning ( SLAM ) er beregningsproblemet med at konstruere eller opdatere et kort over et ukendt miljø og samtidig holde styr på agentens placering i det. Selvom dette i første omgang ser ud til at være et kylling-og-æg-problem, er der kendt flere algoritmer til at løse det, i det mindste cirka, i håndterbar tid i visse miljøer. Populære omtrentlige løsningsmetoder inkluderer partikelfilter , forlænget Kalman -filter , kovariansekryds og GraphSLAM . SLAM -algoritmer er baseret på begreber inden for beregningsgeometri og computersyn og bruges i robotnavigering , robotkortlægning og kilometertælling til virtual reality eller augmented reality .

SLAM -algoritmer er skræddersyet til de tilgængelige ressourcer, derfor ikke rettet mod perfektion, men til driftsoverensstemmelse. Offentliggjorte fremgangsmåder anvendes i selvkørende biler , ubemandede luftfartøjer , autonome undervandsbiler , planetariske rovere , nyere indenlandske robotter og endda inde i menneskekroppen.

Matematisk beskrivelse af problemet

I betragtning af en række kontroller og sensorobservationer over diskrete tidstrin er SLAM -problemet at beregne et skøn over agentens tilstand og et kort over miljøet . Alle størrelser er normalt sandsynlige, så målet er at beregne: ${\ displaystyle u_ {t}}$${\ displaystyle o_ {t}}$${\ displaystyle t}$${\ displaystyle x_ {t}}$${\ displaystyle m_ {t}}$

${\ displaystyle P (m_ {t+1}, x_ {t+1} | o_ {1: t+1}, u_ {1: t})}$

Anvendelse af Bayes 'regel giver en ramme for sekventiel opdatering af placeringen posteriors, givet et kort og en overgangsfunktion , ${\ displaystyle P (x_ {t} | x_ {t-1})}$

${\ displaystyle P (x_ {t} | o_ {1: t}, u_ {1: t}, m_ {t}) = \ sum _ {m_ {t-1}} P (o_ {t} | x_ { t}, m_ {t}, u_ {1: t}) \ sum _ {x_ {t-1}} P (x_ {t} | x_ {t-1}) P (x_ {t-1} | m_ {t}, o_ {1: t-1}, u_ {1: t})/Z}$

På samme måde kan kortet opdateres sekventielt af

${\ displaystyle P (m_ {t} | x_ {t}, o_ {1: t}, u_ {1: t}) = \ sum _ {x_ {t}} \ sum _ {m_ {t}} P ( m_ {t} | x_ {t}, m_ {t-1}, o_ {t}, u_ {1: t}) P (m_ {t-1}, x_ {t} | o_ {1: t-1 }, m_ {t-1}, u_ {1: t})}$

Ligesom mange slutningsproblemer kan løsningerne til at udlede de to variabler sammen findes til en lokal optimal løsning ved at skiftevis opdaterer de to overbevisninger i en form for en forventning -maksimaliseringsalgoritme .

Algoritmer

Statistiske teknikker, der bruges til at tilnærme ovenstående ligninger, omfatter Kalman -filtre og partikelfiltre (også kaldet Monte Carlo -metoder ). De giver et estimat af den posterior sandsynlighedsfunktion for robotens stilling og for parametrene på kortet. Metoder, der konservativt tilnærmer ovenstående model ved hjælp af kovariansekryds, er i stand til at undgå afhængighed af statistiske uafhængighedsforudsætninger for at reducere algoritmisk kompleksitet for store applikationer. Andre tilnærmelsesmetoder opnår forbedret beregningseffektivitet ved at bruge simple afgrænsede områdesrepræsentationer af usikkerhed.

Set-medlemskabsteknikker er hovedsageligt baseret på spredning af intervalbegrænsninger . De giver et sæt, der omslutter robotens pose og en fast tilnærmelse af kortet. Bundlejustering og mere generelt Maximum a posteriori estimation (MAP) er en anden populær teknik til SLAM ved hjælp af billeddata, som i fællesskab estimerer poser og skelsættende positioner, øger kortfidelitet og bruges i kommercialiserede SLAM -systemer som f.eks. Googles ARCore, der erstatter deres tidligere augmented reality -projekt ' Tango '. MAP -estimatorer beregner den mest sandsynlige forklaring på robotposerne og kortet givet sensordata, frem for at forsøge at estimere hele den bageste sandsynlighed.

Nye SLAM -algoritmer forbliver et aktivt forskningsområde og er ofte drevet af forskellige krav og antagelser om typer af kort, sensorer og modeller som beskrevet nedenfor. Mange SLAM -systemer kan ses som en kombination af valgmuligheder fra hvert af disse aspekter.

Kortlægning

Topologiske kort er en metode til repræsentation af miljøet, der fanger forbindelsessystemet (dvs. topologi ) af miljøet frem for at skabe et geometrisk nøjagtigt kort. Topologiske SLAM -tilgange er blevet brugt til at håndhæve global konsistens i metriske SLAM -algoritmer.

I modsætning hertil bruger gitterkort arrays (typisk firkantede eller sekskantede) af diskretiserede celler til at repræsentere en topologisk verden og foretage konklusioner om, hvilke celler der er optaget. Cellerne antages typisk at være statistisk uafhængige for at forenkle beregningen. Under en sådan antagelse sættes til 1, hvis det nye korts celler er i overensstemmelse med observationen på stedet og 0, hvis de er inkonsekvente. ${\ displaystyle P (m_ {t} | x_ {t}, m_ {t-1}, o_ {t})}$${\ displaystyle o_ {t}}$${\ displaystyle x_ {t}}$

Moderne selvkørende biler forenkler for det meste kortlægningsproblemet til næsten ingenting ved at gøre omfattende brug af meget detaljerede kortdata indsamlet på forhånd. Dette kan omfatte kortanmærkninger til niveauet for markering af individuelle hvide linjesegmenter og kantsten på vejen. Placeringsmærkede visuelle data, f.eks. Googles StreetView, kan også bruges som en del af kort. I det væsentlige forenkler sådanne systemer SLAM -problemet til en enklere lokaliseringsopgave , hvilket muligvis kun gør det muligt at opdatere bevægelige objekter som f.eks. Biler og mennesker på kortet ved kørsel.

Sensing

Akkumuleret registreret punktsky fra lidar SLAM.

SLAM vil altid bruge flere forskellige typer sensorer, og kræfterne og grænserne for forskellige sensortyper har været en vigtig drivkraft for nye algoritmer. Statistisk uafhængighed er det obligatoriske krav for at klare metrisk bias og støj i målinger. Forskellige typer sensorer giver anledning til forskellige SLAM -algoritmer, hvis antagelser er mest passende for sensorerne. I den ene ende giver laserscanninger eller visuelle funktioner detaljer om mange punkter inden for et område, nogle gange er SLAM -slutning unødvendig, fordi former i disse punktskyer let og entydigt kan justeres i hvert trin via billedregistrering . I den modsatte ekstreme er taktile sensorer ekstremt sparsomme, da de kun indeholder oplysninger om punkter meget tæt på agenten, så de kræver stærke tidligere modeller for at kompensere i rent taktil SLAM. De fleste praktiske SLAM -opgaver falder et sted mellem disse visuelle og taktile ekstremer.

Sensormodeller deler sig stort set i milepælsbaserede og rådata-metoder. Landemærker er entydigt identificerbare objekter i verden, hvis placering kan estimeres af en sensor - såsom wifi -adgangspunkter eller radiofyr. Rådatatilgange antager ikke, at vartegn kan identificeres og i stedet modelleres direkte som en funktion af placeringen. ${\ displaystyle P (o_ {t} | x_ {t})}$

Optiske sensorer kan være endimensionelle (enkeltstråle) eller 2D- (fejende) laserafstandsmålere , 3D High Definition LiDAR, 3D Flash LIDAR , 2D eller 3D sonarsensorer og et eller flere 2D- kameraer . Siden 2005 har der været intens undersøgelse af VSLAM (visual SLAM), der primært anvender visuelle (kamera) sensorer på grund af den stigende allestedsnærværende kameraer som dem i mobile enheder. Visuelle og LIDAR -sensorer er informative nok til i mange tilfælde at muliggøre milepælsekstraktion. Andre nylige former for SLAM inkluderer taktil SLAM (kun sensing ved lokal berøring), radar SLAM, akustisk SLAM og wifi-SLAM (sensing ved styrker ved nærliggende wifi-adgangspunkter). Nylige tilgange anvender kvasi-optisk trådløs rækkevidde til multilaterering ( RTLS ) eller multivinkling i forbindelse med SLAM som en hyldest til uregelmæssige trådløse foranstaltninger. En slags SLAM til menneskelige fodgængere bruger en sko -monteret inertial måleenhed som hovedsensor og er afhængig af, at fodgængere er i stand til at undgå vægge til automatisk at bygge plantegninger af bygninger ved hjælp af et indendørs positioneringssystem .

For nogle udendørs applikationer er behovet for SLAM næsten helt fjernet på grund af differentierede GPS -sensorer med høj præcision . Fra et SLAM -perspektiv kan disse ses som placeringssensorer, hvis sandsynlighed er så skarp, at de fuldstændigt dominerer slutningen. GPS -sensorer kan dog lejlighedsvis falde eller falde helt, f.eks. I tider med militær konflikt, som er af særlig interesse for nogle robotapplikationer.

Kinematik modellering

Den Betegnelsen repræsenterer kinematik modellen, som normalt indeholder oplysninger om action-kommandoer givet til en robot. Som en del af modellen er robotens kinematik inkluderet for at forbedre estimater af sansning under betingelser for iboende og omgivende støj. Den dynamiske model afbalancerer bidragene fra forskellige sensorer, forskellige delvise fejlmodeller og omfatter til sidst i en skarp virtuel skildring som et kort med robotens placering og overskrift som en sandsynlighedssky. Kortlægning er den sidste skildring af en sådan model, kortet er enten en sådan skildring eller det abstrakte udtryk for modellen. ${\ displaystyle P (x_ {t} | x_ {t-1})}$

For 2D -robotter er kinematikken normalt givet ved en blanding af rotation og "fremad" kommandoer, som implementeres med yderligere motorstøj. Desværre er fordelingen dannet af uafhængig støj i vinkel- og lineære retninger ikke-gaussisk, men tilnærmes ofte af en gaussisk. En alternativ tilgang er at ignorere det kinematiske udtryk og læse kilometertællingsdata fra robothjul efter hver kommando - sådanne data kan derefter behandles som en af ​​sensorerne frem for som kinematik.

Akustisk SLAM

En forlængelse af det fælles SLAM-problem er blevet anvendt på det akustiske domæne, hvor miljøer repræsenteres af lydkildernes tredimensionelle (3D) position, betegnet. Tidlige implementeringer af denne teknik har benyttet Direction-of-Arrival (DoA) estimater af lydkildens placering og er afhængige af hovedteknikker til lydlokalisering til at bestemme kildeplaceringer. En observatør eller robot skal være udstyret med et mikrofonarray for at muliggøre brug af Acoustic SLAM, så DoA -funktioner estimeres korrekt. Akustisk SLAM har banet grundlag for yderligere undersøgelser af akustisk scenekortlægning og kan spille en vigtig rolle i interaktion mellem mennesker og robotter gennem tale. For at kortlægge flere og lejlighedsvis intermitterende lydkilder anvender et akustisk SLAM -system fundamentet i Random Finite Set -teorien til at håndtere den varierende tilstedeværelse af akustiske vartegn. Imidlertid efterlader arten af ​​akustisk afledte funktioner Acoustic SLAM modtagelige for problemer med efterklang, inaktivitet og støj i et miljø.

Audiovisuel SLAM

Oprindeligt designet til interaktion mellem mennesker og robot , er Audio-Visual SLAM en ramme, der giver sammensmeltning af skelsættende funktioner opnået fra både de akustiske og visuelle modaliteter i et miljø. Menneskelig interaktion er kendetegnet ved træk, der opfattes i ikke kun den visuelle modalitet, men også den akustiske modalitet; som sådan skal SLAM-algoritmer til menneskecentrerede robotter og maskiner tage højde for begge sæt funktioner. En audiovisuel ramme estimerer og kortlægger positioner for menneskelige vartegn ved hjælp af visuelle funktioner som menneskelig positur og lydfunktioner som menneskelig tale og smelter troen sammen til et mere robust kort over miljøet. Til applikationer inden for mobil robotik (f.eks. Droner, servicerobotter) er det værdifuldt at bruge lavt strømudstyr, let udstyr såsom monokulære kameraer eller mikroelektroniske mikrofonarrays. Audio-Visual SLAM kan også give mulighed for gratis funktion af sådanne sensorer ved at kompensere for det smalle synsfelt, funktionens okklusioner og optiske nedbrydninger, der er almindelige for lette visuelle sensorer med det fulde synsfelt og uhindrede funktionsrepræsentationer, der er forbundet med lydsensorer. Lydsensorers modtagelighed for efterklang, lydkildens inaktivitet og støj kan også derfor kompenseres ved fusion af skelsættende overbevisninger fra den visuelle modalitet. Gratis funktion mellem lyd- og visuelle metoder i et miljø kan vise sig værdifuld for skabelsen af ​​robotik og maskiner, der fuldt ud interagerer med menneskelig tale og menneskelig bevægelse.

Kollaborativ SLAM

Collaborative SLAM kombinerer billeder fra flere robotter eller brugere til at generere 3D -kort.

Objekter i bevægelse

Ikke-statiske miljøer, f.eks. Dem, der indeholder andre køretøjer eller fodgængere, frembyder fortsat forskningsudfordringer. SLAM med DATMO er en model, der sporer bevægelige objekter på lignende måde som selve agenten.

Sløjfe lukning

Sløjfe lukning er problemet med at genkende en tidligere besøgt lokation og opdatere overbevisninger i overensstemmelse hermed. Dette kan være et problem, fordi model- eller algoritmefejl kan tildele lav prioritet til placeringen. Typiske loop-lukningsmetoder anvender en anden algoritme til at beregne en slags sensormålelighed og genindstille placeringsprioriteterne, når der opdages en match. For eksempel kan dette gøres ved at lagre og sammenligne pose af ordvektorer af SIFT -funktioner fra hvert tidligere besøgte sted.

Udforskning

"Active SLAM" studerer det kombinerede problem med SLAM med at beslutte, hvor man skal flytte næste gang for at bygge kortet så effektivt som muligt. Behovet for aktiv efterforskning er især udtalt i sparsomme sansningsregimer såsom taktil SLAM. Aktiv SLAM udføres generelt ved at tilnærme kortets entropi under hypotetiske handlinger. "Multi agent SLAM" udvider dette problem til flere robotter, der koordinerer sig selv for at udforske optimalt.

Biologisk inspiration

Inden for neurovidenskaben ser hippocampus ud til at være involveret i SLAM-lignende beregninger, hvilket giver anledning til placeringsceller og har dannet grundlaget for bioinspirerede SLAM-systemer såsom RatSLAM.

Implementeringsmetoder

Forskellige SLAM-algoritmer er implementeret i open-source robotoperativsystembiblioteker (ROS), der ofte bruges sammen med Point Cloud-biblioteket til 3D-kort eller visuelle funktioner fra OpenCV .

EKF SLAM

Inden for robotik er EKF SLAM en klasse af algoritmer, der anvender det udvidede Kalman -filter (EKF) til SLAM. Typisk er EKF SLAM -algoritmer funktionsbaserede og bruger den maksimale sandsynlighedsalgoritme til dataforening. I 1990'erne og 2000'erne havde EKF SLAM været de facto -metoden for SLAM, indtil introduktionen af FastSLAM .

Tilknyttet EKF er den gaussiske støjantagelse, som i væsentlig grad forringer EKF SLAMs evne til at håndtere usikkerhed. Med større usikkerhed i det bageste, mislykkes lineariseringen i EKF.

GraphSLAM

I robotteknik , GraphSLAM er en SLAM algoritme, der anvender sparsomme information matricer fremstillet ved at generere en faktor graf af observation indbyrdes afhængighed (to observationer relateret hvis de indeholder data om samme skelsættende).

Historie

Et banebrydende arbejde i SLAM er forskningen fra RC Smith og P. Cheeseman om repræsentation og estimering af rumlig usikkerhed i 1986. Andet pionerarbejde på dette område blev udført af forskergruppen Hugh F. Durrant-Whyte i begyndelsen af ​​1990'erne. som viste, at der findes løsninger til SLAM i den uendelige datagrænse. Dette fund motiverer søgningen efter algoritmer, der er beregningsmæssigt overførbare og tilnærmelsesvis løsningen. Akronymet SLAM blev opfundet i papiret, "Localization of Autonomous Guided Vehicles", der først optrådte i ISR i 1995.

De selvkørende STANLEY- og JUNIOR-biler, ledet af Sebastian Thrun , vandt DARPA Grand Challenge og blev nummer to i DARPA Urban Challenge i 2000'erne og inkluderede SLAM-systemer, der bragte SLAM til verdensomspændende opmærksomhed. Massemarkeds SLAM-implementeringer kan nu findes i forbrugerrobotstøvsugere.

Se også

Referencer

Eksterne links

• Probabilistic Robotics af Sebastian Thrun , Wolfram Burgard og Dieter Fox med et klart overblik over SLAM.
• SLAM For Dummies (En vejledning til samtidig lokalisering og kortlægning) .
• Andrew Davison forskningsside ved Department of Computing , Imperial College London om SLAM ved hjælp af vision.
• openslam.org En god samling af open source -kode og forklaringer på SLAM.
• Matlab Toolbox med Kalman -filtrering anvendes til samtidig lokalisering og kortlægning af køretøjer, der kører i 1D, 2D og 3D.
• FootSLAM forskningsside på DLR inklusive de relaterede Wifi SLAM og PlaceSLAM tilgange.
• SLAM -foredrag Online SLAM -foredrag baseret på Python.