Search
The main task is to implement two approaches solving the curvature-constrained Traveling Salesman Problem with neighborhoods.
DTSPNSolverDecoupled.py
DTSPNSolverNoonBean.py
In the DTSPNSolverDecoupled.plan_tour function implement the decoupled solution for the Dubins TSP with Neighborhoods (DTSPN) with disk-shaped regions.
DTSPNSolverDecoupled.plan_tour
The decoupled approach comprises the following basic steps
Notice, the number of heading and position samples is not defined. Your task is also to try various values and submit a code with a reasonable number of samples.
The DTSPNSolverDecoupled.plan_tour function has the following prescription
class DTSPNSolverDecoupled(DTSPNSolver.DTSPNSolver): ... def plan_tour(self, goals, sensing_radius, turning_radius): """ Compute a DTSPN tour using the decoupled approach. Parameters ---------- goals: list (float, float) list of the TSP goal coordinates sensing_radius: float neighborhood of TSP goals turning_radius: float turning radius for the Dubins vehicle model Returns ------- list (float,float,float) tour as a list of robot configurations (x,y,phi), each corresponding to a TSP goal """ n = len(goals) self.distances = np.zeros((n,n)) self.paths = {} ''' TODO - homework - Compute the distance between the individual goals ''' print ('TODO distances') self.distances = np.ones(self.distances.shape) sequence = self.compute_TSP_sequence() ''' TODO - homework - Sample the configurations ih the goal areas - Find the shortest tour ''' print ('TODO sampling') selected_configurations = [] for a in range(n): selected_configurations.append ( ( goals[sequence[a]][0], goals[sequence[a]][1], math.pi ) ) return selected_configurations
In the DTSPNSolverNoonBean.plan_tour function implement the Noon-Bean trasnform solution for the Dubins TSP with Neighborhoods (DTSPN) with disk-shaped regions.
DTSPNSolverNoonBean.plan_tour
The Noon-Bean approach comprises the following basic steps
The DTSPNSolverNoonBean.plan_tour function has the following prescription
class DTSPNSolverNoonBean(DTSPNSolver.DTSPNSolver): ... def plan_tour(self, goals, sensing_radius, turning_radius): """ Compute a DTSPN tour using the NoonBean approach. Parameters ---------- goals: list (float, float) list of the TSP goal coordinates sensing_radius: float neighborhood of TSP goals turning_radius: float turning radius for the Dubins vehicle model Returns ------- list (float,float,float) tour as a list of robot configurations (x,y,phi), each corresponding to a TSP goal """ n = len(goals) self.distances = np.zeros((n,n)) ''' TODO - Noon-Bean approach ''' print ('TODO - Noon-Bean') configurations = [] for goal in goals: configurations.append((goal[0],goal[1],math.pi)) return configurations
First, download prepared codes and configuration files. Then, download and compile the LKH solver (implementation of the Lin–Kernighan heuristic algorithm) and the GDIP Dubins library as follows
cd lkh ./install.sh cd - cd gdip ./install.sh cd -
https://en.wikipedia.org/wiki/Dubins_path
https://github.com/comrob/gdip