Naslov
Drivable path planning using hybrid search algorithm based on E* and Bernstein-Bezier motion primitives

Autori
Klančar, Gregor ; Seder, Marija ; Blažič, Sašo ; Škrjanc, Igor ; Petrović, Ivan

Izvornik
IEEE Transactions on Systems Man Cybernetics- Systems (2168-2216) 51 (2021), 8; 4868-4882

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Path planning, Bernstein-Bézier curve, motion primitives, hybrid planner, graph search algorithm

Sažetak
This work proposes a hybrid path-planning algorithm, the HE* algorithm, which combines the discrete grid-based E* search and continuous Bernstein-Bézier (BB) motion primitives. Several researchers have addressed the smooth path planning problem and the sample-based integrated path planning techniques. We believe that the main benefits of the proposed approach are: directly drivable path, no additional post- optimization tasks, reduced search branching, low computational complexity, and completeness guarantee. Several examples and comparisons with the state of the art planners are provided to illustrate and evaluate the main advantages of the HE* algorithm. HE* yields a collision-safe and smooth path that is close to spatially optimal (the Euclidean shortest path) with a guaranteed continuity of curvature. Therefore, the path is easily drivable for a wheeled robot without any additional post- optimization and smoothing required. HE* is a two- stage algorithm which uses a direction-guiding heuristics computed by the E* search in the first stage, which improves the quality and reduces the complexity of the hybrid search in the second stage. In each iteration, the search is expanded by a set of BBs, the parameters of which adapt continuously according to the guiding heuristics. Completeness is guaranteed by relying on a complete node mechanism, which also provides an upper bound for the calculated path cost. A remarkable feature of HE* is that it produces good results even at coarse resolutions.

Izvorni jezik
Engleski

Znanstvena područja
Elektrotehnika, Računarstvo, Temeljne tehničke znanosti

POVEZANOST RADA