
\section{Introduction}

	Two decades ago LaValle and Kuffner presented the \emph{Rapidly-exploring Random Tree} ({\tt RRT}\xspace)~\cite{LaVKuf01} method for sampling-based motion planning. Even though numerous alternatives for motion planning have been proposed since then, {\tt RRT}\xspace remains one of the most widely used techniques today.  This is due to its simplicity and practical efficiency, especially when combined with simple heuristics.
	
	RRT is especially useful in single-query settings, as it focuses on finding a single trajectory moving a robot from an initial state to a goal state (or region), rather than exploring the full state space of the problem, as roadmap methods do, such as {\tt PRM}\xspace~\cite{KavETAL96}. To achieve this objective, {\tt RRT}\xspace grows a tree, rooted at an initial state, which is periodically extended towards random state samples until the goal is reached.
	
	Notably, {\tt RRT}\xspace is well suited to complex motion planning tasks and, in particular, problems involving kinodynamic constraints. This is due to the fact that {\tt RRT}\xspace can be implemented
	without a steering function\footnote{This function returns a path between two states in the absence of obstacles. It corresponds to solving a two-point boundary value problem (BVP), which may be a difficult task for many dynamical systems.}, which is difficult to obtain for many systems with complex dynamics. Moreover, {\tt RRT}\xspace has the advantage of low dependence on parameters and is easily extendable to a variety of domains (e.g., {\tt graspRRT} for integrated motion and grasp planning~\cite{VDAD10}).
	
	Since its introduction, numerous variations and extensions of {\tt RRT}\xspace have been proposed (see, e.g.,~\cite{JailletCS10,YershovaJSL05,JYLS05}), to allow improved performance.  While {\tt RRT}\xspace is not asymptotically optimal (AO) and provably does not converge to the optimal solution \cite{NecETAL10,KF11}, it forms the basis of many AO planners, including {\tt RRT}$^*$\xspace and {\tt RRG}\xspace~\cite{KF11}. In particular, the probabilistic completeness (PC) of  most of the aforementioned {\tt RRT}\xspace-based algorithms is derived from the PC properties of {\tt RRT}\xspace. 
	
	Surprisingly, it is not completely obvious under what conditions {\tt RRT}\xspace is probabilistically complete, especially when using forward propagation of controls for the kinodynamic case. Indeed there has been some debate on this issue in the related literature~\cite{KunzS14,CaronETAL17}. This paper aims to address this gap. 
	
	\subsection{Contribution}
	We provide two new proofs of PC of {\tt RRT}\xspace. The first one for the purely geometric setting, where we only require that the solution path has a certain clearance from the obstacles. For the kinodynamic case with forward propagation of random controls and duration, we add mild Lipschitz-continuity conditions. This line of work lays sound foundations for arguing the probabilistic completeness of the variety of methods whose PC relies on that of  {\tt RRT}\xspace. 
	


	
	Section~\ref{sec:related_work} describes related work and  Section~\ref{sec:geometric_proof} proceeds with the probabilistic completeness proof for the geometric case. Section~\ref{sec:kinodyn} gives a proof for the kinodynamic setting.
	A discussion on further research appears in Section~\ref{sec:future}.
	




	









	



	




	
	

	

	
	\section{Related work}
	\label{sec:related_work}
	Sampling-based algorithms are among the state-of-the-art alternatives for robot motion planning. Since their introduction in the mid 90's (e.g., {\tt PRM}\xspace, {\tt EST}\xspace~\cite{HLM97} and {\tt RRT}\xspace), they have been used in numerous robotic tasks. Sampling-based motion planners are also widely used in various fields other than robotics, such as computational biology and digital animation. There are recent reviews that provide a comprehensive coverage of developments in sampling-based motion planning~\cite{ES14, CRCbookChap51}.
	
	Sampling-based planners can potentially provide the following two desirable properties; (i) \emph{probabilistic completeness (PC)} and (ii) \emph{Asymptotic (near)-optimality (AO)}. The former implies that the probability that the planner will return a solution (if one exists) approaches one as the number of samples tends to infinity. AO is a stronger property, as it implies that the cost of the solution returned by the planning algorithm (nearly) approaches the cost of the optimal solution as the number of samples tends to infinity.
	
	The definition of AO variants of {\tt RRT}\xspace and {\tt PRM}\xspace, i.e., the {\tt RRT}$^*$\xspace and {\tt PRM}$^*$\xspace methods, was achieved more recently~\cite{KF11}.  The same line of work introduced another AO planning algorithm, {\tt RRG}\xspace, which constructs a connected {\tt PRM}\xspace-like roadmap in a single-query setting. Interestingly, the PC property of both {\tt RRT}$^*$\xspace and {\tt RRG}\xspace relies entirely on the PC property of {\tt RRT}\xspace. Since then, many variants of {\tt RRT}$^*$\xspace and {\tt RRG}\xspace have been devised ~\cite{GamETAL18, SalH16, ArslanT13, Naderi15, OtteF16, DevETAL16}, most of which inherit their PC and AO properties from {\tt RRG}\xspace and  {\tt RRT}$^*$\xspace. A different series of planners implicitly maintain a {\tt PRM}\xspace structure to guarantee AO planning~\cite{JSCP15,ManETAL18,SolHal17,GamETAL15}. A recent paper develops precise conditions for {\tt PRM}\xspace-based planners (in terms of the connection radius used) to guarantee AO~\cite{SK18}.
	
	Although {\tt RRT}$^*$\xspace, {\tt PRM}$^*$\xspace, and their extensions, were initially developed to deal with geometric planning, they can be extended to kinodynamic planning. This requires proper adjustments to the algorithms and the proofs~(see, e.g.,~\cite{SJP_ICRA15,SJP15,KarFra10, KarFra13,WebBer13,PerETAL12,XieETAL15,GorETAL13}). Nevertheless, these approaches require the use of a steering function, which limits their application to systems for which such a function is readily available. Recent work proposes a different type of approach, called {\tt SST}\xspace, which employs only forward propagation~\cite{LiETAL16} and achieves asymptotic near-optimality. Hauser and Zhou propose a simple yet effective approach termed {\tt AO-RRT}\xspace, which employs a forward-propagating {\tt RRT}\xspace as a black-box component~\cite{HauserZ16}, to achieve asymptotic optimality.
	
	\subsection{PC of Kinodynamic {\tt RRT}\xspace}
	LaValle and Kuffner discuss completeness of {\tt RRT}\xspace in kinodynamic setting in one of the early works on the subject~\cite{LaVKuf01}. While this work provides strong evidence for the PC of {\tt RRT}\xspace, it only provides a proof sketch that does not fully address many of the complications that arise in analyzing sampling-based planners, be it a geometric or kinodynamic setting. For instance, the proofs in that paper assume the existence of ``attraction sequences'' and ``basin regions'', whose purpose is to lead the growth of the {\tt RRT}\xspace tree toward the goal. It is not clear, however, whether such regions exist at all and for what types of robotic systems. It is also not clear whether the number of such regions is finite, and whether it is possible to produce samples in such regions with positive probability.  Similar concerns were expressed by Caron et al.~\cite{CaronETAL17}.
	
	Indeed, in 2014, Kunz and Stilman~\cite{KunzS14} showed that one of the variants of {\tt RRT}\xspace mentioned in the original {\tt RRT}\xspace paper~\cite{LaVKuf01} is in fact not PC. The completeness of the other variants was left as an open question. 
	
	PC proofs of {\tt RRT}\xspace under different steering functions and robot systems were presented in~\cite{CaronETAL17} and~\cite{KunzS14b}. A setting similar to ours of random forward propagation was considered in~\cite{LiETAL16} and~\cite{PapaETAL14}. It should be noted, however, that both papers consider a random-tree planner (and its extensions), which selects the next vertex to expand in a uniform and random manner among all its vertex, unlike {\tt RRT}\xspace which expands the nearest neighbor to a random sample point. Interestingly, the random tree is AO, in contrast to {\tt RRT}\xspace which is not AO~\cite{KF11, NecETAL10}. Nevertheless, the selection process employed by {\tt RRT}\xspace allows it to quickly explore the underlying state space when endowed with an appropriate metric. 
	
	


	
	






	


	
	
	\section{Probabilistic completeness of {\tt RRT}\xspace: The geometric case}
	\label{sec:geometric_proof}
	We start by defining useful notation in Subsection~\ref{ssec:geom_prelim} and then proceed to describe {\tt RRT}\xspace for the geometric case. Then, in Subsection~\ref{ssec:geom_pc_proof}, we provide the PC proof.  We denote the algorithm in this section as {\tt GEOM-RRT}\xspace to distinguish from the kinodynamic version. The geometric case, where a steering function exists and the dimension of the control space is identical to the dimension of the state space, can be considered as a special case of the more general kinodynamic setting. As such, this section can be viewed as an introduction to the more involved non-geometric setting, which is analyzed in the following section. 
	
	\subsection{Preliminaries}
	\label{ssec:geom_prelim}
	Let $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}$ be the state space, which is assumed to be $[0,1]^d$ (a $d$-dimensional Euclidean hypercube), equipped with the standard Euclidean distance metric, whose norm we denote by $\|\cdot\|$. The free space is denoted by $\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}\subseteq\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}$.
	Given a subset $D\subseteq \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}$ we denote by $|D|$ its Lebesgue measure.
	We will use $\B_r(x)$ to denote the ball 
	of radius $r$ centered at $x\in \mathbb{R}} \def\dM{\mathbb{M}} \def\dm{\mathbb{m}^d$.
	Let $x_{\text{init}}\in \mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$ denote the start state, and let $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$ be an open subset of $\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$
	denoting the goal region. For simplicity, we assume that there exist $\delta_{\text{goal}}>0,x_{\text{goal}}\in \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$, such that $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}=\B_{\delta_{\text{goal}}}(x_{\text{goal}})$.
	
	A motion-planning problem is implicitly defined by the triplet $(\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L},x_{\text{init}},\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}})$. A solution to such a problem is a trajectory that moves the robot from the initial state to the goal region while avoiding collisions with obstacles. More formally, a valid trajectory is a continuous map $\pi : [0,t_\pi] \rightarrow \mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$, such that $\pi(0) = x_{\text{init}}$ and $\pi(t_\pi)\in \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$. The clearance of $\pi$ is the maximal $\delta_{\text{clear}}$, such that $\B_{\delta_{\text{clear}}}(\pi(t))\subseteq\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$ for all $t\in [0,t_\pi]$.
	
	We describe here the (geometric) {\tt RRT}\xspace algorithm, {\tt GEOM-RRT}\xspace, based on~\cite{KL2000_geom}.
	\begin{algorithm}
		\caption{\tt GEOM-RRT($x_{\text{init}}, \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}, k, \eta$)}
		\label{algRRTextend}
		\begin{algorithmic}[1]
			\State{$\mathcal{T}.\text{init}(x_{\text{init}})$}
			\For {$i = 1 \text{ to } k$}
			\State $x_{\text{rand}}\gets$ RANDOM\_STATE()
			\State $x_{\text{near}}\gets \text{NEAREST\_NEIGHBOR}(x_{\text{rand}}, \mathcal{T} )$
			\State  $x_{\text{new}} \gets$ NEW\_STATE($x_{\text{rand}}, x_{\text{near}}, \eta$)
			\If {COLLISION\_FREE($x_{\text{near}}, x_{\text{new}}$)} 
			\State{$\mathcal{T}.$add\_vertex($x_{\text{new}}$)}
			\State{$\mathcal{T}.$add\_edge($x_{\text{near}}, x_{\text{new}}$)}
			\EndIf
			\EndFor	
			\State 		\Return $\mathcal{T}$
		\end{algorithmic}
	\end{algorithm}
	
	The input for {\tt GEOM-RRT}\xspace includes the initial configuration $x_{\text{init}}$,
	the goal region $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$, the number of iterations $k$ and the steering parameter $\eta>0$ used by the algorithm.  {\tt GEOM-RRT}\xspace constructs a tree $\mathcal{T}} \def\mathcal{L}{\mathcal{L}} \def\N{\mathcal{N}$ by preforming $k$ iterations of the following form. In each iteration, a new random sample $x_{\text{rand}}$ is returned from $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}$ uniformly by calling the function RANDOM\_STATE. Then, the vertex $x_{\text{near}}\in\mathcal{T}} \def\mathcal{L}{\mathcal{L}} \def\N{\mathcal{N}$ that is closest (according to $\|\cdot\|$) to $x_{\text{rand}}$ is found using the function NEAREST\_NEIGHBOR. A new configuration $x_{\text{new}}\in\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}$ is then returned by the call to NEW\_STATE, such that $x_{\text{new}}$ is located on the connecting line segment between $x_{\text{near}}$ and $x_{\text{rand}}$ and the distance $\Vert x_{\text{near}} - x_{\text{new}}\Vert$ is at most $\eta$. Finally, COLLISION\_FREE($x_{\text{near}}, x_{\text{new}}$) checks whether the path from $x_{\text{near}}$ to $x_{\text{new}}$ is collision free. If so, $x_{\text{new}}$ is added as a vertex to $\mathcal{T}} \def\mathcal{L}{\mathcal{L}} \def\N{\mathcal{N}$ and is connected by an edge from $x_{\text{near}}$. 
	
	To retrieve a trajectory for the robot, the single path in $\mathcal{T}} \def\mathcal{L}{\mathcal{L}} \def\N{\mathcal{N}$ from the root state $x_{\text{init}}$ to the goal is found.  It can then be translated to a feasible, collision-free trajectory for the robot by tracing the configurations along this path.
	
	\subsection{Probabilistic completeness proof}
	\label{ssec:geom_pc_proof}
	Next we devise a PC proof for {\tt GEOM-RRT}\xspace. Throughout this section we will assume that there exists a valid trajectory $\pi:[0,t_{\pi}]\rightarrow \mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$ with clearance $\delta_{\text{clear}}>0$. Without loss of generality, assume that $\pi(t_{\pi})=x_{\text{goal}}$, i.e., the trajectory terminates at the center of the goal region. Denote by~$L$ the (Euclidean) length of  $\pi$. Also, let $\delta:=\min\{\delta_{\text{clear}},\delta_{\text{goal}}\}$.
	
	Let $m=\frac{5L}{\nu}$, where $\nu = \min(\delta,\eta)$, and $\eta$ is the steering parameter of {\tt GEOM-RRT}\xspace. Then, define a sequence of $m+1$ points $x_0=x_{\text{init}},\ldots,x_{m}=x_{\text{goal}}$ along $\pi$, such that the length of the sub-path between every two consecutive points is $\nu/5$. Therefore, $\Vert x_i-x_{i+1}\Vert\leq\nu/5$ for every $0\leq i< m$. Next, we define a set of $m+1$ balls of radius $\nu/5$, centered at these points, and prove that with high probability {\tt GEOM-RRT}\xspace will generate a path that goes through these balls.
	
	\begin{figure}[h!]
		\vspace{-.1in}
		\includegraphics[width=0.9\columnwidth]{fig/geom_lemma_step.pdf}
		\caption{\textsf{Illustration of Lemma~\ref{lem:geometric_step}.}}
		\label{fig:geom_step}
		\vspace{-.1in}
	\end{figure}
	
	We start by proving Lemma~\ref{lem:geometric_step}, which will be used in the proof of Theorem~\ref{thm_main} and specifies a condition for successfully extending the tree to the goal. 
	
	\begin{lemma}
		Suppose that {\tt GEOM-RRT}\xspace  has reached $\B_{\nu/5}(x_i)$, that is, $\mathcal{T}} \def\mathcal{L}{\mathcal{L}} \def\N{\mathcal{N}$ contains a vertex $x'_i$ such that 	$x'_{i}\in \B_{\nu/5}(x_i)$. If a new sample $x_{\text{rand}}$ is drawn such that $x_{\text{rand}}\in \B_{\nu/5}(x_{i+1})$, then the straight line segment between $x_{\text{rand}}$ and its nearest neighbor $x_{\text{near}}$ in $\mathcal{T}} \def\mathcal{L}{\mathcal{L}} \def\N{\mathcal{N}$ lies entirely in $\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$.	
		\label{lem:geometric_step}
	\end{lemma}
	
	\begin{proof}
		
		Denote by $x_{\text{near}}$ the nearest neighbor of $x_{\text{rand}}$ among the {\tt RRT}\xspace vertices. See Figure~\ref{fig:geom_step} for an illustration. Then, from the definition of $x_{\text{near}}$, it is true that $\Vert x_{\text{near}} - x_{\text{rand}}\Vert \leq \Vert  x'_i - x_{\text{rand}} \Vert$, where $x'_i$ is the {\tt RRT}\xspace vertex in the vicinity of $x_i$. 
		
		We show that $x_{\text{near}}$ must lie in $\B_\nu(x_i)$, implying that $\overline{x_{\text{near}}x_{\text{rand}}}\subset\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$, as $x_{rand}\in \B_{\nu/5}(x_{i+1}) \subset \B_{\nu}(x_{i})$. From $\Vert x_{\text{near}} - x_{\text{rand}}\Vert \leq \Vert  x'_i - x_{\text{rand}} \Vert$ and the triangle inequality, we have:
		\begin{align*}
			\Vert  x_{\text{near}} - x_i \Vert &\leq 
			\Vert  x_{\text{near}}- x_{\text{rand}} \Vert + \Vert  x_{\text{rand}} - x_i \Vert 
			\\
			&\leq 
			\Vert  x'_i - x_{\text{rand}} \Vert + \Vert  x_{\text{rand}} - x_i \Vert .
		\end{align*}
		From the triangle inequality, we have that 
		\[\Vert x_{\text{rand}} - x_i\Vert \leq \Vert  x_{\text{rand}} - x_{i+1} \Vert + \Vert  x_{i+1} - x_{i} \Vert,\]
		\[\Vert  x'_i - x_{\text{rand}} \Vert \leq \Vert  x'_i - x_{i} \Vert + \Vert  x_{i} - x_{i+1} \Vert +
		\Vert  x_{i+1} - x_{\text{rand}} \Vert.
		\]
		Therefore:
		\begin{align*}
			\Vert  x_{\text{near}} - x_i \Vert &\leq 
			\Vert x'_i - x_i \Vert + 2\Vert x_{i+1} - x_{\text{rand}}\Vert + \\
			& 2\Vert x_{i+1}-x_{i}\Vert \leq 5\frac{\nu}{5} = \nu.
		\end{align*}
		%
		Hence, $x_{\text{near}}\in\B_\nu(x_{i})\subseteq\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$ and thus $\overline{x_{\text{near}}x_{\text{rand}}}\subset\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$. 
		
		Note that $\Vert x_{\text{near}} - x_{\text{rand}} \Vert \leq \eta$, since: 
		$\Vert x_{\text{rand}} - x_{\text{near}} \Vert \leq \Vert x_{\text{rand}} - x'_i \Vert
		\leq \Vert x_i' - x_i \Vert +  \Vert x_i - x_{i+1} \Vert  + \Vert x_{i+1} - x_{\text{rand}} \Vert \leq 3\cdot\frac{\nu}{5} < \nu \leq \eta.$ 
		The fact that $\Vert x_{\text{near}} - x_{\text{rand}} \Vert \leq \eta$, means that $x_{\text{new}} = x_{\text{rand}}$.
		
		
	
		
	
		
	
		
	
	\end{proof}
	
	
	
	We now prove our main theorem.
	\begin{theorem}
		The probability that {\tt GEOM-RRT}\xspace fails to reach $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$ from $x_{\text{init}}$ after $k$ iterations
		is at most $ae^{-bk}$, for some constants $a,b \in \mathbb{R}} \def\dM{\mathbb{M}} \def\dm{\mathbb{m}_{>0}$.
		\label{thm_main}
	\end{theorem}
	
	\begin{proof}
		
		Assume that $B_{\nu/5}(x_{i})$ already contains an {\tt RRT}\xspace vertex.  Let $p$ be the probability that in the next iteration an {\tt RRT}\xspace vertex will be added to $\B_{\nu/5}(x_{i+1})$. Recall that due to Lemma~\ref{lem:geometric_step}, $x_{\text{rand}}\in \B_{\nu/5}(x_{i+1})$ ensures that {\tt RRT}\xspace will reach $\B_{\nu/5}(x_{i+1})$.  Since at each iteration $i$ we draw $x_{\text{rand}}$ uniformly at random from~$[0,1]^d$, the probability $p$ that this sample falls inside $\B_{\nu/5}(x_{i+1})$ is equal to $|\B_{\nu/5}|/|[0,1]^d|=|\B_{\nu/5}|$.
		
		\begin{figure}[t]
			\includegraphics[width=\columnwidth]{fig/markov_chain.pdf}
			\caption{\textsf{A Markov chain where the success probability $p= |\B_{\nu/5}|$
					is the probability to uniformly sample from a specific ball of radius $\nu/5$.
					State $(m)$ is a terminal state.
					$m$ successful outcomes imply that the algorithm finds a path from initial state to goal, where the $i$th successful
					outcome switches from state $i$ to state $i+1$.}}
			\label{fig:markov}
		\end{figure}
		
		In order for  {\tt GEOM-RRT}\xspace to reach $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$ from $x_{\text{init}}$ we need to repeat this step $m$ times from $x_i$ to $x_{i+1}$ for $0\leq i < m$. This stochastic process can be defined as a Markov chain (see Figure~\ref{fig:markov}). Alternatively, this process can be described as $k$ Bernoulli trials with success probability $p$. The  planning problem can be solved after $m$ successful outcomes (the $i$th outcome adds an {\tt RRT}\xspace vertex in $\B_{\nu/5}(x_i)$). Note that it is possible that the process ends after less than $m$ successful outcomes, i.e., by defining success to be $m$ successful outcomes we obtain an upper bound on the probability of failure. 
		
	
		
	
		
		Next, we bound the probability of failure, that is, the probability that the process does not reach state $(m)$,
		after $k$ steps. Let $X_k$ denote the number of successes in $k$ trials, then
		\begin{align}
			\Pr[X_k < m] &= \sum_{i=0}^{m-1}{\binom{k}{i}p^i(1-p)^{k-i}}\\
			&\leq \sum_{i=0}^{m-1}{\binom{k}{m-1}p^i(1-p)^{k-i}}\\
			&\leq \binom{k}{m-1}\sum_{i=0}^{m-1}{(1-p)^{k}} \\
			&\leq \binom{k}{m-1}\sum_{i=0}^{m-1}{(e^{-p})^{k}}  \\
			&= \binom{k}{m-1}m{e^{-pk}}  \\
			&= \frac{\prod_{i=k-m}^k{i}}{(k-1)!}{me^{-pk}}  \\
			&\leq \frac{m}{(m-1)!}k^m{e^{-pk}},  
		\end{align}
		where (2) is justified since $m\ll k$, (3) uses the fact that $p<\frac{1}{2}$,
		and (4) relies on $(1-p)\leq e^{-p}$.
		
		As $p,m$ are fixed and independent of $k$, the expression $\frac{1}{(m-1)!}k^m m{e^{-pk}}$ decays to zero exponentially with $k$.	Therefore, {\tt GEOM-RRT}\xspace with uniform samples is probabilistically complete.
	\end{proof}
	

	\begin{comment}
	\begin{corollary}\label{cor:path}
	Given a robust path $\pi$ between $s$ and $t\in \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$ lying in $\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$, whose clearance is $\delta>0$.
	It is possible to tile $\pi$ with $m = \frac{5L}{\nu}$ balls of radius $\nu/5$,
	such that after $n$ iterations of {\tt RRT}\xspace, with probability of at least $1-a\cdot e^{-bn}$, every ball will contain at least one {\tt RRT}\xspace vertex, where $\nu = \min{(\delta, \eta)}$ and  $a,b\in \mathbb{R}} \def\dM{\mathbb{M}} \def\dm{\mathbb{m}_{>0}$ are some constants that depend on the path length and on $\nu$.
	
	\end{corollary}
	\end{comment}
	
	
	
	\begin{comment}
	\section{Preliminaries}
	\label{sec:perlim}
	We start by defining the setting and the notation used here.
	Suppose that the free space $\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$ is an open subset of the configuration space $[0,1]^d$, and that the distance metric used is the Euclidean distance,
	denoted by $\Vert \cdot\Vert$.
	Given a subset $D\subseteq [0,1]^d$ we denote by $|D|$ its Lebesgue measure.
	Let $s\in \mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$ denote the start state, and let $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$ be an open subset of $\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$
	denoting the goal region.
	
	A path $\pi$ in  $\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$ from $s$ to $t\in \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$ 
	consists of a continuous map $\pi : [0,1] \rightarrow \mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$, where 
	$\pi(0) = s$ and $\pi(1) = t$.
	Let $\delta>0$ denote the clearance of the path~$\pi$.
	

	
	
	\subsection{The {\tt RRT}\xspace algorithm}
	We describe here the {\tt RRT}\xspace algorithm, as defined in~\cite{LaVKuf01}.
	\begin{algorithm}
	\caption{\tt RRT($x_{\text{init}}, \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}, n, \eta$)}
	\label{algRRTextend}
	\begin{algorithmic}[1]
	\State{$\mathcal{T}.\text{init}(x_{\text{init}})$}
	\For {$k = 1 \text{ to } n$}
	\State $x_{\text{rand}}\gets$ RANDOM\_FREE\_CONF()
	\State $x_{\text{near}}\gets \text{NEAREST\_NEIGHBOR}(x_{\text{rand}}, \mathcal{T} )$
	\State  $x_{\text{new}} \gets$ NEW\_CONF($x_{\text{rand}}, x_{\text{near}}, \eta$)
	\If {COLLISION\_FREE($x_{\text{near}}, x_{\text{new}}$)} 
	\State{$\mathcal{T}.$add\_vertex($x_{\text{new}}$)}
	\State{$\mathcal{T}.$add\_edge($x_{\text{near}}, x_{\text{new}}$)}
	
	\EndIf
	
	\EndFor	
	\State 		\Return $\mathcal{T}$
	
	\end{algorithmic}
	\end{algorithm}
	
	The input for the {\tt RRT}\xspace algorithm includes the initial configuration $x_{\text{init}}$, 
	the goal region $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$, the number of iterations $n$ and the steering parameter $\eta$ used by the algorithm. 
	{\tt RRT}\xspace constructs a tree $\mathcal{T}} \def\mathcal{L}{\mathcal{L}} \def\N{\mathcal{N}$ by preforming $n$ iterations of the following form.
	In each iteration a randomly sampled collision-free configuration $x_{\text{rand}}\in\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$ is returned by calling the function RANDOM\_FREE\_CONF.
	Then, the vertex $x_{\text{near}}\in\mathcal{T}} \def\mathcal{L}{\mathcal{L}} \def\N{\mathcal{N}$ that is closest to $x_{\text{rand}}$ is found using the function
	NEAREST\_NEIGHBOR.
	A new configuration $x_{\text{new}}\in \mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$ is then returned by the call to NEW\_CONF, such that $x_{\text{new}}$ is located on the connecting line segment between $x_{\text{near}}$ and $x_{\text{rand}}$ and the distance $\Vert x_{\text{near}} - x_{\text{new}}\Vert$ is at most $\eta$.
	Finally, COLLISION\_FREE($x_{\text{near}}, x_{\text{new}}$) checks whether the path from $x_{\text{near}}$ to $x_{\text{new}}$ is collision free. If so, $x_{\text{new}}$ is added as a vertex to $\mathcal{T}} \def\mathcal{L}{\mathcal{L}} \def\N{\mathcal{N}$ and is connected by an edge to $x_{\text{near}}$.
	
	\subsection{Original probabilistic completeness proof}
	LaValle and Kuffner~\cite{LaVKuf01} prove that {\tt RRT}\xspace is 
	probabilistically complete (PC) by defining a sequence of 
	subsets of $\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$ called an \emph{attraction sequence}, and showing that 
	the {\tt RRT}\xspace algorithm will be able to have vertices along this set of
	regions with high probability.
	That is, assuming that an attraction sequence exists, the probability that {\tt RRT}\xspace will be able to grow the tree along it tends to 1 as the number of samples $n$ goes to infinity.
	
	We mention that there is no immediate mapping between such an attraction sequence and the clearance $\delta$ of a path $\pi$ from start to goal. Obviously, this attraction sequence should lie within the Minkowski sum 
	of $\pi$ and a ball of radius $\delta$. However, the length of such an attraction sequence is not directly implied.
	
	Next we devise a PC proof for {\tt RRT}\xspace, assuming that a path of clearance $\delta$ exists.
	Our proof resembles the proof of LaValle and Kuffner~\cite{LaVKuf01},
	but requires only a single assumption on the path's clearance, similar to the PC proof of {\tt PRM}\xspace~\cite{kslo-prm}.
	\end{comment}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	\section{Probabilistic completeness of {\tt RRT}\xspace under differential constraints}
	\label{sec:kinodyn}
	We begin by formulating the kinodynamic problem. Our assumptions on the robotic system and the environment as well as the definitions appear in Subsection~\ref{ssec:dyn_prelim} and are adapted from Li et al.~\cite{LiETAL16}.
	Next, we describe the  modifications to {\tt RRT}\xspace required for solving the kinodynamic problem.  Finally, in Subsection~\ref{ssec:dyn_proof}, we devise a novel PC proof for the kinodynamic {\tt RRT}\xspace.
	
	
	
	\subsection{Preliminaries}
	\label{ssec:dyn_prelim}

	We adapt the problem attributes introduced in the previous section to accommodate the more involved structure of the kinodynamic case. The state space $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}\subseteq \mathbb{R}} \def\dM{\mathbb{M}} \def\dm{\mathbb{m}^d$ is a smooth $d$-dimensional manifold. Let $\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}\subset \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}$ denote the free state space.
	As before, we assume that there exist $x_{\text{goal}}\in \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}, \delta_{\text{goal}}>0$, such that $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}=\B_{\delta_{\text{goal}}}(x_{\text{goal}})$.
	
	Let $\mathbb{U}\subseteq\mathbb{R}} \def\dM{\mathbb{M}} \def\dm{\mathbb{m}^D$ denote the space of control vectors. The given system has differential constraints of the following form:
	\begin{equation}
		\dot{x}(t)= f(x(t), u(t)),\quad x(t)\in \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y},\quad  u(t)\in \mathbb{U}.
		\label{eq:dyn}
	\end{equation} 
	
	Trajectories under differential constraints are defined as follows.
	\begin{definition}[]
		A valid trajectory $\pi$  of duration $t_\pi$ is a continuous function
		$\pi: [0, t_\pi ] \rightarrow \mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$. A trajectory
		$\pi$ is generated by starting at a given state $\pi(0)$ and
		applying a control function $\Upsilon : [0,t_\pi ] \rightarrow \mathbb{U}$ by forward
		integrating Equation~\ref{eq:dyn}.
	\end{definition}
	\noindent Similar to prior related work~\cite{LiETAL16}, we consider control functions that are  piecewise constant:
	



	\begin{definition}[]
		A piecewise constant control function $\overline{\Upsilon}$  with resolution $\Delta t$ is the concatenation of constant control functions $\bar{\Upsilon}_i : [0, \Delta t ] \rightarrow u_i$, where $u_i\in \mathbb{U}$, and $1\leq i\leq k$, for some $k\in \mathbb{N}_{>0}$. 
	\end{definition}
	We assume that the system is Lipschitz continuous for both of its arguments. That is,
	$\exists K_u, K_x > 0 $ s.t. $\forall\ x_0,x_1\in \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y},u_0,u_1\in \mathbb{U}$:
	\[\lVert f(x_0, u_0)- f(x_0, u_1)\rVert \leq K_u\lVert u_0-u_1\rVert,\]
	\[\lVert f(x_0, u_0)- f(x_1, u_0)\rVert \leq K_x\lVert x_0-x_1\rVert.\]
	


	
	We describe here the (kinodynamic) {\tt RRT}\xspace algorithm, based on~\cite{LaVKuf01}. 
	\begin{algorithm}
		\caption{\tt RRT($x_{\text{init}}, \mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}, k, T_{\text{prop}}, \mathbb{U}$)}
		\label{algRRTextendKINO}
		\begin{algorithmic}[1]
			\State{$\mathcal{T}.\text{init}(x_{\text{init}})$}
			\For {$i = 1 \text{ to } k$}
			\State $x_{\text{rand}}\gets$ RANDOM\_STATE()
			\State $x_{\text{near}}\gets \text{NEAREST\_NEIGHBOR}(x_{\text{rand}}, \mathcal{T} )$
			\State $t \gets $ SAMPLE\_DURATION($0, T_{\text{prop}}$)
			\State $u \gets $ SAMPLE\_CONTROL\_INPUT($\mathbb{U}$)
			\State  $x_{\text{new}} \gets$ PROPAGATE($x_{\text{near}}, u, t$)
			\If {COLLISION\_FREE($x_{\text{near}}, x_{\text{new}}$)} 
			\State{$\mathcal{T}.$add\_vertex($x_{\text{new}}$)}
			\State{$\mathcal{T}.$add\_edge($x_{\text{near}}, x_{\text{new}}$)}
			\EndIf
			\EndFor	
			\State 	\Return $\mathcal{T}$
		\end{algorithmic}
	\end{algorithm}
	
	The {\tt RRT}\xspace algorithm in dynamic settings with no BVP solver has the following 
	inputs: start state $x_{\text{init}}$, goal region $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$, the number of iterations $k$, the maximal time duration for propagation $T_{\text{prop}}$, and the set of control inputs $\mathbb{U}$. Our proof below assumes that $T_{\text{prop}}$ is positive and independent of $k$.
	
	Lines~5--7 in Algorithm~\ref{algRRTextendKINO} replace line~5 in Algorithm~\ref{algRRTextend}.
	Here, a random time duration $t$ is chosen between $0$ and $T_{\text{prop}}$ as well as a random control input $u\in \mathbb{U}$.
	The algorithm uses a forward propagation approach (function PROPAGATE) from $x_{\text{near}}$: control input $u$ is applied for time duration $t$, reaching a new state $x_{\text{new}}$. Finally, if the trajectory from $x_{\text{near}}$ to $x_{\text{new}}$ is collision-free, then $x_{\text{new}}$ is added to $\mathcal{T}} \def\mathcal{L}{\mathcal{L}} \def\N{\mathcal{N}$ together with a connecting edge to $x_{\text{near}}$.
	


	
	
	







	







	



	
	
	
	
	
	
	
	
	
	
	\subsection{A novel proof}
	\label{ssec:dyn_proof}
	We prove that {\tt RRT}\xspace for a system with dynamics satisfying the aforementioned characteristics is PC. To do so, we start by proving three lemmas. 
	The following lemma is a slight modification of Theorem~15 from~\cite{LiETAL16}.
	\begin{lemma}
		Let $\pi,\pi'$ be two trajectories, with the corresponding control functions $\Upsilon(t),\Upsilon'(t)$. Suppose that $x_0 = \pi(0), x_0' = \pi'(0)$ and $\Vert x_0 - x_0'\Vert \leq \delta$, for some constant $\delta > 0$. 
		Let $T>0$ be a time duration such that for all $t\in[0,T]$ it holds that 
		$\Upsilon(t) = u, \Upsilon'(t) = u'$. That is, $\Upsilon, \Upsilon'$ remain fixed through $[0,T]$. Then 
		\[ \|\pi(T) -\pi'(T)\|\leq e^{K_x T} \delta + K_u Te^{K_x T}\Delta u,\]
		where $\Delta u = \Vert u - u'\Vert$. 
		\label{lem:bound_on_endpoints}
	\end{lemma}
	
	\begin{proof}
		From the Lipschitz continuity assumption and the triangle inequality, we have that 
		\[\Vert f(x_0, u) - f(x'_0, u')\Vert \leq K_u \Delta u  + K_x \Vert x_0-x_0' \Vert . \]
		As in the proof of Theorem~15 in~\cite{LiETAL16}, we will use the Euler integration method to approximate the value of the trajectory $\pi$ at duration $T$.
		We divide $[0,T]$ into $\ell\in \dN_{>0}$ pieces, each of duration $h$, i.e., $T = \ell\cdot h$.
		Let $x_i, x_i'$ denote the resulting approximations of the trajectories $\pi, \pi'$ at duration $i\cdot h$. From Euler's method we have that
		\[x_i = x_{i-1} + h\cdot f(x_{i-1}, u),\]
		\[x_i' = x_{i-1}' + h\cdot f(x_{i-1}', u').\]
		The proof in~\cite{LiETAL16} shows that 
		\begin{equation}
			\Vert x_\ell - x_\ell' \Vert < (1 +K_x h)^\ell \Vert x_0 - x_0' \Vert + K_u Te^{K_x T}\Delta u.
		\end{equation}
		Since 
		\[(1+K_x h)^\ell = (1+K_x T/\ell)^\ell < e^{K_x T},\]
		and $\Vert x_0 - x_0' \Vert \leq \delta$ 
		we have that 
		\[ \Vert x_\ell - x_\ell' \Vert < e^{K_x T}\delta + K_u Te^{K_x T}\Delta u.\]
		
		From the Lipschitz continuity assumption we have that the Euler integration method converges to the solution of the \emph{Initial value problem}. That is, 
		$\forall 0<i\leq\ell$,
		\[\lim_{\ell\to\infty,\: h\to 0,\: \ell h = T} {\|\pi(i\cdot h) -  x_i\|} = 0, \]
		\[\lim_{\ell\to\infty,\: h\to 0,\: \ell h = T} {\|\pi'(i\cdot h) -  x_i'\|} = 0.\]
		Therefore,
		\[\Vert \pi(T)-  \pi'(T)\Vert \leq e^{K_x T} \delta + K_u Te^{K_x T}\Delta u.\]
	\end{proof}
	
	\begin{comment}
	\begin{lemma}
	Let $\pi,\pi'$ be two trajectories, with the corresponding control functions $u,u'$, such that $x_0 = \pi(0), x_0' = \pi'(0)$ and $\Vert x_0 - x_0'\Vert \leq \delta$, for some constant $\delta > 0$. 
	When applied for a time duration $T$, the distance between the trajectories endpoints $\pi(T), \pi'(T)$ will be at most
	\[ e^{K_x T} \delta + K_u Te^{K_x T}\Delta u, \]
	where $\Delta u = \sup_{0<t\leq T}(\Vert u(t) - u'(t)\Vert)$ and $u(t),u'(t)$ are the controls inputs applied at time $t$ in $\pi,\pi'$, respectively. 
	
	\todo{Need to replace $u$ with $\Upsilon$ for clarity.}
	
	\todo{This lemma is too general for our purposes. I suggest to simplify it by considering $\pi$ that consist of a single constant action. This way it will also be easier to understand the connecion to Lemma 2.} 
	\label{lem:bound_on_endpoints}
	\end{lemma}
	\begin{proof}
	The proof of Theorem~15 in~\cite{LiETAL16} uses both the assumption that the control inputs are piecewise constant and the Lipschitz continuity assumption.
	The duration $T$ is broken into $\ell$ pieces, each of duration $\Delta t$, where $\Delta t$ is the resolution of the piecewise constant control function. Thus, $T = \ell\cdot \Delta t$.
	
	The original proof shows that 
	\begin{equation}
	\Vert x_\ell - x_\ell' \Vert < (1 +K_x\Delta t)^\ell \Vert x_0 - x_0' \Vert + K_u Te^{K_x T}\Delta u.
	\end{equation}
	\michal{Need to explain what are the $x_i$-s here.}
	Since 
	\[(1+K_x \Delta t)^\ell = (1+K_x T/\ell)^\ell < e^{K_x T},\]
	we have that 
	\[ \Vert x_\ell - x_\ell' \Vert < e^{K_x T} \Vert x_0 - x_0' \Vert + K_u Te^{K_x T}\Delta u.\]
	
	Since $\Vert x_0 - x_0' \Vert \leq \delta$, we have that after time duration $T$ the distance between the endpoints $\pi(T), \pi'(T)$ will be at most
	\[ e^{K_x T} \delta + K_u Te^{K_x T}\Delta u.\]
	\michal{Perhaps we should add a sentence here explaining the transition from the distance between $x_\ell, x_\ell'$  and the distance between $\pi(T), \pi'(T)$}
	\end{proof}
	
	\end{comment}
	
	Next, we give a lower bound on the probability of a successful forward propagation step of {\tt RRT}\xspace (Algorithm~\ref{algRRTextendKINO}), from a given tree node, a random control $u\in \mathbb{U}$, and a random duration $t\in T_{\text{prop}}$.
	We note that our proof uses similar construction as~\cite[proof of Theorem~17]{LiETAL16}.
	\begin{lemma}
		Let $\pi$ be a trajectory with clearance $\delta >0$, and  duration $t_\pi\leq T_{\text{prop}}$.
		Suppose that the control function $\Upsilon$ is fixed  for all $t\in[0,t_\pi]$, i.e., $\Upsilon(t)=u\in \mathbb{U}$. 
		Denote by $x_0,x_1$ the states  $\pi(0), \pi(t_\pi)$ respectively.
		
		Suppose that the propagation step begins at state $x_0' \in \B_\delta(x_0)$ and ends in $x_1'$. Then for any $\kappa\in (0,1], \epsilon \in (0,\kappa\delta)$, we have that:
		\[\Pr[x'_1\in \B_{\kappa\delta} (x_1)]\geq
		p_t\cdot \frac{\zeta_{D}\cdot
			\max(\frac{\kappa\delta - \epsilon - e^{K_x t_\pi}\delta}{K_u t_\pi e^{K_x t_\pi}},0)}{|\mathbb{U}|}, \]
		where $\zeta_D$ is the Lebesgue measure of the unit ball in $\mathbb{R}^D$ and $0<p_t\leq 1$ is some constant. 
		\label{lem:prop_bound}
	\end{lemma}
	
	\begin{proof}
		Consider a sequence of balls of radius $r' = \kappa\delta-\epsilon$,
		such that (i) the center $c_t$ of each ball lies on $\pi$, that is, $c_t = \pi(t)$ for some duration $t\in [0,t_\pi]$, and (ii) $B_{r'}(c_t)\subset \B_{\kappa\delta}(x_1)$.
		The centers of all such balls constitute a segment of the trajectory $\pi$ whose duration is $T_\kappa$. See Figure~\ref{fig:prop_lemma} for an illustration.
		\begin{figure}[h!]
			\centering
			\includegraphics[width=\columnwidth]{fig/prop_prob_lemma.pdf}
			\caption{\textsf{Illustration of $T_\kappa$.
				}}
				\label{fig:prop_lemma}
			\end{figure}
		
			
			Fix $t\in [0,t_\pi]$, such that $B_{r'}(c_t)\subset \B_{\kappa\delta}(x_1)$. Additionally denote by $u_{\text{rand}}$ the random control generated by {\tt RRT}\xspace, and denote by $\pi_t$ the trajectory corresponding to the propagation step starting at $x'_0$, using the control $u_{\text{rand}}$ and duration $t$. By Lemma~\ref{lem:bound_on_endpoints}, we have that:
			\[ \Vert\pi(t) -  \pi_t(t)\Vert < e^{K_x t} \delta + K_u te^{K_x t}\Delta u, \]
			where $\Delta u=\|u-u_{\text{rand}}\|$. 
			Now, we wish to find the value $\Delta u$ such that $\Vert\pi(t) -\pi_t(t)\Vert < \kappa \delta-\epsilon$, which would imply that $\pi_t(t)=x'_1\in \B_{\kappa\delta} (x_1)$. Thus, we require that 
			\[ e^{K_x t} \delta + K_u te^{K_x t}\Delta u < \kappa\delta - \epsilon, \]
			which implies that 
			\[\Delta u < \frac{\kappa\delta - \epsilon - e^{K_x t}\delta}{K_u t e^{K_x t}}.\]
			To make sure that the bound holds for all possible durations $t$ in the relevant range, we should consider $t_\pi$, which is the maximal duration there. That is, we enforce the following bound 
			\[\Delta u < \frac{\kappa\delta - \epsilon - e^{K_x t_\pi}\delta}{K_u t_\pi e^{K_x t_\pi}}.\]
			
			To summarize, we have shown that for certain values of $t$ and $u_{\text{rand}}$ it is guaranteed to have $x'_1\in \B_{\kappa\delta} (x_1)$. 
			It remains to calculate the probability of randomly choosing such  values. The probability for successful  propagation is  at least the  (a) probability of choosing a proper $t$ such that $\pi(t)$ is a center $c_t$ of a small ball $\B_{r'}(c_t)\subset  \B_{\kappa\delta}(x_1)$ 
			times the (b) probability for choosing a control input that will cause $\pi_t(t)$  to fall inside $\B_{r'}(c_t)\subset \B_{\kappa\delta}(x_1)$. 
			
			Clearly, the probability to choose a proper duration for propagation is at least $p_t = T_\kappa/T_{\text{prop}}>0$.
			The probability\footnote{The expression guarantees that the probability will be valid, that is, at least 0.} to choose a proper control input is at least:
			\[p_u=\frac{\zeta_{D}\cdot \max(\frac{\kappa\delta - \epsilon - e^{K_x t_\pi}\delta}{K_u t_\pi e^{K_x t_\pi}},0)}{|\mathbb{U}|}.\]
			Therefore, the probability for successfully propagating is at least $\rho = p_t\cdot p_u$.
		\end{proof}
		\begin{comment}
		\begin{lemma}
		Let $\pi$ be a trajectory, whose clearance is $\delta >0$ and duration is $t_\pi\leq T_{\text{prop}}$, where $T_{\text{prop}}$ is the maximal duration for a single propagation.
		Denote by $x_0,x_1$ the states  $\pi(0), \pi(t_\pi)$, respectively.
		Let $0<\kappa\leq 1$ be some constant.
		Suppose that the propagation step begins at state $x_0'\in \B_\delta(x_0)$.
		The probability that the propagation step will end in a state $x_1'\in \B_{\kappa\delta} (x_1)$
		is bounded from below by some constant $\rho$. 
		\label{lem:prop_bound}
		\end{lemma}
		
		\begin{proof}
		As in~\cite[proof of Theorem 17]{LiETAL16}, consider a set of 
		smaller balls of radius $r' = \kappa\delta-\epsilon$, for a small constant $\epsilon>0$,
		such that the center $c_j$ of each ball lies on $\pi$, that is, $c_j = \pi(t_j)$ for some duration $0\leq t_j\leq t_\pi$.
		Moreover, all balls are contained in 
		$\B_{\kappa\delta}(x_1)$.
		The centers of all such balls constitute a segment of the trajectory $\pi$ whose duration is $T_\kappa$.
		
		From Lemma~\ref{lem:bound_on_endpoints}, we have that for a given duration~$T$
		\[ \Vert\pi(T) -  \pi'(T)\Vert < e^{K_x T} \delta + K_u Te^{K_x T}\Delta u. \]
		Given the duration $T$, to compute the probability that a control input is chosen such that $\pi(T), \pi'(T)$ are at distance at most $\kappa\delta - \epsilon$, 
		we require that 
		\[ \Vert\pi(T) -  \pi'(T)\Vert < e^{K_x T} \delta + K_u Te^{K_x T}\Delta u < \kappa\delta - \epsilon. \]
		This implies a bound on $\Delta u$ as follows
		\[\Delta u < \frac{\kappa\delta - \epsilon - e^{K_x T}\delta}{K_u T e^{K_x T}}.\]
		To make sure that the bound holds for all possible durations in the relevant range, we should consider $t_\pi$, which is the maximal duration there.
	
		
		
		Finally, the probability for successful propagation is equal to the probability of choosing a proper time duration $t_j$ such that $\pi(t_j)$ is a center $c_j$ of a small ball $\B_{r'}(c_j)$ 
		times the probability for choosing a control input that will cause $\pi'(t_j)$  to fall inside $\B_{r'}(c_j)\subset \B_{\kappa\delta}(x_1)$. 
		
		Clearly, the probability to choose a proper duration for propagation is at least $\frac{T_\kappa}{T_{\text{prop}}}$.
	
	
	
	
		The probability\footnote{the expression makes sure that the probability will be valid, that is, at least 0.} to choose a proper control input is at least
		\[\frac{\zeta_{D}\cdot \max(\frac{\kappa\delta - \epsilon - e^{K_x t_\pi}\delta}{K_u t_\pi e^{K_x t_\pi}},0)}{|\mathbb{U}|},\]
		where $\zeta_D$ is the Lebesgue measure of the unit ball in $\mathbb{R}^D$.
		
		
		Therefore, the probability for successfully propagating is 
		\[\rho = \frac{T_\kappa}{T_{\text{prop}}}\cdot \frac{\zeta_{D}\cdot \max(\frac{\kappa\delta - \epsilon - e^{K_x t_\pi}\delta}{K_u t_\pi e^{K_x t_\pi}},0)}{|\mathbb{U}|}.\]
		
		\end{proof}
		
		\end{comment}
		
		Finally, we prove a lower bound on the probability to grow the tree from a vertex in a certain ball.
		\begin{lemma}
			Let $x\in \mathbb{R}} \def\dM{\mathbb{M}} \def\dm{\mathbb{m}^d$ such that $\B_\delta(x)\subset \mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$.
			Suppose that there exists an {\tt RRT}\xspace vertex $v\in \B_{2\delta/5}(x)$.
			Let $x_{\text{near}}$ denote the nearest neighbor of $x_{\text{rand}}$ among all {\tt RRT}\xspace vertices (see Algorithm~\ref{algRRTextendKINO}).
			The probability that $x_{\text{near}}\in \B_{\delta}(x)$ is at least $|\B_{\delta/5}|/|\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}|$.
			\label{lem:nn_prob}
		\end{lemma}
		\begin{proof}
			Suppose that there exists an {\tt RRT}\xspace vertex $z\not\in \B_{\delta}(x)$, as otherwise it is immediate that  $x_{\text{near}}\in \B_\delta(x)$. We show that if $x_{\text{rand}}\in \B_{\delta/5}(x)$ then $x_{\text{near}}\in \B_\delta(x)$. Use figure~\ref{fig:NN_lemma} for an illustration of the proof.
			\begin{figure}[h!]
				\centering
				\includegraphics[width=0.5\columnwidth]{fig/NN_lemma.pdf}
				\caption{\textsf{Illustration of the proof of Lemma~\ref{lem:nn_prob}.
						$z,v$ are {\tt RRT}\xspace vertices. $x_{\text{rand}}$ is the sampled state.
						Its nearest neighbor will be a vertex in $\B_{2\delta/5}(x)$.
					}}
					\label{fig:NN_lemma}
				\end{figure}
				
				Observe that $\|x_{\text{rand}} - v\| \leq 3\delta/5$ and $\|x_{\text{rand}}-z\|>4\delta/5$. Thus, $v$ is closer to $x_{\text{rand}}$ than $z$ is, implying that $z$ will not be reported as the nearest neighbor of $x_{\text{rand}}$. 
				If $x_{\text{near}}\neq v$, then there must be another {\tt RRT}\xspace vertex $y\in \B_{ 2\delta/5}(x_{\text{rand}})\subset \B_{\delta}(x)$ such that $\Vert y-x_{\text{rand}}\Vert$ is minimal. 
				Finally, the probability to choose $x_{\text{rand}}\in \B_{\delta/5}(x)$ is $|\B_{\delta/5}|/|\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}|$.
			\end{proof}
			
			
			Now we are ready to prove our main theorem.
			\begin{theorem}
				Suppose that there exists a valid trajectory $\pi$ from $x_{\text{init}}$ to $x_{\text{goal}}$ lying in $\mathcal{F}} \def\U{\mathcal{U}} \def\mathcal{L}{\mathcal{L}$, with clearance $\delta_{\text{clear}}>0$.
				Suppose that the trajectory $\pi$ has a piecewise constant control function. 
				Then the probability that {\tt RRT}\xspace fails to reach $\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}_{\text{goal}}$ from $x_{\text{init}}$ after $k$ iterations is at most $a'e^{-b'k}$, for some constants $a',b'\in \mathbb{R}} \def\dM{\mathbb{M}} \def\dm{\mathbb{m}_{>0}$. 
				\label{kino_main_thm}
			\end{theorem}
			
			\begin{proof}
				The high level description of our proof is as follows; we cover the trajectory $\pi$ with a constant number of balls of radius $\delta=\min\{\delta_{\text{goal}},\delta_{\text{clear}}\}$.
				Then, we show that given that an {\tt RRT}\xspace vertex in the $i$th ball exists, the probability that in the next iteration {\tt RRT}\xspace will generate a new vertex in the $(i+1)$st ball when propagating from a vertex in the $i$th ball is bounded from below by a positive constant.
				The rest of the proof is the same as that of Theorem~\ref{thm_main}.
				
				Recall that Lemma~\ref{lem:prop_bound} shows a lower bound $\rho$ on the probability of a successful propagation. 
				Fix $\kappa=2/5$. It holds that  $\rho>0$ for a duration $\tau$ when 	
				\begin{equation}
					2\delta/5 - \epsilon - e^{K_x \tau}\delta>0.
					\label{eq:positive_dist}
				\end{equation} 
				It is clear that there exist values of $\epsilon$ and $\tau$ to accommodate this requirement: we may set, e.g., $\epsilon=5^{-2},$ and pick a strictly positive value of $\tau$ as small as we please. 
				Now, we set $\tau\leq T_{\text{prop}}$
				such that (i) there exists $\ell\in\dN_{>0}$  such that $\ell\cdot\tau = \Delta t$, (ii) Equation~\ref{eq:positive_dist} holds.
				
				Next, we choose a set of durations $t_0=0, t_1, t_2, \ldots, t_m = t_\pi$, such that the difference between every two consecutive ones is $\tau$, where~$t_\pi$ is the duration of $\pi$.
				Let $x_0= \pi(t_0), x_1 = \pi(t_1), \ldots, x_m= \pi(t_m)$ be states along the path $\pi$ that are obtained after duration $t_0,t_1, \ldots , t_m$, respectively. That is, $x_i = \pi(t_i)$.
				Obviously, $m = t_\pi/\tau$ is some constant independent of the number of samples.
				
				We now cover $\pi$ with a set of $m+1$ balls of radius $\delta$ centered at $x_0, \ldots, x_m$.
				Suppose that there exists an {\tt RRT}\xspace vertex $v\in B_{2\delta/5}(x_{i})\subset \B_\delta(x_{i})$. 
				We need to bound the probability $p$ that in the next iteration the {\tt RRT}\xspace tree will grow from  an {\tt RRT}\xspace vertex in $B_{\delta}(x_{i})$, given that an {\tt RRT}\xspace vertex in $B_{2\delta/5}(x_{i})$ exists, and that the propagation step will add a vertex to $\B_{2\delta/5}(x_{i+1})$. 
				That is, $p$ is the probability that in the next iteration both $x_{\text{near}}\in B_{\delta}(x_{i})$ and $x_{\text{new}}\in \B_{2\delta/5}(x_{i+1})$.
				From Lemma~\ref{lem:nn_prob}, we have that the probability that $x_{\text{near}}$ lies in $B_{\delta}(x_{i})$, given that there exists an {\tt RRT}\xspace vertex in $B_{2\delta/5}(x_{i})$, is at least $|\B_{\delta/5}|/|\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}|$.
				By substituting $t_\pi$ with the selected value $\tau$, we have from Lemma~\ref{lem:prop_bound} that 
				the probability for $x_{\text{new}}\in \B_{2\delta/5}(x_{i+1})$ is at least some positive constant $\rho>0$.
				
				Hence, $p\geq (|\B_{\delta/5}|\cdot \rho)/|\mathcal{X}} \def\A{\mathcal{A}} \def\Y{\mathcal{Y}| $. The rest of the proof is the same as that of Theorem~\ref{thm_main}.
			\end{proof}
			
			\begin{comment}
			\subsection{Alternative propagation schemes}
			In our proof we have considered propagation approaches that apply a randomly selected control input for a randomly sampled time duration.
			However, alternative propagation schemes were originally presented in~\cite{LaVKuf01}. 
			These methods may use a fixed time duration at each propagation step or differ in their control vector selection;
			When $\mathbb{U}$ is finite, instead of selecting a random control input, a greedy approach could be applied; the input that gets as close as possible to the randomly sampled state $x_{\text{rand}}$ will be chosen.
			\todo{Explain what remain open}
			\end{comment}
			
			\section{Discussion}
			\label{sec:future}
			Although our proofs assume uniform samples, they can be easily extended to samples generated using a Poisson point process, which is preferable in certain settings~\cite{KF11, SK18}. 
			
			An immediate extension of this work is to further relax some of the assumptions made for kinodynamic systems, such as Lipschitz continuity. Additionally, the work raises the following challenging research question: Is it possible to extend these proofs that have a reduced set of assumptions to other sampling-based planners~\cite{HLM97}, or informed variants of {\tt RRT}\xspace.
			
			\begin{comment}	
			\section{Conclusion}
			\label{sec:future}
			In this work we presented  mathematically-rigorous proofs for probabilistic completeness of {\tt RRT}\xspace.
			We considered both geometric and kinodynamic settings. 
			Our proofs are simple and resemble common {\tt PRM}\xspace-like completeness proofs in the sense that they rely on a single concrete assumption; Specifically, we assume that there exists a path of certain constant clearance.
			Notably, in the kinodynamic settings, our proof covers cases that were never covered before, in terms of the propagation approach.
			
			We note that although our proofs assume uniform samples, they can be easily extended to samples generated using a Poisson point process, 
			which is preferable in certain settings~\cite{KF11, SK18}. 
			
			As a future extension of this work we would like to remove the assumptions made on the kinodynamic system.
			Additionally, the work raises the following interesting research question: Is it possible to extend our proofs to other algorithms, such as, {\tt EST}\xspace~\cite{HLM97} or informed
			variants of {\tt RRT}\xspace.
			
			\kiril{I feel that this section does not provide anything no to the discussion. I suggest to remove it altogether.}
			\end{comment}
			
			\begin{comment} 
			\section{Alternative proof for the probability of successful propagation}
			\begin{theorem}
			Let $\pi$ be a trajectory from $x_0$ to $x_1$, whose duration is $t_\pi\leq T_{\text{prop}}$.
			Suppose that the propagation step starts from $x_0'\in B_\delta(x_0)$.
			The probability that the propagation will end in a state $x_1'\in B_{2\delta/5}(x_1)$ is bounded from below by some constant.
			\label{new_proof}
			\end{theorem}
			
			\begin{proof}
			From the proof of Theorem 15 be have that 
			\begin{equation}
			\Vert x_n - x_n' \Vert < (1 +K_x\Delta t)^n \Vert x_0 - x_0' \Vert + K_u Te^{K_x T}\Delta u
			\end{equation}
			Since 
			\[(1+K_x \Delta t)^n = (1+K_x T/n)^n < e^{K_x T},\]
			we have that 
			\[ \Vert x_n - x_n' \Vert < e^{K_x T} \Vert x_0 - x_0' \Vert + K_u Te^{K_x T}\Delta u.\]
			Therefore, for two trajectories $\pi, \pi'$, whose starting state are $x_0, x_0'$, respectively, and $\Vert x_0 - x_0' \Vert \leq \delta$, we have that after time duration $T$ the distance between their endpoints will be at most
			\[ e^{K_x T} \delta + K_u Te^{K_x T}\Delta u.\]
			
			We would like to compute the probability that a control input is chosen such that the trajectory $\pi'$ will end at a point $x_1'\in\B_{\frac{2\delta}{5}(x_1)}$.
			As in~\cite[proof of Theorem 17]{LiETAL16}, consider a set of 
			smaller balls of radius $r' = \frac{2\delta}{5}-\epsilon$, for a small constant $\epsilon>0$,
			such that each center $c_j$ of each ball lies on $\pi$, that is, $c_j = \pi(t_j)$ for some duration $t_j\leq t_\pi$.
			Moreover, all balls are contained in 
			$\B_{\frac{2\delta}{5}(x_1)}$.
			The centers of all such balls constitute a segment of the trajectory $\pi$ whose duration is $\hat{T}$.
			
			Given a duration $t$, in order to compute the probability that a control input is chosen such that $\pi(t), \pi'(t)$ are at distance at most $\frac{2\delta}{5} - \epsilon$, 
			we require that $\Delta u$ will be bounded as follows:
			\[\Delta u < \frac{(\frac{2\delta}{5} - \epsilon - e^{K_x t})\delta}{K_u t e^{K_x t}}.\]
			
			We use the maximal  possible duration $t_{\pi}$, for which $\B_{r'}\subset \B_{\frac{2\delta}{5}(x_1)}$, and obtain an upper bound on $\Delta u$.
			\[\Delta u < \frac{(\frac{2\delta}{5} - \epsilon - e^{K_x t_\pi})\delta}{K_u t_\pi e^{K_x t_\pi}}.\]
			
			
			Finally, the probability to choose a proper duration for propagation is at least $\frac{\hat{T}}{T_{\text{prop}}}$.
			The probability to choose a proper control input for the piecewise constant control function is 
			\[\frac{\mu(\zeta_{w})\cdot (\frac{(\frac{2\delta}{5} - \epsilon - e^{K_x t})\delta}{K_u t e^{K_x t}})^w}{\mu(\Upsilon)},\]
			where $\Upsilon$ is the piecewise constant control vector space, $w$ is its dimension, and $\zeta_w$ is the unit ball in this space.
			
			Therefore the probability for successfully propagating is 
			\[\rho = \frac{\hat{T}}{T_{\text{prop}}}\cdot \frac{\mu(\zeta_{w})\cdot (\frac{(\frac{2\delta}{5} - \epsilon - e^{K_x t})\delta}{K_u t e^{K_x t}})^w}{\mu(\Upsilon)}.\]
			
			
			\end{proof}
			
			
			
			
			
			
			
			
			\begin{theorem}
			Let $\pi$ be a trajectory from $x_0$ to $x_1$, whose duration is $t_\pi$.
			Suppose that the propagation step starts from $x_0'\in B_\delta(x_0)$.
			The probability that the propagation will end in a state $x_1'\in B_{2\delta/5}(x_1)$ is bounded from below by some constant.
			\label{new_proof}
			\end{theorem}
			
			\begin{proof}
			From the proof of Theorem 15 be have that 
			\begin{equation}
			\Vert x_n - x_n' \Vert < (1 +K_x\Delta t)^n \Vert x_0 - x_0' \Vert + K_u Te^{K_x T}\Delta u
			\end{equation}
			Since 
			\[(1+K_x \Delta t)^n = (1+K_x T/n)^n < e^{K_x T},\]
			we have that 
			\[ \Vert x_n - x_n' \Vert < e^{K_x T} \Vert x_0 - x_0' \Vert + K_u Te^{K_x T}\Delta u.\]
			Therefore, for two trajectories $\pi, \pi'$, whose starting state are $x_0, x_0'$, respectively, and $\Vert x_0 - x_0' \Vert \leq \delta$, we have that after time duration $T$ the distance between their endpoints will be at most
			\[ e^{K_x T} \delta + K_u Te^{K_x T}\Delta u.\]
			
			When applied for a time duration $t_\pi$ the distance between their endpoints will be at most 
			\[ e^{K_x t_\pi} \delta + K_u t_\pi e^{K_x t_\pi}\Delta u.\]
			
			In order to compute the probability that a control input is chosen such that the endpoints are at distance at most $2\delta/5$ 
			we require that $\Delta U$ will be bounded as follows:
			\[\Delta u < \frac{(2/5 - e^{K_x t_\pi})\delta}{K_u t_\pi e^{K_x t_\pi}}\]
			
			
			
			
			
			\end{proof}
			
			\begin{lemma}
			Let $\pi$ be a trajectory from $x_0$ to $x_1$, whose duration is $t_\pi$.
			Suppose that the propagation step starts from $x_0'\in B_\delta(x_0)$.
			The duration $t_{pi'}$ for a trajectory $\pi'$ from $x_0'$ to $x_1$ is at most $ $,
			where $M_{f1}, M_{f2}$ are some constants.
			\end{lemma}
			
			\begin{proof}
			The Lipschitz continuity assumption states that
			$\exists K_u, K_x >0$ s.t.
			\[\lVert f(x_0, u_0)- f(x_0, u_1)\rVert \leq K_u\lVert u_0-u_1\rVert,\]
			\[\lVert f(x_0, u_0)- f(x_1, u_0)\rVert \leq K_x\lVert x_0-x_1\rVert.\]
			
			Therefore, starting at a given state $x_0$
			the function $f(x(t),u(t))$ is bounded as well.
			That is, the velocity cannot change drastically (increase or decrease).
			That is, there exist constants $ M_{f_1}, M_{f_2} $ s.t.
			\[M_{f_1}\leq f(x(t),u(t) \leq M_{f_2}.\]
			
			If $a,b$ are two states along a path such that 
			$a = x(t_1)$ and $b= x(t_1 + t_{ab})$, then:
			\[b = a + \int_{t_1}^{t_1 + t_{ab}}{f(x(t), u(t))dt}.\]
			Therefore, 
			\[\Vert b-a \Vert = \Vert \int_{t_1}^{t_1 + t_{ab}}{f(x(t), u(t))dt}\Vert \geq M_{f_1}\cdot t_{ab}.\]
			
			This gives us an upper bound on the duration $t_{ab}$ of the path from $a$ to $b$.
			\[\vert b-a\Vert \geq M_{f_1}\cdot t_{ab}.\]
			By considering the path $\pi'$ from $x_0'$ to $x_1$, we obtain an upper bound on its duration as follows:
			\[t_{\pi'}\leq \frac{\Vert x_0' - x_1\Vert}{M_{f_1}}.\]
			From the triangle inequality we have that 
			\[\Vert x_0' - x_1\Vert \leq \Vert x_0' - x_0\Vert + \Vert x_0 - x_1\Vert\].
			Since $x_0'\in \B_\delta(x_0)$ then $\Vert x_0' - x_0\Vert\leq \delta$.
			Now, from the same arguments as before there exists a constant $M_{f_2}$ s.t. $\Vert x_0 - x_1\Vert\leq M_{f_2}\cdot t_{\pi}$.
			Putting it all together, we have that 
			\begin{align*}
			t_{\pi'} & \leq \frac{\Vert x_0' - x_1\Vert}{M_{f_1} }\\
			& \leq \frac{\Vert x_0' - x_0\Vert + \Vert x_0 - x_1\Vert}{M_{f_1}}\\
			& \leq \frac{\delta + M_{f_2}\cdot t_{\pi}}{M_{f_1}}.
			\end{align*}
			
			
			\end{proof}
			
			
			
			\end{comment}
			
			
		
		
		
		
		
			
			
			
			
			
			
			
			
			%
			%
			%
		
		
		
		
			%
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
			%
		
		
		
		
		
			%
		
			%
		
		
		
		
		
			%
			%
		
		
			%
		
		
		
		
		
		
		
		
		
		
			%
		
			%
			
			
			%
			%
		
			%
		
		
		
		
		
		
		
		
		
		
		
		
		
			%
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
			%
			%
			%
		
			%
			%
			%
		
			%
		
		
		
			%
		
		
			%
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
			%
		
		
			%
		
		
		
		
			%
		
		
		
		
		
		
		
			%
		
			
		
			
		
			
			\bibliographystyle{IEEEtran}
			