Unmanned aerial vehicle 3D mapping system

[0001] This application claims the benefit of U.S. provisional application No. 62/049,622, filed Sep. 12, 2014, the contents of which are incorporated herein by reference.

[0002] The present application relates to data processing for vehicles, navigation, and relative location, and more specifically to flight plans for unmanned aerial vehicles.

[0003] Unmanned aerial vehicles (UAVs) are remotely piloted or self-piloted aircraft that can carry sensors, communications equipment, or other payloads. They have been used in a reconnaissance and intelligence-gathering role for many years. More recently, UAVs have been developed and used for mapping and modeling functions.

[0004] Typically, UAVs use a Global Positioning System (GPS) to provide navigation over various terrains. For mapping and modeling, UAVs can be equipped with high resolution cameras, which allow UAVs so-equipped to acquire photos cost efficiently and autonomously from unconventional viewpoints. While UAV technology is advancing rapidly, UAVs are constrained by payload and flight time. To fully exploit UAVs for mapping and modeling, the limited flight-time must be accounted for and an efficient flight path must be utilized.

[0005] The challenge of limited UAV flight time is compounded by the requirement of proper photographic coverage to allow proper mapping and modeling. For “easy terrain,” 75% frontal and 50% side overlap photographic coverage is recommended. For “difficult terrain,” 85% frontal with 60% side overlap is recommended. For simple building mapping, oblique photos taken at different altitudes while flying around the building produce acceptable imaging results.

[0006] One method for generating solid models of high accuracy suggests that upon determining an initial movement path based on an estimate of a structure to be modeled, images of the structure to be modeled may be captured and surface hypotheses formed for unobserved surfaces based on the captured images. A normal vector and a viewing cone may be computed for each hypothesized surface. A set of desired locations may be determined based on the viewing cones for the entire structure to be modeled and a least impact path for the UAV determined based on the desired locations and desired flight parameters.

[0007] While preferred photographic coverage is known and suggested, optimal UAV flight patterns are not. For open terrain a “lawnmower-style” mapping route adjusted for the Earth's contour may be preferred. The lawnmower-style route must be adjusted when the area to be mapped contains “difficult terrain,” manmade objects, vertical obstructions, and/or no-fly zones.

[0008] There is a need in the industry for a system that generates an optimal UAV flight plan taking into account the desired photographic coverage and the topographical and other physical constraints of the area to be mapped.

[0009] The present invention solves the foregoing problems by providing an automatic unmanned aerial vehicle (UAV) flight control system for 3D aerial mapping that includes a UAV with an onboard camera, and a controller capable of communication with a flight control module of the UAV. The controller is configured to determine an area mapping flight path based on terrain characteristics of an area to be mapped. The controller also can determine a structure mapping flight path based on the existence and location of vertical structures within the area to be mapped. The area mapping flight path can be appended with the structure mapping flight path, thus providing an integrated and optimized UAV flight path for 3D mapping and modeling.

[0019] The present invention solves the foregoing problems by providing an enhanced 3D mapping and modeling system that provides high-resolution, high-quality images independent of terrain, natural features, and manmade features, e.g., buildings, physical structures. For purposes of describing the present invention, the terms “mapping” and “modeling” are used interchangeably herein. Current mapping solutions primarily map objects using a classical lawnmower flight pattern during which aerial images are taken with specified frontal and side overlap of images. Distortion in 3D maps can occur when a “lawnmower” mapping flight plan is followed. There often is very little detail in the buildings' features and the vertical walls on the buildings appear to be slanted.

[0020] One aspect of the invention is a method for generating a UAV flight plan for an area to be mapped, including identifying the area to be mapped; identifying special regions within the area to be mapped; and applying a rule set for generating an optimized flight plan. Different specified regions within the area to be mapped may have their own optimal flight patterns. The optimal flight patterns from the different regions of the area to be mapped are integrated to generate an optimized flight plan for the entire area to be mapped. For example, once flight planning optimization is initiated, a polygon and/or rectangular grid that encompasses the polygon input by the user is first identified as an area to be mapped. Areas of the grid that fall fully outside of the polygon can be treated as avoidance areas such that the UAV does not fly in those areas. Within this polygon/rectangular area, the first step is to identify any special regions, e.g., avoidance areas, vegetation areas, buildings, cell towers, etc. An optimized flight path can be generated that will allow area coverage to occur efficiently in the “open area.” In optimizing the open area flight path, vegetation is treated as an “open area” below a designated height and as an “avoidance area” above a designated height. Special mapping regions, e.g., buildings, cell towers, etc. are treated as avoidance areas.

[0021] The optimized open area coverage flight path can be determined by an optimization method. Nonlimiting examples of an optimization method can include optimal algorithms, heuristic algorithms including genetic algorithms, and hybrid algorithms. During the initial phase of the UAV flight path planning, rules are applied to regions, e.g., distance the UAV must stay away from avoidance areas, minimum height that must be maintained above vegetation, etc. After the optimized open area coverage flight path is generated, that portion of the flight plan is appended with special region mapping flight paths, e.g., buildings, cell towers, vertical structures, etc. To get the complete/integrated flight path, when the optimized open area coverage flight path encounters a special region, the path is appended with the special flight path needed to map that special region. As used herein “encounters” is defined as reaching the closest point of approach. After the special region flight path is complete, the UAV departs/returns to the optimized open area coverage mapping path.

[0022] Flight waypoints define the UAV flight path. Additional information/data critical to the mapping process is added to each waypoint, e.g., data file. The waypoints themselves are stated as latitude/longitude points, xy points in a predefined grid, etc. Waypoints are typically sensed by a Global Positioning Receiver, although other means of positioning or geolocation can be used, e.g., cell tower triangulation, direction finding, transponder networks, etc. Included at each waypoint within the path plan is the altitude, camera tilt angle, and camera heading (direction/bearing) at each point that is needed to create a 3D map/3D image.

[0023] A second aspect of the invention is an automatic unmanned aerial vehicle (UAV) flight control system for 3D aerial mapping. The system can include a UAV with an onboard camera, and a controller capable of communication with a flight control module of the UAV. The controller can be configured to (i) determine an area mapping flight path based on terrain characteristics of an area to be mapped; (ii) determine a structure mapping flight path based on the existence and location of vertical structures within the area to be mapped; and (iii) determine an optimized flight path for the UAV by integrating the area mapping flight path and the structure mapping flight path.

[0024] A third aspect of the invention is a computer-readable storage medium with instructions stored thereon to control a flight path of an unmanned aerial vehicle (UAV) based image capture system for 3D modeling. The instructions can include determining an initial movement path based on an area to be mapped, the existence of vertical structures and avoidance areas within the area to be mapped; capturing images of the area and structures to be mapped; and guiding the UAV flight path.

[0025] A genetic algorithm (GA) is a heuristic search algorithm based on the mechanics of natural selection and natural genetics. A GA can be used to find the optimal path for flying over an area with an autonomous quadcopter to gather enough camera shots at appropriate angles to develop a 3-D map or model of an area and structures in the area. The flight path must also avoid designated “no-fly” areas and, if necessary, fly above or avoid very tall vegetation (e.g. mature trees). Other approaches can include spanning-tree coverage algorithms and neural network based planning methods.

[0026] The first step in solving the problem is to choose the desired area to be mapped. This is done by selecting the corner points of the area (much like surveyors do when setting pins to mark of an area to be mapped). Once the corner points are chosen they are used to determine a convex hull, as shown in FIG. 1. A convex hull is constructed using all points chosen and finding a convex polygon that contains all the points.

[0027] After the convex hull is created then the polygon is inscribed in a rectangle and a grid is applied. See FIG. 2. The latitude and longitude are maintained for each corner point for reference and a new x-y coordinate system is overlaid onto the rectangle. The initial take-off point and landing point for the quadcopter is noted.

[0028] The next step is to determine if there are areas of avoidance, vegetation to fly over, or structures to map. These areas will be noted with circles, rectangles or irregular polygons. FIG. 3 shows an area with one building marked as a rectangle, vegetation to fly above as a circle and area of avoidance as an irregular polygon.

[0029] After the areas have been determined, each of the regions in the grid is labeled with the appropriate numbers to be used in by the algorithm to determine the appropriate path of the quadcopter. Each region will be labeled with the following: 0 for open to visit; −1 is for avoidance area, either outside designated area or identified as avoid by user; −2 is for vegetation (in the case altitude being flown by the quadcopter is 100 ft then this is becomes an area of avoidance); −3 is for structures to be mapped.

[0030] When the labeling is complete, the GA is used to find an optimal path through the open regions that can be flown (details discussed below). After the GA finds an optimal path then the path around each structure is appended to the optimal area flight path.

[0031] The first step in designing a GA to solve a particular problem is to determine an encoding for an individual solution for the problem as a “chromosome.” A chromosome in this case will be a 1×n matrix, where n is the length of the chromosome. For this problem, the chromosome length (n) is variable and represents the number of open cells the quadcopter visits during its flight. The reason this is variable is that there may be backtracking (revisiting open cells) during the flight and the backtracking may be different for different solutions. The objective is to have the shortest path that visits all open cells and minimizes backtracking. The Fitness Value of a chromosome is computed by the expression below:

[0032] $\mathrm{Fitness}\mathrm{Value}=\{\begin{array}{cc}\frac{\mathrm{number}\mathrm{of}\mathrm{open}\mathrm{cells}}{\mathrm{length}\mathrm{of}\mathrm{the}\mathrm{path}}& \mathrm{for}\mathrm{paths}\mathrm{that}\mathrm{visit}\mathrm{every}\mathrm{open}\mathrm{cell}\\ \frac{\begin{array}{c}\mathrm{number}\mathrm{of}\mathrm{open}\\ \mathrm{cells}\end{array}}{\mathrm{length}\mathrm{of}\mathrm{path}}*0.001& \mathrm{for}\mathrm{paths}\mathrm{that}\mathrm{leaves}\mathrm{open}\mathrm{cells}\mathrm{unvisited}\end{array}$

[0033] An “initial population” or set of 100 chromosomes is developed. Each chromosome is evaluated using the fitness function above to determine how it compares to the other chromosomes based on the criteria set for a good flight path (Fitness Value=1). The GA then will combine solutions using standard GA operations (crossover and mutation—discussed below) to develop better solutions, each successive generation of solutions being as good as or better than the one before it. This process continues until the stopping criteria is met (a solution is produced with optimum fitness value=1 or after 100 generations). A sample chromosome, which represents a flight path, is shown in FIG. 5.

[0034] The initial generation of chromosomes contains eight chromosomes that represent the standard patterns for visiting cells for this coverage type of problem (FIG. 6). The other 92 chromosomes are developed from these original eight chromosomes by mutating (or changing one gene). After the initial population is created then each chromosome is evaluated by the fitness function. The chromosome in FIG. 5 follows pattern 2. This means that at whatever cell the quadcopter starts in on the grid, it goes right 3 times (2,2,2) then from there it goes up one cell (3), then left 3 times (4,4,4), then up 3 times (3,3,3), etc.

[0035] To create the next generation of 100 chromosomes (possible solutions) a mutation of approximately 50% of the original chromosomes is completed to form new chromosomes and additional new chromosomes are developed through crossover of pairs of chromosomes with the highest fitness values. If the chromosome is chosen to be mutated then one gene (number in the chromosome) is randomly selected to be changed. There is 50/50 chance of the chromosome being mutated and added to the new set of chromosomes. A Uniform Crossover is used to combine a chromosome with a high fitness value and another random chromosome with the same length. The Uniform Crossover (FIG. 7) enables the two parent chromosomes to contribute the genes about evenly. If the mixing ratio is 0.5, the offspring has approximately half of the genes from first parent and the other half from second parent, although cross over points can be randomly chosen as seen in FIG. 7.

[0036] After these two operations are completed and the new chromosomes added to the original 100 chromosomes, the total set of chromosomes will be ordered by their fitness values and the best 100 chromosomes will be kept. Then the process starts all over again and continues until either one of the chromosomes has fitness 1 or 100 iterations is completed. When one of the stopping criteria has been met, then the algorithm will output an optimal path (the best one found) for visiting the open regions of the area.

[0037] The next step is to append the structure (or “special”) mapping flight path to the area mapping flight path. The optimal chromosome is applied to the area map that has been overlaid with the labeled grid. When the path moves to a grid region that is adjacent to a region marked with a −3 (structure), then the path will be appended with a structure mapping flight path as shown in FIG. 8.

[0038] To create the structure mapping flight path, an offset distance is chosen and the quadcopter will fly at that distance from the structure. A path is created that surrounds the structure at the distance of the offset away. The structure flight path is segmented using distinct points along the path to be used as waypoints for the quadcopter. A list of waypoints is recorded along with altitude, camera angle, and heading for each point. This information is used to ensure the camera is always facing the structure at the proper angle. The structure mapping flight path always begins and ends at the same location. Once the structure mapping flight path is appended to the area mapping flight path at the proper location, the area mapping algorithm continues on with the original optimal path from the point of departure. When the mapping of the area is completed, then the quadcopter is directed to the take-off/landing position to land.

[0039] While various preferred embodiments have been shown and described, modifications thereof can be made by one skilled in the art without departing from the spirit and teachings herein. The embodiments herein are exemplary only, and are not limiting. Many variations and modifications of the apparatus disclosed herein are possible and within the scope of the invention. Accordingly, the scope of protection is not limited by the description set out above.