SYSTEM AND METHOD FOR RESOURCE ALLOCATION AND MANAGEMENT

• US 20110046837A1
• Filed: 08/19/2009
• Published: 02/24/2011
• Est. Priority Date: 08/19/2009
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Ii, David L., Fuciarelli, David, Khosla, Deepak
• Granted Patent: US 8,634,982 B2
• Time in Patent Office: Days
• US Class Current: 701/26
• 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 movement, comprising:

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

pruning possible sensor movements 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 sensor in each iteration is measured from the starting point of the sensor, thereby ignoring feasibility of moves from iteration to iteration.

2. The method of claim 1, wherein the sensors are unmanned aerial vehicles.

3. The method of claim 1, further comprising further pruning possible sensor 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 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.

4. The method of claim 3, 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 sensor in each iteration is measured from a current starting point of the sensor, thereby ignoring feasibility of moves from iteration to iteration.

5. A method of planning sensor movement, comprising:

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

pruning possible sensor 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 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.

6. The method of claim 5, 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 sensor in each iteration is measured from the current starting point of the sensor, thereby ignoring feasibility of moves from iteration to iteration.

7. The method of claim 5, wherein the sensors are unmanned aerial vehicles.

8. A method of planning sensor movement, comprising:

dividing an 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;

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.

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

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 each sensor, 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 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.

15. The method of claim 8, wherein the global branch and bound function includes pruning possible sensor movements by iterating a beginning branch and bound function for the global look ahead depth, wherein each iteration of the beginning branch and bound function up to the global look ahead depth has a corresponding search distance, the search distance for each sensor in each iteration is measured from a starting point of the sensor, thereby ignoring feasibility of moves from iteration to iteration.

16. The method of claim 15, wherein the global branch and bound function further prunes possible sensor 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 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 global look ahead depth and subtracting a search value for the first of the current movement steps in the global look ahead depth.

17. The method of claim 8, wherein the local branch and bound function includes pruning possible sensor movements by iterating a beginning branch and bound function for the local look ahead depth, wherein each iteration of the beginning branch and bound function up to the local look ahead depth has a corresponding search distance, the search distance for each sensor in each iteration is measured from a starting point of the sensor, thereby ignoring feasibility of moves from iteration to iteration.

18. The method of claim 17, wherein the local branch and bound function further prunes possible sensor 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 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 local look ahead depth and subtracting a search value for the first of the current movement steps in the local look ahead depth.