Task08 - Multi-goal path planning and data collection path planning - TSP-like formulations

Deadline 1. December 2018, 23:59 PST
Points 4
Label in BRUTE Task08
Files to submit archive with som_solver.py
Resources Task08 resource package (version 2)


Download provided codes and run the main script eval_som.py

Slide 15 from the Lecture08:

Utilize 'alternate goal' concept for solving TSP with neighborhoods (TSPN). In each epoch, the neurons are adapted towards the goals which inhibits them. But, in the TSPN, the neurons are adapted to the closes point in the specific goal neighborhood. Therefore, this concept enables to find shorter solutions, see the right image and the following GIF with SOM evolution.

Click on the following image to see the SOM evolution in GIF.

Tasks (4b)

  1. Familiarize yourself with a concept of self-organizing maps for TSP-like problems.
  2. Implement method select_winner(…) which select the closest non-inhibited neuron to the target. Inhibit the selected neuron such that it cannot be selected twice. (1b)
  3. Adapt neighborhood of the winner neuron towards the target in the method learn_epoch(…). If only the selected neuron is adapted, the final tour does not converge the to final solution. Thus a neighborhood of several neurons is also adapted towards the goal. Use 20% of neurons on both side and compute the learning parameter by the provided neighborhood function. Notice the distance is discrete and measured as number of neurons from the selected neuron. (1b)
  4. Extend the provided solver for the TSP with neighborhoods and modify function update_goal_potition(…) to utilize the concept of alternate goal. The closest point on the boundary of the neighborhood region is selected to shorten the final tour. If the selected neuron is already in the region, the alternate goal is set directly to its position. (2b)
courses/b4m36uir/hw/task08.txt · Last modified: 2018/11/26 14:08 by vanapet1