Sensor-based planning: exact cellular decompositions in terms of critical points

Howie M. Choset; Ercan Umut Acar; Alfred A. Rizzi; Jonathan E. Luntz

doi:10.1117/12.417302

2 March 2001 Sensor-based planning: exact cellular decompositions in terms of critical points

Howie M. Choset, Ercan Umut Acar, Alfred A. Rizzi, Jonathan E. Luntz

Proceedings Volume 4195, Mobile Robots XV and Telemanipulator and Telepresence Technologies VII; (2001) https://doi.org/10.1117/12.417302
Event: Intelligent Systems and Smart Manufacturing, 2000, Boston, MA, United States

Abstract

A coverage path planning algorithm produces a path that directs a robot (or its detector range, occupied volume, etc.) to sweep out a target volume. The goal of this work is to direct an agent to cover (fill) an unknown space using different coverage patterns. We achieve coverage by dividing the target region into sub-regions, termed cells, such that coverage in each cell can be accomplished by basic maneuvers, such as simple back-and-forth motions. This approach to coverage employs a representation of the free space called an exact cellular decomposition, which already has been widely used for path planning between two points. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the locations of cell boundaries. Morse functions are those whose critical points are non-degenerate. Different Morse functions induce different coverage patterns. Between critical points, the structure of a Morse function is effectively the same, so simple control laws to achieve tasks, such as coverage, are feasible within each cell. This paper addresses the issue of how to cover a space with varying patterns, but it also suggests a common framework for many conventional path planners. A companion paper describes the sensor based implementation of this approach.

Citation Download Citation

Howie M. Choset, Ercan Umut Acar, Alfred A. Rizzi, and Jonathan E. Luntz "Sensor-based planning: exact cellular decompositions in terms of critical points", Proc. SPIE 4195, Mobile Robots XV and Telemanipulator and Telepresence Technologies VII, (2 March 2001); https://doi.org/10.1117/12.417302

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