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

摘要

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.