Path Optimization of 3D Visual Inspection for Large Facilities and Cities Using CAD Data

Carnegie Mellon University’s Dr. Kenji Shimada and his PhD student Iacopo Gentilini investigated using large CAD models to optimize the flight path of quadrotor drones. Such unmanned aerial vehicles (UAVs) can be used to autonomously survey damaged cities. Optimizing the flight path maximizes the area covered by the drone, accelerating rescue team search operations. To demonstrate this concept, Shimada and Gentilini programmed a quadrotor drone to fly autonomously through the Autodesk Gallery, capturing images of exhibits.

Using Autodesk® Infrastructure Modeler software, the team exported specific CAD data of urban environments. The position and geometry of specific features, such as windows and doors, were extracted using Autodesk® 3ds Max® Design software. Applying an optimizer developed at CMU, the team computed the most efficient path for a commercial quadrotor to survey desired features. Visualizing the resulting optimized drone path with Infrastructure Modeler enables quick identification of critical rescue locations.

Optimum flight path in a low-density town, visualized using Autodesk Infrastructure Modeler.

Rescue sequence visualized using Autodesk Infrastructure Modeler.

The traditional problem of finding an optimal flight path for a drone is formulated as a travelling salesman problem (TSP). The team observed that each picture can be taken from an infinite number of locations, allowing a wider range of flexibility when defining the drone path. The new formulation, based on the traveling salesman problem with neighborhoods (TSPN), broadens the drone target areas into neighborhoods as opposed to distinct, central points. The team developed a novel optimizer for this specific TSPN, shortening the flight path by 20-45 percent, depending on the city density.