Coordenação Multiagente

Como alocar trabalho entre agentes especializados sob restrições de capacidade e custo?

Agentes especializados diferem no custo de cada tarefa e na capacidade. Alocar por ordem de chegada desperdiça as boas correspondências e sobrecarrega alguns agentes.

Alocação é um problema de designação. Há algoritmos exatos em tempo polinomial, então um coordenador pode comparar a sua alocação com o ótimo e saber o preço de uma regra simples.

x_ij vale 1 se a tarefa i vai para o agente j, c_ij é o custo dessa correspondência e k_j a capacidade do agente j.

1. Estimar o custo de cada par tarefa-agente.

2. Expandir cada agente em vagas de capacidade.

3. Resolver a designação exatamente (método húngaro).

4. Comparar com a regra simples usada hoje.

1. Tarefas

2. Estimativas de custo

3. Vagas de capacidade

4. Solucionador de designação

5. Despacho

6. Registro de resultados

Nenhum experimento publicado. O laboratório de Coordenação Multiagente compara uma regra gulosa com o ótimo exato em matrizes de custo sintéticas.

Coordenação Multiagente

Nenhum resultado original de pesquisa é afirmado. Esta área é apresentada como perspectiva técnica, com uma demonstração computável sobre dados sintéticos.

• Os custos precisam ser estimados; estimativas erradas dão a resposta ótima ao problema errado.
• Designação estática ignora tarefas que chegam depois.
• Dependências entre tarefas pedem modelos mais ricos.

Leitura de fundamentação de outros autores. Não são publicações da Menlo Tech, e nenhum artigo da Menlo Tech é citado porque nenhum foi publicado.

• Kuhn, H. "The Hungarian method for the assignment problem." Naval Research Logistics Quarterly 2(1-2), 1955.
• Wooldridge, M. An Introduction to MultiAgent Systems, 2nd ed. Wiley, 2009.