Cooperative control of unmanned aerial vehicles for tracking targets

[0001] This application claims the benefit under 35 U.S.C. §119(e) of the priority of U.S. Provisional Application No. 61/195,669, filed Oct. 8, 2008, entitled “Cooperative Control of UAVs for Multiple Target Tracking in Urban Environments.”

[0002] This invention relates generally to target tracking and more particularly to cooperative control of multiple unmanned aerial vehicles (UAVs) for tracking targets.

[0003] Military forces may face a number of challenges in providing timely and accurate information (e.g., location information) regarding potential targets, particularly since potential targets may be in motion and/or may attempt to elude detection. One technique for providing target information includes the use of UAVs, which may allow target information to be obtained while reducing or eliminating the need to place military personnel in the line of fire and/or in other potentially dangerous or compromising positions.

[0004] According to embodiments of the present invention, disadvantages and problems associated with previous techniques for managing UAVs may be reduced or eliminated.

[0005] In certain embodiments, a method includes accessing first target information associated with a first target visible to a first UAV at a first time and accessing second target information, received from a neighboring UAV, associated with a second target visible to the neighboring UAV at the first time. The method further includes combining the first target information and the second target information to generate combined target information and determining, based on the combined target information, a predicted location for the first and second targets at a second time. The method further includes determining a planned route for the first UAV for the second time by solving an optimization problem, the optimization problem accounting for the determined predicted location for the first and second targets, kinematic constraints associated with the first UAV and the neighboring UAV, and line-of-sight constraints associated with the first UAV and the neighboring UAV.

[0006] Particular embodiments of the present invention may provide one or more technical advantages. In certain embodiments, the present invention may provide a method by which each of a number of UAVs deployed in an airspace located in or around an urban environment (or another environment in which the UAVs may encounter line-of-sight obstructions) may dynamically determine a planned route in order to track one or more targets located in the urban environment. In other words, the present invention may provide a method for autonomous control of a number of UAVs charged with tracking one or more targets in an urban environment, which may reduce or eliminate the need for personnel to control the UAVs. Thus, personnel may be permitted to focus on other tasks, such as analyzing target information gathered by the UAVs.

[0007] Furthermore, each UAV may determine its associated planned route by solving an optimization problem that accounts for predicted locations of one or more targets in the urban environment (i.e., those targets located either in the line-of-sight of a UAV or the line or sight of a neighboring UAV), line-of-sight constraints of the UAVs (e.g., dues to structure in the urban environment), and kinematic constraints of the UAVs. As a result, the planned routes determined by each individual UAV may allow the number of UAVs to collectively gather information in a manner that minimizes location errors associated with targets located in the urban environment.

[0008] Certain embodiments of the present invention may include some, all, or none of the above advantages. One or more other technical advantages may be readily apparent to those skilled in the art from the figures, descriptions, and claims included herein.

[0013] FIGS. 1A-1B illustrate an example system 100 for providing cooperative control of UAVs 102 for tracking targets 104, according to certain embodiments of the present invention. System 100 may include a number of UAVs 102 deployed in an airspace in or around an urban environment having one or more targets 104 (e.g., ground vehicles). Each UAV 102 may include a target sensing unit 106, an antenna 108, and a flight control system 110. Although this particular implementation of system 100 is illustrated and primarily described, the present invention contemplates any suitable implementation of system 100, according to particular needs.

[0014] In general, system 100 is operable to generate target information associated with one or more targets 104 (e.g., ground vehicles) in a particular environment. Each UAV 102 of system 100 may be operable to collect target information associated with one or more targets 104 located within a line-of-sight 112 of the UAV 102 or otherwise detectable to the UAV 102. In certain applications, UAVs 102 may be deployed in an airspace located in or around an environment having one or more objects that may obstruct the line-of-sight of certain UAVs 102. For example, UAVs 102 may be deployed in an airspace located in or around an urban environment having one or more structures 114 (e.g., building) that may obstruct the line-of-sight of certain UAVs 102. As an additional example UAVs 102 may be deployed in an airspace located in or around a rural environment having earth formations (e.g., mountains) that may obstruct the line-of-sight of certain UAVs 102. Because UAVs 102 may be operable to determine planned routes (i.e., flight paths) in a manner that accounts for line-of-sight obstructions (as described below), UAVs 102 may collectively generate target information associated with one or more targets 104 located in a particular environment in a manner that accounts for line-of-sight obstruction of the particular environment.

[0015] Although UAVs 102 are depicted and primarily described as being deployed in an airspace located in or around an environment having one or more objects that may obstruct the line-of-sight of certain UAVs 102, the present invention contemplates UAVs 102 being deployed in an airspace located in or around any suitable environment, according to particular needs.

[0016] One or more UAVs 102 may communicate the collected target information to a target tracking system 116, which may analyze the collected target information and/or generate target tracking information. Furthermore, because each UAV 102 may be able to sense only certain targets 104 (e.g., due to one or more line-of-sight constraints), each UAV 102 may be operable to share sensed target information with neighboring UAVs 102 (i.e., UAVs 102 located within a particular range of communication).

[0017] Each UAV 102 may be operable to combine received target information with sensed target information to create combined target information. The combined target information may provide an extended view of the urban environment from the perspective of a particular UAV 102. Each UAV 102 may be further operable to determine predicted locations associated with those targets 104 located within the extended view of the urban environment based on the combined target information. Each UAV 102 may determine a planned route by solving an optimization problem that accounts for the determined predicted locations of the targets 104, line-of-sight constraints associated with the UAV 102, and kinematic constraints associated with the UAV 102.

[0018] In other words, UAVs 102 may each be operable to dynamically determine planned routes in a manner that accounts for predicted locations of known targets 104, line-of-sight constraints, and kinematic constraints. As a result, UAVs 102 of system 100 may, collectively, generate target information associated with targets 104 in an urban environment in a manner that reduces or eliminates the need for personnel to control UAVs 102. Furthermore, because each UAV 102 may act cooperatively with neighboring UAVs 102 in determining a planned route based on an optimization problem that accounts for line-of-sight constraints and kinematic constraints of UAVs 102, the determined planned routes may result in the collection of target information in a manner that minimizes location errors associated with targets 104.

[0019] UAVs 102 of system 100 may comprise any suitable reusable, uncrewed aircraft capable of being configured with a target sensing unit 106, an antenna 108, and a flight control system 110, each of which is described detail below. As just one example, UAVs 102 may comprise a KillerBee® Unmanned Aircraft System (UAS) manufactured by RAYTHEON COMPANY of Waltham, Mass.

[0020] Although system 100 is depicted and primarily described as including a particular number of UAVs 102, the present invention contemplates system 100 including any suitable number of UAVs 102, according to particular needs. Furthermore, although the present invention is depicted and primarily described as including unmanned aerial vehicles (i.e, UAVs 102), the present invention contemplates system 100 including unmanned ground vehicles, unmanned underwater vehicles, or any other suitable unmanned vehicles, according to particular needs. It should be noted that the present invention contemplates one or more UAVs 102 carrying one or more persons, if appropriate.

[0021] Each UAV 102 of system 100 may include a target sensing unit 106, an antenna 108, a flight control system 110, and any other suitable components. Although the present invention contemplates each UAV 102 of system 100 including each of target sensing unit 106, antenna 108, and flight control system 110, for purposes of simplicity only target sensing unit 106a, antenna 108a, and a flight control system 110a of UAV 102a (depicted in FIG. 1B) are described in detail below. It is understood that the target sensing units 106, antennas 108, and flight control systems 110 of additional UAVs 102 of system 100 may operate in a substantially similar manner as described below with regard to target sensing unit 106a, antenna 108a, and a flight control system 110a of UAV 102a. Components of UAV 102a may be implemented in any suitable combination of firmware, hardware, and software.

[0022] Target sensing unit 106a of a UAV 102a may include any suitable device operable to generate target information associated with one or more targets 104 located within an associated line-of-sight 112a of radar unit 102a (or otherwise detectable to radar unit 102a). For example, target sensing unit 106a may be an omni-directional radar unit operable to generate target information associated with one or more targets 104 located within an associated line-of-sight 112a encompassing a generally conical-shaped volume extending outwardly from target sensing unit 112a.

[0023] Target sensing unit 106a may be located at any suitable location on UAV 102a and may be oriented in any suitable manner with respect UAV 102a, according to particular needs. For example, in embodiments in which target sensing unit 106a is an omni-direction radar unit, target sensing unit 106a may be located on the underside of UAV 102a and oriented with respect to UAV 102a such that the associated line-of-sight 112a encompasses a generally conical-shape including at least a portion of the surface area within the urban environment in or around which UAV 102a is deployed.

[0024] Target sensing unit 106a may be operable to generate target information associated with one or more targets 104 located within the associated line-of-sight 112a at a particular time (or over a particular range of time). Target information associated with a particular target 104 may include a location of the particular target 104, a velocity of the particular target 104, a heading of the particular target 104, or any other suitable information according to particular needs.

[0025] Target sensing unit 106a may be operable to communicate generated target information to one or more neighboring UAVs 102 (e.g., UAV 102b and UAV 102c) via antenna 108a, as described in further detail below. The generated target information may be communicated to one or more neighboring UAVs 102 as discrete units of data at predetermined time intervals (e.g., corresponding to periods of time over which target sensing unit 106a generates target information), as a continuous stream of data, or in any other suitable manner. Additionally, target sensing unit 106a may be operable to communicate generated target information to target tracking system 116. The generated target information may be communicated to target sensing unit 106a as discrete units of data at predetermined time intervals (e.g., corresponding to periods of time over which target sensing unit 106a generates target information), as a continuous stream of data, or in any other suitable manner. Target sensing unit 106a may communicate generated target information to target tracking system 116 via one or more satellite communication links, a network for facilitating wireless communications, or in any other suitable manner, according to particular needs. For example, target sensing unit 106a may communicate generated target information to target tracking system 116 via a network operable to communicate IP packets, Frame Relay frames, Asynchronous Transfer Mode (ATM) cells, voice, video, data, and other suitable information between network addresses.

[0026] Target tracking system 116 may be operable to receive and/or store the communicated target information. The target information received from each UAV 102 of system 100 may be combined, used to generate target tracks associated with targets 104, or otherwise processed to generate actionable intelligence.

[0027] Target tracking system 116 may include one or more computer systems at one or more locations. Each computer system may include any appropriate input devices (such as a keypad, touch screen, mouse, or other device that can accept information), output devices, mass storage media, or other suitable components for receiving, processing, storing, and communicating data. Both the input devices and output devices may include fixed or removable storage media such as a magnetic computer disk, CD-ROM, or other suitable media operable to both receive input from and provide output to a user of user system 102. Each computer system may include a personal computer, workstation, network computer, kiosk, wireless data port, personal data assistant (PDA), one or more processors within these or other devices, or any other suitable processing device. Additionally, target tracking system 116 may include any suitable combination of software, firmware, and hardware.

[0028] Antenna 108 of a UAV 102 (e.g., antenna 108a of UAV 102a) may include any suitable device operable to communicate target information generated by target sensing unit 106a to neighboring UAVs 102 (e.g., UAV 102b and UAV 102c) and/or receive target information generated by target sensing units 106 of neighboring UAVs 102 (e.g., UAV 102b and UAV 102c). For example, antenna 108 may be an antenna configured to send/receive radio frequency (RF) communications.

[0029] Antenna 108a may have an associated maximum communication range 118a. In other words, UAV 102a may not be able to communicate generated target information via antenna 108a to UAVs 102 located at a distance greater than the maximum communication range 118a of antenna 108a. Similarly, assuming all UAVs of system 100 have antennas 108 with associated maximum ranges that are substantially the same (which may not be the case in certain embodiments), the maximum communication range 118a of antenna 108a may also correspond to the range from beyond which UAV 102a cannot receive target information communicated by other UAVs 102.

[0030] For example, because UAVs 102b and 102c lie within the maximum communication range 118a of UAV 102a, UAV 102a may receive target information transmitted by UAVs 102b and 102c (i.e., UAVs 102b and 102c are neighboring UAVs of UAV 102a). Furthermore, because UAV 102d lies outside the maximum communication range 118a of UAV 102a, UAV 102a may not receive target information transmitted by UAV 102d (i.e., UAV 102d is not a neighboring UAV of UAV 102a). In other words, each UAV 102 of system 100 may have a different set of neighboring UAVs 102 which depends on the distance of each UAV 102 from other UAVs 102 in system 100.

[0031] Flight control system 110a of 102a may include one or more electronic computing devices operable to receive, transmit, process, and/or store information, such as target information collected by target sensing unit 106a and/or received from neighboring UAVs 102b and 102c. Flight control system 110a may be implemented using any suitable combination of software, firmware, and hardware. Flight control system 110a may include one or more processing modules (i.e., processing module 120a) and one or more memory modules (i.e., memory module 122a). A processing module as described herein may include one or more microprocessors, controllers, or any other suitable computing devices or resources and may work, either alone or with other components of system 100, to provide a portion or all of the functionality of system 100 described herein. A memory module as described herein may take the form of volatile or non-volatile memory including, with out limitation, magnetic media, optical media, random access memory (RAM), read-only memory (ROM), removable media, or any other suitable memory component.

[0032] In certain embodiments, flight control system 110a includes a route determination application 124a. Route determination application 124a may be implemented using any suitable combination of hardware, firmware, and software. In general, route determination application 124a may be operable to dynamically determine planned routes (i.e., flight paths) for UAV 102 such that UAV 102a may navigate in the absence of control from a human operator, as described in further detail below.

[0033] Route determination application 124a may be operable to receive or otherwise access target information generated by target sensing unit 106a at a first time. The target information received from target sensing unit 106a may correspond to targets located within the line-of-sight 112a of target sensing unit 106a (or otherwise visible to target sensing unit 106a) at the first time. The present invention contemplates that the first time may correspond to any suitable time interval, according to particular needs. Accordingly, it is understood that references to time as used in this description may correspond to any appropriate time interval.

[0034] Route determination application 124a may be operable to receive or otherwise access target information from neighboring UAVs 102b and 102c (e.g., via antenna 108a), the target information having been generated by target sensing units 106b and 106c at the first time and communicated to UAV 102a via antennas 108b and 108c. The target information received from neighboring UAV 102b may correspond to targets 104 located within the line-of-sight 112b of target sensing unit 106b (or otherwise visible to target sensing unit 106b) at the first time and the target information received from neighboring UAV 102c may correspond to targets 104 located within the line-of-sight 112c of target sensing unit 106c (or otherwise visible to target sensing unit 106c) at the first time.

[0035] Additionally, route determination application 124a may be operable to receive or otherwise access information associated with neighboring UAVs 102b and 102c at the first time. For example, with regard to UAV 102b, route determination application 124a may receive a location of UAV 102b, a heading of UAV 102b, and a velocity of UAV 102b. Similarly, with regard to UAV 102c, route determination application 124a may receive a location of UAV 102c, a heading of UAV 102c, and a velocity of UAV 102c.

[0036] Route determination application 124a may be operable to combine the target information received from target sensing unit 106a with the target information received from neighboring UAVs 102b and 102c to generate combined target information. The generated combined target information may include target information for targets 104 located in the line-of-sight of one or more of UAV 102a, UAV 102b, and UAV 102c at the first time. In other words, the combined target information may represent a fused picture corresponding to the portions of the urban environment located within a field of view 112 of one or more of UAV 102a, UAV 102b, and UAV 102c.

[0037] In certain embodiments, route determination application 124a may determine a score associated with the combined target information. Route determination application 124a may determine the score associated with the combined target information in any suitable qualitative manner. For example, route determination application 124a may determine a score associated with the combined target information by determining an inverse of a covariance matrix associated with each target 104 of the combined target information (i.e., the determined score may comprise the inverse of the covariance matrix associated with each target 104 of the combined target information).

[0038] If the determined score associated with the combined target information is less than a pre-determined threshold score, route determination application 124a may determine a predicted location for each of the targets 104 of the combined target information (as described below). For example, if a determined inverse of a covariance matrix associated with a target 104 of the combined target information is less than a predetermined threshold value, route determination application 124a may determine a predicted location for each of the targets 104 of the combined target information. Additionally or alternatively, if the amount of time that has passed since route determination application 124a last determined a planned route for UAV 102a (as described below) is greater than a pre-determined amount of time, route determination application 124a may determine a predicted location for each of the targets 104 of the combined target information (as described below).

[0039] If the determined score associated with the combined target information is greater than the pre-determined threshold score and the elapsed time since the last planned route determination is less than the pre-determined amount of time, the combined target information corresponding to the first time may be discarded (i.e., route determination application 124a may not determine a predicted location for each of the targets 104 of the combined target information).

[0040] Route determination application 124a, using the generated combined target information corresponding to target information generated at a first time, may be operable determine a predicted location for each target 104 of the combined target information at a second time. In other words, route determination application 124a may be operable to propagate forward (from a first time to a second time) a location for each of the targets 104 located in the line-of-sight 112 associated with one or more of UAV 102a, UAV 102b, and UAV 102c.

[0041] As a particular example, the determined predicted location for the target 104 at the second time may correspond to a location relative to the sensed location (i.e., the location included in the combined target information) that is at a distance corresponding to the velocity of the target 104 (as determined from the combined target information) multiplied by the time between the first time and the second time and in a direction corresponding to the heading of the target 104 (as determined from the combined target information).

[0042] Route determination application 124a may determine a planned route for UAV 102a for the second time by solving an optimization problem. The optimization problem (an example of which is described below) may be solved using any suitable procedure, according to particular needs. In certain embodiments, the optimization problem may be solved using a continuous Greedy Randomized Adaptive Search Procedure (GRASP), described in further detail below with regard to FIG. 3.

[0043] In certain embodiments, the optimization problem accounts for the location information of UAV 102a (e.g., location, heading, and velocity of UAV 102a), the location information of neighboring UAVs 102b and 102c (e.g., location, heading, and velocity of UAV 102b and 102c), and the predicted locations of targets 104 of the combined target information. Additionally, the optimization problem may account for a number of constraints. The constraints may include line-of-sight constraints associated with UAV 102a and/or line-of-sight constraints associated with neighboring UAVs 102b and 102c. A line-of-sight constraint for a UAV 102 may define one or more areas that would be within a line-of-sight of a target sensing unit 106 of the UAV 102 but for an obstruction (e.g., structures 114). The constraints may also include kinematic constraints of UAVs 102a, 102b, and 102c. A kinematic constraint of a UAV 102 may include any physical limitation related to the flight characteristics of the UAV 102, such as a maximum velocity of the UAV 102, a minimum velocity of the UAV 102, and a minimum turning radius of the UAV 102.

[0044] Although the optimization problem solved by route determination application 124a in determining a planned route for UAV 102a at a second time is primarily described as accounting for particular information and constraints, the present invention contemplates the optimization problem accounting for any suitable information and/or constraints, according to particular needs.

[0045] In certain embodiments, route determination application 124a may solve an optimization problem by minimizing a sum of determinants of covariances for each of the targets 104 of the combined target information over a time interval from the first time to the second time. By solving the optimization problem in this manner, route determination application 124a may determine optimal planned routes for UAVs 102a, 102b, and 102c for the second time, the optimal planned routes being routes that place UAVs 102a, 102b, and 102c in the best possible position (e.g., taking into account line-of-sight and kinematic constraints) at the second time to generate target information for the targets 104 (i.e., those targets 104 of the combined target information for the first time).

[0046] In certain embodiments, route determination application 124a may solve an optimization problem by minimizing a weighted sum of determinants of covariances for each of the targets 104 of the combined target information over a time interval from the first time to the second time, the sum of determinants of covariances being weighted with an importance function. The importance function may define one or more regions of interest 126 for which accurate target information is of increased importance. In other words, the importance function may weight the minimization in a manner that results in planned route determinations that place an increased importance on obtained accurate target information for target 104 in particular areas of interest 126.

[0047] Route determination application 124a, based on the determined planned route for UAV 102a by solving the optimization problem, may implement the determined planned route for UAV 102a (i.e., route determination application may cause UAV 102a to follow the determined planned route at the second time). Although planned routes may be determined for neighboring UAVs 102b and 102c by solving the optimization problem (as described above), the planned routed determined for UAVs 102b and 102c may not be implemented. Route determination applications 124b and 124c of UAVs 102b and 102c, respectively, may determine a more optimal planned route for UAVs 102b and 102c, and UAVs 102b and 102c may implement these more optimal determined planned routes.

[0048] For example, route determination application 124b of UAV 102b may determine a planned route for UAV 102b by solving an optimization problem that accounts for information not available to UAV 102a (e.g., target information generated by UAV 102d); thus, the planned route for UAV 102b determined by route determination application 124b may be more optimal than the planned route for UAV 102b determined by route determination application 124a of UAV 102a. In other words, a particular UAV 102 may determine a planned route for itself and a planned route for each of its neighboring UAVs 102, but in certain embodiments the particular UAV 102 may only implement the planned route determined for itself.

[0049] An example optimization problem that may be solved by a route determination application 124 of a particular UAV 102 (e.g., route determination application 124a of UAV 102a) to determine planned routes for the particular UAV 102 any neighboring UAVs 102 is described in further detail below. The optimization problem described below is provided for example purposes only and the present invention contemplates any suitable optimization problem, according to particular needs. Furthermore, although the example optimization problem is described as accounting for particular parameters, decision variables, and constraints, the present invention contemplates the optimization problem accounting for any suitable parameters, decision variables, and constraints, according to particular needs.

[0050] The example optimization problem assumes that system 100 includes N homogeneous UAVs 102 flying at a fixed altitude. The UAVs 102 are modeled as non-holonomic point masses on a two-dimensional plane (i.e., a Dubin's vehicle) having a number of kinematic constraints (e.g., a minimum turning radius, a minimum velocity, and a maximum velocity). Additionally, the UAVs 102 are modeled as having a maximum communication range 118 (e.g., associated with an antenna 108, as described above), beyond which information (e.g., target information and location information) cannot be shared.

[0051] The parameters, decision variables, and constraints defined below may be defined for all{circumflex over (1)}εN_i(t), tε[t_c, t_c+Δ_t], lε{1, . . . , 5}, hε{1, . . . H}, jε{1, . . . , J}, uε{1, . . . , 4} as appropriate.

I. Parameters

[0052] The optimization problem may include the following parameters:

• • [0053] t_c=the current time;
  • [0054] Δ_t=the current planning horizon;
  • [0055] C_d=the maximum distance at which any two UAVs may share information (i.e., the maximum distance at which two UAVs may be considered neighbors);
  • [0056] N_i(t)=The neighbors of UAV {circumflex over (1)}, at time t
  • [0057] (i.e., {circumflex over (1)}εN_i(t)∥P_i(t)−P_{{circumflex over (1)}}(t)∥₂≦C_d. N.B.: iεN_i(t));
  • [0058] The UAVs of interest (from UAV {circumflex over (1)}'s perspective) are indexed by {circumflex over (1)}εN_i(t);
  • [0059] The moving ground targets are indexed by jε{1, . . . , J}
  • [0060] The buildings (3D, rectangular, opaque obstacles) are indexed by hε{1, . . . H};
  • [0061] Ω_{{circumflex over (1)}}=The minimum turning radius of UAV {circumflex over (1)};
  • [0062] P_{{circumflex over (1)}}^c=The current position of UAV {circumflex over (1)} (N.B.: P_{{circumflex over (1)}}^c={x_{{circumflex over (1)}}^c, y_{{circumflex over (1)}}^c, z_{{circumflex over (1)}}^c})
  • [0063] S_{{circumflex over (1)}}^min=The minimum speed of UAV {circumflex over (1)};
  • [0064] S_{{circumflex over (1)}}^max=The maximum speed of UAV {circumflex over (1)};
  • [0065] ε₁^min=The minimum distance allowed between any two UAVs (to avoid UAV collisions);
  • [0066] ε₂^min=The minimum distance allowed between any UAV and any known building (assume ε₂^min=0 so that UAVs are constrained to not be within a building, but they can get infinitesimally close to the perimeter of each building);
  • [0067] Z_{{circumflex over (1)}}=The fixed altitude of UAV {circumflex over (1)};
  • [0068] B_h={P_hl}_l=1⁵=The representation of building h, as a set of 5 rectangular regions (i.e., faces) in R³, all oriented in the same counter-clockwise fashion;
  • [0069] P_hl={ρ_hl1, . . . , ρ_hl4}=The l-th oriented rectangle (i.e., face) of building h;
  • [0070] ρ_hlu={ x_hlu, y_hlu, z_hlu}=The u-th point of the l-th oriented rectangle (i.e., face) of building h;
  • [0071] ξ_hl={v_hl; d_hi}=The plane containing face P_hl, represented as a normal vector n_hl and distance to the origin d_hl(v_hl=[=ρ_hl3−ρ_hl2]×[ρ_hl1−ρ_hl2], d_hl=v_hl·ρ_hl1);
  • [0072] γ(x,y)=A function representing the ‘importance’ level of position (x,y) (the higher this value, the more important it is to provide accurate track of targets near (x,y));
  • [0073] Λ_{{circumflex over (1)}j}(t)=The Plüker coordinate representation of the oriented line from the position of UAV {circumflex over (1)} at time t, P_{{circumflex over (1)}}(t), to the estimated position of target j, at time t, X_jⁱ(t);
  • [0074] {circumflex over (Λ)}_hlu,u+1=The Plüker coordinate representation of the oriented line from ρ_hl2, to ρ_hl,u+1, with u+1≡1 when u=4;
  • [0075] G(α, {circumflex over (α)})=α₁{circumflex over (α)}₆+α₂{circumflex over (α)}₅+α₃{circumflex over (α)}₄+α₄{circumflex over (α)}₃−α₅{circumflex over (α)}₂+α₆{circumflex over (α)}₁ where α={α₁, . . . , α₆} and {circumflex over (α)}={{circumflex over (α)}₁, . . . , {circumflex over (α)}₆} are the Plüker coordinate representations of two oriented lines;
  • [0076] R_{{circumflex over (1)}}(t)=The measurement noise for the sensor on board UAV {circumflex over (1)}, at time t

[0077] $(N.B.\text{:}{R}_{\hat{i}}\left(t\right)=\left(\begin{array}{cc}{\sigma }_{r\hat{i}}& 0\\ 0& {\sigma }_{b\hat{i}}\end{array}\right),$
where σ_{r{circumflex over (1)}}=the range measurement error for the radar platform on UAV {circumflex over (1)} and σ_{b{circumflex over (1)}}=the bearing measurement error for the radar platform on UAV {circumflex over (1)});

• • [0078] F_{{circumflex over (1)}}(t)=The system dynamics matrix for the sensor on board UAV {circumflex over (1)}, at time t;
  • [0079] Q_{{circumflex over (1)}}(t)=The process noise for the sensor on board UAV {circumflex over (1)}, at time t;
  • [0080] H_{{circumflex over (1)}}(t)=The observation matrix for the sensor on board UAV {circumflex over (1)}, at time t; and
  • [0081] M=A large enough constant (needed for constraints 7, 14, 15, and 18, described in further detail below).
    II. Decision Variables

[0082] The optimization problem may include the following decision variables:

• • [0083] P_{{circumflex over (1)}}(t)=The position of UAV {circumflex over (1)} at time t (N.B.: P_{{circumflex over (1)}}(t)={x_{{circumflex over (1)}}(t), y_{{circumflex over (1)}}(t), z_{{circumflex over (1)}}});
  • [0084] S_{{circumflex over (1)}}(t)=The speed of UAV {circumflex over (1)} at time t;
  • [0085] θ_{{circumflex over (1)}}(t)=The heading of UAV {circumflex over (1)} at time t;
  • [0086] {X_{{circumflex over (1)}j}(t), Σ_{{circumflex over (1)}j}(t)}=The estimated position and covariance of target j by UAV {circumflex over (1)} at time t;
  • [0087] {X_j^{{circumflex over (1)}}(t),Σ_j^{{circumflex over (1)}}(t)}=The fused position and covariance of target j, from UAV {circumflex over (1)}'s perspective at time t;

[0088] ${\varphi }_{\hat{i}\mathrm{jhl},u+1}\left(t\right)=\{\begin{array}{cc}1& \begin{array}{c}\mathrm{if}\mathrm{line}\mathrm{segment}{\Lambda }_{\hat{i}j}\left(t\right)\mathrm{is}\mathrm{oriented}\mathrm{counterclockwise}\\ \mathrm{with}\mathrm{respect}\mathrm{to}\mathrm{line}\mathrm{segment}{\hat{\Delta }}_{\mathrm{hlu},u+1}\mathrm{at}\mathrm{time}t\end{array}\\ 0& o.w\end{array};$

• • [0089] φ_{{circumflex over (1)}jhl}(t)=The number of line segments representing the l-th face of building h that line segment Λ_{{circumflex over (1)}j}(t) is oriented counterclockwise with respect to, at time t;

[0090] ${\beta }_{\hat{1}\mathrm{jhl}}\left(t\right)=\{\begin{array}{cc}1& \begin{array}{c}\mathrm{if}\mathrm{line}\mathrm{segment}{\Lambda }_{\hat{1}j}\left(t\right)\mathrm{does}\mathrm{not}\mathrm{intersect}\mathrm{the}1\text{-}\mathrm{th}\\ \mathrm{face}\mathrm{of}\mathrm{building}h,\mathrm{at}\mathrm{time}t\end{array}\\ 0& o.w.\end{array};$

• • [0091] β_{{circumflex over (1)}jhl}(t)=The number of faces representing building h that line segment Λ_{{circumflex over (1)}j}(t) does not intersect, at time t;

[0092] ${\psi }_{\hat{1}\mathrm{jh}}\left(t\right)=\{\begin{array}{cc}1& \begin{array}{c}\mathrm{if}\mathrm{there}\mathrm{is}\mathrm{line}\mathrm{of}\mathrm{sight}\mathrm{from}\mathrm{UAV}\hat{1}\mathrm{to}\mathrm{target}\\ j\mathrm{with}\mathrm{respect}\mathrm{to}\mathrm{building}h,\mathrm{at}\mathrm{time}t\end{array}\\ 0& o.w.\end{array};$

• • [0093] {circumflex over (ψ)}_{{circumflex over (1)}j}(t)=The number of buildings that do not restrict line-of-sight from UAV {circumflex over (1)} to target j, at time t; and

[0094] ${\psi }_{\hat{1}j}\left(t\right)=\{\begin{array}{cc}1& \mathrm{if}\mathrm{UAV}\hat{1}\mathrm{has}\mathrm{line}\mathrm{of}\mathrm{sight}\mathrm{to}\mathrm{target}j,\mathrm{at}\mathrm{time}t\\ 0& o.w.\end{array}.$
III. Constraints

[0095] The following is a list of constraints levied on the above-described decision variables for the example optimization problem:

[0096] Constraint 1 prescribe initial positions for each of the UAVs in N_i(t).
P_{{circumflex over (1)}}(t_c)=P_{{circumflex over (1)}}^c∀{circumflex over (1)}  Constraint 1

[0097] Constraints 2-3 define the motion of UAV {circumflex over (1)}, as a function of the speed and heading of the UAV.

[0098] $\begin{array}{cc}\frac{\partial x_{\hat{1}}\left(t\right)}{\partial t}=S_{\hat{1}}\left(t\right)\cos \left[{\theta }_{\hat{1}}\left(t\right)\right]\forall \hat{1},t& \mathrm{Constraint}2\end{array}$

[0099] $\begin{array}{cc}\frac{\partial y_{\hat{1}\left(t\right)}}{\partial t}=S_{\hat{1}}\left(t\right)\sin \left[{\theta }_{\hat{1}}\left(t\right)\right]\forall \hat{1},t& \mathrm{Constraint}3\end{array}$

[0100] Constraint 4 restricts the instantaneous change in heading of UAV {circumflex over (1)} to be less than Ω_{{circumflex over (1)}} (i.e., modeling the UAVs as Dubin's vehicles);

[0101] $\begin{array}{cc}\frac{\partial {\theta }_{\hat{1}\left(t\right)}}{\partial t}\le {\Omega }_{\hat{1}}\forall \hat{1},t& \mathrm{Constraint}4\end{array}$

[0102] Constraint 5 defines a minimum and maximum velocity associated with UAV {circumflex over (1)}.
S_{{circumflex over (1)}}^min≦S_{{circumflex over (1)}}(t)≦S_{{circumflex over (1)}}^max∀{circumflex over (1)},t  Constraint 5

[0103] Constraint 6 enforces that no two UAVs are allowed to be closer than ε₁^min.
∥P_{{circumflex over (1)}1}(t)−P_{{circumflex over (1)}2}(t)∥₂ε₁^min∀_{{circumflex over (1)}1},_{{circumflex over (1)}2},t  Constraint 6

[0104] Constraints 7-8 prescribe that no UAV trajectory can intersect with the boundary of any building.
P_{{circumflex over (1)}}(t)·v_hl+d_hl≧−u_{{circumflex over (1)}hl}(t)M∀{circumflex over (1)},h,l,t  Constraint 7

[0105] $\begin{array}{cc}\sum _{l=1}^5{\mu }_{\hat{1}\mathrm{hl}}\left(t\right)\le 4\forall \hat{1},h,l,t& \mathrm{Constraint}8\end{array}$

[0106] Constraints 9-10 determine the fused covariance and state for target j at time t from UAV {circumflex over (1)}'s perspective based on those neighbors of UAV {circumflex over (1)} that have line-of-sight to target j.

[0107] $\begin{array}{cc}\sum _j^i\left(t\right)=={\left[\sum _{\hat{1}\in \mathrm{Nj}\left(t\right)}{\psi }_{\hat{1}j}\left(t\right)\sum _{\hat{1}j}^1\left(t\right)\right]}^{-1}\forall j,t& \mathrm{Constraint}9\end{array}$

[0108] $\begin{array}{cc}{X}_j^i\left(t\right)=\sum _j^i\left(t\right)·\left[\sum _{\hat{1}\in N_j\left(t\right)}{{\psi }_{\hat{1}}}_j\left(t\right)\sum _{\hat{1}j}^{-1}\left(t\right)X_{\hat{1}j}\left(t\right)\right]\forall j,t& \mathrm{Constraint}10\end{array}$

[0109] Constraints 11-13 are continuous time Kalman filter (Kalman-Bucy filter) equations for the state of target j, as seen from UAV {circumflex over (1)}, where z_{{circumflex over (1)}j}(t) represents the measurement of target j by UAV {circumflex over (1)}, at time t.

[0110] $\begin{array}{cc}\frac{\partial X_{\hat{1}j}\left(t\right)}{\partial t}=F_{\hat{1}}\left(t\right)X_{\hat{1}j}\left(t\right)+K_{\hat{1}}\left(t\right)\left[{\stackrel{\_}{z}}_{\hat{1}j}\left(t\right)-H_{\hat{1}}\left(t\right)X_{\hat{1}j}\left(t\right)\right]\forall \hat{1},j,t& \mathrm{Constrain}t11\end{array}$

[0111] $\begin{array}{cc}\frac{\partial \sum _{\hat{1}j}\left(t\right)}{\partial t}=F_{\hat{1}}\left(t\right)\sum _{\hat{1}j}\left(t\right)+\sum _{\hat{1}j}\left(T\right)F_{\hat{1}}^T\left(t\right)+{\stackrel{\_}{Q}}_{\hat{1}}\left(t\right)-K_{\hat{1}}\left(t\right)R_{\hat{1}}\left(t\right)K_{\hat{1}}^T\left(t\right)\forall \hat{1},j,t& \mathrm{Constraint}12\end{array}$
K_{{circumflex over (1)}}(t)=Σ_{{circumflex over (1)}j}(t)H_{{circumflex over (1)}}^T(t)R_{{circumflex over (1)}}⁻¹(t)∀{circumflex over (1)},j,t  Constraint 13

[0112] Constraints 14-15 force φ_{{circumflex over (1)}hlu,u+1}(t) to be 1 when line segment Λ_{{circumflex over (1)}j}(t) is oriented counterclockwise with respect to the line segment {circumflex over (Λ)}_hlu,u+1(t), at time t, and to be zero otherwise.
G(Λ_{{circumflex over (1)}j}(t),{circumflex over (Λ)}_hlu,u+1)≦ φ_{{circumflex over (1)},jhlu,u+1}(t)M∀{circumflex over (1)},j,h,l,u,t  Constraint 14
−G(Λ_{{circumflex over (1)}f}(t),{circumflex over (Λ)}_hlu,u+1)<(1− φ_jhlu,u+1(t))M∀{circumflex over (1)},j,h,l,u,t  Constraint 15

[0113] Constraint 16 counts the number of line segments representing the l-th face of building h that line segment Λ_{{circumflex over (1)}j}(t) is oriented counterclockwise with respect to at time t.

[0114] $\begin{array}{cc}{\stackrel{\_}{\varphi }}_{\hat{1}\mathrm{jhl}}\left(t\right)=\sum _{u=1}^4{\stackrel{\_}{\varphi }}_{\hat{1}\mathrm{jhlu},u+1}\left(t\right)\forall \hat{1},j,h,l,t& \mathrm{Constraint}16\end{array}$

[0115] Constraints 17-18 force β_{{circumflex over (1)}jhl}(t) to be 1 when line segment Λ_{{circumflex over (1)}j}(t) does not intersect the l-th face of building h, at time t, and to be zero otherwise.
β_{{circumflex over (1)},jhl}(t)M≧4− φ_{{circumflex over (1)},jhl}(t)∀{circumflex over (1)},j,h,l,t  Constraint 17
β_{{circumflex over (1)},jhl}(t)M≧4− φ_{{circumflex over (1)},jhl}(t)∀{circumflex over (1)},j,h,l,t  Constraint 18

[0116] Constraint 19 counts the number of faces of building h that do not inhibit line-of-sight from UAV {circumflex over (1)} to target j, at time t.

[0117] $\begin{array}{cc}{\beta }_{\hat{1}\mathrm{jhl}}\left(t\right)=\sum _{l=1}^5{\beta }_{\hat{1}\mathrm{jhl}}\left(t\right)\forall \hat{1},j,h,t& \mathrm{Constraint}19\end{array}$

[0118] Constraints 20-21 force ψ_{{circumflex over (1)}jh}(t) to be 1 when there is line-of-sight from UAV {circumflex over (1)} to target j, at time t, with respect to building h, and to be zero otherwise.
ψ_{{circumflex over (1)}jh}(t)≦β_{{circumflex over (1)}jhl}(t)∀{circumflex over (1)},j,h,t  Constraint 20
1−ψ_{{circumflex over (1)}jh}(t)≦5− β_{{circumflex over (1)}jh}(t)∀{circumflex over (1)},j,h,t  Constraint 21

[0119] Constraint 22 count the number of buildings that do not inhibit line-of-sight from UAV {circumflex over (1)} to target j, at time t.

[0120] $\begin{array}{cc}{\hat{\psi }}_{\hat{1}j}\left(t\right)=\sum _{h=1}^H{\stackrel{\_}{\psi }}_{\hat{1}\mathrm{jh}}\left(t\right)\forall \hat{1},j,t& \mathrm{Constraint}22\end{array}$

[0121] Constraints 23-24 force ψ_{{circumflex over (1)}j}(t) to be 1 when UAV {circumflex over (1)} has line-of-sight to target j, at time t, and to be zero otherwise.
ψ_{{circumflex over (1)}j}(t)≦ ψ_{{circumflex over (1)}jh}(t)∀{circumflex over (1)},j,t  Constraint 23
1−ψ_{{circumflex over (1)}j}(t)≦H−{circumflex over (ψ)}_{{circumflex over (1)}j}(t)∀{circumflex over (1)},j,t  Constraint 24

[0122] Constraints 25-29 prescribe domain restrictions on all of the decision variables, described above.
P_{{circumflex over (1)}}(t)εR³∀{circumflex over (1)},t  Constraint 25
S_{{circumflex over (1)}}(t)εR₊∀{circumflex over (1)},t  Constraint 26
θ_{{circumflex over (1)}}(t)ε[−π,π]∀{circumflex over (1)},t  Constraint 27
φ_{{circumflex over (1)},jhl}(t),ψ_{{circumflex over (1)}j}(t),β_{{circumflex over (1)}jh}(t)εZ⁺∀{circumflex over (1)},j,h,l,t  Constraint 28
φ_jhlu,u+1(t),ψ_{{circumflex over (1)}j}(t),β_{{circumflex over (1)}jhl}(t),μ_hl(t), ψ_{{circumflex over (1)}jh}(t)ε{0,1}∀{circumflex over (1)}, j,h,l,u,t  Constraint 29
III. Objective Function (For UAV {circumflex over (1)})

[0123] An objective function, F (as defined in Equation 1 below) may minimize the weighted sum of the determinants of the fused covariances for the targets 104 that are known to UAV {circumflex over (1)}, over the time interval from t_c to t_c+Δ_t. The weighting used is the importance function, γ, which defines regions of the domain where it is more important to have accurate positional information on a ground target.

[0124] $\begin{array}{cc}F=\min {\int }_{t_c}^{t_c+{\Delta }_1}\sum _{j-1}^J\left[\gamma \left(X_j^i\left(\tau \right)\right)\sum _j^i\left(\tau \right)\right]d\tau & \mathrm{Equation}1\end{array}$

[0125] In other words, by minimizing Equation 1 (i.e., the optimization problem described above) and taking into account each of the parameters, decision variable, and constraints described above, an optimal planned route may be determined for UAV {circumflex over (1)} (e.g., UAV 102a, described above). In certain embodiments, a continuous GRASP procedure (described in detail below with regard to FIG. 3) may be used to solve the optimization problem (i.e., to minimize the weighted sum of the determinants of the fused covariances for the targets 104 that are known to UAV {circumflex over (1)}).

[0126] Although a particular number of elements of system 100 have been illustrated and primarily described, the present invention system 100 including any suitable number of such components. Furthermore, although route determination applications 124 of UAVs 102 have been described as determining planned routes based on a particular optimization equation taking into account particular constraints, the present invention contemplates route determination applications 124 of UAVs 102 determining planned routes based on any suitable optimization equation taking into any suitable constraints, according to particular needs

[0127] In operation of an example embodiment of system 100, route determination application 124a of a particular UAV 102a may access target information generated by target sensing unit 106a at a first time. Route determination application 124a may access target information from neighboring UAVs 102b and 102c, the target information having been generated by target sensing units 106b and 106c at the first time.

[0128] Route determination application 124a may combine the target information received from target sensing unit 106a with the target information received from neighboring UAVs 102b and 102c to generate combined target information. Route determination application 124a determines a score associated with the combined target information in any suitable qualitative manner. If route determination application 124a determines that the score associated with the combined target information is less than a pre-determined threshold score (or that the amount of time elapsed since route determination application 124a last determined a planned route for UAV 102a is greater than a pre-determined amount of time), route determination application 124a determines a predicted location for each target 104 of the combined target information at a second time.

[0129] Route determination application 124a may determine a planned route for UAV 102a for the second time by solving an optimization problem that accounts for the location information (e.g., location, heading, and velocity) of UAV 102a, the location information (e.g., location, heading, and velocity) of neighboring UAVs 102b and 102c, the predicted locations of targets 104 of the combined target information, and a number of constraints (including line-of-sight constraints and kinematic constraints)

[0130] Route determination application 124a may update the planned route for UAV 102a for the second time to be the planned route determined for UAV 102a, update the first time to be equal to the second time, and cause UAV 102a to move according to the determined planned route.

[0131] A determination may be made as to whether the method is complete. If it is determined that the method is complete (e.g., based on an input from target tracking system 116), the methods ends. Otherwise, route determination application 124a may access target information generated by target sensing unit 106a at the second time. Route determination application 124a may determine that the method is complete in response to, for example, an input from a user of target tracking system 116 indicating that UAV 102a no longer needs to track targets 104.

[0132] Particular embodiments of the present invention may provide one or more technical advantages. In certain embodiments, the present invention may provide a method by which each of a number of UAVs 102 deployed in an airspace located in or around an urban environment (or another environment in which the UAVs may encounter line-of-sight obstructions) may dynamically determine a planned route in order to track one or more targets 104 in the urban environment. In other words, the present invention may provide for autonomous control of a number of UAVs 102 charged with tracking one or more targets 104 in an urban environment, which may reduce or eliminate the need for personnel to control the UAVs 102. Thus, personnel may be permitted to focus on other tasks, such as analyzing target information gathered by the UAVs 102.

[0133] Furthermore, a route determination application 124 of each UAV 102 may determine a planned route by solving an optimization problem that accounts for predicted locations of one or more targets 104 in the urban environment (i.e., those targets 104 located either in the line-of-sight 112 of the UAV 102 or the line or sight 112 of a neighboring UAV 102), line-of-sight constraints of the UAVs 112 (e.g., due to structure 114 in the urban environment), and kinematic constraints of the UAVs 102. As a result, the planned routes determined by each individual UAV 102 may allow the number of UAVs 102 of system 100 to collectively gather information in a manner that minimizes location errors associated with targets 104 located in the urban environment.

[0134] FIG. 2 illustrates an example method 200 for providing cooperative control of UAVs 102 for tracking targets 104, according to certain embodiments of the present invention. For purposes of simplicity, the example method is described as being performed by route determination application 124a of UAV 102 (as described above with regard to FIG. 1); however, the present invention contemplates the described method as being performed by any route determination application of any UAV 102 of system 100.

[0135] The method begins at step 202. At step 204, route determination application 124a accesses target information generated by target sensing unit 106a at a first time. The target information received from target sensing unit 106a may correspond to targets located within the line-of-sight 112a of target sensing unit 106a at the first time. At step 206, route determination application 124a accesses (e.g., via antenna 108a) target information from neighboring UAVs 102b and 102c, the target information generated by target sensing units 106b and 106c at the first time and communicated to UAV 102a via antennas 108b and 108c.

[0136] The target information received from neighboring UAV 102b may correspond to targets located within the line-of-sight 112b of target sensing unit 106b at the first time and the target information received from neighboring UAV 102c may correspond to targets located within the line-of-sight 112c of target sensing unit 106c at the first time. Additionally, route determination application 124a may receive location information associated with neighboring UAVs 102b and 102c (e.g., location, heading, and velocity associated with UAVs 102b and 102c).

[0137] At step 208, route determination application 124a combines the target information accessed from target sensing unit 106a with the target information accessed from neighboring UAVs 102b and 102c to generate combined target information. The generated combined target information may include target information (e.g., position, heading, and velocity) for targets 104 located in the line-of-sight of one or more of UAV 102a, UAV 102b, and UAV 102c at the first time. In other words, the combined target information may represent a fused picture corresponding to the portions of the urban environment located within a field of view 112 of one or more of UAV 102a, UAV 102b, and UAV 102c.

[0138] At step 210, route determination application 124a determines a score associated with the combined target information. Route determination application 124a may determine the score associated with the combined target information in any suitable qualitative manner. At step 212, route determination application 124a determines if the score associated with the combined target information is less than a pre-determined threshold score or if the amount of time that elapsed since route determination application 124a last determined a planned route for UAV 102a is greater than a pre-determined amount of time. If the determination at step 212 is “yes” the method continues to step 214. If the determination in step 212 is “no” the combined target information corresponding to the first time is discarded and the method continues to step 220, as described below.

[0139] At step 214, route determination application 124a determines a predicted location for each target 104 of the combined target information at a second time. In other words, route determination application 124a propagates forward (from a first time to a second time) a location for each of the targets 104 located in the line-of-sight 112 associated with one or more of UAV 102a, UAV 102b, and UAV 102c.

[0140] At step 216, route determination application 124a determines a planned route for UAV 102a for the second time by solving an optimization problem. In certain embodiments, the optimization problem accounts for the location information (e.g., location, heading, and velocity) of UAV 102a, the location information (e.g., location, heading, and velocity) of neighboring UAVs 102b and 102c, and the predicted locations of targets 104 of the combined target information. Additionally, the optimization problem may account for a number of constraints, including line-of-sight constraints (e.g., due to one or more structures 114) associated with UAV 102a, line-of-sight constraints (e.g., due to one or more structures 114) associated with neighboring UAVs 102b and 102c, and kinematic constraints of UAVs 102a, 102b, and 102c.

[0141] In certain embodiments, route determination application 124a solves the optimization problem by minimizing a sum of determinants of covariances for each of the targets 104 of the combined target information over a time interval from the first time to the second time. By solving the optimization problem in this manner, route determination application 124a may determine optimal planned routes for UAVs 102a, 102b, and 102c for the second time, the optimal planned routes being routes that place UAVs 102a, 102b, and 102c in the best possible position (taking into account line-of-sight and kinematic constraints) at the second time to generate target information for the targets 104 (i.e., those targets 104 of the combined target information for the first time).

[0142] At step 218, route determination application 124a updates the planned route for UAV 102a to be the planned route determined in step 216. At step 220, route determination application updates the first time to be equal to the second time. At step 222, route determination application 124a causes UAV 102a to move according to the planned route determined in step 216.

[0143] At step 224, a determination is made as to whether the method is complete. If it is determined that the methods is complete (e.g., based on an input from target tracking system 116), the methods ends at step 226. Otherwise, the method return to 204 and route determination application 124a receives target information generated by target sensing unit 106a at the second time.

[0144] FIG. 3 illustrates an example method 300 for solving an optimization problem in order to determine a planned route for a UAV in the example method illustrated in FIG. 2, according to certain embodiments of the present invention. In particular, the illustrated example method is a continuous GRASP method for optimizing the objective function, F, of Equation 1 (described above).

[0145] The method begins at step 302. At step 304, the best solution for the objective function f (f*) is set to be at positive infinity. At step 306, a determination is made regarding whether any stop condition has been reached. Stop conditions may include, for example, a time limit, a number of iterations, or any other suitable stop condition. If a stop condition has not been met, the method continues to step 308. At step 308, an initial solution (x) is randomly defined and a discretization value h is defined to be a starting discretization h_S. At step 310, a determination is made regarding whether the discretization value h (defined as the starting discretization h_S) is greater than or equal to an ending discretization value (h_e).

[0146] If it is determined that the discretization value h is greater than or equal to an ending discretization value (h_e), a solution is constructed based on the starting solution (x) at step 314. At step 316, a local search is performed on the constructed solution to locate a better solution in the neighborhood of the constructed solution. If the located better solution in the neighborhood of the constructed solution (which is still called x) results in a better objective value than f* at step 318, then f* is updated and variable x* is updated with the current solution x at step 320.

[0147] At step 322, a determination is made as to whether the updates of step 320 result in an improved solution. If the updates of step 320 did not result in an improved solution, then the discretization value h is halved at step 324 (making the grid more fine than it was previously). If the updates of step 320 did result in an improved solution, the discretization value h is left unchanged and the process returns to step 310 and another solution is constructed based upon the improved solution. The method continues until the discretization value h is less than the ending discretization value (h_e), at which point the process returns to step 306 to determine if a stop condition is met. If a stop condition is determined to be met at step 306, the best determined solution x* is returned at step 326.

[0148] Thus, the continuous GRASP approach allows for starting with a coarse discretization value (h) and adaptively increasing the density of the discretization value as needed, thereby intensifying the search in a more dense discretization when a good solution has been found.

[0149] Although the present invention has been described with several embodiments, diverse changes, substitutions, variations, alterations, and modifications may be suggested to one skilled in the art, and it is intended that the invention encompass all such changes, substitutions, variations, alterations, and modifications as fall within the spirit and scope of the appended claims.