Apparatus and method for resource negotiations among autonomous agents

• US 20010042123A1
• Filed: 12/19/2000
• Published: 11/15/2001
• 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
• Granted Patent: US 6,842,899 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• 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 among autonomous agents for allocation of resources and comprising:

a communications network for passing messages between computers connected thereto;

a plurality of computers connected to said network for running programs thereon including at least first and second autonomous agents;

each said 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 and each said agent employs the associated said 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; and

,

said agents negotiate with each other for the resources needed to carry out the task or tasks to be performed by said agents.

2. A system as set forth in

claim 1

wherein each said agent additionally receives initialization data relating to the associated said graph.

3. A system as set forth in

claim 2

wherein each said agent determines whether said initialization data has been received.

4. A system as set forth in

claim 3

wherein if the determination is affirmative, then the agent sets up an internal representation respecting the initialization data.

5. A system as set forth in

claim 4

wherein said graph is a PN graph and said representation is a PN representation and each said agent calculates deadlock avoidance structures relating to said PN representation and graph.

6. A system as set forth in

claim 4

wherein each said agent receives cost data representing cost and task completion rewards.

7. A system as set forth in

claim 6

wherein each said agent determines whether said cost data has been received.

8. A system as set forth in

claim 7

wherein each said agent forwards update data to a central authority and wherein said update data represents local connections and dependencies.

9. A system as set forth in

claim 8

wherein each said agent additionally forwards additional update data to said central authority wherein said additional update data also includes data representing remaining resources and task status.

10. A system as set forth in

claim 9

wherein each said agent calculates desired output offer costs.

11. A system as set forth in

claim 10

wherein each said agent forwards outgoing offers of resources to other agent or agents.

12. A system as set forth in

claim 11

wherein each agent determines whether any additional resource or resources are needed for task completion by that agent.

13. A system as set forth in

claim 12

wherein each agent calculates desired resource bid cost if any additional resource or resources are needed.

14. A system as set forth in

claim 13

wherein each said agent forwards outgoing bids for resources to the other agent or agents.

15. A system as set forth in

claim 14

wherein each said agent receives incoming offers of resources from the other agent or agents.

16. A system as set forth in

claim 15

wherein each said agent receives data representing incoming bids from the other agent or agents seeking additional resource or resources.

17. A system as set forth in

claim 16

wherein each said agent determines whether there are any acceptable offers or bids from the other agent or agents.

18. A system as set forth in

claim 17

wherein each said agent making an affirmative determination respecting acceptable offers or bids and forwards an outgoing acceptance.

19. A system as set forth in

claim 17

wherein each agent that determines that there are no acceptable offers or bids receives incoming acceptances from the other agent or agents.

20. A system as set forth in

claim 19

wherein each agent determines if any more resources are required for task completion by that agent.

21. A system as set forth in

claim 20

wherein each agent that no longer needs resources searches the associated graph for a path for task completion and then completes that task.

22. A method operative in a distributed data processing system employing negotiation among autonomous agents for allocation of resources and employing a communications network for passing messages between computers connected thereto and wherein said computers are operative to run programs thereon including a central authority and at least first and second autonomous agents comprising the steps of:

each said agent receiving a graph associated therewith and representing for that agent what resources that agent has and what task or tasks that agent may use the resources for;

each said agent employing the associated said graph for determining what resource or resources are needed by that agent to carry out the task or tasks to be performed by that agent; and

,

said agents negotiating with each other for the resources needed to carry out the task or tasks to be performed by said agents.

23. A method as set forth in

claim 22

wherein the step of receiving a said associated graph includes the step at each agent of receiving initialization data relating to the associated said graph.

24. A method as set forth in

claim 23

including the step of determining if said initialization data has been received and if so sefting up an internal representation based on said initialization data.

25. A method as set forth in

claim 24

wherein said representation is an internal PN representation.

26. A method as set forth in

claim 25

including the step at each agent of calculating deadlock avoidance structures based on said PN representation.

27. A method as set forth in

claim 24

including the step of receiving cost data and determining whether the cost data has been received and if so then forwarding updated data to a central authority with said updated data including data representing local connections and dependencies.

28. A method as set forth in

claim 27

wherein said step of forwarding said updated data includes additional updated data representing the remaining resources and task status.

29. A method as set forth in

claim 28

including the step at each agency of calculating the desired output offer cost and forwarding outgoing offers to the other agent or agents.

30. A method as set forth in

claim 29

including the steps at each agent of determining whether any additional resources are needed to complete the task by that agent and f so calculating desired resource bid costs.

31. A method as set forth in

claim 30

including the step of forwarding outgoing bids for resources to the other agent or agents.

32. A method as set forth in

claim 31

including the steps at each agent of receiving incoming offers of resources and bids seeking additional resources from the other agent or agents and then determining at each agent whether any acceptable offers or bids have been received.

33. A method as set forth in

claim 32

including the step at each agent of forwarding outgoing acceptances if the determination of whether any acceptable offers or bids is affirmative.

34. A method as set forth in

claim 31

including the step at each agent of determining whether any more resources are needed.

35. A method as set forth in

claim 34

wherein each agent searches the associated graph for a path for task completion and then completes the task.

36. A computer program product operative in a distributed data processing system employing negotiation among autonomous agents for allocation of resources wherein the system includes a communications network for passing messages between computers connected thereto and wherein said computers are connected to said network for running programs thereon including at least two autonomous agents;

and comprising;

first and second autonomous agents, each said 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 use the resources for;

each said agent employs the associated said 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; and

,

said agents negotiate with each other for the resources needed to carry out the task or tasks to be performed by said agents.

37. A system as set forth in

claim 36

wherein each said agent additionally receives initialization data relating to the associated said graph.

38. A system as set forth in

claim 37

wherein each said agent determines whether said initialization data has been received.

39. A system as set forth in

claim 38

wherein if the determination is affirmative, then the agent sets up an internal representation respecting the initialization data.

40. A system as set forth in

claim 39

wherein said graph is a PN graph and said representation is a PN representation and each said agent calculates deadlock avoidance structures relating to said PN representation and graph.

41. A system as set forth in

claim 39

wherein each said agent receives cost data representing cost and task completion rewards.

42. A system as set forth in

claim 41

wherein each said agent determines whether said cost data has been received.

43. A system as set forth in

claim 42

wherein each said agent forwards update data to a central authority and wherein said update data represents local connections and dependencies.

44. A system as set forth in

claim 43

wherein each said agent additionally forwards additional update data to said central authority wherein said additional update data also includes data representing remaining resources and task status.

45. A system as set forth in

claim 44

wherein each said agent calculates desired output offer costs.

46. A system as set forth in

claim 45

wherein each said agent forwards outgoing offers of resources to other agent or agents.

47. A system as set forth in

claim 46

wherein each agent determines whether any additional resource or resources are needed for task completion by that agent.

48. A system as set forth in

claim 47

wherein each agent calculates desired resource bid cost if any additional resource or resources are needed.

49. A system as set forth in

claim 48

wherein each said agent forwards outgoing bids for resources to the other agent or agents.

50. A system as set forth in

claim 49

wherein each said agent receives incoming offers of resources from the other agent or agents.

51. A system as set forth in

claim 50

wherein each said agent receives data representing incoming bids from the other agent or agents seeking additional resource or resources.

52. A system as set forth in

claim 51

wherein each said agent determines whether there are any acceptable offers or bids from the other agent or agents.

53. A system as set forth in

claim 52

wherein each said agent making an affirmative determination respecting acceptable offers or bids and forwards an outgoing acceptance.

54. A system as set forth in

claim 53

wherein each agent that determines that there are no acceptable offers or bids then receives incoming acceptances from the other agent or agents.

55. A system as set forth in

claim 54

wherein each agent determines if any more resources are required for task completion by that agent.

56. A system as set forth in

claim 55

wherein each agent that no longer needs resources searches the associated graph for a path for task completion and then completes that task.