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

VONÁSEK, Vojtěch, Robert PĚNIČKA and Barbora KOZLÍKOVÁ. Searching Multiple Approximate Solutions in Configuration Space to Guide Sampling-Based Motion Planning. Journal of Intelligent & Robotic Systems. Springer Nature B. V., 2020, vol. 100, 3-4, p. 1527-1543. ISSN 0921-0296. Available from: https://dx.doi.org/10.1007/s10846-020-01247-4.

Basic information

Original name

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

Authors

VONÁSEK, Vojtěch (203 Czech Republic, guarantor), Robert PĚNIČKA (203 Czech Republic) and Barbora KOZLÍKOVÁ (203 Czech Republic, belonging to the institution)

Edition

Journal of Intelligent & Robotic Systems, Springer Nature B. V. 2020, 0921-0296

---

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10200 1.2 Computer and information sciences

Country of publisher

Switzerland

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

URL

Impact factor

Impact factor: 2.646

RIV identification code

RIV/00216224:14330/20:00116340

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1007/s10846-020-01247-4

UT WoS

000564529000001

Keywords in English

motion planning;rapidly-exploring random tree

---

Abstract

V originále

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.