HW 03 - Data Collection Planning

The goal of this homework is to implement two various solutions for TSP with neighborhoods (TSPN) in the provided maze environment.

Implement second part of the Decoupled approach where you should find the shortest tour which visits all the given target regions. The sequence was already computed by LKH Solver based on the distances between target centroids computed by provided A* algorithm. For each target region, $k$ samples are selected on its boundary which gives us $k^2n$ samples at total. Finding the shortest tour should take $\mathcal{O}(n^3k)$ since we aim to find a closed-loop path.

Please, implement your codes in the following function:

def plan_tspn_decoupled(self, map, goals, samples):	

Other possible approach is to solve the sequencing problem together with selecting the visiting configurations. First, we need to calculate mutual distances between all samples which creates the following discrete graph:

The graph represents Generalized TSP (GTSP) instaces where exactly one visiting configuration $q_{i}^{j}$ is selected from each set $\mathcal{R}_i$ with $k$ samples. We transform the GTSP instance into the TSP by utilizing the Noon-Bean transformation. Then, the problem can be solved by existing TSP solver, such as LKH. We use symmetric distance matrix in the environment, but the Noon-Bean transformation is applicable even for the asymmetric case (from the GATSP to the ATSP).

Noon-Bean transformation contains several basic steps:

1. Transform the GTSP matrix into TSP matrix.
   1. Set the TSP distance matrix to $2M$ value.
   2. Create zero-length cycle in each set of samples.
   3. Transform each original edge $(q_i^m, q_j^n)$ to the transform one $(q_i^m, q_j^{n+1})$.
   4. Increase value of each transformed edge by big $M$ constant.
2. Solve the transformed TSP problem (by heuristic LKH Solver).
3. Reconstruct the found solution and return the final tour.

Example of the Noon-Bean transformation from the Lecture08.

Example of the found solution in the transformed TSP instance.

Please, implement your codes in the following function:

def plan_tspn_noon_bean(self, map, samples):

This homework is about finding a tour in an environment with obstacles (maze map). However, during the testing phase, it can be beneficial to use more simple Euclidean distance. Hence, there is a prepared variable for this situation in the provided code:

# enable to use Euclidean distances (without obstacles) for testing
use_euclidean = True

Please, provide a short report about your work. Especially if your code is working and which scenarios have you tested. Notice that the LKH does not always return the optimal solution because it is a heuristic algorithm. So, report which approach (Decoupled vs. Noon-Bean) provides better results. The report should not exceed a single A4 page.

All implementations will be evaluated manually.