The main task is to implement two approaches solving the curvature-constrained Traveling Salesman Problem with neighborhoods.
Deadline | November 30th, 2019, 23:59 PST |
Points | 5 |
Label in BRUTE | T2b-dtspn |
Files to submit | archive with DTSPNSolverDecoupled.py and DTSPNSolverNoonBean.py |
Resources | T2b-dtspn resource pack (updated 22.11.19) |
In the DTSPNSolverDecoupled.plan_tour
function implement the decoupled solution for the Dubins TSP with Neighborhoods (DTSPN) with disk-shaped regions.
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.
The Noon-Bean 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 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 -