====== Lab04 - Grid and Graph-based Path Planning Methods  ======

^ Motivations and Goals  ^
| Become familiar with grid based path planning  |
| Be able to implement simple path planning algorithms and deploy them in robot navigation |
^ Tasks ([[courses:b4m36uir:internal:instructions:lab04|teacher]]) ^
| Implement selected search algorithms such as BFS, Dijkstra, and A* in grid-based path planning |
| Implement robot embodiment and extension of the grid map to configuration space |
^ Lab resources ^
| Lab scripts: {{:courses:b4m36uir:hw:lab04.zip|lab04 resource files}} |
| V-REP scenes: {{:courses:b4m36uir:labs:scenes.zip| maze1.ttt}}|
| V-REP remoteAPI: {{:courses:b4m36uir:labs:hexapod_vrep_v3_0.zip|hexapod_vrep_v3.0}} | 


=== Evaluation of path planning methods in robotics ===
Typical steps of planning evaluation in robotics consists of following steps
  - Purely software testing of the planning algorithm without execution
  - Simulation of execution with perfect information and perfect execution
  - Simulation in realistic simulator with perfect information and imperfect execution given by simulated physics
  - 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


=== Coordinate transformations between the grid map and the real-world coordinates ===
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.\\
{{:courses:b4m36uir:labs:maze1.png?300|Coordinates system transformation}}

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)$