HW 03b - Data Collection Planning for Surveillance Missions

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.

Deadline	January, 1, 2018, 23:59 PDT
Label in BRUTE	HW03b
Files to submit	archive with `.py` files, mandatory files: `planner.py`
Bonus Mandatory tasks	8 Points
Bonus Voluntary tasks	7 Points
Resources	Lab10-Dubins Dubins TSP from Lab10

Bonus Mandatory 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:
2 points	Implementation of DTSP solver with simple heuristics based on solution of the ETSP and Alternating Algorithm (AA), i.e., ETSP+AA
6 points	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.
Bonus Voluntary tasks - Implementation of a more complex solver for DTSP and DTSPN (`planner-dtspn.py`):
4 points	Implementation of DTSP solver based on ETSP+DTP or sampling-based GTSP approach.
3 points	Implementation of DTSPN solver - sampling-based with the generalization of the DTP to the DTRP or the GATSP formulation with the transformation to the ATSP. The DTSPN is with the disk-shaped 𝛿-neighborhood
Additional remarks
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 ρ and for the DTSPN the 𝛿-neighborhood
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-130.

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

or

python2 planner-dtspn.py --dubins-radius 1 --sensing-distance 5 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) and –sensing-distance can be used to specify the sensing range as the $\delta$-neighborhood (in meters). Notice, if $\delta$>0 the given problem instance is treated as DTSPN; otherwise as the DTSP. For the sampling based approaches, the further parameters can be used:

–heading-samples specifying the number of samples per each waypoint location
–neighborhood-samples specifying the number of sampled waypoint locations per each region specified by the center of disk read from the input file and the disk-shaped $\delta$-neighborhood, where $\delta$ is the radius of the disk.

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.