The main task is to implement two approaches solving the curvature-constrained Traveling Salesman Problem with neighborhoods.
Due date | December 01, 2024, 23:59 PST |
Deadline | January 11, 2025, 23:59 PST |
Points | 7 |
Label in BRUTE | t2b-dtspn |
Files to submit | archive with DTSPNSolver.py |
Resources | B4M36UIR_t2_resource_pack |
For Ubuntu 22.04 and newer pydubins |
|
LKH |
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.
On Ubuntu 18.04
or Ubuntu 20.04
(or Python < 3.9
), install the package using
pip3 install dubins # or our favorite way to install the packageOn
Ubuntu 22.04
(or Python >= 3.9
), the package is not available in pip, and it needs to be installed from the provided source (pydubins in b4m36uir_23_dubins_resource_pack.zip) located inside your resource pack directory using
./install_dubins.sh
3) The LKH solver (implementation of the Lin–Kernighan heuristic algorithm) and the GDIP Dubins library are already part of the resource package and they are installed as follows
./install_lkh.sh
Since both the dubins package and the LKH wrapper used the second part of the task 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