Strategy for 3D path planning over large distances with kinodynamic constraints

I was hoping to pick your brains about a problem that even after much reading has left me baffled.

My Application: For the sake of simulating underwater scenarios in very large environments (up to 100 km by 100 km in the X-Y plane), I am attempting to implement a path planner capable of planning a path that brings an underwater vehicle such as a submarine from a the starting position to a final 3D waypoint while avoiding obstacles. The vehicle will have high level knowledge of the map for things like the location of the ocean floor, and will sense other obstacles as it moves through the environment. The environment will not be obstacle dense, but they can be moving (other submarines, etc)

My general problem: Underwater vehicles such as submarines have significant kinodynamic constraints associated with them. This makes using strictly geometric planners such as RRT*(the geometric version anyway...) or D*-Lite unrealistic, since the generated path could be entirely unimplementable by the vehicle even after smoothing. However, kinodynamic path planners cannot be reasonably applied over such large distances due to their computational complexity, especially in the context of new obstacles potentially being discovered all the time, requiring repairing or re-planning of the path. Are there standard methods for dealing with these type of complex scenarios that I am unaware of? Otherwise, can anyone propose a strategy well suited to this type of problem? Thank you.

One idea I had was to use a geometric planner like RRT* as a 'global' planner' that generates a coarse plan that would then be roughly followed by a 'local' kinodynamic planner such as RRT-X. The local planner would ensure nearby obstacles are avoided while adhering to the constraints of the vehicle. I am a complete novice in this area though so I am unsure if even that is reasonable.

• Do you anticipate replanning? – holmeski Jul 18 '18 at 18:49
• Have you looked into life long planning? – holmeski Jul 18 '18 at 18:49
• I do anticipate replanning because, for example, the submarine could detect something like a mine. These mines would then define an enormous obstacle (blast radius) that the submarine would have to avoid, potentially impeding the current path. Thus, it would be preferable if the planner could utilize its old information and just replan a path that goes around the new obstacle, such as with D*-lite. I have not looked into life long planning. I will do that now. Thank you for the tip! – user1964932 Jul 18 '18 at 19:16
• What makes you think this requires kino dynamic path planning? – holmeski Jul 18 '18 at 19:18
• I think I at least something that utilizes motion primitives in the path generation, because of the limited mobility of the vehicles in question. For example, in 3D, a geometric path planner might decide that the optimal way to go around an obstacle is to go right up to it and then dive while also turning left or right. That isn't something that a submarine can really do. It is essentially limited to either moving up/down, or navigating in the 2D X-Y plane, but not at the same time. Thus, a geometric planner may yield a path that is difficult or impossible for the vehicle to follow. – user1964932 Jul 18 '18 at 19:29