<p>In this article :<br>
Kinodynamic Motion Planning<br>
B. Donald, P. Xavier, J. Canny, J. Reif<br>
<a href="https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf" rel="nofollow noreferrer">https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf</a>  </p>

<p>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. </p>

<p>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.<br>
Instead the complexity that is noted on page 5 of the article is this :</p>

<blockquote>
  <p>$O( n( \frac{lv\gamma³}{\epsilon⁶})^d)$</p>
</blockquote>

<p>$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$.  </p>

<p>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? </p>

<p>Thanks </p>

CC BY-SA 3.0
2017-03-10T18:35:57.103Z
_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.
PsySp
CC BY-SA 3.0
2017-03-11T07:50:19.267Z
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.
David Eppstein
CC BY-SA 3.0
2017-03-11T12:58:21.783Z
@PsySp my bad they're not the same n's, I'll change the first n
J. Schmidt
CC BY-SA 3.0
2017-03-11T13:09:21.147Z
@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.
J. Schmidt
<complexity>
Why does this algorithm not have an exponential complexity?
J. Schmidt
# Why does this algorithm not have an exponential complexity?

(Asked by: username_0 on 2017-03-10)

In this article :  
Kinodynamic Motion Planning  
B. Donald, P. Xavier, J. Canny, J. Reif  
<https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf>

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?

Thanks

**Tags:** complexity

> **Comments:**
> **username_1**: _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.  
> **username_2**: 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.  
> **username_0**: @username_1 my bad they're not the same n's, I'll change the first n  
> **username_0**: @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.  

---

## 0 answers

