Searching Multiple Approximate Solutions in Configuration Space to Guide Sampling-Based Motion Planning

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00342314" target="_blank" >RIV/68407700:21230/20:00342314 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216224:14330/20:00116340

Výsledek na webu

<a href="https://doi.org/10.1007/s10846-020-01247-4" target="_blank" >https://doi.org/10.1007/s10846-020-01247-4</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10846-020-01247-4" target="_blank" >10.1007/s10846-020-01247-4</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Searching Multiple Approximate Solutions in Configuration Space to Guide Sampling-Based Motion Planning

Popis výsledku v původním jazyce

High-dimensional configuration space is usually searched using sampling-based motion planning methods. The well-known issue of sampling-based planners is the narrow passage problem caused by small regions of the configuration space that are difficult to cover by random samples. Practically, the presence of narrow passages decreases the probability of finding a solution, and to cope with it, the number of random samples has to be significantly increased, which also increases the planning time. By dilating the free space, e.g., by scaling-down or thinning the robot (or obstacles), narrow passages become wider, which allows us to compute an approximate solution. Then, the configuration space can be sampled densely around the approximate solution to find the solution of the original problem. However, this process may fail if the final solution is too far from the approximate one. In this paper, we propose a method to find multiple approximate solutions in the configuration space to increase the chance of finding the final solution. The approximate solutions are computed by repeated search of the configuration space while avoiding, if possible, the already discovered solutions. This enables us to search for distinct solutions leading through different parts of the configuration space. The number of approximate solutions is automatically determined based on their similarity. All approximate solutions are then used to guide the sampling of the configuration space. The performance of the proposed approach is verified in scenarios with multiple narrow passages and the benefits of the method are demonstrated by comparing the results with the state-of-the-art planners.

Název v anglickém jazyce

Searching Multiple Approximate Solutions in Configuration Space to Guide Sampling-Based Motion Planning

Popis výsledku anglicky

High-dimensional configuration space is usually searched using sampling-based motion planning methods. The well-known issue of sampling-based planners is the narrow passage problem caused by small regions of the configuration space that are difficult to cover by random samples. Practically, the presence of narrow passages decreases the probability of finding a solution, and to cope with it, the number of random samples has to be significantly increased, which also increases the planning time. By dilating the free space, e.g., by scaling-down or thinning the robot (or obstacles), narrow passages become wider, which allows us to compute an approximate solution. Then, the configuration space can be sampled densely around the approximate solution to find the solution of the original problem. However, this process may fail if the final solution is too far from the approximate one. In this paper, we propose a method to find multiple approximate solutions in the configuration space to increase the chance of finding the final solution. The approximate solutions are computed by repeated search of the configuration space while avoiding, if possible, the already discovered solutions. This enables us to search for distinct solutions leading through different parts of the configuration space. The number of approximate solutions is automatically determined based on their similarity. All approximate solutions are then used to guide the sampling of the configuration space. The performance of the proposed approach is verified in scenarios with multiple narrow passages and the benefits of the method are demonstrated by comparing the results with the state-of-the-art planners.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

20204 - Robotics and automatic control

Projekt

<a href="/cs/project/GJ19-22555Y" target="_blank" >GJ19-22555Y: Vzorkovací techniky plánování pohybu a akcí s využitím aproximačních řešení</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Intelligent and Robotic Systems

ISSN

0921-0296

e-ISSN

1573-0409

Svazek periodika

100

Číslo periodika v rámci svazku

August

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

17

Strana od-do

1527-1543

Kód UT WoS článku

000564529000001

EID výsledku v databázi Scopus

2-s2.0-85090020216