Sparse 3D Topological Graphs for Micro-Aerial Vehicle Planning
Abstract
Micro-Aerial Vehicles (MAVs) have the advantage of moving freely in 3D space. However, creating compact and sparse map representations that can be efficiently used for planning for such robots is still an open problem. In this paper, we take maps built from noisy sensor data and construct a sparse graph containing topological information that can be used for 3D planning. We use a Euclidean Signed Distance Field, extract a 3D Generalized Voronoi Diagram (GVD), and obtain a thin skeleton diagram representing the topological structure of the environment. We then convert this skeleton diagram into a sparse graph, which we show is resistant to noise and changes in resolution. We demonstrate global planning over this graph, and the orders of magnitude speed-up it offers over other common planning methods. We validate our planning algorithm in real maps built onboard an MAV, using RGB-D sensing.
Community
Proposes a method for constructing a scene graph containing topological information for 3D planning of a MAV (micro-aerial vehicle); use Euclidean signed distance function (ESDF - each point in a 2D slice/grid stores distance to nearest obstacle), extract 3D generalized Voronoi Diagram (GVD - all points that are equidistant from two or more obstacles) that is a skeleton of topological structure of the environment, convert to scene graph (robust to noise and sensor resolution); speed up in path planning. Skeleton diagram construction: get ESDF (using Voxblox), ridges in ESDF give GVD; iterate over ESDF voxels and compare parent directions (to closest occupied point) with 6-connected neighbors; use theta simplified medial axis (theta-SMA) check (takes directions of current and neighbor, dot product less than a cosine threshold) for distinct basis points on object boundaries (point in GVD/boundary); for edge extraction, check 26 connected neighbors and pick voxels with at least 18-connected neighbors in medial axis (boundary); thinning of GVD edges (medial lines) using template matching (preserve connectivity). Scene graph generation: get vertices in the tinned medial lines (final skeleton diagram) by neighbor checks, k-D tree and pruning in radius (retain vertices farthest from obstacles); connect vertices using edge following of connected neighbors (directions followed by priority FILO stack); edge splitting for collision free paths, use diagram A-star and path deviations, make use of already existing vertices in the graph (remove duplicated near-by vertices); sparse graph is made by connecting sub-graphs (with more than one vertex) using A-star feasible paths. A-star is fastest through sparse (scene) graphs (since they’re of consistent size against voxel size and noise level) over skeleton diagram (which is sensitive to parameters). Sparse graph planning is much faster (real time planner) than raw RRT-star or A-star but produces longer path lengths over more vertices. Also has timing information (diagram showing time taken by individual components) by running a MAV and initially using ORB SLAM2 for state estimation and loop closure. From ETHz (ASL, Helen Oleynikova).
Links: YouTube 1, GitHub (skeleton planning)
Models citing this paper 0
No model linking this paper
Datasets citing this paper 0
No dataset linking this paper
Spaces citing this paper 0
No Space linking this paper
Collections including this paper 0
No Collection including this paper