Using uncertain sensing data to create reliable maps: an algorithm for exploring/mapping unknown graphlike worlds

Gregory Dudek; Paul Freedman; Souad Hadjres

doi:10.1117/12.143834

4 May 1993 Using uncertain sensing data to create reliable maps: an algorithm for exploring/mapping unknown graphlike worlds

Gregory Dudek, Paul Freedman, Souad Hadjres

Author Affiliations +

Proceedings Volume 1831, Mobile Robots VII; (1993) https://doi.org/10.1117/12.143834
Event: Applications in Optical Science and Engineering, 1992, Boston, MA, United States

Abstract

We describe an approach to the exploration and mapping of unknown environments using a mobile robot. This technique presupposes that the world can be described in terms of a fixed set of discrete locations or regions with an ordered set of paths between them. This is abstracted as a graph with a cyclic edge ordering. In previous work, it was shown that such worlds can be fully explored and described in limited complexity using a single movable marker (like a pebble) even if there are no spatial metrics and almost no sensory ability on the part of the robot [Dudek et al. 1991]. Here we present an approach to the exploration of unknown worlds without such a moveable marker. Locations in the world are identified by a non-unique 'signature' that serves as an abstraction for a percept that might be obtained from a robotic sensor. While the signature of any single location may not be unique, under appropriate conditions the distinctiveness of a particular set of signatures in a neighborhood increases with neighborhood size. By using a collection of non-unique local signatures we can thereby construct an 'extended' signature that uniquely determines the robot's position (although in certain degenerate worlds, additional information is also required). The algorithm makes use of no metric information such as the distances of the paths traversed, but the availability of such measurements would simplify the mapping problem.

Citation Download Citation

Gregory Dudek, Paul Freedman, and Souad Hadjres "Using uncertain sensing data to create reliable maps: an algorithm for exploring/mapping unknown graphlike worlds", Proc. SPIE 1831, Mobile Robots VII, (4 May 1993); https://doi.org/10.1117/12.143834

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
11 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Mobile robots

Associative arrays

Sensors

Robotics

3D modeling

Data modeling

Cognition

Show All Keywords

Keywords/Phrases

Search In:

Publication Years