===== Task10bonus2 - Bounds for the DTSPN using GDIP and sampling-based approach ======

|**Deadline**  |  13. January 2019, 23:59 PST |
|**Points**  |  5 |
|**Label in BRUTE**  |  Task10bon2 |
|**Sources**  |  {{ :courses:b4m36uir:hw:task10b2-v1.zip |Task10b2-v1}} |

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.

{{:courses:b4m36uir:hw:gdip.png|}}

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.

{{:courses:b4m36uir:hw:sampling.png?400|}}

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

{{:courses:b4m36uir:hw:dtp-graph.png?400|}}

The overall algorithm is:

{{:courses:b4m36uir:hw:gdip-algorithm.png?500|}}


=== Student tasks ===

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.


=== Expected results ===

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:

<code>
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
</code>

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:

{{:courses:b4m36uir:hw:resolution-4.png?400|}}
{{:courses:b4m36uir:hw:resolution-8.png?400|}}
{{:courses:b4m36uir:hw:resolution-16.png?400|}}
{{:courses:b4m36uir:hw:resolution-32.png?400|}}
{{:courses:b4m36uir:hw:resolution-64.png?400|}}


=== Evaluation - how will be the homework evaluated ===
The codes will be evaluated manually by the teacher.