Spatial Constraint Generation for Motion Planning in Dynamic Environments
Open Access
- 27 September 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 384-389
Abstract
This paper presents a novel method to generate spatial constraints for motion planning in dynamic environments. Motion planning methods for autonomous driving and mobile robots typically need to rely on the spatial constraints imposed by a map-based global planner to generate a collision-free trajectory. These methods may fail without an offline map or where the map is invalid due to dynamic changes in the environment such as road obstruction, construction, and traffic congestion. To address this problem, triangulation-based methods can be used to obtain a spatial constraint. However, the existing methods fall short when dealing with dynamic environments and may lead the motion planner to an unrecoverable state. In this paper, we propose a new method to generate a sequence of channels across different triangulation mesh topologies to serve as the spatial constraints. This can be applied to motion planning of autonomous vehicles or robots in cluttered, unstructured environments. The proposed method is evaluated and compared with other triangulation-based methods in synthetic and complex scenarios collected from a real-world autonomous driving dataset. We have shown that the proposed method results in a more stable, long-term plan with a higher task completion rate, faster arrival time, a higher rate of successful plans, and fewer collisions compared to existing methods.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Dynamic Channel: A Planning Framework for Crowd Navigation2019
- Navigation meshes and real-time dynamic planning for virtual worlds2014
- Field D* path-finding on weighted triangulated and tetrahedral meshesAutonomous Agents and Multi-Agent Systems, 2012
- An enhanced dynamic Delaunay triangulation-based path planning algorithm for autonomous mobile robot navigation2010
- Delete and insert operations in Voronoi/Delaunay methods and applicationsComputers & Geosciences, 2003
- Incremental topological flipping works for regular triangulationsAlgorithmica, 1996
- Computing minimum length paths of a given homotopy classComputational Geometry, 1994
- Fully dynamic delaunay triangulation in logarithmic expected time per operationComputational Geometry, 1992
- Constrained delaunay triangulationsAlgorithmica, 1989
- Primitives for the manipulation of general subdivisions and the computation of VoronoiACM Transactions on Graphics, 1985