This project is about computational geometry and its application to robotics. The main objective is that the reader has a complete view on how to resolve the shortest path planning problem for a robot given an initial position, a goal position and a set of obstacles. Some assumptions and simplifications of the reality will be made in this case. Thus the robot and the obstacles will be defined to be convex or non-convex polygons on a planar region, the environment will be considered to be static so the obstacles will not move, and the robot cannot turn but it can move to front, back, right and left.

The content of this blog is oriented to show the construction of three main concepts to resolve the shortest path planning problem:

  • Minkownski Sums
  • Union of Polygons
  • Visibility Graphs construction

Some Definitions Before Starting

Let \(R\) be a simple polygon that represents the robot shape. It moves on a planar region which is a 2-dimensional environemnt that is called work space. Such region contains a set of \(S = \{P_1, P_2, ... , P_i\} \) obstacles with \(P_i\) to be a simple polygon that represents the obstacle shape for all \(i\).

A robot has a reference point attached to it which is not necessary inside the robot. This point describes the translation of the robot on the work space as a vector. Thus \(R(0,0)\) is the origin. If the robot moves three metters to the left and four metters to the top then the reference point will be at \(R(3,4)\).

A configuration space denoted by \(C(R)\) is a complete specification of the position of every point in the system. Thus not all the points in the configuration space are accessible for the robot. For instance, those points that are occupied by the obstacles. They are called the forbidden configuration denoted by \(C_{forb}(R, S)\). The rest of the space that are not occupied by obstacles are totally accessible for the robot, called the free space and denoted by \(C_{free}(R,S)\).

An obstacle \(P\) is mapped into the configuration space. The result is called configuration-space obstacle or \(C\)-obstacle of \(P\).