RRT * garantit-il une optimalité asymptotique pour une métrique de coût de dégagement minimum?

Il a été démontré que l' algorithme optimal de planification de mouvement basé sur l'échantillonnage $\text{RRT}^*$ (décrit dans cet article ) donne des chemins sans collision qui convergent vers le chemin optimal à mesure que le temps de planification augmente. Cependant, pour autant que je puisse voir, les preuves d'optimalité et les expériences ont supposé que la métrique de coût du trajet est la distance euclidienne dans l'espace de configuration. La $\text{RRT}^*$ également fournir des propriétés d'optimalité pour d'autres mesures de qualité de trajet, telles que la maximisation du dégagement minimum des obstacles tout au long du trajet?

Pour définir le jeu minimum: pour simplifier, on peut considérer un robot ponctuel se déplaçant dans l'espace euclidien. Pour toute configuration qui se trouve dans l'espace de configuration sans collision, définissez une fonction qui renvoie la distance entre le robot et l'obstacle C le plus proche. Pour un chemin , le jeu minimal est la valeur minimale de pour tout . Dans une planification de mouvement optimale, on peut souhaiter maximiser le dégagement minimum des obstacles le long d'un chemin. Cela signifierait définir une mesure des coûts $q$ $d(q)$ $\sigma$ $\text{min_clear}(\sigma)$ $d(q)$ $q \in \sigma$ tel que augmente à mesure que la distance minimale diminue. Une fonction simple serait . $c(\sigma)$ $c$ $c(\sigma) = \exp(-\text{min_clear}(\sigma))$

Dans le premier article introduisant , plusieurs hypothèses sont émises sur la métrique de coût du chemin afin que les preuves soient valables; l'une des hypothèses concernait l'additivité de la métrique de coût, qui n'est pas valable pour la métrique de dégagement minimum ci-dessus. Cependant, dans l' article de journal le plus récent décrivant l'algorithme, plusieurs des hypothèses antérieures n'étaient pas répertoriées, et il semblait que la mesure du coût de dédouanement minimum pourrait également être optimisée par l'algorithme. $\text{RRT}^*$

Est-ce que quelqu'un sait si les preuves de l'optimalité de la peuvent contenir une métrique de coût de dégagement minimum (peut-être pas celle que j'ai donnée ci-dessus, mais une autre qui a le même minimum), ou si des expériences ont été effectuées pour soutenir l'utilité de l'algorithme pour une telle métrique? $\text{RRT}^*$

motion-planning algorithm rrt theory giogadi
la source

Je ne connais pas la métrique du coût de dédouanement minimum, bien que par son nom j'aie une idée générale. Est-ce une fonction spécifique ou une classe de fonctions?

DaemonMaker

Bonne question: puisque la métrique varie en fonction du robot, supposons que nous regardons un robot ponctuel holonomique se déplaçant dans l'espace euclidien. Dans toute configuration q, nous avons une fonction d (q) qui renvoie la distance entre le robot ponctuel et l'obstacle C le plus proche. Par conséquent, pour un chemin dans l'espace de configuration, le dégagement minimum de tout le chemin est la valeur minimale de d (q) pour tous les q du chemin.

giogadi

Méta-question: quand est-il recommandé pour moi de modifier la question d'origine avec des clarifications qui ont été énoncées dans les commentaires et autres réponses?

giogadi

Ceci est une bonne méta-question et obtiendrait plus de réponses dans la méta SE Robotics . ;) Cependant, il est généralement bon de modifier la question pour plus de clarté. Je recommande particulièrement de le faire lorsque les réponses obtenues ne correspondent pas à la question prévue.

DaemonMaker

Réponses:

* Remarque, est la concaténation des chemins et . Alors défini comme le jeu minimal implique $a|b$ $a$ $b$ $c(\cdot)$ $c(a|b)=min(c(a),c(b))$

Vous faites référence (dans la référence 1):

Théorème 11: (Additivité de la fonction de coût.) Pour tout , , la fonction de coût c satisfait les éléments suivants: $\sigma_1$ $\sigma_2$ $\in X_{free}$ $c(\sigma_1|\sigma_2) = c(\sigma_1) + c(\sigma_2)$

Qui est devenu (dans la référence 3, problème 2):

La fonction de coût est supposée être monotone, en ce sens que pour tout $\sigma_1,\sigma_2\in\Sigma:c(\sigma_1)\leq c(\sigma_1|\sigma_2)$

Ce qui n'est toujours pas le cas pour la distance de dégagement minimale.

Mise à jour: Compte tenu de la restriction assouplie des coûts de trajet, votre suggestion d'exp (-min_clearance) semble correcte.

Josh Vander Hook
la source

Votre réponse m'a fait réaliser que la métrique telle que je l'ai décrite est en fait mal posée. Nous voulons généralement MAXIMISER le dégagement minimum sur un chemin, donc en fait le coût d'un chemin devrait AUGMENTER car le dégagement minimum d'un chemin DIMINUE. La première fonction de coût à laquelle j'ai à l'esprit est c (sigma) = 1 / min_ clearance (sigma), mais cela laisse la fonction indéfinie aux limites des obstacles, et je crois que RRT * nécessite que Q_free soit fermé pour que les preuves fonctionnent . Sauf problème de frontière, cette nouvelle fonction de coût serait monotone comme l'exige la preuve.

giogadi

Je suppose qu'une fonction de coût simple qui évite le problème de limite pourrait être c (sigma) = -min_clearance (sigma), mais je ne suis pas sûr de ce que le fait d'avoir une métrique négative pourrait faire pour d'autres parties de la preuve RRT * ...

Giogadi

L'article suppose explicitement un coût

zéro. Vous pouvez agrandir l'espace de configuration de quelques

pour tenir compte de la singularité de toucher la frontière, mais l'article suppose également une dégagement

, ce qui pourrait provoquer un conflit avec la modification de

. Je pense que vous essayez de répondre à une question différente maintenant, et cela pourrait impliquer une discussion, ce qui n'est pas facile dans ce format.

\geq

$\geq$

ϵ > 0

$\epsilon > 0$

δ

$\delta$

X_{f r e e}

$X_{free}$

Josh Vander Hook

Une autre métrique possible: c (sigma) = exp (-min_clear (sigma))

giogadi

J'aime mieux la fonction de coût exponentiel.

Josh Vander Hook

Dans une réponse précédente , nous en sommes venus à convenir qu'une fonction de coût définie comme

$c(\sigma) = \text{exp}(-\text{min_clear}(\sigma))$

satisferait les propriétés requises pour que RRT * produise une optimalité asymptotique sous cette métrique.

Cependant, lors de l'examen de l'article de l'IJRR qui décrit RRT *, cette fonction de coût ne satisfait pas techniquement aux hypothèses formulées dans l'article. Plus précisément, cette fonction de coût viole la propriété de délimitation , définie comme suit:

$\exists k_c \quad c(\sigma) \leq k_c\text{TV}(\sigma), \forall \sigma \in \Sigma$

$\text{TV}(\sigma)$ est la variation totale d'un chemin, qui est essentiellement la longueur euclidienne du chemin. Dans cette hypothèse de délimitation, un chemin de longueur 0 doit également avoir un coût de 0.

$\sigma_0$ $q$ $\sigma_0$ $c(\sigma_0) = \text{exp}(-d(q)) > 0$

Je me demande si RRT * ne produira tout simplement pas des solutions asymptotiquement optimales dans une telle fonction de coût, ou si cela pourrait encore, mais peut-être que ces hypothèses simplifiaient les preuves d'optimalité dans le document.

giogadi
la source