Lab09 - Data Collection Planning (TSP(N))

Motivations and Goals
Become familiar with data collection planning approaches
Be able to formulate the data collection task as a variant of traveling salesman problem or orienteering problem
Tasks (teacher)
Implement extension of Self-organizing maps approach for TSP problems to take into account the neighborhood of the point
Implement the euclidean TSP and extend it to obstacle aware TSP
Lab09S SOM resource files
Lab09P Pac-man resource files

Self-organizing maps for TSP-like problems

Download provided codes and run the main script

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 (2b) - Lab09S

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

Combinatorial methods for TSP-like problems

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 1 point to 1 point
    • 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

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:

cd LKH
cd -

Now, you should be able to run Packman example.


The result should be similar to:

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. You can simply run it by enabling the following line:

path = solver.plan_tour_obstacles(map, goals, "E4")

Tasks (5 points) - Lab09P

  1. 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. (3 points)
  2. Solve TSP instance of the created distance matrix using existing LKH Solver.
  3. Create the final path from the found sequence by connecting corresponding shortest paths between visited dots.
  4. Extend this approach to solve open-loop problem from start (first goal) to end (last goal) which collect a subset of 50 “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/lab09.txt · Last modified: 2018/09/06 14:06 (external edit)