The goal of this (bonus) homework is to find solution with tight bounds for the Dubins TSP with Neighborhoods (DTSPN). Since the problem is very complex, we will consider only a single sequence already found by the Euclidean TSP, and all the regions are disk-shaped. The task is implement informed sampling procedure based on a tight lower bound estimation. The boundary of each regions is samples using smaller disk-shaped regions and possible heading angles are divided into intervals. Thus, each sample is given by a disk region and interval of the heading angle and the lower bound between two consecutive samples can be found using so called Generalized Dubins Interval Problem, see the following plot.

Example of the position sampling on the boundary of the target region is depicted in the following images. Uniform sampling (left) is able to provide the required lower bound; however, the informed sampling (right) converges much faster to the optimal solution.

Once the samples are created, the shortest tour is found in the following graph structure.

The overall algorithm is:

Implement method for finding the shortest lower/upper-bound tour for the actual sampling. The lower bound tour is then then utilized for refinement in the informed sampling approach.

The expected result is that the gap from the optimal solution is about 5% for maximal resolution of 64 for both position and heading angle sampling. The output in the command line is expected to be as follows:

Resolution:    4 Lower bound:   9.76 Upper bound (feasible):  30.25 Gap(%):  67.75
Resolution:    8 Lower bound:  14.50 Upper bound (feasible):  23.95 Gap(%):  39.44
Resolution:   16 Lower bound:  17.68 Upper bound (feasible):  22.04 Gap(%):  19.77
Resolution:   32 Lower bound:  19.56 Upper bound (feasible):  21.84 Gap(%):  10.43
Resolution:   64 Lower bound:  20.63 Upper bound (feasible):  21.77 Gap(%):   5.21

During the calculation, the program plot the actual lower-bound (red) and upper-bound feasible (blue) paths. These two paths are expected to converge together with increasing the maximal sampling resolution, see:

The codes will be evaluated manually by the teacher.