System and method for resource allocation and management

• US 8,634,982 B2
• Filed: 08/19/2009
• Issued: 01/21/2014
• Est. Priority Date: 08/19/2009
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Khosla, Deepak, Fuciarelli, David, Ii, David L
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Lewandroski, Sara
• Application Number:
  US12/543,665
• Publication Number:
  US 20110046837A1
• Time in Patent Office: 1,616 Days
• Field of Search: 701/25, 701/26, 701/528, 701/533, 701/410, 701/411, 701/420, 712/233
• US Class Current: 701/25
• CPC Class Codes: G05D 1/104 involving a plurality of aircrafts, e.g. formation flying traffic control systems for aircraft G08G5/00

Abstract

To improve the scheduling and tasking of sensors, the present disclosure describes an improved planning system and method for the allocation and management of sensors. In one embodiment, the planning system uses a branch and bound approach of tasking sensors using a heuristic to expedite arrival at a deterministic solution. In another embodiment, a progressive lower bound is applied to the branch and bound approach. Also, in another embodiment, a hybrid branch and bound approach is used where both local and global planning are employed in a tiered fashion.

Claims

1. A method of planning sensor platform movement, comprising:

dividing an area of interest into a grid of grid cells, each grid cell having a target probability and the sensor platform having a starting point corresponding to one of the grid cells;

determining, via a computer system, a heuristic for the sensor platform by;

iteratively searching a subset of the grid cells within incrementing respective search distances, from a search depth equal to one to a search depth defined by a look ahead depth, for a predetermined number of iterations defined by the look ahead depth,

selecting, in each iteration, the grid cell having the highest target probability of the grid cells searched,

logging the respective target probabilities of the selected grid cells and logging the respective search distances associated with the respective selected grid cells,

wherein the search distance for the sensor platform in each iteration is measured from the starting point of the sensor platform, thereby ignoring feasibility of moves from the selected grid cell of one iteration to the selected grid cell of a subsequent iteration;

determining, via the computer system, a current best path through the grid cells of the area of interest for a number of moves up to the look ahead depth;

pruning, via the computer system, possible sensor platform movements by iterating a beginning branch and bound function for the predetermined number of steps in the look ahead depth, by comparing potential branches with the current best path, and eliminating potential branches that are not better than the current best path, wherein the potential branches each include a current node corresponding to the current step in the look ahead depth and ancestor and successor nodes collectively equal to the look ahead depth minus one, the current node having a value corresponding to a target probability of a feasible move, each ancestor node having a value corresponding to a target probability of a feasible move and each successor node having a value corresponding to a target probability of the heuristic; and

tasking the sensor platform in accordance with the pruned possible sensor platform movements.

2. The method of claim 1, wherein the sensor platform is an unmanned aerial vehicle.

3. The method of claim 1, further comprising further pruning possible sensor platform movements by carrying out 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 an end node of a predetermined path, adding a search value for corresponding movement resulting from the greedy search to a current cumulative search value for all predetermined movement steps in the look ahead depth and subtracting a search value for the first of the predetermined movement steps in the predetermined path.

4. The method of claim 3, wherein the predetermined path is a path planned in a previous iteration of a path planner using the method of claim 1.

5. A method of planning sensor platform movement, comprising:

dividing an area of interest into a grid of grid cells, each grid cell having a target probability and the sensor platform having a current starting point corresponding to one of the grid cells;

pruning possible sensor platform movements through the grid cells of the area of interest by carrying out a progressive lower bound branch and bound function by a computer 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 an end node of a predetermined path, adding a search value for corresponding movement resulting from the greedy search to a current cumulative search value for all predetermined movement steps in the predetermined path and subtracting a search value for the first of the movement steps in the predetermined path; and

tasking the sensor platform in accordance with the pruned possible sensor platform movements.

6. The method of claim 5, wherein the predetermined path is determined using a heuristic, the heuristic being determined by:

iteratively searching a subset of grid cells within incrementing respective search distances, from a search depth equal to one to a search depth defined by a look ahead depth, for a predetermined number of iterations defined by the look ahead depth,

selecting, in each iteration, the grid cell having the highest target probability of the grid cells searched,

logging the respective target probabilities of the selected grid cells and logging the respective search distances associated with the respective selected grid cells,

wherein the search distance for the sensor platform in each iteration is measured from a then-current starting point of the sensor platform, thereby ignoring feasibility of moves from the selected grid cell of one iteration to the selected grid cell of a subsequent iteration.

7. The method of claim 5, wherein the sensor platform is an unmanned aerial vehicle.

8. A method of planning sensor platform movement, comprising:

dividing an area of interest into a first grid covering the extent of the area of interest, the first grid being a coarse grid of coarse grid cells;

dividing the area of interest into a second grid covering the extent of the area of interest, the second grid being a fine grid of fine grid cells, the area of each fine grid cell being smaller than the area of each coarse grid cell;

determining a gross movement path from a starting point to an ending point in a coarse grid cell through the coarse grid cells by carrying out via a computer a global branch and bound function using a global search depth on the coarse grid; and

determining an exact movement path from the starting point to the ending point in the coarse grid cell through the fine grid cells by carrying out via the computer 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 sensor platform in accordance with the exact movement path.

9. The method of claim 8, wherein the sensor platform is an unmanned aerial vehicle.

10. The method of claim 8, wherein a ratio of the number of coarse grid cells to the number of fine grid cells is about 1:

4 to about 1;

10.

11. The method of claim 8, wherein each coarse grid cell reachable in the look ahead depth has a target probability that is determined as a target probability of a fine grid cell corresponding to an endpoint of the coarse grid cell, the endpoint being a destination for a move to the coarse grid cell.

12. The method of claim 11, wherein the endpoint is determined using local branch and bound planning for the fine grid cells in the coarse grid cell.

13. The method of claim 8, wherein for the sensor platform, the global branch and bound function considers coarse grid cells reachable within the global look ahead depth, including the coarse grid cell in which the sensor platform is currently located.

14. The method of claim 13, wherein the global branch and bound function further considers the fine grid cell corresponding to the current position of the sensor platform.

15. The method of claim 8, wherein the global branch and bound function includes pruning possible sensor platform movements by iterating a beginning branch and bound function for the global look ahead depth and using a heuristic for the sensor platform by:

iteratively searching a subset of grid cells within incrementing respective search distances, from a search depth equal to one to a search depth defined by a look ahead depth, for a predetermined number of iterations defined by the look ahead depth,

selecting, in each iteration, the grid cell having the highest target probability of the grid cells searched,

logging the respective target probabilities of the selected grid cells and logging the respective search distances associated with the respective selected grid cells,

wherein the search distance for the sensor platform in each iteration is measured from a starting point of the sensor platform, thereby ignoring feasibility of moves from the selected grid cell of one iteration to the selected grid cell of a subsequent iteration.

16. The method of claim 15, wherein the global branch and bound function further prunes possible sensor platform movements by carrying out 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 an end node of a predetermined global path, adding a search value for corresponding movement resulting from the greedy search to a current cumulative search value for all predetermined global movement steps in the global look ahead depth and subtracting a search value for the first of the predetermined global movement steps in the predetermined global path.

17. The method of claim 8, wherein the local branch and bound function includes pruning possible sensor platform movements by iterating a beginning branch and bound function for the local look ahead depth and using a heuristic for each sensor platform by:

iteratively searching a subset of grid cells within incrementing respective search distances, from a search depth equal to one to a search depth defined by a look ahead depth, for a predetermined number of iterations defined by the look ahead depth,

selecting, in each iteration, the grid cell having the highest target probability of the grid cells searched,

logging the respective target probabilities of the selected grid cells and logging the respective search distances associated with the respective selected grid cells,

wherein the search distance for the sensor platform in each iteration is measured from a starting point of the sensor platform, thereby ignoring feasibility of moves from the selected grid cell of one iteration to the selected grid cell of a subsequent iteration.

18. The method of claim 17, wherein the local branch and bound function further prunes possible sensor platform movements by carrying out 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 an end node of a predetermined local path, adding a search value for corresponding movement resulting from the greedy search to a current cumulative search value for all predetermined local movement steps in the local look ahead depth and subtracting a search value for the first of the predetermined local movement steps in the predetermined local path.

19. The method of claim 8, further comprising

estimating a cost and a value of a move between coarse grid cells;

estimating a cost and a value of a search move within a coarse grid cell; and

determining a gross movement path by maximizing a value-to-cost ratio of possible movement paths, wherein

the value of a search move is estimated with a heuristic determined by iteratively searching fine grid cells within an incrementing fine search distance for a predetermined number of steps in a fine look ahead depth, the fine search distance for the sensor platform in each iteration is measured from one of a current fine grid cell location of the sensor platform or from a predetermined fine grid cell endpoint of a coarse grid cell, thereby ignoring feasibility of moves from iteration to iteration.