Viseras, Alberto und Ortiz Losada, Rafael und Merino, Luis (2016) Planning with ants: Efficient path planning with rapidly exploring random trees and ant colony optimization. International Journal of Advanced Robotic Systems. SAGE Publications. doi: 10.1177/1729881416664078. ISSN 1729-8806. (im Druck)
Es ist eine neuere Version dieses Eintrags verfügbar. |
PDF
- Nur DLR-intern zugänglich
5MB |
Kurzfassung
Rapidly exploring random trees (RRTs) have been proven to be efficient for planning in environments populated with obstacles. These methods perform a uniform sampling of the state space, which is needed to guarantee the algorithm’s completeness but does not necessarily lead to the most efficient solution. In previous works it has been shown that the use of heuristics to modify the sampling strategy could incur an improvement in the algorithm performance. However, these heuristics only apply to solve the shortest path-planning problem. Here we propose a framework that allows us to incorporate arbitrary heuristics to modify the sampling strategy according to the user requirements. This framework is based on ‘learning from experience’. Specifically, we introduce a utility function that takes the contribution of the samples to the tree construction into account; sampling at locations of increased utility then becomes more frequent. The idea is realized by introducing an ant colony optimization concept in the RRT/RRT* algorithm and defining a novel utility function that permits trading off exploitation versus exploration of the state space. We also extend the algorithm to allow an anytime implementation. The scheme is validated with three scenarios: one populated with multiple rectangular obstacles, one consisting of a single narrow passage and a maze-like environment. We evaluate its performance in terms of the cost and time to find the first path, and in terms of the evolution of the path quality with the number of iterations. It is shown that the proposed algorithm greatly outperforms state-of-the-art RRT and RRT* algorithms.
elib-URL des Eintrags: | https://elib.dlr.de/106682/ | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Dokumentart: | Zeitschriftenbeitrag | ||||||||||||||||
Titel: | Planning with ants: Efficient path planning with rapidly exploring random trees and ant colony optimization | ||||||||||||||||
Autoren: |
| ||||||||||||||||
Datum: | 2016 | ||||||||||||||||
Erschienen in: | International Journal of Advanced Robotic Systems | ||||||||||||||||
Referierte Publikation: | Ja | ||||||||||||||||
Open Access: | Ja | ||||||||||||||||
Gold Open Access: | Ja | ||||||||||||||||
In SCOPUS: | Ja | ||||||||||||||||
In ISI Web of Science: | Nein | ||||||||||||||||
DOI: | 10.1177/1729881416664078 | ||||||||||||||||
Verlag: | SAGE Publications | ||||||||||||||||
ISSN: | 1729-8806 | ||||||||||||||||
Status: | im Druck | ||||||||||||||||
Stichwörter: | Mobile robots, autonomous agents, motion and path planning, rapidly exploring random trees, ant colony optimization, bio-inspired robotics | ||||||||||||||||
HGF - Forschungsbereich: | Luftfahrt, Raumfahrt und Verkehr | ||||||||||||||||
HGF - Programm: | Verkehr | ||||||||||||||||
HGF - Programmthema: | Verkehrsmanagement (alt) | ||||||||||||||||
DLR - Schwerpunkt: | Verkehr | ||||||||||||||||
DLR - Forschungsgebiet: | V VM - Verkehrsmanagement | ||||||||||||||||
DLR - Teilgebiet (Projekt, Vorhaben): | V - Vabene++ (alt) | ||||||||||||||||
Standort: | Oberpfaffenhofen | ||||||||||||||||
Institute & Einrichtungen: | Institut für Kommunikation und Navigation > Nachrichtensysteme | ||||||||||||||||
Hinterlegt von: | Viseras Ruiz, Alberto | ||||||||||||||||
Hinterlegt am: | 26 Okt 2016 09:36 | ||||||||||||||||
Letzte Änderung: | 08 Mär 2018 18:29 |
Verfügbare Versionen dieses Eintrags
- Planning with ants: Efficient path planning with rapidly exploring random trees and ant colony optimization. (deposited 26 Okt 2016 09:36) [Gegenwärtig angezeigt]
Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags