Es wurde gezeigt, dass der optimale Bewegungsplanungsalgorithmus ( in diesem Artikel beschrieben ) kollisionsfreie Pfade liefert, die mit zunehmender Planungszeit zum optimalen Pfad konvergieren. Soweit ich jedoch sehen kann, haben die Optimalitätsnachweise und Experimente angenommen, dass die Pfadkostenmetrik die euklidische Entfernung im Konfigurationsraum ist. Kann auch Optimalitätseigenschaften für andere liefern, z. B. die Maximierung des Mindestabstands von Hindernissen auf dem gesamten Pfad?
Mindestabstand definieren: Der Einfachheit halber können wir einen Punktroboter betrachten, der sich im euklidischen Raum bewegt. Definieren Sie für jede Konfiguration , die sich im kollisionsfreien Konfigurationsraum befindet, eine Funktion die den Abstand zwischen dem Roboter und dem nächsten C-Hindernis zurückgibt. Für einen Pfad ist der minimale Abstand der minimale Wert von für alle . Bei einer optimalen Bewegungsplanung kann es wünschenswert sein, den Mindestabstand zu Hindernissen entlang eines Pfades zu maximieren . Dies würde bedeuten, eine Kostenmetrik so zu definieren, dasssteigt mit abnehmendem Mindestabstand. Eine einfache Funktion wäre .
In der ersten Veröffentlichung, in der , werden verschiedene Annahmen über die Pfadkostenmetrik getroffen, damit die Beweise gültig sind. Eine der Annahmen betraf die Additivität der Kostenmetrik, die für die oben genannte Mindestabstandsmetrik nicht gilt. In dem neueren Zeitschriftenartikel , der den Algorithmus beschreibt, wurden jedoch einige der früheren Annahmen nicht aufgeführt, und es schien, dass die Mindestabfertigungskostenmetrik auch durch den Algorithmus optimiert werden könnte.
Weiß jemand, ob die Beweise für die Optimalität von für eine Mindestabfertigungskostenmetrik gelten können (vielleicht nicht die, die ich oben angegeben habe, aber eine andere, die das gleiche Minimum hat), oder ob Experimente durchgeführt wurden die Nützlichkeit des Algorithmus für eine solche Metrik unterstützen?
quelle
Antworten:
* Beachten Sie, dass ist die Verkettung der Pfade a und b . Dann impliziert c ( ⋅ ), definiert als das minimale Spiel, c ( a | b ) = m i n ( c ( a ) , c ( b ) )a|b a b c(⋅) c(a|b)=min(c(a),c(b))
Sie beziehen sich auf (in Referenz 1):
Was wurde (in Referenz 3, Problem 2):
Was für den Mindestabstand immer noch nicht der Fall ist.
Update: Angesichts der lockeren Beschränkung der Pfadkosten scheint Ihre vorgeschlagene Exp (-min_clearance) in Ordnung zu sein.
quelle
In einer früheren Antwort haben wir uns darauf geeinigt, dass eine Kostenfunktion definiert ist als
würde die Eigenschaften erfüllen, die für RRT * erforderlich sind, um unter dieser Metrik eine asymptotische Optimalität zu erzielen.
Bei Durchsicht des IJRR-Artikels, in dem RRT * beschrieben wird, entspricht diese Kostenfunktion jedoch technisch nicht den im Artikel getroffenen Annahmen. Diese Kostenfunktion verletzt insbesondere die Boundedness- Eigenschaft, die wie folgt definiert ist:
Dabei ist die Gesamtvariation eines Pfades, die im Wesentlichen die euklidische Länge des Pfades ist. Unter dieser Beschränkungsannahme muss ein Pfad der Länge 0 auch Kosten von 0 haben.TV(σ)
Definieren wir einen Pfad , der aus einer einzelnen Konfiguration q besteht , was bedeutet, dass die Länge von σ 0 0 ist. Unsere Pfadkosten sind daher c ( σ 0 ) = exp ( - d ( q ) ) > 0 , was die Annahme der Begrenzung verletzt . Daher erfüllt diese Kostenfunktion nicht die im IJRR-Artikel festgelegten Anforderungen, um eine asymptotische Optimalität zu erzielen.σ0 q σ0 c(σ0)=exp(−d(q))>0
Ich frage mich, ob RRT * unter einer solchen Kostenfunktion einfach keine asymptotisch optimalen Lösungen liefert, oder ob es immer noch möglich ist, dass diese Annahmen die Optimalitätsnachweise im Papier vereinfachen.
quelle