Abstract-We consider the challenge of planning a minimum length path from an initial position to a final position for a rotorcraft. The path is found in a 3-dimensional Euclidean space containing a geometric obstacle. We base our approach on visibility graphs which have been used extensively for roadmap based path planning in 2-dimensional Euclidean space. Generalizing to 3-dimensional space is not straightforward, unless a visibility graph is generated that, when searched, will only provide an approximate minimum length path. Our approach generates such a visibility graph that is composed by an obstacle graph and two supporting graphs. The obstacle graph is generated by approximating a mesh around the configuration space obstacle, which is build from the convex hull of its work space counterpart. The supporting graphs are generated by finding the supporting lines between the initial or final position and the mesh. An approximation to the optimal path can subsequently be found using an existing graph search algorithm. The presented approach is suitable for fully known environments with a single truly 3-dimensional (not merely "raised" 2-dimensional) obstacle. An example for generating a nearly minimum length path for a small-scale helicopter operating near a building is shown. Path planning and trajectory generation are fundamental areas for UAS development and both provide the ability to figure out a way to efficiently and safely travel through an environment under a set of constraints. Specifically, for tasks such as surveillance, inspection, aerial mapping, etc., smallscale autonomous helicopters are increasingly being used. In many such tasks it is advantageous to operate in close proximity to the obstacles or to follow their surface. The practical use of the presented work is to obtain methods for path planning that can be used for operating a small-scale helicopter in an environment constrained by obstacles. The presented method is near-optimal, that is, able to produce a path close to the Euclidean shortest path inside a space. This space is constrained by a single obstacle such that no parts of the vehicle may intersect the obstacle at any time. In this space the vehicle is represented by its bounding sphere, which is centered in center-of-mass. The presented approach for path planning use visibility graphs (VG). Theses VGs are based on describing the obstacles in a configuration space (CS), which in turn are based on the work space (WS). The generation of those CS obstacles and VGs are the main contribution of this paper. The WS obstacle can be build from any set of vertices such as a point-cloud from sampled data. The WS obstacle is made convex since non-convex parts are not relevant when searching the VG for a solution. In fact, when computing the shortest path between two points in the CS, the shortest path is a series of connected edges that are either on the convex hull of the obstacle, or tangents from the points to the obstacle. Previous work on how to practically, automatically, and efficiently generate a configuration space from a 3D pointcloud in WS seems limited to building primitive solids or geometric representations, and in many path planning publications an existing configuration space is simply assumed. Visibility graphs for 2D path planning have been used extensively. However finding an optimal solution to the general path planning problem in 3D is NP-complete, see [1] , [2] . The difficulty of the problem is that the shortest path around a polyhedral obstacle does not in general traverse only vertices of the polyhedron, but also points somewhere on the edges of the polyhedron. The concept of adding additional vertices along these edges in configuration space so that no edge vertices are spaced more than a specified maximum length is introduced by Lozano-Perez and Wesley [1] . This approach generally results in a good approximation to the optimal path. Lozano-Perez [3] presents an algorithm for the 2D case that use the Minkowski sum (see [4] for details on Minkowski sum) to generate a CS obstacle from a polygonal obstacle and a polygonal vehicle. While CS obstacles could be generated by approximating the vehicle with a geodesic dome, the obstacles are described by a sequence of algebraic equations, which makes the optimization problem difficult to solve without resorting to numerical methods. Also Bajaj and Kim [5] describe algebraic algorithms for representing the boundary of CS obstacles as patches of quadratic surfaces. We propose a method for generating a VG from 1) a pointcloud that represent the WS obstacle, 2) a vehicle bounding sphere with radius r bs , and 3) an initial and final position for the vehicle. The generalized visibility graph VG(N, L) contains a node set N and a link set L of links between node pairs. Each node in the graph is assigned a possible configuration (or position), and each link represents a visible (linear) connection between them. The VG is composed of two parts; an obstacle visibility graph VG o that links nodepairs near the obstacle surface, and a supporting visibility 2012 Intelligent Vehicles Symposium
For example, Scholer et al. REF construct a three-dimensional visibility graph for UAVs, composed of one obstacle, and two supporting graphs.
Generating approximative minimum length paths in 3D for UAVs
2012 IEEE Intelligent Vehicles Symposium
2012 IEEE Intelligent Vehicles Symposium
Mathematics Computer Science