Formalization and implementation of topological visual navigation in two dimensions

John R. Kender; Il-Pyung Park; David Yang

doi:10.1117/12.25493

1 March 1991 Formalization and implementation of topological visual navigation in two dimensions

John R. Kender, Il-Pyung Park, David Yang

Proceedings Volume 1388, Mobile Robots V; (1991) https://doi.org/10.1117/12.25493
Event: Advances in Intelligent Robotics Systems, 1990, Boston, MA, United States

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

Citation Download Citation

John R. Kender, Il-Pyung Park, and David Yang "Formalization and implementation of topological visual navigation in two dimensions", Proc. SPIE 1388, Mobile Robots V, (1 March 1991); https://doi.org/10.1117/12.25493

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