I am working on motion planning algorithm for quadrotor. As I have learned in Coursera Aerial robotics course, trajectories for quadrotors should minimize snap which is equivalent to interpolating waypoints with 7th degree polynomial. It's not very hard to interpolate them. However I am not sure how to make trajectory satisfy constraints on maximum velocity and acceleration. I am aware of parametrization and temporal scaling but in order to satisfy constraints it is necessary to find maximum velocity and acceleration achieved in planned trajectory. Unfortunately if function of position is 7th degree polynomial then velocity is a function of 6th degree polynomial and it would be necessary to find roots of 5th degree polynomials in order to find critical points in velocity function. The only method, I am aware of, which can solve the problem is based on computing eigenvalues of a companion matrix and it is iterative. Personally I do not like any iterative methods in run time.

Based on what is said in the above I have several questions:

1. Is it okay to solve polynomials equations with described method in run time? Especially if fast trajectory re-planning is required?

2. Maybe there is a way not to strictly satisfy the constraints but give some bounds on the planning results? Like in 95 percent trajectory will be fine and in other 5 percent it is possible to re-plan it when out of bound constraint is detected.

3. Will it make a big difference if I interpolate waypoints with 3d order polynomials instead of 7th? In case of 3d order polynomials problem of searching for critical points for velocity and acceleration becomes a trivial task.

4. Maybe there is totally another way of dealing with trajectories which exceeds bound on maximum velocity and acceleration?


  • $\begingroup$ Not a full answer. There are other (iterative) polynomial root-finding algorithms such as Durand-Kerner method, which, in my experience, can actually give solutions with better accuracy than solving Eigenvalue problems. Also, iterative algorithms are not always too bad. Finding all roots of a quintic can be done in something like tens of microsecond (implemented in C++). $\endgroup$ Jun 1 '19 at 6:48
  • $\begingroup$ @PetchPuttichai thank you for your answer. I also found two other iterative methods and I am sure that they can be fast. But what I am not sure about is the convergence. Do they always converge? Is it possible that some of the reals roots will be missing because of numerical issues and etc. I was not able to find information about that. $\endgroup$
    – Long Smith
    Jun 2 '19 at 7:45
  • $\begingroup$ I don’t have enough knowledge about the convergence. But what I’ve seen is solving for eigenvalues of a companion matrix is prone to error especially when there are repeating roots. It’s gonna be difficult to decide which roots are real/complex due to numerical errors. You’d also certainly need some other numerical procedures to refine those roots afterwards. $\endgroup$ Jun 4 '19 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.