Warning

## Task10bonus1 - DTSP - ETSP+AA and plan execution

 Deadline 13. January 2019, 23:59 PST Points 5 Label in BRUTE Task10bon1

The goal of this (bonus) homework is to implement data collection planning algorithm motivated by surveillance missions planning for unmanned aerial vehicle (UAV) modeled as Dubins vehicle. The problem can be addressed as the Dubins Traveling Salesman Problem (DTSP) and for further scoring as the Dubins Travling Salesman Problem with Neighbourhoods (DTSPN). Moreover, additional points can be gained for execution of the planned trajectories in the MRS simulation framework.

Bonus tasks - Implement the solver in planner-dtsp.py that reads the given problem (DTSP and DTSPN) and produce a trajectory as a sequence of waypoints:
5 points Implementation of DTSP solver with simple heuristics based on solution of the ETSP and Alternating Algorithm (AA), i.e., ETSP+AA
Plan execution - use the MRS simulation framework to execute the planned trajectories using one of the available models of UAVs and the supplementary problem files. Please upload pdf report with description of code usage, simulation printscreens and graph comparison of the trajectory plan and its execution.
The solver is a program that reads the input file and produces the output file. Besides, it accepts command line arguments for specifying the minimal turning radius ρ.
There are at least four computers with the pre-installed MRS simulation framework available in the MRS computer laboratory KN:E-118. If it is not accessible, it can be managed at KN:E-121.

#### Evaluation - how will be the homework evaluated

The solution will be evaluated using the MRS simulation framework. The planner should provide a trajectory (for an instance of the DTSP and DTSPN) that is than executed in the simulator. The solver can be called as follows

python2 planner-dtsp.py --dubins-radius 1 dtsp-1.txt dubins_trajectory.txt
The program argument –dubins-radius allows to specify the minimal turning radius of the Dubins vehicle $\rho$ (in meters).

The input file contains a list of sensing locations as $(x,y)$ in floating point numbers, one sensing location per line.

The output file is a list of waypoints as $(x, y, \theta)$, where $\theta$ is the heading of the vehicle, one waypoint per line, stored as floating point numbers with maximum number of floating point digits.

AD output file: For the MRS simulation framework, the trajectory handler expects to load the file with waypoints $(x, y, z, \theta)$, where the additional $z$ is the flight altitude. Furthermore, the trajectory handler expects the wayponts to be exactly 0.2 seconds from each other. By this manner you can also control speed of the vehicle by resampling the trajectory. The simulated hexacopter is limited by maximal horizontal speed $v=$8.33 ms$^{-1}$ and maximal horizontal acceleration $a=$2.0 ms$^{-2}$. The created trajectory for the MRS trajectory handler has to meet the speed and acceleration constraints and also the formula for uniform circular motion $a=\dfrac{v^2}{ \rho }$. The used dubins-radius $\rho$ should be selected with respect to the constraints. Your solution should show plots of both planned trajectories and UAV positions while flying the trajectory.