The main task is to implement two approaches solving the curvature-constrained Traveling Salesman Problem with neighborhoods.
Deadline | November 28, 2021, 23:59 PST |
Points | 7 |
Label in BRUTE | t2b-dtspn |
Files to submit | archive with DTSPNSolver.py |
Resources | B4M36UIR_t2_resource_pack |
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
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 Vector3 list of the TSP goal coordinates (x, y, 0) sensing_radius: float neighborhood of TSP goals turning_radius: float turning radius for the Dubins vehicle model Returns ------- Path, path_length (float) tour as a list of robot configurations in SE3 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
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 Vector3 list of the TSP goal coordinates (x, y, 0) sensing_radius: float neighborhood of TSP goals turning_radius: float turning radius for the Dubins vehicle model Returns ------- Path, path_length (float) tour as a list of robot configurations in SE3 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_lkh.sh
Since both the dubins package and the LKH wrapper used the second part of the tasj use SE(2) coordinates represented as tuples, pose_to_se2
are se2_to_pose
functions are provided for you convenience:
def pose_to_se2(pose): return pose.position.x,pose.position.y,pose.orientation.to_Euler()[0] def se2_to_pose(se2): pose = Pose() pose.position.x = se2[0] pose.position.y = se2[1] pose.orientation.from_Euler(se2[2],0,0) return pose