Wiki : Four different strategies to find our way - archetag/smart-water-quality-monitoring GitHub Wiki

Wiki: Four different strategies to find our way

Now that the sailboat and the measurement zone are defined and modeled, various algorithms can be implemented to solve this specific Travelling Salesman Problem. To make the boat autonomous, various maps and measurement patterns will be used.

Table of contents

1. How to define the edges?
2. Solving algorithms
a. The Random strategy
b. The Loop strategy
c. The Genetic algorithm strategy
d. The Nearest Neighbour strategy
3. Implementation and comparison
4. Additional shapes

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).

This wiki assumes you have already read the Modelling for the salesman problem wiki section, especially the last part.

1. How to define the edges?

After having declared the graph, chosen the wind's characteristics, and added the vertices, you have to decide how to define the edges. The Graph python class in the graph.py script of the PathPlanning folder already proposes three kinds of set up:

  • Manual Setup: to build all the edges on your own, or to modify one particular value (from its index or coordinates).
# definition of the graph and the wind
x,y = [0,1,3,2.5,6,5,4],[0,1,6,1,0.5,4,1]
graph = Graph() 
graph.defineWind(angle=pi/2,speed=5)
graph.addVertices(x,y)

print(graph.vertices) # to know the indexes of the two vertices we want to link together.
graph.addEdge(from_node = index1, to_node = index2, weight = value, obstacle=False) # construct edge in one direction
print(graph.edges[(index1,index2)]) # returns the weight
print(graph.edges[(index2,index1)]) # does not work

# the graph is already initialized with vertices, the wind is defined.
print(graph.vertices) # to know the available coordinates
graph.addEdgeFromCoords(from_node = (x1,y1), to_node = (x2,y2) , weight= value)
print(graph.edges[(index1,index2)]) # returns a first weight
print(graph.edges[(index2,index1)]) # returns a second weight
  • Complete Setup: to connect all the vertices together, in order to create a complete graph.
# the graph is already initialized with vertices, the wind is defined.
graph.addEdgesAll()
print(graph.edges) # all the existing links with their associated weight
  • Delaunay Setup: to connect the vertices with their closest neighbors, so that it automatically disqualifies long edges.
# the graph is already initialized with vertices, the wind is defined.
graph.addEdgesDelaunay()
print(graph.edges) # all the existing links with their associated weight

From the obtained graphs, it is easy to see that the Delaunay triangulation already facilitates the future work of solving algorithms. However, its major weakness is the possible absence of a final edge for returning to the starting point: an alternative edge (linking the ending point with the starting one) is created in this case, but it may encounter an obstacle.

If the wind speed is superior to 0, the weighted graph.edges[(vertexA,vertexB)] and graph.edges[(vertexB,vertexA)] are not equal due to wind penality.

2. Solving algorithms

The following algorithms can be tested by importing the Graph class from the graph.py script in the folder PathPlanning of the GitHub project.

a. The Random strategy

Although not very optimized, the use of randomness is a basic alternative to exact and costly algorithms that compare all possible path combinations. This algorithm provides good results for a large number of iterations.

  • Description
Init: The first path is randomly generated. 

Actualization: Two random points of the path are exchanged to create a new path. 
               If this new path is shorter, we keep this path. 
               Otherwise, we keep the previous one.
  • Implementation
x,y = [0,1,3,2.5,6,5,4],[0,1,6,1,0.5,4,1]
graph = Graph() 
graph.defineWind(angle=pi/2,speed=5)
graph.addVertices(x,y)
graph.addEdgesAll()
graph.solveRandom(nb_of_tour=100000,show_evolution=True)
graph.plot() # graph before resolution
graph.plotPath(gradual=True) # graph with found path 
plt.figure(1)
plt.show()

b. The Loop strategy

This method is more exhaustive than the random strategy since all possible pairs of vertices are exchanged and tested. One iteration automatically tests all pairs of vertices once, so this method needs fewer iterations than the previous one.

  • Description
Init: The first path is randomly generated. 

Actualization: For i in range(number_of_vertices):
                   For j in range(i) and j!=i :
                      Points i and j of the path are exchanged to create a new path. 
                      If this new path is shorter, we keep this path. 
                      Otherwise, we keep the previous one.
  • Implementation
x,y = [0,1,3,2.5,6,5,4],[0,1,6,1,0.5,4,1]
graph = Graph() 
graph.defineWind(angle=pi/2,speed=5)
graph.addVertices(x,y)
graph.addEdgesAll()
graph.solveLoop(nb_of_tour=100,show_evolution=True)
graph.plot() # graph before resolution
graph.plotPath(gradual=True) # graph with found path 
plt.figure(1)
plt.show()

c. The Nearest Neighbour strategy

The philosophy of this approach (greedy algorithm) is making the locally optimal choice at each stage. There is no guarantee to find the best optimal path, but at least a solution is proposed in a very reasonable number of steps.

  • Description
Init: The first point of the path is the starting point of the graph. 

Actualization: The next point of the path will be the nearest neighbor of the previous point.
  • Implementation
x,y = [0,1,3,2.5,6,5,4],[0,1,6,1,0.5,4,1]
graph = Graph() 
graph.defineWind(angle=pi/2,speed=5)
graph.addVertices(x,y)
graph.addEdgesAll()
graph.solveNearestNeighbour()
graph.plot() # graph before resolution
graph.plotPath(gradual=True) # graph with found path 
plt.figure(1)
plt.show()

d. The Genetic algorithm strategy

The last algorithm is inspired by Charles Darwin's theory of natural evolution. It reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation. Relevant results emerge with a minimal number of individuals and an high temperature.

  • Description
Init: A population of individuals is created. Each individual is a randomly generated path.
      The initial fitness score of each individual is calculated.

Actualization: Crisis: Only the best 50% of individuals survived (based on fitness score). 
               Children are born (a surviving individual duplicates himself two or three times, like some bacterias, to keep the population constant).
               Mutations occur: two random points are exchanged in the path of each individual.
                 If the individual is fitter, he survives.
                 Otherwise, if an individual has not become fitter with mutations, its chances of surviving are of 0.987 (luck).
  • Implementation
x,y = [0,1,3,2.5,6,5,4],[0,1,6,1,0.5,4,1]
graph = Graph() 
graph.defineWind(angle=pi/2,speed=5)
graph.addVertices(x,y)
graph.addEdgesAll()
graph.solveGenetic(temperature = 1000000, pop_size = 20, show_evolution=True)
graph.plot() # graph before resolution
graph.plotPath(gradual=True) # graph with found path 
plt.figure(1)
plt.show()

3. Implementation and comparison

  • Implementation

To solve your own TSP problem:

  1. Open the salesman_problem.py python script, and be sure to have in the same environment the following ones: graph.py, area_generator.py, boat.py. All can be found in the PathPlanning folder of the GitHub project.
  2. In the 'name'=='main' section, uncomment and customize the general shape and size of the graph (grid, circle, coastal...).
  3. Uncomment the edge creation method (all, Delaunay, ...)
  4. Uncomment the solving strategy (Random, Loop, Nearest Neighbours, Genetic,...)
  5. If you want to have in addition the simulation of the boat performing the path (otherwise comment those parts):
    • Precise the characteristics of the autonomous boat.
    • Choose the integration method (Euler, Rune-Kutta).
  • Comparison of solving strategies

A graphical tool was added to the code for a better understanding of the result. The path first is green and gradually becomes red until the end. There is no evolution of score over time for the nearest neighbor strategy because it needs only one iteration.

For a North wind, with all edges existing at the beguinning:

Actually, in the case of a simple rectangular grid, the nearest neighbor strategy seems to provides the optimal existing path (17.47 length). A trend for straight and parallel sections of path also emerges with other algorithms, but they cannot compete here with the score found by the first one, certainly because the process got stuck at a time and it asks too many changes to significantly decrease the total length (cf the convergence). The loop strategy converges faster than the random strategy. The genetic strategy needs more time than the others, but already offers a better score than the random-based algorithms. For an East wind, with all edges existing at the beguinning:

The observations are the same, but the sensitivity to the wind's direction is visible.

4. Additional shapes

For more realistic simulations with variable measuring zones, three shapes have been conceived in the area_generator.py script. A graphical tool is added to quickly visualize generated maps with the starting point colored in red.

  • grid shape
nb_of_points = 100
GPSpoints = np.array([0,0],[0,100],[100,100],[100,0],[0,0](/archetag/smart-water-quality-monitoring/wiki/0,0],[0,100],[100,100],[100,0],[0,0)) # 5 points for a rectangular contour 
grid = Area(nb_of_points,GPSpoints[0,:],GPSpoints,"grid")
grid.placeMeasurementPoints()
x = grid.points_lat.reshape(nb_of_points).tolist()
y = grid.points_lon.reshape(nb_of_points).tolist()
grid.generateMap() # plot 
#  grid.generateFile()  # to write in a points.txt file 

# to use in the *graph.py* script to read the *points.txt* file 

# begining,lat,lon = readData("points.txt")
# x_list_utm,y_list_utm = LatLonToUTMXY(lat,lon)
# x_list,y_list = normalize(x_list_utm,y_list_utm)
  • circle shape

This shape adapts to measurement zones that should particularly focus on a specific point, far from the coast. The Delaunay edges construction method and the Nearest Neighbor strategy are highly recommended for this shape.

center, beginning = [1,1],[4,4]
circle = Area(65,beginning,beginning,"circle",center, angle_division=16)
circle.placeMeasurementPoints()
x,y = circle.points_lat, circle.points_lon
circle.generateMap()
  • coastal shape

This shape was though to reproduce irregular coastal contours.

GPSpoints = np.array([1,1],[10,1],[10,10],[9,9],[8,9],[7,10.8],[6,10.8],[6.5,10],[6,8],[5,11],[4,9],[3,8.5],[2,11],[1,10],[1,1](/archetag/smart-water-quality-monitoring/wiki/1,1],[10,1],[10,10],[9,9],[8,9],[7,10.8],[6,10.8],[6.5,10],[6,8],[5,11],[4,9],[3,8.5],[2,11],[1,10],[1,1))
coast = Area(100,GPSpoints[0,:],GPSpoints,"coastal")
coast.placeMeasurementPoints()
coast.generateMap() # plot
x,y = coast.points_lat, coast.points_lon

Note: graphs are built with an additional option for coastal shapes : #G = Graph(coast.contour) instead of #G = Graph().

The Delaunay method may appear as not fully reliable for this kind of area. On the contrary, the allEdges method is more likely to guarantee alternative paths to leave from the points inside sensible zones (near borders).

Obstacles avoidance strategies need to be implemented to allow the perfect exploitation of this shape (next wiki):