Abstract-This korrespondens beskriver en metod som spänner data från en sonar rangfinder kan användas för att bestämma den tvådimensionella positionen och orienteringen för en mobil robot inne i ett rum. Planen för rummet är modellerad som en lista över segment som anger väggarnas lägen. Algoritmen fungerar genom att korrelera raka segment i intervallet data mot rumsmodellen, sedan eliminera osannolika konfigurationer med hjälp av sonarbarriärtestet, som utnyttjar fysiska begränsningar på sonardata. Metoden är extremt tolerant mot buller och oreda. Övergående föremål som möbler och människor behöver inte ingå i rumsmodellen, och mycket bullriga sensorer med låg upplösning kan användas. Algoritmens prestanda demonstreras med hjälp av en Polaroid Ultrasonic Rangefinder. Index Terms-Mobile robotar, navigering, ekolod. Denna korrespondens behandlar problemet med att göra det möjligt för en mobil robot att bestämma sin position och orientering (sin konfiguration) inne i en byggnad på ett sätt som är oberoende av antaganden om tidigare rörelser. Denna förmåga kommer att kallas absolut lokalisering, eller helt enkelt lokalisering. Lokalisering är den direkta mätningen av fordonets position, i motsats till död räkning, eller bana integration, som deducerar fordonets position från dess hastighet historia. Hastighet mäts i förhållande till närliggande stationära föremål såsom marken. Eftersom de fel som man stöter på vid dödräkning är kumulativa, kommer en robot som navigerar enbart genom dödräkning till slut att förlora sin position. I slutändan kan detta förhindras endast genom periodiskt återupprättande av robotens absoluta position. Därför är ett sätt att lokalisera nödvändig för säker och tillförlitlig robotnavigering. Vissa lösningar på detta problem har föreslagits som kräver ändringar i miljön, såsom triangulering från infraröda beacons [4]. Det vore önskvärt att lösa problemet utan att ändra miljön. De flesta av de mobila robotnavigationssystem som utvecklats hittills, såsom [111, är i huvudsak döda beräkningsmetoder, som saknar någon möjlighet att periodvis lokalisera roboten. Sådana system skulle kunna dra nytta av lokaliseringen. I den metod för lokalisering som beskrivs i denna korrespondens är robotens miljö ett rum eller område inne i en byggnad. Miljön kan inkludera hela byggnaden. Robotens användare måste tillhandahålla en modell av rummet bestående av en lista över segment Manuskript mottagen 14 april 1985; reviderad 6 maj 1986. Rekommenderas för godkännande av R. Bajcsy. Detta arbete stöddes delvis av ett bidrag från Systemutvecklingsstiftelsen, och delvis av byrån för avancerade forskningsprojekt under Office of Naval Research Contracts N00014-80-C-0505 och N00014-82-K-0334. Författaren är med Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139. En del av detta arbete utfördes medan han var med Thinking Machines Corporation, 245 First Street, Cambridge, MA 02142. IEEE Loggnummer 8612401. som anger väggarnas placering. En sådan modell är lätt konstruerad av en arkitekts teckning. Den avståndsmätare som används i detta papper är en Polaroid Ultrasonic Rangefinder, men alla avståndsmätare kan användas (se t.ex. [7], [8], [9], och [14] ). Vi kallar ultraljudsspår för sonar. Den slutna konturen som erhålls genom en 360-graders svepning med en ekolodssignal kommer att kallas en ekolodskontur. De linjer som dras från robotens position till de enskilda datapunkterna i ekolodskonturen representerar individuella avståndsavläsningar och kallas ekolodsstrålar. Bilda.  1 visar en typisk rumskontur, en typisk ekolodskontur som erhålls inifrån rummet, och motsvarande lokalisering som bestäms av algoritmen. De senaste dokumenten [3], [5] och [6] har infört en ny metod för objektigenkänning och lokalisering som bygger på utnyttjande av enkla geometriska begränsningar mellan avkännade data och en modell. Avsnitt II-D baseras till stor del på algoritmen av Grimson och Lozano-Perez, som beskrivs i [6]. Den största skillnaden mellan avsnitt II-D och dessa papper är användningen av sonarsegment, som är raka segment extraherade från en ekolodskontur, i stället för position/normal-vektorpar, som de primära ingångarna till algoritmen. Denna korrespondens introducerar en ny idé som kallas sonarbarriärtest i avsnitt II-E. Sonarbarriären kontrollerar den fysiska konsistensen genom att avgöra om formen på en ekolodskontur för en föreslagen lokalisering överensstämmer med det faktum att ekolod inte tränger igenom fasta föremål. Om en inkonsekvens upptäcks, förkastas den föreslagna lokaliseringen. Sonarbarriärtestet gör algoritmens prestanda överlägsen det som kunde uppnås med hjälp av endast Grimson- och Lozano-Perez-algoritmen. Miller [10] beskriver också en strategi för robotlokalisering med hjälp av sonar, enligt metoderna Gaston, Grimson och LozanoPerez. Den metod som beskrivs i [10] använder enstaka sonarstrålar i stället för större datafunktioner som de primära ingångarna till algoritmen, och den använder en annan uppsättning lokala geometriska begränsningar. Inget jämförbart med sonarbarriärtestet presenteras. Vårt tillvägagångssätt är att betrakta lokaliseringsprocessen som en tvådimensionell matchning (inklusive rotation) mellan ekolodets kontur och rummets kontur. Vi vill bestämma det geometriska förhållandet mellan roboten och rummet. Inställningen av roboten i förhållande till ekolodskonturen är alltid känd, så om vi bestämmer en möjlig konfiguration för ekolodskonturen i förhållande till För enkelhetens skull kommer vi hädanefter att klumpa radial- och vinkelfel tillsammans, och modellera deras kombination som oförutsägbar men avgränsad av ett konstant E. Således antar vi att placeringen av endpointen för en ekolodsstråle kan vara fel med så mycket som E. Värdet av E bestäms experimentellt; detta diskuteras i avsnittet Resultat. 2) Falska reflektioner: Baserat på den föregående diskussionen, kan man tycka att det är möjligt att extrahera en användbar approximation av rummet kontur från ekolod konturen. Detta kan göras med sonar skannar som erhållits från flera platser i hela rummet, som i [12]. Men en sådan metod går emot vårt syfte, vilket är att lokalisera roboten med hjälp av sonardata som erhållits från en enda plats i rummet, snarare än att konstruera en karta med hjälp av data från flera platser. Det är praktiskt taget omöjligt att få en användbar approximation av ett rum kontur från en enda position av dessa skäl: * oftast endast en liten del av ett rum är synlig från en enda position (detta gäller alla avståndsmätare), * sonar rangefinder avläsningar ofta innehåller extremt stora fel på grund av falska reflektioner. Falska reflektioner uppstår när sonarstrålens retums till avståndsmätaren efter att ha studsat av något annat objekt än det närmaste objektet i strålens väg. Denna effekt observeras mycket ofta och har följande förklaring. Pulsen från Polaroid-enheten har en frekvens på cirka 55 kHz och en våglängd på cirka en kvarts tum. Om inte den förnämda ytan har oegentligheter vars storlek är i samma ordning som denna våglängd, kan strålen reflekteras i stället för att spridas. I detta fall kan det antingen inte finnas något eko eller ett eko som produceras efter reflektion av något annat objekt än tho mål. Dessa falska reflektioner inträffar när strålens infallsvinkel är större än en kritisk angi 'y, som definierar konen av reflexion (CR) för ytan (se bild.   Fyra )............................................................................................................ En ekolod som träffar en vägg inifrån CR kommer att reflektera direkt tillbaka till sensorn. En stråle som träffar väggen utanför CR kommer att reflekteras bort från sensorn, vilket gör att strålen tydligen tränger igenom väggen. Ett exempel på denna effekt kan ses som den skarpa "hom" som sticker ut ur ekolodskonturen i Bild.  1................................................................ Varje ytmaterial har sin egen CR-halvvinkel, som kan variera från 7 eller 8 grader (för glas) till nästan 90 grader för grova ytor. Bilda. 1 visar hur en typisk ekolodskontur kan bära lite resem-326 IEEE TRANSAKTIONER PÅ PATTERN ANALYS OCH MACHINE INTEELLIGENCE, VOL. - Nej, det gör jag inte. 2, MARCH 1987 blanche, i global bemärkelse, till rummet. Detta faktum gör det osannolikt att en convolution-typ localization metod såsom i [12], skulle möta med mycket framgång med hjälp av data som erhållits från en enda position i rummet. B. Clutter En annan källa till fel som lokaliseringsmetoden måste övervinna är skräp, som hänvisar till något objekt som inte ingår i rumsmodellen. Clutter som möbler eller människor kan införa "falska väggar" som hindrar försök att matcha raka segment i ekolodskonturen med väggar i rumsmodellen. Vi kommer att visa att det tillvägagångssätt som beskrivs här är mycket effektivt när det gäller att ignorera oreda. En ekolodskontur består av 100 avståndsavläsningar, tagna från ett enda läge i rummet, med 3,6-graders vinkelintervall. Sensorn är monterad på en höjd av 5,5 meter på ett steppermotordrivet "huvud", som kan placera sensorn under datorstyrning. Den straight-line finder som används för att extrahera raka segment från en kontur är den iterativa endpoint passform [1]. Denna algoritm extraherar non overlapping contiguous subcontours som ungefärliga raka segment. (En sammanhängande underkontur är en grupp av ändpunkter för ekolodsstrålar som förekommer i följd i ekolodskonturen.) Algoritmen har två operativa parametrar, N och 6; den finner den uppsättning av längsta subcontours som innehåller minst N poäng och har ingen punkt längre än 6 från en linje genom slutpunkterna i subcontour. Objektigenkänningsalgoritmen av Grimson och Lozano-Perez En naiv expansion av IT skulle generera nk blad, där n är antalet väggar och k är antalet sonar segment. I princip skulle vi kunna generera alla nk blad och testa var och en för geometrisk konsistens. Detta skulle vara oöverkomligt dyrt och mycket slösaktigt med tanke på att endast en liten del av bladen kommer att vara till och med möjligt. Den metod som beskrivs i [6] beskär stora delträd från sökandet med hjälp av enkla lokala geometriska begränsningar. Till exempel i Fig. 5, När vi har tilldelat SI till W2, kan vi tilldela S2 till en annan vägg Wi endast om de relativa avstånden och orienteringarna för W2 och Wi liknar dem för SI och S2. En av de viktigaste aspekterna av tolkningsträdmetoden är tillägget av en null gren på varje nivå i IT. Valet av null grenen (eller nullväggen) på mth nivå i IT representerar möjligheten att mth sonar segent är dåliga data (clutter, buller, eller slumpmässig justering av ekolod ray endpoints), och bör därför inte paras med någon vägg. Man kan anta, a priori, att alla undergrupper av sonarsegmenten är dåliga data. Detta skulle återigen leda till ett ohanterligt antal blad i IT, eftersom många tolkningar som annars kunde förkastas skulle sparas genom att tilldela sina inkonsekventa segment till nollmuren. Därför, Grimson och Lozano-Perez algoritm tillämpar heuristic att anta så få dåliga datapunkter som möjligt. Under denna "minst dåliga data" begränsas endast de vägar som utlovar det största antalet icke-null uppdrag utforskas. I synnerhet, IT genomsöks djup först, och en väg överges om det inte kan leda till ett blad som innehåller färre null parnings än det bästa blad som redan hittats. Vi utnyttjar följande lokala begränsningar vid beskärning av tolkningsträdet: * Avstånd Restriktion: Omfattningen av möjliga avstånd mellan ett par ekolod segment, med hänsyn till sensorfel, måste överlappa intervallet av avstånd mellan de väggar som de tilldelas i en tolkning. * av sonar segment, med hänsyn till sensor fel, måste innehålla den kända vinkeln mellan de väggar som de tilldelas i en tolkning. (Vi antar att felet i ett sonarsegments orientering q begränsas av en konstant EO.) * Normal-Direction Restriktion: Detta är s., milar to the distance restrikt, förutom att avstånd mellan segment mäts endast längs segmentens normala vektorer. De lokala begränsningar som beskrivs ovan beskrivs närmare i [2], [3], [5] och [6]. Efter beskärning av IT med hjälp av enkla lokala begränsningar, kan vi tillämpa ett dyrare test för global geometrisk konsistens. Vi bestämmer (för varje överlevande tolkning) en översättning och en rotation av ekolod konturen som kommer att överlägga varje ekolod segment på väggen med vilken det är parat [3]. När vi har bestämt denna konfiguration, vi kontrollera om slutpunkterna för varje ekolod segment ligger inom E av dess tilldelade vägg, och om roboten har lokaliserats för att ligga inne i rummet. (Sådana globala förhållanden är inte alltid uppfyllda av lokala beskärningsbegränsningar.) Det finns ett sista test som varje överlevande tolkning måste klara: en tolkning får inte antyda att ekolodet tränger igenom några väggar inifrån sin reflexionskon. Bilda. 6 illustrerar detta. Efter att vi har beskärt tolkningsträdet är vi kvar med en uppsättning, som kan vara tom, av möjliga robotkonfigurationer. Till exempel i Fig. 6 * Om någon sådan ray finns, kasta tolkningen och lokaliseringen, eftersom de innebär en fysiskt omöjlig situation. Observera att den mängd med vilken en ekolodsstråle måste ligga utanför väggen inte nödvändigtvis är E. Vi har råd att använda en mindre fel bunden, kallad En (för "normalt fel"), eftersom vi kontrollerar felet av ekolodsstrålar som vi vet är nästan normal till en vägg (återkalla Avsnitt II-A-1). Programmet skulle vara mycket ineffektivt om det utförde sökandet efter "genomträngande strålar" på exakt det sätt som just beskrivits. Istället finner programmet först alla väggar som innehåller minst en punkt så att en stråle som dras från robotens plats till punkten ligger inom CR för väggen. Sen kontrollerar den bara ekolodsstrålarna som faller innanför CR:erna på väggarna. I lokaliseringen visas i bild. 7, till exempel, endast de väggar markerade i tung svart skulle användas i sonar barriär testet. Sonarbarriärtestet kan vara mycket effektivt för att eliminera felaktiga lokaliseringar som överlever beskärningen av tolkningsträdet. Tänk till exempel på ett fall där roboten ligger nära ett hörn i byggnaden. I detta fall bildar sonarsegmenten ofta ett litet L-format mönster. Detta arrangemang av ekolod segment hjälper inte att välja ett visst hörn i byggnaden, eftersom alla hörn är lokalt identiska. Resten av ekolodskonturen kan dock innehålla en hel del mindre tydlig information om rummets form. Sonarbarriärtestet är utformat för att använda denna information för att bestämma vilket hörn roboten upptar. 1) Maximal-kontakt Heuristic: I den sällsynta händelse att alla ovanstående förfaranden misslyckas med att producera en unik tolkning, då den tolkning som maximerar summan av längden av sonar segment i icke-null parningar väljs som det slutliga svaret. Denna åtgärd, som vi kallar den maximala kontakten heuristiska, uttrycker vår preferens för tolkningar baserade på långa sonarsegment, som är mindre benägna att vara dåliga data. Observera att det fortfarande är möjligt att göra flera tolkningar. Algoritmen som beskrivs i detta dokument har körts på riktiga ekolodsdata. Följande avsnitt beskriver några av resultaten från dessa experiment. Sonardata erhölls från tre olika rum i Artificial Intelligence Laboratory vid MIT. Rummets konturer visas i figurer. 8, 9 och 10. Bredvid varje rum kontur är ett fotografi taget inifrån rummet. Fotografierna är avsedda att ge läsaren en grov uppfattning om hur belamrade och "riktiga" dessa rum är. Robotens faktiska position mättes för hand med ett måttband och en protraktor; den är exakt inom en tum eller två och cirka 5 grader. I de figurer som följer, de överlevande tolkningar och deras motsvarande konfigurationer trycks di- rektly under varje ritning. Den faktiska konfigurationen skrivs också ut. Robotens faktiska konfiguration representeras grafiskt av konturen av en triangel med en liten cirkel inuti. Robotens ekolodsbestämda konfiguration representeras av en massiv vit triangel med ett kors i mitten. Noggrannheten av en lokalisering kan bedömas kvantitativt läsa de tryckta numeriska resultaten eller kvalitativt genom att inspektera anpassningen av de grafiska symbolerna. Siffrorna innehåller information om hur många tolkningar som eliminerades genom sonarbarriärtestet och den maximala kontaktheuristiska. Summan av dessa två tal plus ett är det totala antalet tolkningar som hittas med hjälp av endast Grimson och Lozano-Perez algoritm. N = 7 (minsta antal punkter i ett ekolodssegment), 6 = 0,5 ft (högsta vinkelräta avvikelse för punkter i ett ekolodssegment), y = 7 grader (halvvinkel i reflexionskonen), En = 0,7 ft (högsta fel för en ekolodsstråle som man vet är nästan vinkelrät mot en vägg). Denna uppsättning parametervärden användes för varje resultat som visas i denna korrespondens. Denna uppsättning kanske inte är optimal, eftersom den valdes baserat på en liten mängd experiment. Eftersom beteendet hos en sonar rangefinder är mycket svårt att förutsäga analytiskt, författaren anser att det mest effektiva sättet att bestämma en bra uppsättning av programparametrar är genom att testa programmet i stor utsträckning i miljön där det ska användas. eventuellt påträffas, nämligen ett glasfönster (för vilket 7y < 10 grader). Siffrorna i detta dokument är hämtade från en session med 24 program körs. Sjutton av dessa tester gav en lokalisering som var korrekt att inom en fot i vilken riktning som helst och cirka fem grader i riktning. Två lokaliseringar hade helt fel, d.v.s. de hade fel med mer än en fot. De fem ekolodskonturer som inte gav någon lokalisering misslyckades av en av dessa skäl: * ekolodskonturen innehöll mindre än två ekolodssegment, * ekolodssegmenten förenades med varandra parallella väggar. Vi har i våra experiment med algoritmen sett att det är osannolikt att en lokalisering baserad på en korrekt tolkning kommer att vara fel med en stor mängd. Detta innebär att döda fel lokala-liknande data funktioner med väggar i rumsmodellen, beskärning inkonsekvent parningar med hjälp av lokala geometriska begränsningar. Nyckeln till att avvisa felaktiga konfigurationer som består är att utnyttja globala geometriska begränsningar, som härrör från enkla fysiska lagar, på formen av en ekolodsområde contur. Sonarområdets data innehåller ofta extrema fel på grund av ljudutbredningens natur. På grund av detta representerar användningen av en sonarrangefinder, i någon mening, ett värsta scenario för lokalisering med avståndsdata. Även om algoritmen som beskrivs här är effektiv på att ignorera sådana fel, författaren anser att bättre prestanda kan uppnås genom användning av högupplösta avståndsmätare, såsom laserenheter beskrivs i [7] och [8]. Författaren vill tacka T. Lozano-Perez för hans insiktsfulla vägledning under författarens förarbete i detta ämne Också, tack till P. Gaston, E. Grimson, och T. Lozano-Perez för att utveckla de idéer som mycket av denna uppsats bygger på. [3] P. C. Gaston och T. Lozano-Perez, "Taktil igenkänning och lokalisering med hjälp av objektmodeller: REFERENSER
Innan relativt låg kostnad LiDAR blev tillgänglig, användes sonar för att observera en priori-line-baserade kartor över miljön REF.
Mobile Robot Localization Using Sonar
{'venue': 'IEEE Transactions on Pattern Analysis and Machine Intelligence', 'journal': 'IEEE Transactions on Pattern Analysis and Machine Intelligence', 'mag_field_of_study': ['Computer Science', 'Medicine']}