Planning Paths Through A Spatial Hierarchy: Eliminating Stair-Stepping Effects

Marc G. Slack

doi:10.1117/12.948949

5 January 1989 Planning Paths Through A Spatial Hierarchy: Eliminating Stair-Stepping Effects

Marc G. Slack

Proceedings Volume 1003, Sensor Fusion: Spatial Reasoning and Scene Interpretation; (1989) https://doi.org/10.1117/12.948949
Event: 1988 Cambridge Symposium on Advances in Intelligent Robotics Systems, 1988, Boston, MA, United States

Abstract

Many of the current approaches toward the creation of an intelligent robotic system involve the creation and maintenance of an explicit world model. One such world model decomposes space into a hierarchical grid, representing spatial features of interest in high detail and those of lesser interest in lower detail. These models provide an effective interface for sensory information as well as an efficient mechanism for performing spatial inferences. Although hierarchical decompositions provide efficient representations of space, paths generated by planning systems operating within such representations tend to suffer from stair-stepping effects. Stair-stepping effects are a result of the loss of spatial continuity resulting from the decomposition of space into a grid. This paper presents a path planning algorithm which eliminates stair-stepping effects induced by the grid-based spatial representation. The algorithm exploits a hierarchical spatial model to efficiently plan paths for a mobile robot operating in dynamic domains. The spatial model and path planning algorithm map to a parallel machine, allowing the system to effectively operate incrementally, thereby accounting for unexpected events in the operating space.

Citation Download Citation

Marc G. Slack "Planning Paths Through A Spatial Hierarchy: Eliminating Stair-Stepping Effects", Proc. SPIE 1003, Sensor Fusion: Spatial Reasoning and Scene Interpretation, (5 January 1989); https://doi.org/10.1117/12.948949

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