Share Email Print
cover

Proceedings Paper

Planning Viewpoints And The Navigation Route Of A Patrol Robot In A Known 2-D Environment
Author(s): Shun-en Xie; Thomas W. Calvert; Binay K. Bhattacharya
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper 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(N2 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(N3) time.

Paper Details

Date Published: 25 February 1987
PDF: 7 pages
Proc. SPIE 0727, Mobile Robots I, (25 February 1987); doi: 10.1117/12.937798
Show Author Affiliations
Shun-en Xie, Simon Fraser University (Canada)
Thomas W. Calvert, Simon Fraser University (Canada)
Binay K. Bhattacharya, Simon Fraser University (Canada)


Published in SPIE Proceedings Vol. 0727:
Mobile Robots I
Nelson Marquina; William J. Wolfe, Editor(s)

© SPIE. Terms of Use
Back to Top