Safe Path Planning Using Cell Decomposition Approximation

ABBADI, Ahmad a Václav PŘENOSIL. Safe Path Planning Using Cell Decomposition Approximation. Online. In Mirosav Hrubý. International Conference DISTANCE LEARNING, SIMULATION AND COMMUNICATION. první. Brno: University of Defence, Brno, 2015, s. 8-14. ISBN 978-80-7231-992-3.

Základní údaje

• Originální název: Safe Path Planning Using Cell Decomposition Approximation
• Název česky: Bezpečné plánování trasy pomocí aproximace rozkladu na elementy okolí
• Autoři: ABBADI, Ahmad (760 Sýrie, domácí) a Václav PŘENOSIL (203 Česká republika, domácí).
• Vydání: první. Brno, International Conference DISTANCE LEARNING, SIMULATION AND COMMUNICATION, od s. 8-14, 7 s. 2015.
• Nakladatel: University of Defence, Brno

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Stať ve sborníku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Česká republika
• Utajení: není předmětem státního či obchodního tajemství
• Forma vydání: elektronická verze "online"
• WWW: URL
• Kód RIV: RIV/00216224:14330/15:00083282
• Organizační jednotka: Fakulta informatiky
• ISBN: 978-80-7231-992-3
• UT WoS: 000380565400001
• Klíčová slova česky: plánování trasy pohybu; rozklad na elementy; čtyřcestný sprom; bezpečná cesta; plánování trasy
• Klíčová slova anglicky: motion planning; cell decomposition; quad-tree; safety path; path planning
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

Motion planning is an essential part in robotics domain; it is responsible for guiding the robot motion toward the goal. It generates a path from one location to another one, while avoiding the obstacles in the way. The planning modules could be configured to check the optimality, completeness, power saving, shortness of path, minimal number of turn, or the turn sharpness, etc., in addition to path safety. In this paper the cell decomposition approximation planar is used to find a safe path; the quad-tree approximation algorithm divides the workspace into manageable free areas, and builds a graph of adjacency between them. New methods are proposed to keep the robot far away from the obstacles boundaries by a minimum safe distance. These methods manipulate the weights of adjacency graph's edges. They utilize and reflect the size of free cells when planning a path. These approaches give a lower weight to the connection between big free cells, and a higher weight to the connections between the smaller cells. The planner after that searches for the lowest cost path based on these weights. The safe path in this work is the path which keeps the robot far away from obstacles by specified minimum safety distance and it bias the robot's motion to follow the bigger areas in the workspace. The shortest path is not considered. However a tradeoff between the real path cost and the safe path cost is considered when choosing the weight values.

Anotace česky

Plánování trasy pohybu robota je jednou ze základních úloh robotiky. Představuje úlohu bezpečného dovedení robota k cíli. Spočívá v návrhu trasy jednoho místa do druhého místa, přeičemž obchází překážky. Plánovací modul by může být nakonfigurován tak, že respektuje různá kritéria optimalizace - úplnost, minimalizace spotřeby energie, minimalizace délky trasy, minimální počet zatáček nebo maximálně povelý úhel zatáček aj. Jedním z kritérií je také bezpečnosti cesty. V tomto článku je popsána metoda rokladu terénu na elementy používáné pro nalezení bezpečné cesty. Algoritmus čtyřcestného stromu rozděluje pracovní plochu na elementární akceptovatelné plochy a generuje graf jejich vzájemné "přilehlosti". Jsou zde diskutovány metody umožňující pohyb robota v minimální bezpečné vzdálenosti od překážek. Diskutovaná metoda je založena na manipulaci s vahami hran "přilehlosti" hran oblastí. Algoritmus respektuje váhy jednotlivých oblastí pro plánování trasy. Tento přístup využívá nižší váhy propojení mezi velkými volnými buňkami na jedné straně a vyšší váhy na propojení mezi menšími buňkami. Plánovač trasy hledá trasu na základě minimalizace vah všech použitých oblastí. Bezpečná trasa je ta, která udržuje robota v bezpečné minimální vzdálenosti od překážek a umožňuje sledovat větší prostor prostoru v němž se robot pohybuje. Nehledá se nejkratší cesta. Kompromis mezi náklady na použití trasy a bezpečností trasy představují hodnotu vahy.