For a robotic application, I am looking for a mathematical tool for finding the best curve passing by or near (up to a certain radius) from waypoints as shown below. The pink circles are obstacles that should be avoided at all cost.
I looked at NURBS or Bezier curves, but most of the examples I found do not intersect with waypoints.
The criteria for finding the curve are:
- Minimum distance
- Maximum curvature (or tangential velocity)
- Avoid obstacles.
Our initial approach was to use A* algorithm to find the shortest path between two points. Then keypoints are identified from the yellow curve and a smooth, continuous curve is computed. It is quite easy to draw such curve by hand, but I currently found no reliable tool or mathematical approach to automate the process.
What would be a good mathematical approach for such problem?
Constructing a curve that passes through your “way points” is fairly simple. For example, you could construct a spline curve that interpolates these points. Look up the term “spline interpolation”, or start here.
Regarding your constraints on distance (arclength) and curvature, they are contradictory, and you’ll need to find a way to balance them. The shortest curve is a piecewise linear one, with a straight line between each consecutive pair of way points, but this obviously has infinite curvature at the way points.
I suspect that what you’re really trying to do is minimize the travel time of the robot. To do this, you have to vary both the path and the velocity. This is a well-studied problem in robotics. Consult the literature.