SYSTEM AND METHOD FOR RESOURCE ALLOCATION AND MANAGEMENT

• US 20120209652A1
• Filed: 03/23/2011
• Published: 08/16/2012
• 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.
• Granted Patent: US 8,396,730 B2
• Time in Patent Office: Days
• US Class Current: 705/7.16
• 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 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 an upper bound for a branch and bound objective function for each of the plural operational modes of the resources;

combining 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; and

pruning possible resource movements by carrying out a branch and bound process with the single upper bound.

2. The method of claim 1, wherein the branch and bound process is constructed in accordance with a model that includes hostile targets that attempt to destroy the resources.

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

4. The method of claim 1, wherein the operational modes include a search operation, a localization operation, and a task execution operation.

5. The method of claim 4, wherein the task execution operation is a target kill operation.

6. The method of claim 5, wherein the upper bound for the target kill operation is the smaller of a first potential upper bound where multiple resources are assignable to the same target and a second potential upper bound where multiple targets are assignable to the same resource.

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

8. The method of claim 7, wherein passive geolocation starts upon detection of a target.

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

10. The method of claim 9, wherein the task execution operation starts when localization error falls below a second threshold.

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

12. The method of claim 11, wherein the resources are unmanned aerial vehicles.

13. 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.

14. The method of claim 1, wherein the pruning of possible resource movements is carried out by iterating a beginning branch and bound function for a predetermined number of steps in a look ahead depth, wherein each iteration of the beginning branch and bound function up to the look ahead depth has a corresponding search distance, the search distance for each resource in each iteration is measured from the starting point of the resource, ignoring feasibility of moves from iteration to iteration.

15. The method of claim 1, wherein the pruning of possible resource movements is carried out using a progressive lower bound branch and bound function that includes determining an initial lower bound for the progressive lower bound branch and bound function by performing a greedy search of moves available from a current end node, adding a search value for corresponding movement resulting from the greedy search to a current cumulative search value for all current movement steps in the look ahead depth and subtracting a search value for the first of the current movement steps in the look ahead depth.

16. The method of claim 15, wherein each iteration of the progressive lower bound branch and bound function using the initial lower bound up to the look ahead depth has a corresponding search distance, the search distance for each resource in each iteration is measured from a current starting point of the resource, ignoring feasibility of moves from iteration to iteration.

17. The method of claim 1, 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, 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 by carrying out a global branch and bound function using a global search depth on the coarse grid; and

determining an exact movement path by carrying out 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.