I have code for using particle swarm optimization to find an ~optimal path between two points. I call this the Goto planner. However, this is not the only type of path planning relevant to this project. I have now implemented three separate planner modules to handle three planning tasks. Each module it its own python library. A mission planner python program handles the complete planning system, and calls these libraries.

Target Selection Path Planner The analyst role generates a number of targets. These targets have an interestingness score and dimensions. The target is not a single point, but a shape that the robot should cover. In order to effectively visit these targets, the mission planner must decide which targets to visit and in what order. The robot wants to maximize the overall interestingness covered. However, the robot must also end the day at one of several safe zones. The optimization problem is basically traveling salesman but choosing from a pool of endpoints for the last node to visit.

I used genetic algorithm with a chromosome where each gene is an integer index into a list of points to visit. For all genes expect the last, these index a table of targets. The last gene indexes a table of safe zones. The start position is not in the chromosome since it is set by the robot’s current position.

A simple/naive approach is to measure the fitness of a straight line between each points. The fitness would be determined by the distance, energy use, and terrain presence along the line. However, the actual path taken is unlikely to be a straight line. Eventually, the Goto planner will make a better line. But the Goto planner is slow and it is not feasible to plan between each pair of a potentially large number of targets (and their many possible links).

So, I use some simple heuristics to get an idea of the path complexity. I penalize the presence of obstacles on the line as normal. But for currents, I sample points within a margin along the line. I collect a number of current magnitudes at different times and give an overall complexity score. It does not go so deep that it considers whether or not those currents will hurt or help, since sampling points does not reveal is there is a consistently helpful path. But it does promote taking paths that are overall less intensive. (Note that I should also sample points for terrain. It could quickly give insight into how hard terrain avoidance will be.)

Coverage Path Planner Once at a target, the robot needs to do area coverage. My coverage algorithm is a very simple GA implementation that generates a movement path between nodes. The allowed moves are forward, back, up, down, and skip. The purpose of skip is to handle the unknown chromosome length needed. Suppose you have 20 points you need to visit to effectively cover a region. If there is no terrain, there should be no repeated nodes. But in the presence of terrain, you may need to revisit nodes. So the length of the path will be longer in that case. My simple strategy was to allow an extra percentage of the number of nodes. But using the skip, GA can fill in a gene with nothing. Another technique I implemented is to allow some wiggle room around the target area. Again, suppose there is a terrain blocking the robot. It may be shorter to go around the terrain into space outside the region instead of a longer path that intersects visited target nodes.

Geometric-based coverage planners may be much better suited to the movement dynamics of boats. (Source? I read this somewhere, but I don’t see it in 20 seconds of Googling) Spiral paths, etc have been shown to be effective. But it was easy for me to leverage my familiarity with metaheuristic algorithms on node/grid-based environments to quickly produce a usable planner. At this point, I want to have each planner in place so that I can get results. Then, I can consider improvements.

Goto Path Planner I have discussed this at length.