Share Email Print

Proceedings Paper

Using uncertain sensing data to create reliable maps: an algorithm for exploring/mapping unknown graphlike worlds
Author(s): Gregory Dudek; Paul Freedman; Souad Hadjres
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 4 May 1993
PDF: 11 pages
Proc. SPIE 1831, Mobile Robots VII, (4 May 1993); doi: 10.1117/12.143834
Show Author Affiliations
Gregory Dudek, McGill Univ. (Canada)
Paul Freedman, Ctr. de Recherche Informatique de Montreal (Canada)
Souad Hadjres, McGill Univ. (Canada)

Published in SPIE Proceedings Vol. 1831:
Mobile Robots VII
William J. Wolfe; Wendell H. Chun, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?