CourseWare Wiki
Switch Term
Winter 2020 / 2021
Winter 2019 / 2020
Winter 2018 / 2019
Older
Search
Log In
b191
courses
b4m36uir
hw
t2b-dtspn
Warning
This page is located in archive. Go to the latest version of this
course pages
.
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
Both sides previous revision
Previous revision
2019/11/22 19:56 pragrmi1
2019/11/22 13:16 pragrmi1
2019/11/08 14:29 pragrmi1
2019/09/22 19:36 faiglj
2019/09/22 18:57 pragrmi1
2019/09/22 18:56 pragrmi1
2019/09/22 05:23 faiglj [T2a-dtspn - Data collection path planning with curvature-constrained trajectory - Dubins TSP with Neighborhoods (DTSPN) - decoupled approach]
2019/09/22 05:23 faiglj created
Go
Next revision
Previous revision
2019/11/22 19:56 pragrmi1
2019/11/22 13:16 pragrmi1
2019/11/08 14:29 pragrmi1
2019/09/22 19:36 faiglj
2019/09/22 18:57 pragrmi1
2019/09/22 18:56 pragrmi1
2019/09/22 05:23 faiglj [T2a-dtspn - Data collection path planning with curvature-constrained trajectory - Dubins TSP with Neighborhoods (DTSPN) - decoupled approach]
2019/09/22 05:23 faiglj created
Go
Next revision
Both sides next revision
courses:b4m36uir:hw:t2b-dtspn [2019/09/22 18:57]
pragrmi1
courses:b4m36uir:hw:t2b-dtspn [2019/11/08 14:29]
pragrmi1
Line 1:
Line 1:
===== T2b-dtspn - Data collection path planning with curvature-constrained trajectory - Dubins TSPN ======
===== T2b-dtspn - Data collection path planning with curvature-constrained trajectory - Dubins TSPN ======
-
<
fc #ff0000
>
This page will available soon
</
fc
>
+
+
The main task is to implement two approaches solving the curvature-constrained Traveling Salesman Problem with neighborhoods.
+
+
|**Deadline** | November 23rd, 2019, 23:59 PST |
+
|**Points** | 5 |
+
|**Label in BRUTE** | T2b-dtspn |
+
|**Files to submit** | archive with ''DTSPNSolverDecoupled.py'' and ''DTSPNSolverNoonBean.py'' |
+
|**Resources** | {{ :courses:b4m36uir:hw:uir-t2b-dtspn.zip | T2b-dtspn resource pack }} |
+
+
\\
+
+
==== Decoupled Approach ====
+
+
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
+
- Estimate sequence of visits by Euclidean TSP connecting centers of the regions.
+
- For each region, sample boundary points and heading angles.
+
- Find the shortest feasible tour comprising Dubins maneuvers connecting the regions, where the sequence of visits is estimated from the ETSP.
+
+
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
+
<
code python
>
+
+
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
+
+
</
code
>
+
+
\\
+
+
+
==== Noon-Bean Transform Approach ====
+
+
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
+
- For each region, sample boundary points and heading angles.
+
- Construct a distance matrix using the Noon-Bean transform ({{courses:b4m36uir:lectures:b4m36uir-lec05-slides.pdf| Lecture 5. Multi-goal (data collection) planning}}) where the individual regions correspond to the NoonBean's Generalized TSP sets.
+
- Find the shortest feasible tour created from Dubins maneuvers by solving the Asymmetric TSP problem characterized by the distance matrix.
+
+
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
+
<code python>
+
+
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
+
</code>
+
+
\\
+
+
==== Appendix ====
+
\\
+
+
=== Installation of the Prepared Dependencies ===
+
+
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
+
+
<code bash>
+
cd lkh
+
./install.sh
+
cd -
+
+
cd gdip
+
./install.sh
+
cd -
+
</code>
+
+
\\
+
+
=== Dubins maneuver ===
+
[[https://en.wikipedia.org/wiki/Dubins_path]]
+
+
\\
+
+
=== Generalized Dubins Interval Problem ===
+
[[https://github.com/comrob/gdip]]
courses/b4m36uir/hw/t2b-dtspn.txt
· Last modified: 2019/11/22 19:56 by
pragrmi1