Wiki: Modelling for the Travelling Salesman Problem

To facilitate path planning, the problem modelling should take into account all constraints associated with the sailboat's properties, the wind's speed and direction as well as the measurement area's borders and obstacles.

Table of contents

1. Design a simulation model for the sailboat
2. Control the sailboat with waypoints
3. Represent the TSP with a graph

Material needed

• Python 3.6
• Modules used: matplotlib, scipy, numpy, math

You can use Python 2.7 but some characters may be not recognized by this version (Greek alphabet).

1. Design a simulation model for the sailboat

This section refers to the model proposed by J. Melin in chapter 2 of Modeling, control and state-estimation for an autonomous sailboat. This assumes that: the boat has a unique effective sail and evolves in a 2D-space, where the influence of waves and current is neglected, and where the Coriolis and Centripetal forces are neglected (since velocity is assumed to be small).

Variables of the boat

• The state vector of the boat is defined as :

with sailboat's position (), velocity , heading , and rotational speed, given in a North-East-Up reference frame.

• δr is the angle of the rudder and δs is the angle of the sail which is proportional to the length of the mainsheet.
• Others variables intrinsically linked to the boat's shape and dimensions:

	value	unit	explaination
p1	0.03	_	drift coefficient
p2	40	kg/s	tangential friction
p3	6000	kg.m	angular friction
p4	200	kg/s	sail lift
p5	1500	kg/s	rudder lift
p6	0.5	m	distance to sail CoE
p7	0.5	m	distance to mast
p8	2	m	distance to rudder
p9	300	kg	mass of boat
p10	400	kg.m2	moment of inertia
p11	0.2	_	rudder break coefficient

Variables of the wind

• True wind : , the coordinates in the global frame of the wind of speed and direction .
• Apparent wind : , the (cartesian or polar) coordinates of the wind perceived by the boat in its frame (relative to its own direction).

Evolution equations

Considering the sail force, the rudder force and the friction, we finally obtain (consult the paper for more detail):

2. Control the sailboat with waypoints

This section refers to the strategy proposed by L. Jaulin and F. Le Bars in A simple controller for line following of sailboats, in which they introduce a pragmatic approach influenced by a potential field strategy for the sailboat model previously described. With this method, the boat is progressively attracted by the line to follow until it fits it.

Parameters

To fit as much as possible to the real sailboat, the different variables calculated by J.Melin (Part 1) are chosen.

• Sensors: The heading θ of the robot is measured by a compass. The angle of the wind ψ is returned by a weather vane. The position m is given by a GPS.
• Actuators: The inputs of the robot are the angle of the rudder δr and the maximum angle for the sail δmax (which is directly related to the length of the mainsheet).
• Parameters: δmax is the maximal angle of the rudder, r is the cutoff distance (i.e., we want that the distance of the boat to the line be less than r), γ∞ is the incidence angle and ζ is the close-hauled angle.
• References: Two points (a,b) which define the line to be followed.
• State variable: This will be a discrete variable q (-1 or 1) corresponding to the favored tack.

Consistency with the wind

Some directions, like paths facing the wind, are not feasible for the sailboat. These unfeasible courses form a no-go zone (painted in grey), that can be avoided thanks to a keep close-hauled strategy. Therefore, instead of directly following a line, the boat will adopt a zigzag trajectory to target the goal while staying at the frontier of the allowed zone.

Algorithm

Finally, the algorithm groups the two strategies: a potential field strategy if the boat is guaranteed to stay in the allowed zone, and a closed-hauled strategy if it risks to end up in the no-go zone. For more details on each step, consult the paper.

Implementation

For better precision, a Runge-Kutta integration method has been added to the script. It may be slower than the initial Euler method, but changes are noticeable in sharp bends. The boat is represented as a python class for convenience.

0. Open the python script boat.py in the folder PathPlanning of the GitHub project. This script groups the boat modelling as well as the controller.
1. In the name == 'main' section, set up the parameters allowed for the boat and the characteristics of the environment.
2. Configure the path at your will accordingly to the example (points A,B,C ...). The matplotlib graph should adapt to the coordinates of your points.
3. Choose the integration method. Because the Runge-Kutta method is slow, its update can be modified with the plot_rate variable (when increased, the plotting could become jolting).

3. Represent the TSP with a graph

The traveling salesman problem problem

The traveling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?". Although apparently simple, the real challenge is to find the optimal path that minimizes the total length of the trip (find the minimal cost Hamiltonian cycle), which is not always easy to determine (NP-hard combinatory problem). Graphs are a common tool to illustrate the givens of the problem.

Such a graph is composed of:

• vertices, with unique labels, for the different cities to visit
• edges, for the existing paths that link each city to another
• weight, to consider the distance between each city.

The simpler TSP generally asks for a complete undirected graph, in which every pair of distinct vertices is connected by a unique city. In other words, every city can be reached from every other city, and since there is no direction, all distances remain the same between two distinct cities (same length to go from A to B, and from B to A).

The traveling sailboat problem

Considering a sailboat this time, some adjustments on the previous modelling need to be made. The measurement points are identified as the cities to visit. However, the orientation of the wind prevents the boat from moving in all directions. Consequently, the graph of the problem becomes asymmetrical (oriented). We can consider that all measurement points are still reachable from every other point, but that the distance between two points differs depending on the direction (a wind penalty increases the distance). A complete digraph is obtained to model our problem.

# details of the addEdge() method adding a wind penalty
def addEdge(self, from_node, to_node, weight, obstacle=False):
            xa,ya = self.vertices[from_node]
            xb,yb = self.vertices[to_node]
            slope = atan2(yb-ya,xb-xa)
            penalty = self.wind_speed*cos(self.wind_angle-slope)
            self.edges[(from_node, to_node)] = weight*(1+max(0,penalty))

In addition, it becomes very difficult to use Dijkstra or Floyd-Warshall algorithms in this case, and there is not any chance to think about the Christofides algorithm (triangle inequality not guaranteed). Some other strategies should be built.

All the vertices' data is stored in lists instead of matrices, to reduce the complexity of the calculations when the number of cities becomes really big.

Implementation

To construct your own graph:

0. Open the graph.py python script in the folder PathPlanning of the GitHub project.
1. In the 'name'=='main' section, copy-paste this script to create a simple graph:

x,y = [0,1,3,2.5,6,5,4],[0,1,6,1,0.5,4,1]
G = Graph() 
G.defineWind(angle=pi/2,speed=5)
G.addVertices(x,y)  # adds the nodes
G.addEdgesAll()  # defines how the nodes are linked together
G.plot()
plt.show()

2. To discover more possibilities with this class, consult the next wiki guide: Four different strategies to find our way.