Kinodynamic RRTs with Fixed Time Step and Best-Input Extension Are Not Probabilistically Complete

摘要

RRTs are a popular method for kinodynamic planning that many consider to be probabilistically complete. However, different variations of the RRT algorithm exist and not all of them are probabilistically complete. The tree can be extended using a fixed or variable time step. The input can be chosen randomly or the best input can be chosen such that the new child node is as close as possible to the sampled state according to the used distance metric. It has been shown that for finite input sets an RRT using a fixed step size with a randomly selected input is probabilistically complete. However, this variant is uncommon since it is less efficient. We prove that the most common variant of choosing the best input in combination with a fixed time step is not probabilistically complete.