Decentralized coordination of resource usage in multi-agent systems

• US 20070039004A1
• Filed: 08/15/2005
• Published: 02/15/2007
• Est. Priority Date: 08/15/2005
• Status: Abandoned Application

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Guralnik, Valerie, Wagner, Thomas, Phelps, John
• Application Number:
  US11/204,816
• Publication Number:
  US 20070039004A1
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources

Abstract

Systems and methods operable on a network to coordinate resource utilization amongst agents in a multi-agent systems in a decentralized manner. In one embodiment, this includes interconnected agents that circulate coordination keys amongst coordination group members. The coordination key includes information defining the coordination group, resources coordinated by group members, and information about scheduled resource utilization. In some embodiments, each agent in a coordination group determines its local schedule of resource utilization based on information in the coordination key to achieve its local goals while coordinating with other agents to achieve coordination group goals.

Claims

1. A system comprising:

a network;

a first group of agents operative on the network to coordinate resource utilization by multiple agents, wherein the first group of agents coordinate utilization of multiple resources, wherein each resource of the multiple resources can be utilized in a similar manner; and

a second group of agents operative on the network to coordinate resource utilization by multiple agents;

wherein the resource is of limited availability.

2. The system of claim 1, wherein the resource of limited availability is a one of a kind resource.

3. The system of claim 1, wherein a resource of the first or second groups belongs to an agent.

4. The system of claim 3, wherein the resource that belongs to an agent is a capability of the agent to perform a task.

5. The system of claim 1, wherein one of the resources is an item utilized in performance of a task.

6. The system of claim 5, wherein the item utilized in performance of a task includes one or more of a tool, a geographic space, a data processing resource, and a skill of an agent.

7. The system of claim 1, wherein the first group of agents and second group of agents each circulate a coordination key for their respective group, each coordination key including:

a member representation including a representation of each member of the respective coordination group;

a resource representation; and

preferred constraints on resource utilization.

8. The system of claim 7, wherein an agent extracts the preferred constraints on resource availability from a primary schedule of resource utilization included in the coordination key.

9. The system of claim 8, wherein each agent, upon receipt of the coordination key, determines if conflicts exist in the schedule and modifies its primary schedule to resolve any conflicts.

10. The system of claim 8, wherein the agent in possession of the coordination key further generates a secondary schedule within the coordination key as a proposal for schedule modifications.

11. The system of claim 10, wherein the secondary schedule is generated as a function of a quality value associated with each resource to be utilized and a quality-accumulation-function.

12. The system of claim 7, wherein the preferred extracted constraints include a deadline constraint by which one or more resource consuming tasks must be completed.

13. The system of claim 7, wherein the primary schedule is modified as a function of a quality value associated with each resource to be utilized.

14. The system of claim 1, wherein at least one of the members of the first group of agents is also a member of another group of agents.

15. The system of claim 1, further comprising:

an agent operative on the network capable of joining existing coordination groups and forming a new coordination group as needed.

16. A system to coordinate resource utilization by an agent in a multi-agent environment, the system comprising:

a network interface;

a memory;

a processor;

software stored in the memory and operable on the processor to cause the system to;

communicate with other agents over the network interface to coordinate resource utilization;

store a local schedule of the agent'"'"'s scheduled resource utilization in the memory;

receive a coordination key from another agent, wherein the coordination key includes;

a member representation identifying a coordination group of agents that coordinate resource utilization,

a resource representation identifying one or more resources,

a primary schedule of resource utilization, and

a secondary schedule of resource utilization;

resolve conflicts between the local schedule and the primary and the secondary schedules, wherein resolving conflicts includes modifying the local schedule and modifying the primary and the secondary schedules, further wherein conflict resolution decisions are made as a function of a cumulative quality value associated with resources scheduled to be utilized; and

forward the coordination key to another agent identified in the member representation over the network interface.

17. The system of claim 16, wherein the agent extracts primary constraints on resource availability from the primary schedule of the coordination key and extracts secondary constraints on resource availability from the secondary schedule, wherein the agent modifies the primary schedule as a function of the primary constraints and modifies the secondary schedule as a function of the secondary constraints.

18. The system of claim 17, wherein the extracted constraints of the primary and secondary schedules specify a deadline constraint by which one or more resource consuming tasks must be completed, further wherein the cumulative quality value associated with a resource is scaled as a function of the deadline constraint.

19. The system of claim 16, wherein the software is further operable on the system to coordinate resource utilization by the agent with multiple coordination groups, each coordination group defined in a coordination key of each respective coordination group.

20. The system of claim 16, wherein the software is further operable on the system to coordinate the resource utilization by the agent with a coordination group of agents that utilize the same or similar resources and to coordinate the resource utilization by the agent with a second coordination group of agents that utilize a one of a kind resource.

21. A method comprising:

receiving a coordination key from a member agent of a coordination group, wherein the coordination key specifies a period when resources are to be utilized by coordination group members and a deadline by which the coordination group members must release the resources to be utilized by other coordination group members;

scheduling resource utilization and resolving schedule conflicts in a schedule of the coordination key as a function of a quality value associated with each resource; and

forwarding the coordination key to another coordination group member.

22. The method of claim 21, wherein resolving schedule conflicts includes changing the schedule of a coordination group and notifying at least one other coordination group member of the schedule change.

23. The method of claim 21, further comprising:

generating a proposed schedule, wherein resource utilization in the proposed schedule is scheduled to increase the cumulative quality value from resource utilization, wherein the cumulative quality value is calculated as a function of a quality value associated with each respective resource and a deadline by which tasks utilizing resources must be completed.