| Abstract: | We address the problem of collision free navigation of a point robot among polygonal obstacles in a bounded known terrain in two dimensional space. The obstacles could be convex or concave polygons. We consider a combinatorial approach to the problem and focus on partitioning the terrain into distinct regions and encoding these regions. We then build a region-graph whose nodes represent the regions and every pair of neighbouring regions (nodes) are connected by an edge. We propose an o(n 4) preprocessing algorithm to do this. This converts the problem of navigation from a source point to a destination point into a problem of finding a path in a planar graph from one of its nodes to another in O (n 2 log n) time. The shortest path is derivable in 0(n 4) time. The extension of the algorithm for three-dimensional space is also discussed. |
