Real-time multi-agent response based on a preference-based consensus
A method and associated systems provide real-time response to a request received from a real-time system like a self-driving vehicle or a device that communicates interactively with its environment. The response is selected from a set of candidate feasible responses by a group of computerized agents that each sort the feasible responses in order of that agent's specific preferences, based on that agent's particular priorities or expertise. The agents then reconcile their differences through an iterative procedure. During each iteration, each agent decides whether to retain its current preferences or to adopt the preferences of another agent. This decision is made by determining which preferences are most similar to that agent's own initial preferences, and by which preferences would be most useful in helping to achieve that agent's particular goals. When the agents reach consensus, the group's most-preferred response is returned quickly enough to provide real-time, interactive response.
1. A real-time multi-agent system comprising a processor, a memory coupled to the processor, and a computer-readable hardware storage device coupled to the processor, the storage device containing program code configured to be run by the processor via the memory to implement a method for real-time multi-agent response based on a preference-based consensus, the method comprising:
the system receiving from a real-time application a request for a real-time response to a detected condition, where the requested response is selected by the system from a set of feasible responses;
the system forwarding the request to a set of computerized agents;
the system further receiving an initial preference from each agent,
where each agent's initial preference identifies an initial ordering of the set of feasible responses, and
where each agent's initial ordering ranks the set of feasible responses as a function of that agent's relative degree of preference for each response of the set of feasible responses;
the system identifying a consensus response of the set of feasible responses by iteratively reconciling the agents' initial orderings,
where each iteration of the reconciling attempts to reduce differences among the agents' initial orderings by:
the system identifying whether the agents' initial preferences are in agreement;
the system, whenever identifying that the agents' initial preferences are not in agreement:
the system directing each agent of the set of computerized agents to update its current preference as a function of the preferences most recently received by the system from other agents of the set of computerized agents,
where the directing a first agent of the set of computerized agents to update the first agent's current preference comprises associating the first agent's current preference with a utility value that comprises a private utility component and a public utility component,
where the utility value associated with the first agent is proportional to:
a total number of agents in the set of computerized agents,
a value of a Distance function that returns a degree of dissimilarity between the first agent's initial preference and the first agent's current preference,
values of a Similarity function that returns a degree of similarity between current preferences of each pair of agents of the set of computerized agents, and
a number of combinations of all possible orderings of the set of feasible responses, taken two at a time,
where the private utility component identifies a relative value to the first agent of the current preference of the first agent, and
where the public utility component identifies a relative value to the first agent of the current preferences of other agents of the set of computerized agents;
the system receiving from each agent of the set of computerized agents that agent's updated preference;
the system repeating the directing and the receiving the updated preferences until the system identifies that the set of computerized agents are in agreement; and
the system selecting the consensus response to be a response of the set of feasible responses that is that is associated, by the agents' most recently updated preferences, with a highest relative degree of preference; and
the system returning a real-time response to the real-time application that identifies the consensus response.
2. The system of claim 1 , where the reconciling further comprises:
the system, if identifying that the agents' initial preferences are in agreement, selecting the consensus response to be a response of the set of feasible responses that is associated, by the agents' initial preferences, with a highest relative degree of preference.
3. The system of claim 1 , where the system directs a first agent to update its current preference by directing the first agent to:
announce the first agent' s current preferences to other agents of the set of computerized agents;
compute a set of similarity values, where each similarity value of the set of similarity values is proportional to a degree of similarity between the first agent's initial preference and a current preference of another agent of the set of computerized agents;
select a subset of current preferences of other agents of the set of computerized agents, where the preferences comprised by the subset are each associated with a similarity value of the set of similarity values that exceeds a minimum threshold similarity value;
compute a set of utility values that each identifies a relative usefulness to the first agent of a preference of the subset of the current preferences;
select a most-useful preference of the subset of current preferences, where the most-useful preference is associated with a highest utility value associated with any preference of the subset of current preferences; and
update the first agent's current preference, by means of a random choice, to either become the most-useful preference or to remain unchanged.
4. The system of claim 1 , where the system directs a first agent to update its current preference by directing the first agent to:
announce the first agent' s current preferences to other agents of the set of computerized agents;
compute a set of utility values that each identifies a relative usefulness to the first agent of a current preference of an agent of the set of computerized agents;
compute a set of similarity values, where each similarity value of the set of similarity values is proportional to a degree of similarity between the first agent's initial preference and a current preference of another agent of the set of computerized agents;
select a subset of current preferences of other agents of the set of computerized agents, where the preferences comprised by the subset are each associated with a utility value of the set of utility values that exceeds a utility value, of the set of utility values, that is associated with the first agent;
select a most-similar preference of the subset of current preferences, where the most-similar preference is associated with a highest similarity value associated with any preference of the subset of current preferences; and
update the first agent's current preference, by means of a random choice, to either become the most-similar preference or to remain unchanged.
5. The system of claim 1 ,
where the system directing a first agent to update its current preference comprises associating the first agent's current preference with a set of similarity values,
where each similarity value of the set of similarity values is proportional to a degree of similarity between the first agent's initial preference and the current preference of another agent of the set of computerized agents, and
where a degree of similarity between two preferences is deemed to be greater when the two preferences order a greater number of feasible responses in a similar manner.
6. The system of claim 1 ,
where the real-time application comprises an Internet-of-Things controller that receives real-time information from a computerized Internet-of-Things device, and
where the computerized Internet-of-Things device requires from the system a real-time response to the received real-time information.
7. The system of claim 1 ,
where the real-time application comprises a vehicle controller that receives real-time information from a self-driving vehicle, and
where the self-driving vehicle requires from the system a real-time response to the received real-time information.
8. The system of claim 1 ,
where the system identifies the consensus response to be a response that is most preferred by the agents when the set of computerized agents reach agreement, and
where the set of computerized agents are deemed to have reached agreement when:
a subset, of the set of computerized agents, are each associated with a corresponding set of agent preferences,
where each of the corresponding sets consists of preferences that, when applied to a first subset of the feasible responses, ranks the first subset in an identical order,
where a number of agents in the subset of the set of computerized agents exceeds a first predetermined threshold value, and
where a number of responses in the first subset exceeds a second predetermined threshold value.
9. A method for real-time multi-agent response based on a preference-based consensus, the method comprising:
a real-time multi-agent system receiving from a real-time application a request for a real-time response to a detected condition, where the requested response is selected by the system from a set of feasible responses;
the system forwarding the request to a set of computerized agents;
the system further receiving an initial preference from each agent,
where each agent's initial preference identifies an initial ordering of the set of feasible responses, and
where each agent's initial ordering ranks the set of feasible responses as a function of that agent's relative degree of preference for each response of the set of feasible responses;
the system identifying a consensus response of the set of feasible responses by iteratively reconciling the agents' initial orderings,
where each iteration of the reconciling attempts to reduce differences among the agents' initial orderings by:
the system identifying whether the agents' initial preferences are in agreement
the system, whenever identifying that the agents' initial preferences are not in agreement:
the system directing each agent of the set of computerized agents to update its current preference as a function of the preferences most recently received by the system from other agents of the set of computerized agents,
where the directing a first agent of the set of computerized agents to update the first agent's current preference comprises associating the first agent's current preference with a utility value that comprises a private utility component and a public utility component,
where the utility value associated with the first agent is proportional to:
a total number of agents in the set of computerized agents,
a value of a Distance function that returns a degree of dissimilarity between the first agent's initial preference and the first agent's current preference,
values of a Similarity function that returns a degree of similarity between current preferences of each pair of agents of the set of computerized agents, and
a number of combinations of all possible orderings of the set of feasible responses, taken two at a time,
where the private utility component identifies a relative value to the first agent of the current preference of the first agent, and
where the public utility component identifies a relative value to the first agent of the current preferences of other agents of the set of computerized agents;
the system receiving from each agent of the set of computerized agents that agent's updated preference;
the system repeating the directing and the receiving the updated preferences until the system identifies that the set of computerized agents are in agreement and
the system selecting the consensus response to be a response of the set of feasible responses that is that is associated, by the agents' most recently updated preferences, with a highest relative degree of preference; and
the system returning a real-time response to the real-time application that identifies the consensus response.
10. The method of claim 9 , where the reconciling further comprises:
the system, if identifying that the agents' initial preferences are in agreement, selecting the consensus response to be a response of the set of feasible responses that is associated, by the agents' initial preferences, with a highest relative degree of preference.
11. The method of claim 9 , where the system directs a first agent to update its current preference by directing the first agent to:
announce the first agent's current preferences to other agents of the set of computerized agents;
compute a set of similarity values,
where each similarity value of the set of similarity values is proportional to a degree of similarity between the first agent's initial preference and a current preference of another agent of the set of computerized agents, and
where a degree of similarity between two preferences is deemed to be greater when the two preferences order a greater number of feasible responses in a similar manner;
select a subset of current preferences of other agents of the set of computerized agents, where the preferences comprised by the subset are each associated with a similarity value of the set of similarity values that exceeds a minimum threshold similarity value;
compute a set of the utility values;
select a most-useful preference of the subset of current preferences, where the most-useful preference is associated with a highest utility value associated with any preference of the subset of current preferences; and
update the first agent's current preference, by means of a random choice, to either become the most-useful preference or to remain unchanged.
12. The method of claim 9 , where the system directs a first agent to update its current preference by directing the first agent to:
announce the first agent's current preferences to other agents of the set of computerized agents;
compute a set of the utility values;
compute a set of similarity values,
where each similarity value of the set of similarity values is proportional to a degree of similarity between the first agent's initial preference and a current preference of another agent of the set of computerized agents, and
where a degree of similarity between two preferences is deemed to be greater when the two preferences order a greater number of feasible responses in a similar manner;
select a subset of current preferences of other agents of the set of computerized agents, where the preferences comprised by the subset are each associated with a utility value of the set of utility values that exceeds a utility value, of the set of utility values, that is associated with the first agent;
select a most-similar preference of the subset of current preferences, where the most-similar preference is associated with a highest similarity value associated with any preference of the subset of current preferences; and
update the first agent's current preference, by means of a random choice, to either become the most-similar preference or to remain unchanged.
13. The method of claim 9 ,
where the real-time application comprises an Internet-of-Things controller that receives real-time information from a computerized Internet-of-Things device, and
where the computerized Internet-of-Things device requires from the system a real-time response to the received real-time information.
14. The method of claim 9 ,
where the real-time application comprises a vehicle controller that receives real-time information from a self-driving vehicle, and
where the self-driving vehicle requires from the system a real-time response to the received real-time information.
15. The method of claim 9 , further comprising providing at least one support service for at least one of creating, integrating, hosting, maintaining, and deploying computer-readable program code in the computer system, wherein the computer-readable program code in combination with the computer system is configured to implement the receiving a request, the forwarding, the further receiving, the identifying a consensus response, the receiving each agent's updated preference, the repeating, the selecting, and the returning.
16. A computer program product, comprising a first non-transitory computer-readable hardware storage device having a computer-readable program code stored therein, the program code configured to be executed by a real-time multi-agent system comprising a processor, a memory coupled to the processor, and a second non-transitory computer-readable hardware storage device coupled to the processor, the second non-transitory storage device containing program code configured to be run by the processor via the memory to implement a method for real-time multi-agent response based on a preference-based consensus, the method comprising:
the real-time multi-agent system receiving from a real-time application a request for a real-time response to a detected condition, where the requested response is selected by the system from a set of feasible responses;
the system forwarding the request to a set of computerized agents;
the system further receiving an initial preference from each agent,
where each agent's initial preference identifies an initial ordering of the set of feasible responses, and
where each agent's initial ordering ranks the set of feasible responses as a function of that agent's relative degree of preference for each response of the set of feasible responses;
the system identifying a consensus response of the set of feasible responses by iteratively reconciling the agents' initial orderings,
where each iteration of the reconciling attempts to reduce differences among the agents' initial orderings by:
the system identifying whether the agents' initial preferences are in agreement;
the system, whenever identifying that the agents' initial preferences are not in agreement:
the system directing each agent of the set of computerized agents to update its current preference as a function of the preferences most recently received by the system from other agents of the set of computerized agents,
where the directing a first agent of the set of computerized agents to update the first agent's current preference comprises associating the first agent's current preference with a utility value that comprises a private utility component and a public utility component,
where the utility value associated with the first agent is proportional to:
a total number of agents in the set of computerized agents,
a value of a Distance function that returns a degree of dissimilarity between the first agent's initial preference and the first agent's current preference,
values of a Similarity function that returns a degree of similarity between current preferences of each pair of agents of the set of computerized agents, and
a number of combinations of all possible orderings of the set of feasible responses, taken two at a time,
where the private utility component identifies a relative value to the first agent of the current preference of the first agent, and
where the public utility component identifies a relative value to the first agent of the current preferences of other agents of the set of computerized agents;
the system receiving from each agent of the set of computerized agents that agent's updated preference;
the system repeating the directing and the receiving the updated preferences until the system identifies that the set of computerized agents are in agreement and
the system selecting the consensus response to be a response of the set of feasible responses that is that is associated, by the agents' most recently updated preferences, with a highest relative degree of preference; and
the system returning a real-time response to the real-time application that identifies the consensus response.
17. The computer program product of claim 16 , where the reconciling further comprises:
the system, if identifying that the agents' initial preferences are in agreement, selecting the consensus response to be a response of the set of feasible responses that is associated, by the agents' initial preferences, with a highest relative degree of preference.
18. The computer program product of claim 16 , where the system directs a first agent to update its current preference by directing the first agent to:
announce the first agent's current preferences to other agents of the set of computerized agents;
compute a set of similarity values,
where each similarity value of the set of similarity values is proportional to a degree of similarity between the first agent's initial preference and a current preference of another agent of the set of computerized agents, and
where a degree of similarity between two preferences is deemed to be greater when the two preferences order a greater number of feasible responses in a similar manner;
select a subset of current preferences of other agents of the set of computerized agents, where the preferences comprised by the subset are each associated with a similarity value of the set of similarity values that exceeds a minimum threshold similarity value;
compute a set of the utility values;
select a most-useful preference of the subset of current preferences, where the most-useful preference is associated with a highest utility value associated with any preference of the subset of current preferences; and
update the first agent's current preference, by means of a random choice, to either become the most-useful preference or to remain unchanged.
19. The computer program product of claim 16 , where the system directs a first agent to update its current preference by directing the first agent to:
announce the first agent's current preferences to other agents of the set of computerized agents;
compute a set of the utility values;
compute a set of similarity values,
where each similarity value of the set of similarity values is proportional to a degree of similarity between the first agent's initial preference and a current preference of another agent of the set of computerized agents, and
where a degree of similarity between two preferences is deemed to be greater when the two preferences order a greater number of feasible responses in a similar manner;
select a subset of current preferences of other agents of the set of computerized agents, where the preferences comprised by the subset are each associated with a utility value of the set of utility values that exceeds a utility value, of the set of utility values, that is associated with the first agent;
select a most-similar preference of the subset of current preferences, where the most-similar preference is associated with a highest similarity value associated with any preference of the subset of current preferences; and
update the first agent's current preference, by means of a random choice, to either become the most-similar preference or to remain unchanged.
20. The computer program product of claim 16 ,
where the real-time application comprises an Internet-of-Things controller that receives real-time information from a computerized Internet-of-Things device, and
where the computerized Internet-of-Things device requires from the system a real-time response to the received real-time information.
21. The computer program product of claim 16 ,
where the real-time application comprises a vehicle controller that receives real-time information from a self-driving vehicle, and
where the self-driving vehicle requires from the system a real-time response to the received real-time information.