System and method for resource allocation and management

• US 8,396,730 B2
• Filed: 03/23/2011
• Issued: 03/12/2013
• Est. Priority Date: 02/14/2011
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Khosla, Deepak, Huang, Eric, Ii, David L.
• Primary Examiner(s): Bayat, Bradley B
• Assistant Examiner(s): FEENEY, BRETT A
• Application Number:
  US13/069,638
• Publication Number:
  US 20120209652A1
• Time in Patent Office: 720 Days
• Field of Search: None
• US Class Current: 705/7.11
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations

Abstract

To improve the scheduling and tasking of resources, the present disclosure describes an improved planning system and method for the allocation and management of resources. The planning system uses a branch and bound approach of tasking resources using a heuristic to expedite arrival at a deterministic solution. For each possible functional mode of the resources, an upper bound is determined. The upper bounds are employed in an objective function for the branch and bound process to determine the functional mode in which to place the resources and to determine movement paths for the resources, all in an environment where a hostile force may attempt to destroy the resources.

Claims

1. A method of planning resource tasking and movement where there are plural resources and plural targets and each resource has plural operational modes, comprising:

dividing an area of interest into a grid of grid cells, each grid cell having a probability that a target is present in the grid cell and each resource having a starting point corresponding to one of the grid cells;

determining, via a computer system, an upper bound for a branch and bound objective function for each of the plural operational modes of the resources;

combining, via the computer system, the upper bounds for each operational mode into a single upper bound and determining whether to change operational modes of one or more of the resources;

pruning, via the computer system, possible resource movements by carrying out a branch and bound process with the single upper bound; and

tasking each resource in accordance with the pruned possible resource movements,

wherein the operational modes for at least one resource includes a target interaction operation and wherein determining, via the computer system, the upper bound for the target interaction operation comprises;

selecting, via the computer system, a minimum of a first potential upper bound and a second potential upper bound; and

determining, via the computer system, the first potential upper bound by summing probabilities of each target being interacted with by a resource, ignoring feasibility of each resource being able to interact with more than one target.

2. The method of claim 1, wherein the upper bounds for each operational mode are combined as a weighted sum.

3. The method of claim 1, wherein the operational modes for at least one resource include a search operation and for at least one resource include a localization operation.

4. The method of claim 3, wherein the localization operation includes passive geolocation and active geolocation.

5. The method of claim 4, wherein passive geolocation starts upon detection of a target.

6. The method of claim 5, wherein active geolocation starts when localization error falls below a first threshold.

7. The method of claim 6, wherein the target interaction operation starts when localization error falls below a second threshold.

8. The method of claim 1, wherein the resources are autonomous mobile vehicles.

9. The method of claim 8, wherein the resources are unmanned aerial vehicles.

10. The method of claim 1, wherein operational mode capabilities for a first one of the resources and a second one of the resources are not the same.

11. The method of claim 1, further comprising:

determining the second potential upper bound by summing probabilities of each resource interacting with the target that each resource has the highest probability of being able to interact with, ignoring the feasibility of each target being interacted with more than once.

12. The method of claim 11 further comprising:

determining, via the computer system, the probabilities of each resource interacting with the target and the probabilities of each target being interacted with by a resource based on distance to each target and localization error of each target.

13. The method of claim 1

wherein the operational modes for at least one resource includes an active localization operation and wherein determining, via the computer system, the upper bound for the active localization operation comprises:

determining, via the computer system, a weighted sum of an upper bound of a geometric term and an upper bound of a distance term.

14. The method of claim 13 further comprising:

determining, via the computer system, the upper bound of the distance term by determining a complement over [0,1] of the root mean square of a lower bound pairwise distance between each resource and a target.

15. The method of claim 13 further comprising:

determining, via the computer system, the upper bound of the geometric term by determining a complement over [0,1] of the root mean square of arc distances, wherein the arc distances are respective measures of how different two sets of distances are, wherein each set of distances are the distances between two resources that can be achieved within a predetermined time.

16. The method of claim 13, wherein the operational modes for at least one resource include a search operation and for at least one resource include a task execution operation.

17. A method of planning resource tasking and movement where there are plural resources and plural targets and each resource has plural operational modes, comprising:

dividing an area of interest into a grid of grid cells, each grid cell having a probability that a target is present in the grid cell and each resource having a starting point corresponding to one of the grid cells;

determining, via a computer system, an upper bound for a branch and bound objective function for each of the plural operational modes of the resources;

combining, via the computer system, the upper bounds for each operational mode into a single upper bound and determining whether to change operational modes of one or more of the resources;

pruning, via the computer system, possible resource movements by carrying out a branch and bound process with the single upper bound; and

tasking each resource in accordance with the pruned possible resource movements,

wherein the operational modes for at least one resource includes a search operation and wherein determining, via the computer system, the upper bound for the search operation comprises;

iteratively searching the grid cells within an incrementing search distance for a predetermined number of steps of a look ahead depth for the highest probability, the search distance for the resource in each iteration is measured from a starting point of the resource, thereby ignoring feasibility of moves from iteration to iteration, and

summing the highest probability from each iteration.

18. The method of claim 17, wherein the upper bounds for each operational mode are combined as a weighted sum.

19. The method of claim 17, wherein the operational modes for at least one resource include a task execution operation and for at least one resource include a localization operation.

20. The method of claim 17, wherein:

the dividing of the area of interest includes;

dividing the area of interest into a coarse grid of coarse grid cells;

dividing the area of interest into a fine grid of fine grid cells overlapping the coarse grid of coarse grid cells, the area of each fine grid cell being smaller than the area of each coarse grid cell; and

the pruning of possible resource movements is carried out using a progressive lower bound branch and bound function that includes;

determining a gross movement path through the coarse grid cells by carrying out via the computer system a global branch and bound function using a global search depth on the coarse grid; and

determining an exact movement path through the fine grid cells by carrying out via the computer system a local branch and bound function using a local search depth on the fine grid, wherein the fine grid cells considered by the local branch and bound function are reachable within the local search depth from a path of fine grid cells through which the gross movement path traverses; and

tasking the resource in accordance with the exact movement path.