CSCE 452/752: Homework 17

$ \def\R{\mathbb{R}} \def\C{\mathcal{C}} \def\Cfree{\C_{\rm free}} \def\Cobst{\C_{\rm obst}} \def\qinit{q_{\rm init}} \def\qgoal{q_{\rm goal}} $ We described the motion planning problem in terms of these inputs:

A description of $\Cfree$.
A start configuration $\qinit \in \Cfree$.
A goal configuration $\qgoal \in \Cfree$.

And these outputs:

A path through $\Cfree$ from $\qinit$ to $\qgoal$, if a path exists.
A failure status, if no path exists.

Consider the Probabilistic Roadmap (PRM) algorithm applied to this problem.

[a] If the PRM returns a path, can we be certain that the path travels through $\Cfree$ from $\qinit$ to $\qgoal$? Answer YES or NO and give a persuasive argument to support your answer. (5 points)

[b] If the PRM fails to find a path, can we be certain that no path in $\Cfree$ from $\qinit$ to $\qgoal$ exists? Answer YES or NO and give a persuasive argument to support your answer. (5 points)