Lab04 - Grid and Graph-based Path Planning Methods

Typical steps of planning evaluation in robotics consists of following steps

1. Purely software testing of the planning algorithm without execution
2. Simulation of execution with perfect information and perfect execution
3. Simulation in realistic simulator with perfect information and imperfect execution given by simulated physics
4. Deployment on a real robot with imperfect information and imperfect execution

For evaluation of the path, different metrics can be used. In general following properties are examined:

• Feasibility - whether the path is feasible for particular robot given its embodiment
• Length - the overall path length
• Planning time - in the real-time applications and multi-goal path planning, the overall planning time is a crucial parameter
• Clearance - how far from the obstacles the robot navigate. Low distance may result in robot damage in case of inaccurate path execution

The relation between the grid map represented as an array and the real world is given by transformation of coordinates. This transformation is essential in execution of the planned path in the simulator or on the real robot. The main idea of the coordinates system transformation is visualized in the following figure.

As it can be seen, the coordinate systems transformation requires x,y offsets of the coordinate frame origins and the size of the map voxel. The transformation of map coordinates $(x_m, y_m)$ to simulator coordinates $(x_s, y_s)$ is then given as:

$x_s = x_m\cdot voxelSize - offset_x,\quad\quad y_s = -y_m\cdot voxelSize + offset_y$

And vice versa, the transformation of simulator coordinates $(x_s, y_s)$ to map coordinates $(x_m, y_m)$ are given as:

$x_m = \text{round}\left(\dfrac{x_s + offset_x}{voxelSize}\right), \quad\quad y_m = \text{round}\left(-\dfrac{y_s - offset_y}{voxelSize}\right)$