1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ How many vertices does the graph have? Are you familiar with en.wikipedia.org/wiki/…? $\endgroup$
    – D.W. ♦
    Commented Mar 12, 2017 at 14:59
  • $\begingroup$ @D.W. the graph has l/(aτ²/2) * l/(aτ/2) vertices, with τ being a timestep chosen at the start of the algorithm in function of epsilon and a. In the link you posted, the time complexity is stated to be O(|V|+|E|) but higher up on the page, this complexity is stated equal to O(b^d). It is not specified what b and d are however, but this means it's still exponential right? $\endgroup$
    – J. Schmidt
    Commented Mar 13, 2017 at 8:10
  • $\begingroup$ I suppose the complexity of this BFS can be expressed both as O(3^x) or as O(|V|+|E|)? The second one being used to obtain the complexity stated in the paper? $\endgroup$
    – J. Schmidt
    Commented Mar 13, 2017 at 8:23

1 Answer 1

Reset to default
1
$\begingroup$

The graph in question is a grid discretization of the phase space ($TC$ in the paper). Consider a 4-connected grid in the plane with 10x10 vertices. The branching factor of this graph is 4 (ignoring the boundary), but there are only 100 vertices in this graph total. BFS on this graph will not take exponential time because BFS throws away exponentially many paths by keeping track of nodes that have already been "explored" and not adding them back to the queue.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.