This thesis is concerned with algorithms for finding natural features that are then used for simultaneous localisation and mapping, commonly known as SLAM in navigation theory. The task involves capturing raw sensory inputs, extracting features from these inputs and using the features for mapping and localising during navigation. The ability to extract natural features allows automatons such as robots to be sent to environments where no human beings have previously explored working in a way that is similar to how human beings understand and remember where they have been. In extracting natural features using images, the way that features are represented and matched is a critical issue in that the computation involved could be wasted if the wrong method is chosen. While there are many techniques capable of matching pre-defined objects correctly, few of them can be used for real-time navigation in an unexplored environment, intelligently deciding on what is a relevant feature in the images. Normally, feature analysis that extracts relevant features from an image is a 2-step process, the steps being firstly to select interest points and then to represent these points based on the local region properties. A novel technique is presented in this thesis for extracting a small enough set of natural features robust enough for navigation purposes. The technique involves a 3-step approach. The first step involves an interest point selection method based on extrema of difference of Gaussians (DOG). The second step applies Textural Feature Analysis (TFA) on the local regions of the interest points. The third step selects the distinctive features using Distinctness Analysis (DA) based mainly on the probability of occurrence of the features extracted. The additional step of DA has shown that a significant improvement on the processing speed is attained over previous methods. Moreover, TFA / DA has been applied in a SLAM configuration that is looking at an underwater environment where texture can be rich in natural features. The results demonstrated that an improvement in loop closure ability is attained compared to traditional SLAM methods. This suggests that real-time navigation in unexplored environments using natural features could now be a more plausible option.

Thesis (M.S. in Management)--Naval Postgraduate School, June 1990. / Thesis Advisor(s): McMasters, Alan W. ; Bailey, Michael P. "June 1990." Description based on signature page as viewed on October 21, 2009. DTIC Identifier(s): Computerized simulation, logistics management. Author(s) subject terms: Multi-echelon, simulation, SLAM II, models. Includes bibliographical references (p. 142-147). Also available in print.

Thesis (MSc)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: In this thesis we consider the problem of building a dense and consistent map of a mobile robot’s environment that is updated as the robot moves. Such maps are vital for safe and collision-free navigation. Measurements obtained from a range sensor mounted on the robot provide information on the structure of the environment, but are typically corrupted by noise. These measurements are also relative to the robot’s unknown pose (location and orientation) and, in order to combine them into a world-centric map, pose estimation is necessary at every time step. A SLAM system can be used for this task. However, since landmark measurements and robot motion are inherently noisy, the pose estimates are typically characterized by uncertainty. When building a map it is essential to deal with the uncertainties in range measurements and pose estimates in a principled manner to avoid overconfidence in the map. A literature review of robotic mapping algorithms reveals that the occupancy grid mapping algorithm is well suited for our goal. This algorithm divides the area to be mapped into a regular lattice of cells (squares for 2D maps or cubes for 3D maps) and maintains an occupancy probability for each cell. Although an inverse sensor model is often employed to incorporate measurement uncertainty into such a map, many authors merely state or depict their sensor models. We derive our model analytically and discuss ways to tailor it for sensor-specific uncertainty. One of the shortcomings of the original occupancy grid algorithm is its inability to convey uncertainty in the robot’s pose to the map. We address this problem by altering the occupancy grid update equation to include weighted samples from the pose uncertainty distribution (provided by the SLAM system). The occupancy grid algorithm has been criticized for its high memory requirements. Techniques have been proposed to represent the map as a region tree, allowing cells to have different sizes depending on the information received for them. Such an approach necessitates a set of rules for determining when a cell should be split (for higher resolution in a local region) and when groups of cells should be merged (for lower resolution). We identify some inconsistencies that can arise from existing rules, and adapt those rules so that such errors are avoided. We test our proposed adaptive occupancy grid algorithm, that incorporates both measurement and pose uncertainty, on simulated and real-world data. The results indicate that these uncertainties are included effectively, to provide a more informative map, without a loss in accuracy. Furthermore, our adaptive maps need far fewer cells than their regular counterparts, and our new set of rules for deciding when to split or merge cells significantly improves the ability of the adaptive grid map to mimic its regular counterpart. / AFRIKAANSE OPSOMMING: In hierdie tesis beskou ons die probleem om ’n digte en konsekwente kaart van ’n mobiele robot se omgewing te bou, wat opgedateer word soos die robot beweeg. Sulke kaarte is van kardinale belang vir veilige, botsingvrye navigasie. Metings verkry vanaf ’n sensor wat op die robot gemonteer is, verskaf inligting rakende die struktuur van die omgewing, maar word tipies deur ruis vervorm. Hierdie metings is ook relatief tot die robot se onbekende postuur (posisie en oriëntasie) en, om hulle saam te voeg in ’n wêreldsentriese kaart, is postuurafskatting nodig op elke tydstap. ’n SLAM stelsel kan vir hierdie doeleinde gebruik word. Aangesien landmerkmetings en die beweging van die robot inherent ruiserig is, word die postuurskattings gekarakteriseer deur onsekerheid. Met die bou van ’n kaart moet hierdie onsekerhede in afstandmetings en postuurskattings op ’n beginselvaste manier hanteer word om te verhoed dat te veel vertroue in die kaart geplaas word. ’n Literatuurstudie van karteringsalgoritmes openbaar die besettingsroosteralgoritme as geskik vir ons doel. Die algoritme verdeel die gebied wat gekarteer moet word in ’n reëlmatige rooster van selle (vierkante vir 2D kaarte of kubusse vir 3D kaarte) en onderhou ’n besettingswaarskynlikheid vir elke sel. Alhoewel ’n inverse sensormodel tipies gebruik word om metingsonsekerheid in so ’n kaart te inkorporeer, noem of wys baie outeurs slegs hulle model. Ons herlei ons model analities en beskryf maniere om sensorspesifieke metingsonsekerheid daarby in te sluit. Een van die tekortkominge van die besettingsroosteralgoritme is sy onvermoë om onsekerheid in die postuur van die robot na die kaart oor te dra. Ons spreek hierdie probleem aan deur die opdateringsvergelyking van die oorspronklike besettingsroosteralgoritme aan te pas, om geweegde monsters van die postuuronsekerheidsverdeling (verskaf deur die SLAM stelsel) in te sluit. Die besettingsroosteralgoritme word soms gekritiseer vir sy hoë verbruik van geheue. Tegnieke is voorgestel om die kaart as ’n gebiedsboom voor te stel, wat selle toelaat om verskillende groottes te hê, afhangende van die inligting wat vir hulle verkry is. So ’n benadering noodsaak ’n stel reëls wat spesifiseer wanneer ’n sel verdeel (vir ’n hoër resolusie in ’n plaaslike gebied) en wanneer ’n groep selle saamgevoeg (vir ’n laer resolusie) word. Ons identifiseer teenstrydighede wat kan voorkom as die huidige reëls gevolg word, en pas hierdie reëls aan sodat sulke foute vermy word. Ons toets ons voorgestelde aanpasbare besettingsroosteralgoritme, wat beide metings- en postuuronsekerheid insluit, op gesimuleerde en werklike data. Die resultate dui daarop dat hierdie onsekerhede op ’n effektiewe wyse na die kaart oorgedra word sonder om akkuraatheid prys te gee. Wat meer is, ons aanpasbare kaarte benodig heelwat minder selle as hul reëlmatige eweknieë. Ons nuwe stel reëls om te besluit wanneer selle verdeel of saamgevoeg word, veroorsaak ook ’n merkwaardige verbetering in die vermoë van die aanpasbare roosterkaart om sy reëlmatige eweknie na te boots.

Many applications for field robots can benefit from large numbers of robots, especially applications where the objective is for the robots to cover or explore a region. A key enabling technology for robust autonomy in these teams of small and cheap robots is the development of collaborative perception to account for the shortcomings of the small and cheap sensors on the robots. In this dissertation, I present DDF-SAM to address the decentralized data fusion (DDF) inference problem with a smoothing and mapping (SAM) approach to single-robot mapping that is online, scalable and consistent while supporting a variety of sensing modalities. The DDF-SAM approach performs fully decentralized simultaneous localization and mapping in which robots choose a relevant subset of variables from their local map to share with neighbors. Each robot summarizes their local map to yield a density on exactly this chosen set of variables, and then distributes this summarized map to neighboring robots, allowing map information to propagate throughout the network. Each robot fuses summarized maps it receives to yield a map solution with an extended sensor horizon. I introduce two primary variations on DDF-SAM, one that uses a batch nonlinear constrained optimization procedure to combine maps, DDF-SAM 1.0, and one that uses an incremental solving approach for substantially faster performance, DDF-SAM 2.0. I validate these systems using a combination of real-world and simulated experiments. In addition, I evaluate design trade-offs for operations within DDF-SAM, with a focus on efficient approximate map summarization to minimize communication costs.