Published January 1, 2020
| Version v1
Publication
Open
A Variable-Step RRT<sup>*</sup> Path Planning Algorithm for Quadrotors in Below-Canopy
Description
Rapidly-exploring random tree (RRT * ) algorithm has been widely applied to path planning problem for quadrotor, which takes a great amount of static and dynamic constraints into account.However, conventional RRT * algorithm is suffering low convergence rate and efficiency in below-canopy environment, where is usually occupied with narrow aisles and uneven distributed obstacles.In order to enrich the forest information database and obtain information efficiently in blow-canopy, an improved variable-step RRT * algorithm has been proposed in this paper.In the proposed algorithm, the sampling nodes are determined by the target bias sampling strategy with variable probability.To further increase the efficiency of node generation and balance the searching time and security in areas with different obstacles densities, the eventtriggered step size extension has been proposed according to hyperbolic tangent function.After that, both Euclidean distance and angle constraints are adopted in the cost function of node connection optimization.Then, the path is further optimized by path trimming and Bezier curves smooth method.Finally, the demonstration of the proposed algorithm is presented to show its efficiency, and the comparison result with existing RRT-like algorithms indicates that the performance of our algorithm is better than RRT, RRT * and DDRRT in terms of convergence and accuracy.Comparing to other classical path planning methods such as A * , Artificial potential field and Fuzzy-logic, our method also shows its superiority.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تم تطبيق خوارزمية الاستكشاف السريع للشجرة العشوائية (RRT *) على نطاق واسع على مشكلة تخطيط المسار للدوار الرباعي، والتي تأخذ قدرًا كبيرًا من القيود الثابتة والديناميكية في الاعتبار. ومع ذلك، فإن خوارزمية RRT * التقليدية تعاني من انخفاض معدل التقارب والكفاءة في بيئة أسفل المظلة، حيث عادة ما تكون مشغولة بالممرات الضيقة والعقبات الموزعة غير المستوية. من أجل إثراء قاعدة بيانات معلومات الغابة والحصول على المعلومات بكفاءة في مظلة النفخ، تم اقتراح خوارزمية RRT * متغيرة الخطوة في هذه الورقة. في الخوارزمية المقترحة، يتم تحديد عقد أخذ العينات من خلال استراتيجية أخذ العينات للتحيز المستهدف مع احتمالية متغيرة. لزيادة كفاءة توليد العقدة وتحقيق التوازن بين وقت البحث والأمن في المناطق ذات الكثافات المختلفة للعقبات، تم اقتراح امتداد حجم الخطوة الذي تم تشغيله وفقًا لوظيفة الظل الزائدي. بعد ذلك، يتم اعتماد كل من قيود المسافة والزاوية الإقليدية في وظيفة التكلفة لتحسين اتصال العقدة. ثم، يتم تحسين المسار بشكل أكبر عن طريق تقليم المسار ومنحنيات بيزيه بطريقة سلسة. أخيرًا، يتم عرض عرض الخوارزمية المقترحة لإظهار كفاءتها، ونتيجة المقارنة مع الخوارزميات الحالية الشبيهة بـ RRT تشير إلى أن أداء خوارزميتنا أفضل من RRT و RRT * و DDRRT من حيث التقارب والدقة. بالمقارنة مع طرق تخطيط المسار الكلاسيكية الأخرى مثل A * و مجال الجهد الاصطناعي و المنطق الغامض، تظهر طريقتنا أيضًا تفوقها.Translated Description (French)
L'algorithme d'arbre aléatoire à exploration rapide (RRT * ) a été largement appliqué au problème de planification de chemin pour quadrotor, qui prend en compte une grande quantité de contraintes statiques et dynamiques. Cependant, l'algorithme RRT * conventionnel souffre d'un faible taux de convergence et d'une faible efficacité dans un environnement sous la canopée, où il est généralement occupé par des allées étroites et des obstacles distribués inégaux. Afin d'enrichir la base de données d'informations forestières et d'obtenir des informations efficacement dans la canopée, un algorithme RRT * à pas variable amélioré a été proposé dans cet article. Dans l'algorithme proposé, les nœuds d'échantillonnage sont déterminés par la stratégie d'échantillonnage de biais cible avec une probabilité variable. Pour augmenter encore l'efficacité de la génération de nœuds et équilibrer le temps de recherche et la sécurité dans des zones avec différentes densités d'obstacles, l'extension de taille de pas déclenchée par un événement a été proposée selon la fonction de tangente hyperbolique. Après cela, les contraintes de distance et d'angle euclidiennes sont adoptées dans la fonction de coût de l'optimisation de la connexion des nœuds. Ensuite, le chemin est encore optimisé par le rognage du chemin et la méthode lisse des courbes de Bézier. Enfin, la démonstration de l'algorithme proposé est présentée pour montrer son efficacité et le résultat de la comparaison avec les algorithmes existants de type RRT indique que les performances de notre algorithme sont meilleures que RRT, RRT * et DDRRT en termes de convergence et de précision. Comparée à d'autres méthodes classiques de planification de chemin telles que A * , le champ de potentiel artificiel et la logique floue, notre méthode montre également sa supériorité.Translated Description (Spanish)
El algoritmo de árbol aleatorio de exploración rápida (RRT * ) se ha aplicado ampliamente al problema de planificación de rutas para quadrotor, que tiene en cuenta una gran cantidad de restricciones estáticas y dinámicas. Sin embargo, el algoritmo RRT * convencional está sufriendo una baja tasa de convergencia y eficiencia en el entorno debajo del dosel, donde generalmente está ocupado con pasillos estrechos y obstáculos distribuidos desiguales. Con el fin de enriquecer la base de datos de información forestal y obtener información de manera eficiente en el dosel de soplado, en este documento se ha propuesto un algoritmo RRT * de paso variable mejorado. En el algoritmo propuesto, los nodos de muestreo están determinados por la estrategia de muestreo de sesgo objetivo con probabilidad variable. Para aumentar aún más la eficiencia de la generación de nodos y equilibrar el tiempo de búsqueda y la seguridad en áreas con diferentes densidades de obstáculos, la extensión del tamaño del paso desencadenada por eventos se ha propuesto de acuerdo con la función tangente hiperbólica. Después de eso, se adoptan restricciones de distancia y ángulo euclidianas en la función de costo de la optimización de la conexión de nodos. Luego, la ruta se optimiza aún más mediante el recorte de ruta y el método suave de curvas de Bezier. Finalmente, se presenta la demostración del algoritmo propuesto para mostrar su eficiencia y el resultado de la comparación con algoritmos similares a RRT existentes indica que el rendimiento de nuestro algoritmo es mejor que RRT, RRT * y DDRRT en términos de convergencia y precisión. En comparación con otros métodos clásicos de planificación de rutas como A * , campo de potencial artificial y lógica difusa, nuestro método también muestra su superioridad.Files
09046759.pdf.pdf
Files
(245 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:20eaf914a69803e74268ccc88dd29455
|
245 Bytes | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- خوارزمية تخطيط المسار<sup></sup> ذات الخطوة المتغيرة للدوارات الرباعية في أسفل المظلة
- Translated title (French)
- Un algorithme de planification de chemin RRT<sup>*</sup> à pas variable pour les quadrotors en dessous de la canopée
- Translated title (Spanish)
- Un algoritmo de planificación de ruta RRT<sup>*</sup> de paso variable para cuadricópteros en el dosel inferior
Identifiers
- Other
- https://openalex.org/W3013946224
- DOI
- 10.1109/access.2020.2983177
References
- https://openalex.org/W1763528081
- https://openalex.org/W1850131177
- https://openalex.org/W1854270966
- https://openalex.org/W1971086298
- https://openalex.org/W1988615714
- https://openalex.org/W2041990848
- https://openalex.org/W2050635900
- https://openalex.org/W2078441432
- https://openalex.org/W2089888607
- https://openalex.org/W2104246659
- https://openalex.org/W2136534584
- https://openalex.org/W2141664020
- https://openalex.org/W2143826757
- https://openalex.org/W2149067903
- https://openalex.org/W2412423240
- https://openalex.org/W2522123397
- https://openalex.org/W2523274246
- https://openalex.org/W2523453107
- https://openalex.org/W2555104325
- https://openalex.org/W2563320938
- https://openalex.org/W2753014192
- https://openalex.org/W2765452429
- https://openalex.org/W2898753109
- https://openalex.org/W2901062134
- https://openalex.org/W2941387609
- https://openalex.org/W2963530188
- https://openalex.org/W2966139841
- https://openalex.org/W3176100771