System for allocating resources to optimize transition from a current state to a desired state

• US 8,458,715 B1
• Filed: 02/21/2008
• Issued: 06/04/2013
• Est. Priority Date: 02/23/2007
• Status: Active Grant

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Khosla, Deepak, Guillochon, James
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): LEE, TAMMY EUNHYE
• Application Number:
  US12/070,865
• Time in Patent Office: 1,930 Days
• Field of Search: None
• US Class Current: 718/104
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

Described is a Distributed Resource Allocation System (DRAS) for sensor control and planning. The DRAS comprises an information framework module that is configured to specify performance goals, assess current performance state, and includes sensor models to achieve the performance goals. The DRAS is configured to further allocate the sensors to achieve the performance goals. Once allocated, the DRAS then reassesses the current performance state and continues reallocating the sensors until the current performance state is most similar to the performance goals.

Claims

1. A distributed resource allocation system, comprising:

a plurality of resources, each of the resources having a resource manager, with each resource manager having a processor and a memory encoded with knowledge of its own resource capabilities and being configured to cause the processor to execute instructions encoded on the memory to perform operations of;

(a) receiving both a desired system state and a current system state;

(b) computing a difference between the desired system state and the current system state; and

if the difference between the current system state and the desired system state is less than or equal to a predetermined threshold, then exiting;

or

if the difference between the current system state and the desired system state is greater than the predetermined threshold, then perform the following;

i. based on the resource capabilities and the current system state and desired system state, each resource manager independently determines an expected rate of information gain (RIG) if used to move the current system state toward the desired system state;

ii. communicate the expected RIG to other resource managers;

iii. review the expected RIG s and collectively determine with other resource managers which resource has the highest expected RIG in moving the current system state to the desired system state, with the resource with the highest expected RIG then being designated as an allocated resource to perform an allocated task in order to move the current system state toward the desired system state, with the remaining resources then being designated as unallocated resources having unallocated resource managers;

iv. compute an expected modified current system state due to the expected RIG of the allocated resource;

v. wherein the unallocated resource managers repeat the operations above until the plurality of resources have been allocated; and

wherein each allocated resource is further configured to perform the allocated task, which results in an updated current system state, and where upon completion of the allocated task, each corresponding resource manager is configured to repeat operations (a) through (b)(v).

2. A distributed resource allocation system as set forth in claim 1, wherein when determining the expected RIG, each resource manager is configured to perform the following operations:

generating a possible allocation tree having a base representing a current system state and a plurality of step-wise nodes, each node representing an expected modified current system state based on the possible allocation of the resource to a task and providing a possible expected gain for allocation of the resource to the task, the possible allocation tree being generated until a predetermined fixed horizon of planning;

computing a total possible expected RIG for each path from each node at the horizon of planning to the base;

ordering a total possible expected RIG for each path;

determining a path with the highest total possible expected RIG s; and

using the path with the highest total possible expected RIG s as the expected RIG s to be communicated to other resource managers.

3. A distributed resource allocation system as set forth in claim 2, wherein the resources are sensors.

4. A distributed resource allocation system as set forth in claim 3, wherein the sensors are configured to observe the current system state and generate signals reflective of the current system state.

5. A distributed resource allocation system as set forth in claim 4, further comprising a fusion manager configured to receive signals from the sensors and generate an updated current system state.

6. A distributed resource allocation system as set forth in claim 5, wherein sensors are configured to sense objects present in a scene.

7. A distributed resource allocation system as set forth in claim 6, wherein the fusion manager includes a tracker module, the tracker module being configured to track objects present in the scene.

8. A distributed resource allocation system as set forth in claim 6, wherein the fusion manager includes a reasoner module, the reasoner module being configured to identify objects present in the scene.

9. A distributed resource allocation system as set forth in claim 6, wherein the fusion manager includes a tracker module, the tracker module being configured to track objects present in the scene, and wherein the fusion manager includes a reasoner module, the reasoner module being configured to identify objects present in the scene, and wherein the fusion manager is configured to track identified objects in the scene across multiple sensors.

10. A distributed resource allocation system as set forth in claim 9, wherein each sensor includes a sensing range and wherein the fusion manager is configured to track identified objects in the scene across multiple sensors, such that as the object travels from the sensing range of a first sensor and into the sensing range of a second sensor, the fusion manager coordinates the identification of the object from the first sensor to the second sensor to provide an updated current system state that reflects motion of the identified object from the first sensor to the second sensor.

11. A distributed resource allocation system as set forth in claim 1, wherein when determining the expected RIG, the operation is performed in at least a first round and a second round;

wherein in the first round, each resource manager is configured to perform the following operations;

generating a possible allocation tree having a base representing a current system state and a plurality of step-wise nodes, each node representing an expected modified current system state based on the possible allocation of the resource to a task and providing a possible expected gain for allocation of the resource to the task, the possible allocation tree being generated until a predetermined fixed horizon of planning;

computing a total possible expected RIG for each path from each node at the horizon of planning to the base;

ordering a total possible expected RIG for each path;

determining a path with the highest total possible expected RIG s; and

using the path with the highest total possible expected RIG s as the expected RIG s to be communicated to other resource managers, with the resource with the highest expected RIG then being designated as an allocated resource to perform an allocated task in order to move the current system state toward the desired system state, with the remaining resources then being, designated as unallocated resources having unallocated resource managers; and

wherein in the second round, each unallocated resource manager is configured to perform the following operations;

independently determines an expected RIG if used to move the current system state toward the desired system state;

communicate the expected RIG to other unallocated resource managers; and

review the expected RIG s and collectively determine with other unallocated resource managers which resource has the highest expected RIG in moving the current system state to the desired system state, with the resource with the highest expected RIG then being designated as an allocated resource to perform an allocated task in order to move the current system state toward the desired system state.

12. A method for allocating resources, comprising acts of:

utilizing a plurality of resources, each of the resources having a resource manager, with each resource manager having a processor and a memory encoded with knowledge of its own resource capabilities and being configured to cause the processor to execute instructions encoded on the memory to perform acts of;

(a) receiving both a desired system state and a current system state;

(b) computing a difference between the desired system state and the current system state; and

if the difference between the current system state and the desired system state is less than or equal to a predetermined threshold, then exiting;

or

if the difference between the current system state and the desired system state is greater than the predetermined threshold, then performing the following acts;

i. based on the resource capabilities and the current system state and desired system state, each resource manager performs an act of independently determining an expected rate of information gain (RIG) if used to move the current system state toward the desired system state;

ii. communicating the expected RIG to other resource managers;

iii. reviewing the expected RIG s and collectively determining with other resource managers which resource has the highest expected RIG in moving the current system state to the desired system state, with the resource with the highest expected RIG then being designated as an allocated resource to perform an allocated task to move the current system state toward the desired system state, with the remaining resources then being designated as unallocated resources having unallocated resource managers;

iv. computing an expected modified current system state due to the expected RIG of the allocated resource;

v. wherein the unallocated resource managers repeat the acts above until the plurality of resources have been allocated; and

causing the allocated resource to perform the allocated task which results in an updated current system state, and where upon completion of the allocated task, each corresponding resource manager is configured to repeat acts (a) through (b)(v).

13. A method as set forth in claim 12, wherein when determining the expected RIG, each resource manager is further configured to perform the following acts:

generating a possible allocation tree having a base representing a current system state and a plurality of step-wise nodes, each node representing an expected modified current system state based on the possible allocation of the resource to a task and providing a possible expected gain for allocation of the resource to the task, the possible allocation tree being generated until a predetermined fixed horizon of planning;

computing a total possible expected RIG for each path from each node at the horizon of planning to the base;

ordering a total possible expected RIG for each path;

determining a path with the highest total possible expected RIG s; and

using the path with the highest total possible expected RIG s as the expected RIG s to be communicated to other resource managers.

14. A method as set forth in claim 13, wherein in the act of utilizing a plurality of resources, the resources are sensors.

15. A method as set forth in claim 14, wherein the sensors are configured to perform acts of observing the current system state and generating signals reflective of the current system state.

16. A method as set forth in claim 15, further comprising acts of receiving signals from the sensors and generating an updated current system state.

17. A method as set forth in claim 16, further comprising an act of sensing objects present in a scene.

18. A method as set forth in claim 17, further comprising, an act of tracking objects present in the scene.

19. A method as set forth in claim 17, further comprising an act of identifying objects present in the scene.

20. A method as set forth in claim 19, further comprising acts of:

tracking objects present in the scene;

identifying objects present in the scene; and

tracking identified objects in the scene across multiple sensors.

21. A method as set forth in claim 20, further comprising an act of tracking identified objects in the scene across multiple sensors, such that as the object travels from a sensing range of a first sensor and into a sensing range of a second sensor, the identification of the object is coordinated from the first sensor to the second sensor to provide an updated current system state that reflects motion of the identified object from the first sensor to the second sensor.

22. A method as set forth in claim 12, wherein when determining the expected RIG, the act is performed in at least a first round and a second round;

wherein the first round further comprises the following acts;

generating a possible allocation tree having a base representing a current system state and a plurality of step-wise nodes, each node representing an expected modified current system state based on the possible allocation of the resource to a task and providing a possible expected gain for allocation of the resource to the task, the possible allocation tree being generated until a predetermined fixed horizon of planning;

computing a total possible expected RIG for each path from each node at the horizon of planning to the base;

ordering a total possible expected RIG for each path;

determining a path with the highest total possible expected RIG s; and

using the path with the highest total possible expected RIG s as the expected RIG s to be communicated to other resource managers, with the resource with the highest expected RIG then being designated as an allocated resource to perform an allocated task in order to move the current system state toward the desired system state, with the remaining resources then being designated as unallocated resources having unallocated resource managers; and

wherein the second round further comprises the acts of;

independently determining an expected RIG if an unallocated resource is used to move the current system state toward the desired system state;

communicating the expected RIG to other unallocated resource managers; and

reviewing the expected RIG s and collectively determine with other unallocated resource managers which resource has the highest expected RIG in moving the current system state to the desired system state, with the resource with the highest expected RIG then being designated as an allocated resource to perform an allocated task in order to move the current system state toward the desired system state.

23. A computer program product for distributing a plurality of resources, where each of the resources has a resource manager, with each resource manager having knowledge of its own resource capabilities, the computer program product comprising computer-readable instruction means stored on a non-transitory computer-readable medium that are executable by a computer for causing the computer to perform operations of:

(a) receive both a desired system state and a current system state;

(b) compute a difference between the desired system state and the current system state; and

if the difference between the current system state and the desired system state is less than or equal to a predetermined threshold, then exiting;

or

if the difference between the current system state and the desired system state is greater than the predetermined threshold, then performing the following operations;

i. based on the resource capabilities and the current system state and desired system state, determining an expected rate of information gain (RIG) if used to move the current system state toward the desired system state;

ii. communicate the expected RIG to other resource managers;

iii. review the expected RIG s and collectively determine with other resource managers which resource has the highest expected RIG in moving the current system state to the desired system state, with the resource with the highest expected RIG then being designated as an allocated resource to perform an allocated task in order to move the current system state toward the desired system state, with the remaining, resources then being designated as unallocated resources having unallocated resource managers;

iv. compute an expected modified current system state due to the expected RIG of the allocated resource;

v. wherein if designated as an unallocated resource manager, repeat the operations above until the plurality of resources have been allocated; and

causing the resource to perform the allocated task which results in an updated current system state, and where upon completion of the allocated task, the corresponding resource manager is configured to repeat operations (a) through (b)(v).

24. A computer program product as set forth in claim 23, further comprising instruction means for causing a computer to perform operations of:

generating a possible allocation tree having a base representing a current system state and a plurality of step-wise nodes, each node representing an expected modified current system state based on the possible allocation of the resource to a task and providing a possible expected gain for allocation of the resource to the task, the possible allocation tree being generated until a predetermined fixed horizon of planning;

computing a total possible expected RIG for each path from each node at the horizon of planning to the base;

ordering a total possible expected RIG for each path;

determining a path with the highest total possible expected RIG s; and

using the path with the highest total possible expected RIG s as the expected RIG s to be communicated to other resource managers.

25. A computer program product as set forth in claim 24, further comprising instruction means for causing a computer to utilize a sensor as the resource.

26. A computer program product as set forth in claim 25, further comprising instruction means for causing the sensor to observe the current system state and generate signals reflective of the current system state.

27. A computer program product as set forth in claim 26, further comprising instruction means for causing the computer to receive signals from the sensor and generate an updated current system state.

28. A computer program product as set forth in claim 27, further comprising, instruction means for causing the sensor to sense objects present in a scene.

29. A computer program product as set forth in claim 28, further comprising instruction means for causing the computer to track objects present in the scene.

30. A computer program product as set forth in claim 28, further comprising instruction means for causing the computer to identify objects present in the scene.

31. A computer program product as set forth in claim 28, further comp instruction means for causing the computer to perform operations of:

tracking objects present in the scene;

identifying objects present in the scene; and

tracking identified objects in the scene across multiple sensors.

32. A computer program product as set forth in claim 31, further comprising instruction means for causing the computer to perform an operation of tracking identified objects in the scene across multiple sensors, such that as the object travels from a sensing range of a first sensor and into a sensing range of a second sensor, the identification of the object is coordinated from the first sensor to the second sensor to provide an updated current system state that reflects motion of the identified object from the first sensor to the second sensor.

33. A computer program product as set forth in claim 23, further comprising instruction means for causing a computer to perform operations of determining the expected RIG in at least a first round and a second round;

wherein in the first round, each resource manager is configured to perform the following operations;

generating a possible allocation tree having a base representing a current system state and a plurality of step-wise nodes, each node representing an expected modified current system state based on the possible allocation of the resource to a task and providing a possible expected gain for allocation of the resource to the task, the possible allocation tree being generated until a predetermined fixed horizon of planning;

computing a total possible expected RIG for each path from each node at the horizon of planning to the base;

ordering a total possible expected RIG for each path;

determining a path with the highest total possible expected RIG s; and

using the path with the highest total possible expected RIG s as the expected RIG s to be communicated to other resource managers, with the resource with the highest expected RIG then being designated as an allocated resource to perform an allocated task in order to move the current system state toward the desired system state, with the remaining resources then being designated as unallocated resources having unallocated resource managers; and

wherein in the second round, each unallocated resource manager is configured to perform the following operations;

independently determines an expected RIG if used to move the current system state toward the desired system state;

communicate the expected RIG to other unallocated resource managers; and

review the expected RIG s and collectively determine with other unallocated resource managers which resource has the highest expected RIG in moving the current system state to the desired system state, with the resource with the highest expected RIG then being designated as an allocated resource to perform an allocated task in order to move the current system state toward the desired system state.