Patent ID: 8082102

Claim:
A computer-based method for computing flight plans for unmanned aerial vehicles (UAVs) while rerouting around obstacles, the computer-based method comprising: receiving data representing a plurality of destinations to be visited by a UAV; receiving data representing a plurality of obstacles, wherein each of the plurality of obstacles are defined in at least three dimensions; calculating, using a processor, a trajectory for the UAV, wherein the trajectory comprises at least two of the plurality of destinations and the trajectory is specified in at least three dimensions; computing an initial flight plan for the UAV that incorporates at least the trajectory; calculating an initial cost associated with the initial flight plan; determining whether the trajectory intersects at least one of the plurality of obstacles; when the trajectory intersects at least one of the plurality of obstacles, computing an altered flight plan for the UAV, the altered flight plan incorporating an altered trajectory that avoids the at least one of the plurality of obstacles, calculating an altered cost associated with the altered flight plan, determining whether the altered cost exceeds a specified upper bound, altered cost exceeds the specified upper bound, computing a final flight plan for the UAV, the final flight plan incorporating a final trajectory that avoids the at least one of the plurality of obstacles, calculating a final cost associated with the final flight plan, the final cost being less than the altered cost, and selecting the final flight plan; and when the altered cost does not exceed the specified upper bound, selecting the altered flight plan; and when the trajectory does not intersect at least one of the plurality of obstacles, selecting the initial flight plan.