Why don't you use B-Spline curve to generate continuously differentiable path

[yiakwy]

In 3D reconstruction, there is a famous clean implementation (contrast to PINV-K algo) to generate B-Spine curve Autonomous Vehicles at O(nlogn) cost where n represents the number of points. I don't understand why you used dynamic programming for spline curve generation, because DP means nearly brute force search and easy to write but no more benefits brought.

Another problem I am concerned about is that there is no detailed benchmark test (time consuming, latency, precision etc.) report about task optimizers. Could you give me more hints on big idea how you implemented it?

There are still some gaps between Perception and "Planner". I am trying to use log trace back the data flow. However, since I am not familiar with ROS, it might take times. Any help will be appreciated. For example, once caffe accepts raw features draw from Lidar points and provide features help Object Cluster to update tracker lists, and then RPC call might finish and I have no idea what happened before data frame enter into EM planner optimizers main loop.

[lianglia-apollo]

Thanks a lot for your comments. I will provide a brief answer to the B-spline part.

In Apollo's algorithm, trajectory generation is divided into two parts -- dynamic programming and quadratic programming. The DP algorithms are used to provide decisions on obstacles, which are transformed to boundary conditions in QP. We believe that with fine tuning costs, DP is good to make decisions (on obstacles, including left nudge, right nudge, overtake, yield, etc ...). We are unable to directly reach the step of curve generation.

Many methods, including B-spline, can be used for smooth curve generation, but it will be difficult to generate curves that cover all corner cases from varies environments without pre-calculated decisions.

If you have any suggestion on how to use B-spline curves to replace the current algorithm, please let us know.

[yiakwy]

@lianglia-apollo In B-spline curves, control points except the first and the last ones will never be touched by generated curves. Hence we can sample points in the corners, lanes, obstacles. I have implemented them a long time ago but I know the following truths:

1) it is not hard by following "de Boor" scheme or "divide and conquer" scheme based on bezier Castelijau scheme , I have codes loose coupled with OpenGL demo 2) by sampling control points, you can avoid anything you want 3) you can adjust it by increasing or decreasing degrees

[lianglia-apollo]

It is possible to do it this way. It seems DP or some other method with similar complexity is needed to find the control points?

[jmtao]

@yiakwy hope our answer resolved your question. We will close the issue for now. If you have any additional question, please feel free to open an new issue. Our engineer team are more than happy to help that.

Thank you for supporting Apollo!

[yiakwy]

@lianglia-apollo @jmtao I have created a random library (supporting generate control points and knots sparsely using statistic sampling algorithms ). It draws smooth curve by using De Boor algorithm adaptively (you don't need to explicitly specify how many sampling points you want) Currently I used it for opendrive format alike map generation, and curves planning (to escape unwanted points).

If you don't have plan to support it, let me do the job. Currently it supports "Rad", "Snake", alike shapes .

Any suggestions ?