Search
The main task is to implement two approaches solving the curvature-constrained Traveling Salesman Problem with neighborhoods.
DTSPNSolver.py
Ubuntu 22.04
6. Multi-goal Path planning
7. Data Collection Planning
8. 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.
plan_tour_decoupled
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.
plan_tour_noon_bean
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.
dubins
On Ubuntu 18.04 or Ubuntu 20.04 (or Python < 3.9), install the package using
Ubuntu 18.04
Ubuntu 20.04
Python < 3.9
pip3 install dubins # or our favorite way to install the package
Python >= 3.9
./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:
pose_to_se2
se2_to_pose
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
https://en.wikipedia.org/wiki/Dubins_path