Collided path replanning in dynamic environments using RRT and Cell decomposition algorithms

ABBADI, Ahmad and Václav PŘENOSIL. Collided path replanning in dynamic environments using RRT and Cell decomposition algorithms. Online. In Hodicky, Jan. Modelling and Simulation for Autonomous Systems,. BERLIN, GERMANY: Springer International Publishing, 2015, p. 131-143. ISBN 978-3-319-22382-7. Available from: https://dx.doi.org/10.1007/978-3-319-22383-4_9.

Basic information

• Original name: Collided path replanning in dynamic environments using RRT and Cell decomposition algorithms
• Name in Czech: Kolizní plánování cesty v dynamickém prostředí využívající algoritmus RRT a rozkladu elementů
• Authors: ABBADI, Ahmad (760 Syrian Arab Republic, belonging to the institution) and Václav PŘENOSIL (203 Czech Republic, belonging to the institution).
• Edition: BERLIN, GERMANY, Modelling and Simulation for Autonomous Systems, p. 131-143, 13 pp. 2015.
• Publisher: Springer International Publishing

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Czech Republic
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: electronic version available online
• WWW: URL
• Impact factor: Impact factor: 0.402 in 2005
• RIV identification code: RIV/00216224:14330/15:00083283
• Organization unit: Faculty of Informatics
• ISBN: 978-3-319-22382-7
• ISSN: 0302-9743
• Doi: http://dx.doi.org/10.1007/978-3-319-22383-4_9
• UT WoS: 000365044100009
• Keywords (in Czech): přeplánování trasy; plánování pohybu; RRT; rozklad na elementy; multi-RRT
• Keywords in English: path re-planning; motion planning; RRT; cell decomposition; Multi RRT
• Tags: International impact, Reviewed

Abstract

The motion planning is an important part of robots’ models. It is responsible for robot’s movements. In this work, the cell decomposition algorithm is used to find a spatial path on preliminary static workspaces, and then, the rapidly exploring random tree algorithm (RRT) is used to validate this path on the actual workspace. Two methods have been proposed to enhance the omnidirectional robot’s navigation on partially changed workspace. First, the planner creates a RRT tree and biases its growth toward the path’s points in ordered form. The planner reduces the probability of choosing the next point when a collision is detected, which in turn increases the RRT’s expansion on the free space. The second method uses a straight planner to connect path’s points. If a collision is detected, the planner places RRTs on both sides of the collided segment. The proposed methods are compared with the others approaches, and the simulation shows better results in term of efficiency and completeness.

Abstract (in Czech)

Plánování pohybu robota je důležitou součástí modelování funkcí robotů. Plán řídí pohyby robota. V této práci se algoritmus rozkladu na buňky používá k nalezení cesty pracovní plochou a algoritmus prozkoumání náhodného stromu (RRT) k ověření cesty skutečným prostorem. Byly navrženy dvě metody ke zlepšení navigace všesměrové pohyblivého robota částečně změněnou pracovní plochou. Za prvé, plánovač vytvoří RRT strom a vychyluje jeho růst směrem k bodu na cestě. Plánovač snižuje pravděpodobnost výběru dalšího bodu, když je detekována kolize, což zase zvyšuje expanzi RRT na volném prostoru. Druhá metoda používá shodný plánovač pro napojení bodů cesty. Pokud je detekována kolize, plánovač upravuje RRT na obou stranách kolizního segmentu. Navrhované metody jsou porovnávány s dalšími používanými přístupy, přečemž simulace ukazuje lepší výsledky z hlediska účinnosti a úplnosti plánování cesty.