The main task is to implement two approaches solving the curvature-constrained Traveling Salesman Problem with neighborhoods.

5. Multi-goal Path planning

6. Data Collection Planning

7. Curvature-constrained Data collection Planning

In the plan_tour_decoupled function implement the decoupled solution for the Dubins TSP with Neighborhoods (DTSPN) with disk-shaped regions.

The decoupled approach comprises the following basic steps

1. Estimate sequence of visits by Euclidean TSP connecting centers of the regions.
2. For each region, sample boundary points and heading angles.
3. Find the shortest feasible tour comprising Dubins maneuvers connecting the regions, where the sequence of visits is estimated from the ETSP.

The plan_tour_decoupled function has the following prescription:

def plan_tour_decoupled(goals, sensing_radius, turning_radius):
    """
    Compute a DTSPN tour using the decoupled approach.  
 
    Parameters
    ----------
    goals: list (float, float)
        list of the TSP goal coordinates (x, y)
    sensing_radius: float
        neighborhood of TSP goals  
    turning_radius: float
        turning radius for the Dubins vehicle model  
 
    Returns
    -------
    list (float,float,float), path_length (float)
        tour as a list of robot configurations (x, y, phi) densely sampled
    """

In the plan_tour_noon_bean function implement the Noon-Bean trasnform solution for the Dubins TSP with Neighborhoods (DTSPN) with disk-shaped regions.

The Noon-Bean approach comprises the following basic steps

1. For each region, sample boundary points and heading angles.
2. Construct a distance matrix using the Noon-Bean transform (from lectures) where the individual regions correspond to the NoonBean's Generalized TSP sets.
3. Find the shortest feasible tour created from Dubins maneuvers by solving the Asymmetric TSP problem characterized by the distance matrix.

The plan_tour_noon_bean function has the following prescription

def plan_tour_noon_bean(goals, sensing_radius, turning_radius):
    """
    Compute a DTSPN tour using the NoonBean approach.  
 
    Parameters
    ----------
    goals: list (float, float)
        list of the TSP goal coordinates (x, y)
    sensing_radius: float
        neighborhood of TSP goals  
    turning_radius: float
        turning radius for the Dubins vehicle model  
 
    Returns
    -------
    list (float,float,float), path_length (float)
        tour as a list of robot configurations (x, y, phi) densely sampled
    """

1) Download prepared codes and configuration files.

2) Install 'dubins' package to python3.

pip3 install dubins # or our favorite way to install the package

3) Compile the LKH solver (implementation of the Lin–Kernighan heuristic algorithm) and the GDIP Dubins library as follows

./install.sh

https://en.wikipedia.org/wiki/Dubins_path