TASK ALLOCATION MECHANISMS AND MARKETS FOR ACQUIRING AND HARNESSING SETS OF HUMAN AND COMPUTATIONAL RESOURCES FOR SENSING, EFFECTING, AND PROBLEM SOLVING

• US 20100332281A1
• Filed: 06/26/2009
• Published: 12/30/2010
• Est. Priority Date: 06/26/2009
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric, Shahaf, Dafna
• Application Number:
  US12/493,146
• Publication Number:
  US 20100332281A1
• Time in Patent Office: Days
• US Class Current: 705/7.13
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A set of projects may be defined, each project having a set of tasks to be performed. In turn, each task may be mapped to a set of task capabilities that are involved in completing the task. A set of agents and components (potentially including both human agents and automated agent, and components for sensing and effecting action in the world) may also be defined, and each agent may have a set of agent capabilities representing skills, knowledge, resources, relationships, etc., that an agent may commit to a task. The tasks of the projects may be fulfilled by identifying coalitions of agents for respective tasks, featuring a sufficient set of agent capabilities corresponding to the task capabilities. This model may be used, e.g., in a matching service, whereby projects submitted by managers may be completed through an automated matching of tasks with a set of agents subscribing to the service.

Claims

1. A method of allocating an agent set comprising agents comprising at least one agent capability to perform at least one project, respective projects comprising at least one task, respective tasks involving at least one task capability, the method using a computer having a processor and comprising:

executing on the processor instructions configured to;

while at least one task of at least one project is unfulfilled;

select a coalition comprising at least one agent in the agent set, the agents of the coalition collectively comprising agent capabilities corresponding to the task capabilities of an unfulfilled task;

allocate the coalition to fulfill the task; and

remove the agents in the coalition from the agent set.

2. The method of claim 1, the instructions configured to:

receive from at least one manager at least one project involving at least one task, and

after allocating the coalitions to fulfill the tasks of the project, notify the manager of the coalitions allocated to the tasks of the project.

3. The method of claim 1, the instructions configured to, after receiving a project from the at least one manager, identify the at least one task comprising the project.

4. The method of claim 1, the agents selected from a set of agent types comprising at least one of:

a skill agent having an agent capability representing a skill;

a sensor agent having an agent capability representing a sensory output;

an effector agent having an agent capability representing a transformative effect;

a resource agent having an agent capability representing an access to a resource; and

a task evaluation agent having an agent capability representing a logical evaluation of a task.

5. The method of claim 1, the agent set comprising:

at least one human agent asserting at least one agent capability, and

at least one automated agent configured to perform at least one agent capability.

6. The method of claim 5, selecting an agent for a coalition comprising:

for at least one human agent asserting at least one agent capability corresponding to at least one task capability of at least one task, offering the task to the human agent; and

upon receiving from at least one human agent an acceptance of the task, selecting the agent for the coalition.

7. The method of claim 5, the instructions configured to generate the agent set by:

upon receiving a request from a human agent to be added to the agent set, the human agent asserting at least one capability;

testing the human agent in the agent capability with a capability test, and

upon the human agent passing the capability test, adding the human agent to the agent set.

8. The method of claim 1, comprising:

after allocating the coalition to fulfill the tasks of the projects, committing the coalitions to perform the tasks.

9. The method of claim 8, committing a human agent in a coalition to perform a task capability of the task comprising:

presenting to the human agent a game involving performing the task capability.

10. The method of claim 1:

respective agent capabilities of an agent having a capability proficiency, and

selecting the coalition comprising;

selecting a coalition maximizing the capability proficiencies of the agent capabilities of the agents corresponding to the task capabilities of the task.

11. The method of claim 10, at least one capability proficiency of at least one agent capability of at least one agent identified by:

training a learning function to identify capability proficiency s of agent capabilities in a proficiency training set, and

identifying the capability proficiency by applying the learning function to the at least one agent capability of the at least one agent.

12. The method of claim 1:

respective agent capabilities of an agent having a capability cost, and

selecting the coalition comprising;

selecting a coalition minimizing the capability costs of the agent capabilities of the agents corresponding to the task capabilities of the task.

13. The method of claim 1:

respective agent capabilities of an agent having a capability capacity;

respective task capabilities of a task having a capability consumption;

selecting the coalition comprising;

selecting a coalition comprising at least one agent in the agent set, the agents of the coalition collectively comprising agent capabilities that;

correspond to the task capabilities of the task, and

have a capability capacity satisfying the capability consumption of the task capability of the task;

allocating the coalition comprising;

for respective task capabilities of the task, reducing the capability capacity of the agent capability of the agent by the capability consumption of the task capability of the task; and

removing the agents in the coalition from the agent set comprising;

removing agents in the coalition having no remaining capability capacity of any agent capability from the agent set.

14. The method of claim 1:

respective tasks having a task start state to a task end state;

respective task capabilities and respective agent capabilities representing a transition from the task start state to the task end state; and

selecting the coalition comprising;

selecting a coalition comprising at least one agent in the agent set, the agents of the coalition collectively comprising agent capabilities that represent a transition sequence from the task start state to the task end state.

15. The method of claim 14, the coalitions selected to maximize a performance quality of the tasks computed according to the mathematical formula:

maxΣ

_iΣ

_{e to ti}f_i^out(e),

Σ

_ef_iⁱⁿ(e)≦

c_e,

Σ

_{e from si}f_iⁱⁿ(e)=d_i,

f_i^out(e)=w(e)·

f_iⁱⁿ(e),

Σ

_wf_i^out(w,u)=Σ

_wf_iⁱⁿ(u,v)u≠

s_i, t_i,

wherein;

s_i represents the task source state of a task i;

t_i represents the task end state of a task i;

c_e represents a capability capacity of an agent capability of an agent, the agent capability utilized at task state e;

f_iⁱⁿ(e) represents a performance quality of a task i entering a task state e;

f_i^out(e) represents a performance quality of a task i leaving a task state e;

d_i represents a starting performance quality at the task source state; and

w(e) represents a capability proficiency of an agent capability of an agent, the agent capability utilized at task state e.

16. The method of claim 15:

respective agent capabilities representing a duration for transitioning from the first task state to the second task state; and

selecting the coalition comprising;

selecting a coalition minimizing, for respective tasks, the duration of the transition sequence from the task start state to the task end state.

17. The method of claim 1, the instructions configured to:

for respective coalitions that may perform the task, calculate an expected utility of the task based on at least one potential task outcome of the coalition if allocated to fulfill the task; and

apply a decision-theoretic function to select a coalition maximizing the expected utility of the tasks of the project.

18. A system configured to allocate an agent set comprising agents comprising at least one agent capability to perform at least one project, respective projects comprising at least one task, respective tasks involving at least one task capability, the system comprising:

a task selecting component configured to select at least one unfulfilled task of at least one project;

a coalition selecting component configured to select a coalition comprising at least one agent in the agent set, the agents of the coalition collectively comprising agent capabilities corresponding to the task capabilities of the task selected by the task selecting component; and

an agent allocating component configured to;

allocate the coalition selected by the coalition selecting component to fulfill the task selected by the task selecting component, and

remove the agents in the coalition from the agent set.

19. The system of claim 18, comprising:

a task interpreting component configured to interpret a task received in a natural language into a formal task specification;

a task decomposition component configured to identify a subtask structure comprising at least one subtask;

a task planning component configured to invoke the task selecting component, the coalition selecting component, and the agent allocation component to, for respective subtasks, allocate a coalition to perform the subtask;

a task coordination component configured to, for respective subtasks, receive a subtask result from the coalition upon fulfilling the subtask; and

a task composition component configured to compile a task result from the subtask results.

20. A computer-readable medium comprising a set of processor-executable instructions that, when executed on a processor of a computer having access to agent set comprising agents comprising at least one agent capability having a capability proficiency and a capability cost, the agent set comprising at least one human agent asserting at least one agent capability and at least one automated agent configured to perform at least one agent capability, and the computer having access to at least one project, respective projects comprising at least one task, respective tasks involving at least one task capability, cause the processor to allocate the agents of the agent set to the tasks of the projects by:

receiving from at least one manager at least one project involving at least one task;

upon receiving a request from a human agent to be added to the agent set, the human agent asserting at least one capability;

testing the human agent in the capability with a capability test, and

upon the human agent passing the capability test, adding the human agent to the agent set;

while at least one task of at least one project is unfulfilled;

for respective coalitions that may perform the task, calculating an expected utility of a project based on at least one potential task outcome of the coalition if allocated to fulfill the task;

applying a decision-theoretic function to select a coalition maximizing the expected utility of the task, the coalition comprising at least one agent in the agent set, the agents of the coalition collectively comprising agent capabilities corresponding to the task capabilities of the task, and selecting a human agent comprising;

offering the task to the human agent; and

upon receiving from the human agent an acceptance of the task, selecting the agent for the coalition;

allocating the coalition to fulfill the task;

removing the agents in the coalition from the agent set, the coalitions selected to achieve at least one project preference selected from a set of project preferences comprising;

maximizing the capability proficiencies of the agent capabilities of the agents corresponding to the task capabilities of the task,

minimizing the capability costs of the agent capabilities of the agents corresponding to the task capabilities of the task, and

for respective tasks, minimizing agent capabilities of the coalition not corresponding to the task capabilities of the task;

after allocating the coalitions to fulfill the tasks of a project received from a manager;

committing the coalitions to perform the tasks of the project, and

notifying the manager of the coalitions allocated to the tasks of the project.