Distance function issues

The RDT construction algorithm is heavily influenced by the distance function $\rho$. This was also true for RDTs applied to the Piano Mover's Problem; however, it becomes more critical and challenging to design a good metric in the presence of differential constraints. For example, the metric given by Example 5.3 is inappropriate for measuring the distance between configurations for the Dubins car. A more appropriate metric is to use length of the shortest path from $q$ to ${q}'$ (this length is easy to compute; see Section 15.5). Such a metric would be more appropriate than the one in Example 5.3 for comparing the configurations, even for car models that involve dynamics and obstacles.

Although many challenging problems can be solved using weighted Euclidean metrics [611], dramatic improvements can be obtained by exploiting particular properties of the system. This problem might seem similar to the choice of a potential function for the randomized potential field planer of Section 5.4.3; however, since RDTs approach many different samples in ${\alpha }(i)$, instead of focusing only on the goal, the performance degradation is generally not as severe as the local minimum problem for a potential field planner. There are many more opportunities to escape in an RDT. Metrics that would fail miserably as a potential function often yield good performance in an RDT-based planner.

The ideal distance function, as mentioned in Section 14.3, is to use the optimal cost-to-go, denoted here as $\rho^*$. Of course, computing $\rho^*$ is at least as hard as solving the motion planning problem. Therefore, this idea does not seem practical. However, it is generally useful to consider $\rho^*$ because the performance of RDT-based planners generally degrades as $\rho$, the actual metric used in the RDT, and $\rho^*$ diverge. An effort to make a crude approximation to $\rho^*$, even if obstacles are neglected, often leads to great improvements in performance. An excellent example of this appears in [363], in which value iteration was used to compute the optimal cost-to-go in the absence of obstacles for an autonomous helicopter using the maneuver automaton model of Figure 14.8.