Wiki : Integration of borders and obstacles into the map - archetag/smart-water-quality-monitoring GitHub Wiki

Wiki : Integration of borders and obstacles into the map

The majority of coastal areas have irregular borders and obstacles. Then, the autonomous boat must integrate obstacle avoidance strategies when planning its path.

1. Avoid obstacles with short detours
2. Exploit Voronoi diagram against too many obstacles

Material needed

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

This wiki assumes you have already read the Four strategies to find our way wiki section.

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

1. Avoid obstacles with short detours

To make sure the boat will avoid obstacles without modifying its general trajectory, obstacles can be circumvented with safety distance as presented in Optimization Based Motion Planning With Obstacles And Priorities by Greiff and Robertsson.

Steps of the algorithm

Polygon obstacles are inflated accordingly to a safety distance. Edges intersecting this new polygon are removed.

All pairs of points with no edges linking them anymore are identified.

For each pair of points (A,B), summits of the safety polygon that are directly accessible from them are kept as new trajectory candidates. With projection (consult the paper for more details), the more insightful ones are selected.

Finally, the candidates allowing the shortest detour are selected, the newly formed path is added to the graph.

Implementation

Open the graph.py script in the PathPlanning folder of the GitHub project.
Copy-paste the following code:

# measurement points
x,y = [0,1,3,2.5,6,5,4],[0,1,6,1,0.5,4,1]
# graph
G = Graph()
G.defineWind(angle=pi/2,speed=5)
G.addVertices(x,y)

# uncomment the edges building method
#G.addEdgesAll()
G.addEdgesDelaunay()

# obstacles
obx,oby = [3,3.25,3.5,3.5,3],[0.5,0,0.5,2,2]
G.addPolygoneObstacleAtCoords(obx,oby,safety_distance = 0.2)
#obx2,oby2 = [2.5,7.5,7.5,5,2.5],[0,0,15,17,15]
#G.addPolygoneObstacleAtCoords(obx2,oby2,safety_distance = 0.2)
    
# uncomment the solving strategy
G.solveRandom(100000,show_evolution=True)
# G.solveLoop(100,show_evolution=True)
# G.solveNearestNeighbour()
# G.solveGenetic(temperature = 1000000, pop_size = 20, show_evolution=True)
    
# plotting 
G.plot()
G.plotPath(gradual=True,obstacle_x = obx, obstacle_y = oby)
plt.figure(1)
plt.show()

You can add as many obstacles as long as the coordinates of their contours are positive.

2. Exploit Voronoi diagram against too many obstacles

In another scenario, where the boat needs to go through a zone with multiple obstacles but does not need to make measurements, Voronoi diagram is a common tool for avoiding obstacles.

Steps of the algorithm

The coordinates of the edges of the obstacles as well as the frame of the zone are the points used to obtain the Voronoi diagram. Concave obstacles are transformed into convex polygons for convenience.

The Voronoi diagram is generated. Edges passing trough obstacles or inside them are identified and removed.

Finally, Dijkstra's algorithm is used to join another point using the shortest path.

Implementation