August 2-26, 2011
In the Autodesk IDEA Studio, researchers from Carnegie Mellon University explored using CAD models of cities to optimize the flight path of an autonomous drone for rescue missions.
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 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 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 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.
The traditional problem of finding an optimal flight path for a drone is formulated as a traveling 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.