A polynomial time algorithm for an exact encoding of space containing

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 ₄) 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 ₂ log n) time. The shortest path is derivable in 0(n ₄) time. The extension of the algorithm for three-dimensional space is also discussed.

Keywords:

• Polytime complexity
• polygonal obstacles
• Encoding of space

C.R Categories:

• 3.14