===== Task09 - 	Data collection path planning  ======

|**Deadline**  |  8. December 2018, 23:59 PST |
|**Points**  |  4 + 3 |
|**Label in BRUTE**  |  Task09 |
|**Files to submit**  |  archive with ''MGMPSolver.py'' |
|**Resources**  | {{ :courses:b4m36uir:hw:task09-v3.zip | Task09 resource package (Version 3)}}|

/*
===Assignment===

<note warning>Under reconstruction!</note>

  - Familiarize yourself with a concept of self-organizing maps for TSP-like problems.
  - Extend the provided solver for the TSP with neighborhoods and modify function ''update_goal_potition(...)'' to utilize the concept of ''alternate goal''.
*/

===== Task09a - Data collection path planning - obstacle aware planning  =====

==== Short theory - Graph based planning ====

In contrast to a classical path planning (from A to B), we need to estimate all distances between the given points in the multi-goal path planning problem. It can be done by existing algorithm:

  * **From point A to point B**  
     * Breadth First Search (BFS)
     * Depth first search (DFS)
     * A* algorithm
  * **From 1 point to N points**
    * Dijkstra's algorithm
  * **From N points to N points**
    * [[https://www.algoritmy.net/article/5207/Floyd-Warshalluv-algoritmus|Floyd–Warshall algorithm]]

Notice that algorithms from the first two groups have to be called multiple times to get the full distance matrix.

==== Installation of the prepared codes ====

Download prepared codes and configuration files. Then download and compile LKH solver (implementation of the Lin–Kernighan heuristic algorithm) as follows:

<code bash>
cd lkh
./install.sh
cd -
</code>

Now, you should be able to run Packman example. 

<code bash>
./task9_eval.py
</code>

The result should be similar to:

{{:courses:b4m36uir:labs:packman-etsp-crop.png|}}
==== Pac-man scenario ====

This scenario is prepared with a working example which finds the shortest tour (TSP solution) based on the Euclidean distance. However, the obstacles in the environment are not considered and, therefore, the final trajectory collides with the walls, see the image above.

Our task is to replace the Euclidean distance by the shortest feasible trajectory in the maze. Since the original Pac-man can move only in 4 direction, we also utilizes the same 4 moves during the planning phase and discard all diagonal moves. In the prepared codes, a naive implementation is provided using A* from previous lectures. The A* algorithm needs to be called $\mathcal(n^2)$ times which is the main drawback of this approach. 

/*
<code python>
path = solver.plan_tour_obstacles(map, goals, "E4")
</code>
*/

<note important>Use 4 neighborhood for planning.</note>

=== Tasks (4 points) - Task09a ===

  - Implement the pre-prepared **Floyd–Warshall algorithm** for finding shortest paths between all places with "dots" (should be eaten by Packman) and store the values into distance matrix. Use Euclidean distance and prepared 4-neighborhood utilized in previous laboratories. **(2 points)**
  - Solve TSP instance of the created distance matrix using existing LKH Solver.
  - Create the final path from the found sequence by connecting corresponding shortest paths between visited dots.
  - Extend this approach to **solve open-loop** problem from start (first goal) to end (last goal) which collect a subset of "dots". **(2 point)**

=== Expected result in GIF (3.2 MB + 1.1 MB) ===

  * An example of a closed-loop path of 50 goals (left) and an open-loop path of 10 goals (right). 

{{:courses:b4m36uir:labs:packman.gif?300|}} {{:courses:b4m36uir:labs:packman_open.gif?300|}}

===== Task09b - Data collection path planning with remote sensing (TSPN) - decoupled approach   =====

===== Neighborhoods in maze scenario =====

<note important>Use 8 neighborhood for planning.</note>

  - **Decoupled approach** (3 points)
    - First, find the goal sequence by the ETSP. Then, find the final trajectory.
    - First, find the goal sequence by the TSP utilizing the found shortest paths between centres of the given regions. Then, find the final trajectory as the shortest tour connecting the neighborhood samples in the given sequence.

{{:courses:b4m36uir:hw:neighborhoods-large-solution.png?300|}} 

  - **Sampling-based approach** (BONUS - 5 points)
    - Create samples in the goal neighborhoods and all shortest paths. Then, transform the problem to the ATSP by the Noon-Bean transformation


=== Noon-Bean transformation ===

{{:courses:b4m36uir:labs:noon-bean.png?500|}}