Apparatus and method for resource negotiations among autonomous agents

• US 6,842,899 B2
• Filed: 12/19/2000
• Issued: 01/11/2005
• Est. Priority Date: 12/21/1999
• Status: Active Grant

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Moody, John O., Szczerba, Robert, Glickstein, Ira
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): ZHEN, LI B
• Application Number:
  US09/740,544
• Publication Number:
  US 20010042123A1
• Time in Patent Office: 1,484 Days
• Field of Search: 718/100, 718/104, 718/102, 718/106, 709/226
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/4875 with migration policy, e.g. auction, contract negotiation
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

Abstract

A distributed data processing system employing negotiation among autonomous agents for allocation of resources is presented herein. The system includes a communications network for passing messages between computers connected thereto, a plurality of computers connected to the network for running programs thereon including at least first and second autonomous agents. Each agent receives a graph associated therewith and wherein the graph represents for the associated agent what resources that agent has and what task or tasks that agent may perform. Each agent employs the associated graph to determine what resource or resources are needed by that agent to carry out the task or tasks to be performed by that agent. The agents negotiate with each other for the resources needed to carry out the task or tasks to be performed by the agents.

Claims

1. A distributed data processing system employing negotiation for allocation of resources, said system comprising:

a communications network for passing messages;

a plurality of computers connected to said communication network for running programs, said plurality of computers including a first autonomous agent computer and a second autonomous agent computer;

said first agent computer having a first graph representing resources required for tasks performed by said first agent computer, said second agent computer having a second graph representing resources required for tasks performed by said second agent computer,

said first agent computer negotiating with said second agent computer for resources required to perform tasks by said first agent computer, said second agent computer negotiating with said first agent computer for resources required to perform tasks by said second agent computer,

said first agent computer calculating deadlock avoidance structures relating to an internal representation of initialization data and said first graph.

2. A system as set forth in claim 1 wherein said first agent computer receives initialization data relating to said first graph.

3. A system as set forth in claim 2 wherein said first agent computer determines whether the initialization data has been received.

4. A system as set forth in claim 3 wherein, if the initialization data has been received, said first agent computer provides an internal representation of the initialization data.

5. A system as set forth in claim 4 wherein said first agent computer receives cost data and task completion reward data.

6. A system as set forth in claim 5 wherein said first agent computer determines whether the cost data has been received.

7. A system as set forth in claim 6 wherein said first agent computer forwards update data to a central authority computer, the update data representing local connections and dependencies.

8. A system as set forth in claim 7 wherein said first agent computer forwards additional update data to said central authority computer, the additional update data including data representing remaining resources and task status.

9. A system as set forth in claim 8 wherein said first agent computer calculates desired output offer costs.

10. A system as set forth in claim 9 wherein said first agent computer forwards outgoing offers of resources to said second agent computer.

11. A system as set forth in claim 10 wherein said first agent computer determines whether additional resources are needed for task completion by said first agent computer.

12. A system as set forth in claim 11 wherein said first agent computer calculates desired resource bid cost if additional resources are needed.

13. A system as set forth in claim 12 wherein said first agent computer forwards outgoing bids for resources to said second agent computer.

14. A system as set forth in claim 13 wherein said first agent computer receives incoming offers of resources from said second agent computer.

15. A system as set forth in claim 14 wherein said first agent computer receives data representing incoming bids from said second agent computer, said second agent computer seeking additional resources.

16. A system as set forth in claim 15 wherein said first agent computer determines whether offers from said second agent computer are acceptable.

17. A system as set forth in claim 16 wherein said first agent computer provides an affirmative determination of an offer, said first agent computer forwarding an outgoing acceptance.

18. A system as set forth in claim 16 wherein said first agent computer receives an incoming acceptance from said second agent computer.

19. A system as set forth in claim 18 wherein said first agent computer determines whether additional resources are required for task completion by said first agent computer.

20. A system as set forth in claim 19 wherein said first agent computer no longer needs resources, said first agent computer searching said first graph for a path for task completion, said first agent computer completing the task.

21. A method for allocation of resources, said method comprising the steps of:

employing a communications network for passing messages between a first agent computer and a second agent computer;

executing programs by a central authority computer, the first agent computer, and the second agent computer;

receiving a first graph by the first agent computer, the first graph representing a first set of tasks and resources utilized by the first set of tasks;

receiving a second graph by the second agent computer, the second graph representing a second set of tasks and resources utilized by the second set of tasks;

utilizing the first graph for determining resources required by the first agent computer to perform the first set of tasks;

utilizing the second graph for determining resources required by the second agent computer to perform the second set of tasks;

negotiating between the first agent computer and the second agent computer for resources requires to perform the first and second sets of tasks; and

calculating deadlock avoidance structures based on an internal representation of initialization data.

22. A method as set forth in claim 21 further including the step of receiving initialization data relating to the first graph.

23. A method as set forth in claim 22 further including the steps of determining whether initialization data has been received and setting up a representation based on the initialization data.

24. A method as set forth in claim 23 wherein the representation is an internal representation.

25. A method as set forth in claim 23 further including the steps of receiving cost data, determining whether the cost data has been received, and forwarding updated data to the central authority computer, the updated data representing local connections and dependencies.

26. A method as set forth in claim 25 wherein the updated data includes data representing remaining resources and task status.

27. A method as set forth in claim 26 further including the steps of calculating desired output offer cost and forwarding outgoing offers to the first and second agent computers.

28. A method as set forth in claim 27 further including the steps of determining whether additional resources are needed to complete a task by the first agent computer and calculating desired resource bid costs.

29. A method as set forth in claim 28 further including the step of forwarding outgoing bids for resources to the second agent computer.

30. A method as set forth in claim 29 further including the steps of receiving incoming offers of resources, receiving bids seeking additional resources from the second agent computer, and determining whether acceptable bids have been received.

31. A method as set forth in claim 30 further including the step of forwarding outgoing acceptances of acceptable bids.

32. A method as set forth in claim 29 further including the step of determining whether more resources are required by the first agent computer.

33. A method as set forth in claim 32 wherein the first agent computer searches the first graph for task completion path, the first agent computer completing the task.

34. A computer program product stored in a computer readable medium, said product being operative in a distributed data processing system employing negotiation for allocation of resources, the system including a communications network, said product including:

a first autonomous agent node receiving a first graph representing a first set of tasks and resources for performing the first set of tasks, the first agent node utilizing the first graph to determine the resources required for performing the first set of tasks;

a second autonomous agent node receiving a second graph representing a second set of tasks and resources for performing the second set of tasks, the second agent node utilizing the second graph to determine the resources required for performing the second set of tasks;

the first agent node negotiating with the second agent node for resources required to perform the first set of tasks,

the first agent node calculating deadlock avoidance structures relating to an internal representation of initialization data and the first graph.

35. A system as set forth in claim 34 wherein the first agent node receives initialization data relating to the first graph.

36. A system as set forth in claim 35 wherein the first agent node determines whether the initialization data has been received by the first agent node.

37. A system as set forth in claim 36 wherein the first agent node sets up an internal representation of the initialization data.

38. A system as set forth in claim 37 wherein the first agent node receives data representing task completion costs and task completion rewards.

39. A system as set forth in claim 38 wherein the first agent node determines whether the task completion costs have received.

40. A system as set forth in claim 39 wherein the first agent node forwards update data to a central authority node for maintaining update data, the update data representing local connections and dependencies.

41. A system as set forth in claim 40 wherein the first agent node forwards additional update data to the central authority node, the additional update data including remaining resources and task status.

42. A system as set forth in claim 41 wherein the first agent node calculates a desired output offer cost.

43. A system as set forth in claim 42 wherein the first agent node forwards outgoing offers of resources to the second agent node.

44. A system as set forth in claim 43 wherein the first agent node determines whether additional resources are required for completion of the first set of tasks.

45. A system as set forth in claim 44 wherein the first agent node calculates a desired resource bid cost.

46. A system as set forth in claim 45 wherein the first agent node forwards outgoing bids for resources to the second agent node.

47. A system as set forth in claim 46 wherein the first agent node receives an incoming offer of resources from the second agent node.

48. A system as set forth in claim 47 wherein the first agent node receives data representing incoming bids from the second agent node.

49. A system as set forth in claim 48 wherein the first agent node determines whether there are any acceptable bids from the second agent node.

50. A system as set forth in claim 49 wherein the first agent node affirmatively determines acceptable bids and forwards an outgoing acceptance.

51. A system as set forth in claim 50 wherein the first agent node determines no acceptable bids and receives incoming acceptances from the second agent node.

52. A system as set forth in claim 51 wherein the first agent node determines whether more resources are required for task completion by the first agent node.

53. A system as set forth in claim 52 wherein the first agent node searches the first graph for a path for task completion.