Robot Navigation - The Rotational Sweep Algorithm

Objective

The aim of this post is to understand the rotational plane sweep algorithm to build a visibility graph and implement it in Matlab.

1 - Introduction

The rotational plane sweep is a path planning algorithm based on topological maps. It is one of the most powerful method of intelligent robot navigation. The basic concepts and details of the algorithm are going to be explained in the next chapter. After that, we are going to see the results.

2 - The Algorithm

Topological map is a simplified map with only relationship between points. It can be represented as a graph:

• nodes are real positions
• edges join positions in the free space.

They include the distance. It is easy to find a path in a topological map. So, the only problem is how to build a topological map? We are going to create visibility graph.

In order to create visibility graph. We should define for a 2D polygonal configuration space

• The nodes $v_{i}$ of the visibility graph include the start location, the goal location, and all the vertices of the configuration space obstacles. 
• The graph edges $e_{ij}$ are straight-line segments that connect two line-of-sight nodes $v_{i}$ and $v_{j}$, i.e., 

\begin{equation} e_{ij} \neq \emptyset \Longleftrightarrow sv_{i} + (1 - s)v_{j} \in cl(Q_{free}) \forall s \in [0, 1] \end{equation}