In this article :
Kinodynamic Motion Planning
B. Donald, P. Xavier, J. Canny, J. Reif

The authors present a PTAS algorithm that can compute a safe, close to optimal trajectory from a point A (having a certain speed vector) to a point B (having a certain speed vector). They do this by transforming the problem to finding the shortest path in a directed graph. All vertices in the resulting directed graph have an outgoing degree of 3.

I don't understand how we can find the shortest path in this directed path from one point to another (by using BFS) without the complexity being exponential, since doing a BFS from the starting point until we encounter the end point would take $O(3^x)$ with $x$ being the layer of the BFS.
Instead the complexity that is noted on page 5 of the article is this :

$O( n( \frac{lv\gamma³}{\epsilon⁶})^d)$

$n$ being the number of bounding halfplanes on obstacles, $l$ being the length of the side of a cube in which all points are placed, $v$ is maximum velocity and $\gamma$ is maximum acceleration divided by maximum velocity. $\epsilon$ as always is the approximation value and $d$ the number of dimensions in which our problem is placed. For simplicity let $d$ be $1$.

Clearly we can see this complexity is not exponential, my question is why? Even in one dimension, we still obtain a graph in 2 dimensions (1 for position and one for velocity) and the BFS will still take exponential running time. Am I missing something?


  • $\begingroup$ the BFS will still take exponential running time. Exponential in what? Also, it seems you are mixing n: is n the layer of the bfs or the number of bounding hyperplanes? You should think how the former and the later are connected. $\endgroup$
    – PsySp
    Mar 10, 2017 at 18:35
  • 4
    $\begingroup$ Are you using the AI version of the analysis of breadth first search, where you don't bother to remember already-visited vertices and the time is (branching factor)^(search depth)? You need to be using the CS theory version of the analysis (please note the board on which you posted this question), where vertices once added to the BFS queue are marked so that they are never added again, and where the time is proportional to the size of the whole graph being searched. $\endgroup$ Mar 11, 2017 at 7:50
  • $\begingroup$ @PsySp my bad they're not the same n's, I'll change the first n $\endgroup$
    – J. Schmidt
    Mar 11, 2017 at 12:58
  • 2
    $\begingroup$ @DavidEppstein Thanks, I think this might be where I went wrong. I was probably thinking of the AI version instead of the CS theory version of the analysis. This would make sense, if the complexity stated would be proportional to the size of the graph. I don't directly see the link, but I'll look at it again to verify. $\endgroup$
    – J. Schmidt
    Mar 11, 2017 at 13:09


Browse other questions tagged or ask your own question.