Planning Viewpoints And The Navigation Route Of A Patrol Robot In A Known 2-D Environment

Shun-en Xie; Thomas W. Calvert; Binay K. Bhattacharya

doi:10.1117/12.937798

25 February 1987 Planning Viewpoints And The Navigation Route Of A Patrol Robot In A Known 2-D Environment

Shun-en Xie, Thomas W. Calvert, Binay K. Bhattacharya

Proceedings Volume 0727, Mobile Robots I; (1987) https://doi.org/10.1117/12.937798
Event: Cambridge Symposium_Intelligent Robotics Systems, 1986, Cambridge, MA, United States

Abstract

For a patrol robot, it is important to select optimal viewpoints and arrange corresponding navigation routes which are as short as possible. In general, this problem is NP-hard. This paper describes two heuristic approaches for planning viewpoints in 2-dimensions. The first O(N² log N) approach is based on the static partition of a weakly simple polygon into star-shaped polygons. The second O(N2log N) approach is characterized by the sequential selection of viewpoints; this results in covering the edges of a weakly simple polygon with star-shaped polygons and may require fewer viewpoints than the first approach. For a patrol robot, it is necessary to reorder the sequence of the viewpoints and arrange the navigation route accordingly. By decomposing the free spaces into simpler components and connecting viewpoints with pass-ways, the problem of arrangement of the navigation route can be reduced to the well known NP-hard Traveling Salesman problem. Thus, it can be solved by one of the known approximation algorithms, such as Christofide's Heuristic algorithm in O(N³) time.

Citation Download Citation

Shun-en Xie, Thomas W. Calvert, and Binay K. Bhattacharya "Planning Viewpoints And The Navigation Route Of A Patrol Robot In A Known 2-D Environment", Proc. SPIE 0727, Mobile Robots I, (25 February 1987); https://doi.org/10.1117/12.937798

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