Share Email Print

Proceedings Paper

Formalization and implementation of topological visual navigation in two dimensions
Author(s): John R. Kender; Il-Pyung Park; David Yang
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

In this paper we formalize and implement a model of topological visual navigation in two-dimensional spaces. Unlike much of traditional quantitative visual navigation the emphasis throughout is on the methods and the efficiency of qualitative visual descriptions of objects and environments and on the methods and the efficiency of direction-giving by means of visual landmarks. We formalize three domainsthe world itself the map-maker''s view of it and the navigator''s experience of itand the concepts of custom maps and landmarks. We specify for a simplified navigator (the " level helicopter" ) the several ways in which visual landmarks can be chosen depending on which of several costs (sensor distance or communication) should be minimized. We show that paths minimizing one measure can make others arbitrarily complex the algorithm for selecting the path is based on a form of Dijkstra''s algorithm and therefore automatically generates intelligent navigator overshooting and backtracking. We implement using an armheld camera such a navigator and detail its basic seek-and-adjust behaviors as it follows visual highways (or departs from them) to reach a goal. Seeking is based on topology and adjusting is based on symmetry there are essentially no quantitative measures. We describe under what circumstances its environment is visually difficult and perceptively shadowed and describe how errors in path-following impact landmark selection. Since visual landmark selection and direction-giving are in general NP-complete and rely on the nearly intractable

Paper Details

Date Published: 1 March 1991
PDF: 14 pages
Proc. SPIE 1388, Mobile Robots V, (1 March 1991); doi: 10.1117/12.25493
Show Author Affiliations
John R. Kender, Columbia Univ. (United States)
Il-Pyung Park, Columbia Univ. (United States)
David Yang, Columbia Univ. (United States)

Published in SPIE Proceedings Vol. 1388:
Mobile Robots V
Wendell H. Chun; William J. Wolfe, 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?