{{indexmenu_n>7}}

===== t2-tspn - Data-collection Path Planning with Remote Sensing (TSPN) ======

The main task is to implement a solver for instances of the Traveling Salesman Problem with Neighborhoods (TSPN), specifically with the disk-shaped neighborhood, a.k.a. Close Enough TSP, using unsupervised learning principles of the Self-Organizing Map (SOM).

|**Files**  |  ''SOMSolver.py'' - File to be implemented \\ ''utils.py'', ''Path.py'', and ''Point2D.py'' - Helpers for evaluation, drawing, and saving figures \\ ''problems'' - Scenarios and \\ ''t2-tspn.py'' - Evaluation script |
|**Resources**  |  {{ :courses:crl-courses:redcp:tasks:t2-tspn.zip |}} - **<fc #ff0000>Initial files and evaluation script</fc>** |

<note tip>Implement determination of the ''alternate_goal'' in ''learn_epoch()'' function of ''SOMSolver.py''. </note>

----

===Assignment===

Familiarize yourself with the provided ''SOMSolver.py'' that implements an unsupervised learning-based solution to the TSP using principles of Self-Organizing Maps (SOMs) according to slides from lec05.

From Lecture 05:

|{{:courses:crl-courses:redcp:tasks:lec05-slide32.jpeg?800|}}|
|{{:courses:crl-courses:redcp:tasks:lec05-slide33.jpeg?800|}}|

Utilize the ''alternate goal'' concept for solving instances of the TSP with Neighborhoods (TSPN). 
In the regular SOM-based solution to the TSP, the neurons are adapted towards the goals (cities) in each epoch.
However, in the TSPN, the neurons are adapted to the closes point in the goal's neighborhood, as shown in the figure.
|{{:courses:crl-courses:redcp:tasks:lec05-slide37.jpeg?800|}}|
Therefore, the concept enables us to find shorter solutions than neurons directly to the goals (disks' centers); see the right image and the following GIF with SOM evolution.

| {{:courses:crl-courses:redcp:tasks:som_tspn_orig.png?400|}} | {{:courses:crl-courses:redcp:tasks:som_tspn.png?400|}} |

See the SOM evolution.

{{:courses:crl-courses:redcp:tasks:som_tspn_learning.gif?500|}}

----

=== Approach ===

The SOM-based unsupervised learning for routing problems is a repetitive learning of one-dimensional SOM that iteratively adapts to the input goal locations in a number of learning epochs.
In each epoch, the goal locations are presented to the network in a random order (to avoid local extreme) and for each presented location, ''select_winner()'' method determines the best-fitting (closest) non-inhibited neuron. The winner is then adapted towards the goal together with its neighboring neurons, which is effectively the movement of the weights of the neurons (coords in a plane) towards the goal location with the decreasing power according to the distance of the neighboring neuron to the winner (in the number of neurons). 
The winner is then inhibited not to be a winner for more than one goal location in each learning epoch.
The winner neighboring can be set to about 20 % of the total number of neurons. 

<note>
The provided implementation in Python is not computationally efficient.
Proper implementation is several orders of magnitude faster, such as https://github.com/comrob/gsoa. 
Clone ''git clone https://github.com/comrob/gsoa'' and install ''apt install libboost-all-dev''.
</note>

The provided implementation adapts the neurons directly to the goal location. 
Therefore, it is necessary to adjust the winner selection using the concept of the ''alternate goal''.
Notice that for the instances with disk-shaped neighborhoods of identical radii, we can just alternate the target locations towards which the neurons are adapted.
However, it is more suitable to consider the alternate goal directly in the winner selection for varying radii.

<note important>In the evolution ''t2-tspn.py'',  the animation can be disable by setting ''animate'' to False.
<code python>
import SOMSolver as som

animate = False

planner = som.SOMSolver()
path = planner.plan_tour(goals, radius, animate)

</code>
</note>