# What are the state-of-the-art algorithms for pathfinding on a continuous map of the Earth?

Suppose I have got a solar-powered autonomous surface vessel somewhere in the fjords of Norway, supplied with a fairly recent set of maps, a GPS receiver, and no means of downlinking detailed commands from me. This vessel has to reach, say, the island of Hainan at the earliest possible moment.

• What are the deterministic algorithms for finding a maritime route on a globe?
• What is their time and memory complexity?

• Can I, for instance, use A* after transforming the map of the globe into a diagram with connected polygons (i.e. Delaunay triangulation on a sphere/ellipsoid) and what are other feasible approaches?

Answers should ideally provide references to papers with discussion of the above-mentioned questions.

As pointed out by Rob Lang, the algorithms must fit the usual criteria: in the absence of time constraints, lead to the shortest path between any two points on Earth's oceans and seas, or indicate pathfinding failure otherwise.

There are interesting sub-topics here (trading pre-computation time/storage for online computations, providing slightly suboptimal routes before a deadline kicks in etc.), but these are ancillary to the main issue.

## migrated from ai.stackexchange.comFeb 24 '14 at 18:18

This question came from our site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment.

• @JDong - land-based navigation follows routes/roads, by and large, hence A* comes naturally. A pre-built graph is what I'd use. – Deer Hunter Feb 14 '14 at 5:12
• Ah, I missed the critical part of your question: 'continuous'. In that case perhaps vector or potential fields might be promising. – JDong Feb 14 '14 at 5:18
• @RobLang - question edited. – Deer Hunter Feb 14 '14 at 9:44
• For a maritime route you will need to take sea levels, wind and water flow into calculations. What kind of ship we are talking about? OpenSeaMap provides some shipping lanes. If you could use those A* would work. I also think this question is to broad for this beta. – PiTheNumber Feb 15 '14 at 19:24
• I think this question is okay if it just asks for the best dynamic pathfinding algorithms for continuous spaces of today. I might attempt answering this later today after a little bit of research. – JDong Feb 16 '14 at 22:27

The deterministic requirement isn't all that constraining. That just implies your vehicle is certain of the state it's in. That being said, you'll probably want to plan paths in a way that allows you to avoid obstacles. The best way I've seen this done is with sampling-based planners. Steven LaValle wrote the central academic resource on this topic: Planning Algorithms.

The RRT* algorithm is among the planners he describes. This algorithm generates the state space tree with random samples and a few heuristics to ensure feasibility (e.g. obstacle avoidance) and optimality. Details on RRT* can be found in LaValle's book, or at Sertac Karaman's website. The asymptotic time and memory characteristics are described as O(nlogn) to process, and O(n) for queries. The algorithm is linear, O(n), in space complexity too.

• Upvoted for the refs. Will consider accepting upon reading LaValle's book and checking out the RRT* stuff. Thanks! – Deer Hunter Feb 18 '14 at 12:37

For your further consideration, potential fields are an interesting, low-cost choice for pathfinding. You would place a strong charge at the destination, and eventually the agent would arrive at the charge. A more technical article by the International Foundation for Autonomous Agents and Multiagent Systems provides more insights.

Vector fields are also a very cheap solution, but more often used for multi-agent pathfinding. Vector fields are very good however for open areas. None of the above methods guarantee the shortest path however, sacrificing optimal pathing for better dynamic response.

Combined approaches are also strong, such as using A* beforehand to generate waypoints and using vector fields to go to each waypoint. This will probably give much more optimal behavior on a macro scale.

Keep these in mind in case you acquire a swimming robot army.