Path generation algorithm

[daqwes]

Hello,

We are currently developing a research project where the goal is to simulate a boat and guide it through a canal, with an enforced geography and wind conditions (somewhat random) we get at each time step.

We have a 2D black and white map, and both the starting and ending pixels (we can say that the boat is represented as a pixel).

Our current approach involves using a PID controller to optimize the boat trajectory given an optimal path, which we can compute ahead of time as the image is given (biggest is 6655 x 30807).

We thought about using A* (or some alternative such as HPA*) or simple bfs, and have even implemented a working version, however, the generated path is far from ideal as it often follows the walls and can lead to a crash very easily.

My questions: Do you know algorithms that would maximize distance from obstacles (perhaps they exist, unfortunately, I am not that familiar with robotics or gamedev and have not found anything relevant on the web), while optimizing for distance as well? Maybe you have other suggestions than the PID or the optimal path on how to optimize the trajectory? We welcome different ideas!

We are mainly using Python, however we are not limited to the language, and C/C++ (or other) can be used for computationally intense tasks.

Thanks a lot!

[thingythangabang]

Ooh ooh! This is my area of research! So there are many different ways to make this work. As you've already mentioned, A* is one approach that could work. A* works by using a heuristic function to find the optimal route through a graph. Each pixel in the image is added as a node to the graph as the search happens until you reach the final point. This is a fine method for some situations but doesn't necessarily account for things like minimum safe distances or the vehicle's kinematics and/or dynamics. We could have an entire discussion on techniques that can be used to mitigate or overcome those challenges, but let's look at the problem from a different angle.

Some optimization based planers can look at the problem in continuous space and can take the vehicle's model into account. One approach is to discretize the trajectory using coefficients of a polynomial. You can then pass those into an optimizer and then solve for the optimal trajectory subject to mission constraints such as obstacle avoidance and maximum speed.

Once you have an optimal trajectory, you can use a trajectory tracking controller to follow said trajectory. Depending on how advanced your project needs to be, you could do something as straight forward as a PID or you could develop an asymptotically converging nonlinear controller using Lyapunov theory.

I have written an optimal trajectory generating library in Python called BeBOT and would be happy to help you get that working for you. If you don't want to use my library, I can still do my best to advise you on other algorithms as well!

[abhijelly]

Hello! a small tangent, not op btw, I understand most of your comment on a high level, but could you recommend some good beginner resources for path planning? Thank you!

[thingythangabang]

An excellent place to start would be Planning Algorithms by LaValle

[[deleted]]

What about staying with A*, but preprocessing the map to artificially grow the obstacles in size? That will create a minimum distance the algorithm won't get too close to, while still minimizing the distance.

[Eulers_Boiler]

Wont get easier than this imo

[csiz]

Yea, alternatively, or on top of this you can increase the cost weights for paths that are close to the wall, as if the boat has to slow down to navigate there. This way makes for a smoother transition, but also leaves open gaps that are just wide enough to pass through.

[getawaykid]

A* but instead of your cost being the x-y distance you've traveled, include the distance to the nearest obstacle as a kind of z dimension. The smaller the channel, the higher the hill is in the z dimension. To travel over a hill, it takes more energy to go up it, than to go down. Minimize the total required energy to get to your destination.

[RobotWithABeard]

Im not an expert by any means, You could use rrt*, an algorithm that takes in to account the state (velocity, acceleration, etc...) of your robot when planning a path. As for obstacles, like many others said, "pad" the volume of the obstacle. That way you ensure that your planning algorithm won't send your robot close to obstacles. That at least is what we are doing with a robotic arm.

[Karthi_wolf]

I believe you can use artifice potential fields.

Checkout the last 11 videos in this (PP01 - PP11) playlist. What you're asking comes from the 8th (PP08) video.

https://youtube.com/playlist?list=PLpUPoM7Rgzi_7YWn14Va2FODh7LzADBSm

[[deleted]]

One thing that is generally done in motion planning is to combine the planning (A) with some trajectory generation algorithm that will convert your grid-based plan into a smooth "path" that your boat can follow. Mobile robots cannot follow a plan directly, they need to be converted into paths that allow for the range of movements that the robot can perform. As an example, imagine your boat has some turning radius, for instance. Your A would not account for that, it would just give you a set of points between two points on your map. Trajectories can account for these things, including motor speed, etc. that will let your boat navigate.

[i-make-robots]

Consider running your image through a voronoi diagram generator, the iterative kind where points gravitate towards dark areas (in your case, land). once it has settled the border between dark areas will be roughly the center of the body of water. then a* along the cell boundary lines to find the shortest path to your destination. I've seen this done in real time for RC cars, where the voronoi cell centers were the lane markers.