Sistemas Multi-Agentes no Desenvolvimento de um
Protótipo de um Sistema de Logística

Alexandre Leopoldo Gonçalves¹

Jomi Fred Hübner²

Resumo

Este artigo faz uma breve introdução a Inteligência Artificial Distribuída (IAD) demonstrando a aplicação de seus princípios na resolução de problemas, ou seja, se a solução pode ser alcançada pela cooperação entre agentes, sugerindo um estudo de caso na área de logística. O protótipo visa implementar um sistema de distribuição de produtos entre fábricas e mercados onde a solução é alcançada pela troca de mensagens entre os agentes participantes. Para modelar a comunicação entre os agentes é proposta uma linguagem de descrição de protocolo utilizando-se de diagramas de transição de estados (DTE). Para a implementação utilizou-se a linguagem Java devido as suas facilidades para projetar aplicações em rede.

Palavras-chaves: Inteligência Artificial Distribuída, Sistemas Multiagentes, Resolução Distribuída de Problemas, Protocolo de Comunicação.

Abstract

This article introduces Distributed Artificial Intelligence (DAI), showing principles in the problem-solving, where the solution of problem can be reached with the cooperation among agents, suggesting a case study in the logistic area. The prototype suggests to implement a product distribuition system among factories and markets, where the solution is reached throught of messages exchange. To model the communication among agents is showed a protocol description language using states transition diagrams (STD). The Java language is used to implementation the system due to its project network aplication facilities.

1. Introdução

A maioria das pesquisas de IA sobre comportamentos inteligentes está aumentando devido ao recente desenvolvimento de computadores paralelos poderosos, a proliferação de redes de computadores e o reconhecimento de que as ações humanas e a resolução de problemas envolvem mais do que uma pessoa. A Inteligência Artificial Distribuída (IAD) é um subcampo da IA preocupada com a cooperação, coordenação e interação na IA evoluindo da visão individual para a coletiva.

Segundo [GAS88], [GAS90], pode-se distinguir duas principais áreas da IAD: Resolução Distribuída de Problemas (RDP) e Sistemas Multiagentes (SMA). A RDP é o estudo de técnicas para dividir o trabalho de resolução de um problema particular em muitos módulos que cooperam pela interação e compartilhamento de conhecimento sobre este problema. Na RDP, os agentes são criados em função e conforme a necessidade do problema proposto. Segundo [JEN94], a RDP pode ser caracterizada em três fases como mostrado na figura 1.1. Na primeira fase, o problema (P) é continuamente decomposto pelo projetista até que subtarefas sejam geradas. Em seguida, os subproblemas individuais são resolvidos por agentes que se comunicam e cooperam quando necessário. Finalmente, os resultados dos subproblemas são integrados para produzir uma solução global (S).

Figura 1.1 - Resolução distribuída de problemas.

Os SMA preocupam-se com procedimentos inteligentes coordenados entre uma coleção de agentes inteligentes autônomos, como estes podem coordenar seus conhecimentos, metas, habilidades e planos conjuntamente para obter informações ou resolver problemas [BON88]. Nos SMA os agentes já existem e interagem entre si para resolver problemas buscando uma solução global. A interação entre os agentes acontece ou pela troca de mensagens ou por quadros negros (áreas comuns de armazenamento de dados utilizadas pelos agentes).

2. Descrição de Protocolos de Comunicação

O processo de comunicação entre entidades são essenciais para a cooperação na busca de solução para um problema. Este processo é guiado por protocolos visando identificar, simplificar e normalizar tarefas dentro de um contexto. Nesse sentido, um SMA possui protocolos de comunicação que determinam o comportamento de interação entre os agentes.

A comunicação entre agentes está baseada em mensagens. Em [WOO94], é feita uma abordagem levando em conta a troca ou passagem de mensagens entre agentes, sendo apresentado três formas:

mensagens ponto-a-ponto: este tipo de mensagem é muito utilizado em sistemas concorrentes baseados-em-objetos. As mensagens são enviadas para um endereço específico (o receptor) que é conhecido pelo transmissor. Isto representa vantagens uma vez que o transmissor sabe para quem a mensagem está sendo enviada e os controles de segurança são mais facilmente implementados;
mensagens broadcast: não se baseia na passagem para um endereço específico, mas para todos os agentes que participam do sistema. Contudo este tipo de passagem de mensagem não é seguro uma vez que todos os agentes podem verificar o conteúdo de uma mensagem;
mensagens multicast: diferente do broadcast este método visa a passagem de mensagens para um grupo de agentes. Desta maneira quando se deseja informar uma mensagem para um agente, a mensagem é enviada para o grupo que esse faz parte.

A especificação do protocolo de comunicação proposto é descrito por diagramas de transição de estados, onde a troca de informações entre os agentes promove mudanças de estados. Esta troca é efetuada através de mensagens que possuem o formato mostrado na tabela 2.1.

Tabela 2.1 - Formato da Mensagem do Protocolo de Comunicação.

Identificador	Descrição
Origem	é o identificador do tipo do agente, caso a mensagem seja para todos os agentes de um tipo, estes utilizam-se do símbolo "
Tipo	identifica o estado da mensagem, sendo inform quando um agente informa uma mensagem para outro, request quando um agente requisita uma informação ou reply quando um agente responde a uma requisição efetuada por outro agente
Mensagem	conteúdo que será trocado entre os agentes
Destino	segue a descrição do identificador origem
Pré-condições	fatos que devem ser verdade no mundo do agente para este enviar ou receber uma mensagem
Pós-condições	fatos que passam a ser verdade no mundo do agente após ter enviado ou recebido uma mensagem

3. Uma visão de Logística

Nos dias atuais tem-se falado muito em logística. Isto deve-se a uma crescente preocupação com os custos nas empresas, a competição por mercados consumidores, necessidade de garantir prazos visando oferecer melhores serviços e, por último, a globalização da economia mundial. Esta por sua vez representa um dos maiores desafios levando em consideração o Mercosul, onde as indústrias e empresas nacionais preocupam-se cada vez mais com a concorrência.

A logística estuda como prover melhores níveis de rentabilidade nos serviços de distribuição aos clientes e consumidores, através de planejamento, organização e controle efetivo para as atividades de movimentação e armazenagem visando facilitar o fluxo de produtos [BAL93]. Tendo como uma das principais preocupações a distribuição, uma vez que produtos e clientes muitas vezes encontram-se separados geograficamente, a logística visa minimizar a separação que existe entre oferta e demanda, procurando atender o cliente da melhor maneira possível.

Segundo [BAL93] existem três objetivos logísticos chaves:

transportes: representa a atividade mais importante pois absorve a maior parte dos custos logísticos. É primordial pois nenhuma empresa consegue movimentar cargas sem ter que transportá-las por via térrea, ferroviária, marítima ou aérea;
manutenção de estoques: toda indústria possui um grau razoável de disponibilidade de produtos para regular a oferta e a demanda. Essa administração deve preocupar-se em manter os níveis de estoque pequenos sem afetar o atendimento aos clientes;
processamento de pedidos: representa o passo inicial para a efetividade do processo. A rapidez que este processo é realizado representa aumento ou diminuição no tempo para entrega de mercadorias sendo de suma importância para a satisfação do cliente e um fator decisivo na redução do tempo.

É certo que os processos logísticos determinam fatores importantes na administração de empresas pois lidam diretamente com o principal indicador de aceitação de determinado produto, o consumidor final. Para tal é necessário processos capazes de atender com rapidez determinado mercado ou usuário final visando minimizar custos e tempos.

A logística ocupa uma posição intermediária entre a produção e marketing [BAL93] dividindo funções e promovendo uma integração no processo administrativo de empresas (figura 3.1) visando a integração e o bom funcionamento das áreas em questão.

Figura 3.1 - Visão geral das atividades logísticas.

Nos últimos anos, a distribuição de produtos tornou-se um fator chave para as empresas tendo em vista que a distribuição é determinante no processo de obtenção de resultados positivos ou negativos. O sistema de distribuição de produtos de uma empresa é importante e muitas vezes complexo, pois este constitui parte integrante na análise de custos da atividade industrial e comercial.

Contudo, é certo que muitas empresas de pequeno e médio porte não possuem análises visando identificar o quanto realmente representa o custo do transporte em seu produto final ou o quanto é importante a satisfação do cliente aliado a redução de custos, pois muitas vezes faltam recursos tecnológicos ou humanos capazes de mensurar com precisão tais custos. Para minimizarem tais problemas é de grande importância que empresas possuam ferramentas capazes de auxiliar em questões de aspecto financeiro.

4. Estudo de Caso : Sistema de Distribuição de Produtos

Para validar e testar soluções para problemas reais utilizando-se de agentes, é apresentada uma implementação visando solucionar o problema de distribuição de produtos entre várias fábricas e vários mercados, levando em consideração algumas restrições deste ambiente.

4.1 Descrição do Problema

existem várias fábricas e vários mercados que desejam distribuir ou receber determinado produto;
cada fábrica possui ofertas de produtos com seus custos unitários;
cada mercado possui demandas de produtos;
existem distâncias a serem consideradas entre os vários pontos (fábricas e mercados);
para cada produto existe um custo unitário que multiplicado pela distância entre o ponto origem e destino resulta no custo total de transporte por produto.

4.2 Especificação do Protocolo de Comunicação

Para o desenvolvimento do trabalho é apresentada uma especificação do protocolo de comunicação usado pelos agentes do sistema. O sistema é composto por quatro modelos de agentes: o agente servidor que gerencia e monitora as transações do sistema, agentes do tipo fábrica que oferecem produtos, agentes do tipo mercado que recebem ofertas e agentes interfaces que possibilitam a entrada de dados pelo usuário. A tabela 4.1 mostra as notações utilizadas.

Tabela 4.1 - Notação Utilizada nas Mensagens do Protocolo.

Notação	Abreviação
Agente Servidor	S
Agente Fábrica	F
Agente Mercado	M
Interface da Base de Conhecimento	BC
Interface de Distâncias	D
Interface de Consulta	C
Para toda Fábrica e Mercado	" F+M
Para toda Fábrica	" F

O protocolo é representado através de estados onde cada estado possui uma numeração identificando uma ação junto aos agentes e a transição de um estado para outro ocorre com o recebimento ou envio de mensagens. O formato da mensagem já foi apresentado na tabela 2.1. A figura 4.1 mostra o protocolo a nível do agente Servidor sendo composto por dez estados:

estado E0: representa o estado de espera onde o servidor fica monitorando todas as requisições dos agentes interfaces ou mensagens do agentes dos sistema que participam da solução;
estado E1: o agente S passa para este estado quando recebe uma mensagem da interface BC informando a base de conhecimento de cada agente. Recebida a mensagem, o agente S efetua a criação dos agentes e guarda sua localização. Após isso devolve uma mensagem de confirmação do recebimento e retorna para o estado de espera;
estado E2: o agente S passa para este estado quando recebe da interface D uma mensagem informando as distâncias entre todos os agentes F e M do sistema. Então a mensagem é acrescida do identificador "Distancia" e enviada para todos os agentes F;
estado E3: este é um estado intermediário pois apenas compõem a mensagem de requisição da base de conhecimento para todos os agentes F e agentes M contendo o identificador "Requisita";
estado E4: é um estado onde o agente S espera pelas respostas de todos os agentes F e M que estão enviando suas bases de conhecimento;
estado E5: o agente S passa para este estado quando começa a receber as mensagens dos agentes F e agentes M com suas bases de conhecimento. Após isso compõem uma mensagem única contendo a base de todos os agentes e informa esta base para todos os agentes F do sistema voltando para um estado de espera;
estado E6: representa o estado que inicializa a solução enviando para cada agente F uma mensagem contendo o identificador "RequisitaO";
estado E7: o agente S passa para este estado após ter informado aos agentes F para começarem a resolução do problema. Neste estado chegam as mensagens dos agentes F contendo a oferta a ser distribuída para cada produto;
estado E8: neste estado o agente S identifica o destino de cada mensagem de oferta informando ao agente M correspondente para que este possa suprir sua demanda. Após isso retorna ao estado anterior para receber novas informações dos agentes F até que o processo esteja finalizado. Este estado também constitui-se em um estado de espera que aguarda as soluções (demandas utilizadas) vindas dos agentes M ou requisições da interface C. O conjunto de todas as respostas enviadas pelos agentes M formará o resultado da solução do problema;
estado E9: o agente S passa para este estado após receber uma requisição da solução do problema. Então identifica qual interface C requisitou a solução e devolve uma mensagem que será apresentada ao usuário.

Figura 4.1 - Protocolo de comunicação do agente servidor.

A figura 4.2 mostra o protocolo a nível do agente Fábrica sendo composto por cinco estados:

estado E0: representa o estado de espera onde o agente F monitora todas as informações iniciais vindas do agente S;
estado E1: o agente passa para este estado quando começa a receber informações do agente S sobre as distâncias entre os agentes F e agentes M. Ainda nesse estado, as informações são armazenadas a fim de possibilitarem a melhor distribuição dos diversos produtos;
estado E2: o agente passa para este estado quando começa a receber mensagens vindas do agente S requisitando a base de conhecimento. Então o agente compõem uma mensagem contendo toda a sua base;
estado E3: o agente passa para este estado após ter enviado a mensagem contendo sua base de conhecimento;
estado E4: este estado acontece quando o agente recebe a mensagem do agente S contendo a base de todos os outros agentes. Esta base mais as distâncias possibilitam que o agente escolha qual o melhor produto a distribuir e para quem. Nesse ponto o agente F começa o processo de resolução e tendo efetuado uma escolha passa a informar para o agente S as ofertas e para quem devem ser enviadas. Esse processo se repete até que não haja mais quantidades de produtos a distribuir ou a solução ideal tenha sido encontrada. Após isso o agente F passa para um estado de espera.

Figura 4.2 - Protocolo de comunicação do agente fábrica.

A figura 4.3 mostra o protocolo a nível do agente Mercado sendo composto por quatro estados:

estado E0: representa o estado de espera onde o agente M monitora todas as requisições vindas do agente S;
estado E1: o agente M passa para este estado quando recebe uma mensagem do servidor requisitando sua base de conhecimento. Então uma mensagem é composta contendo toda a sua base que será enviada para o agente S para que este formule uma base geral;
estado E2: o agente M passa para este estado após ter respondido ao agente S informando a sua base de conhecimento;
estado E3: o agente M passa para este estado após receber as ofertas do agente S. Nesse momento o agente atualiza sua base e repete o procedimento até que as demandas de todos os produtos estejam satisfeitas ou até que não haja mais ofertas vindas do servidor. Após isso o agente volta para um estado de espera.

Figura 4.3 - Protocolo de comunicação do mercado.

4.3 Esboço do Funcionamento do Sistema

O sistema é composto por agentes fábricas e agentes mercados sendo criados e gerenciados por um agente servidor. Tais agentes interagem trocando mensagens objetivando a melhor distribuição dos diversos produtos de cada fábrica nos diversos mercados levando em consideração a oferta de cada fábrica, a demanda de cada mercado, o valor do frete de cada produto e a distância da fábrica em relação ao mercado (figura 4.4). Existem ainda agentes interfaces (base de conhecimento, distância e consulta) que tem como função a consulta e a manipulação da base de conhecimento.

Figura 4.4 - Modelo para otimização da distribuição de produtos.

5. Implementação do Protótipo

O protótipo foi projetado em Java utilizando-se basicamente de sockets e threads. É composto por três módulos sendo o primeiro o servidor, o segundo o cliente (base de conhecimento, distância e consulta) e o último o módulo agente.

5.1 Módulo servidor

O módulo servidor constitui-se de uma aplicação Java que tem função de facilitador da comunicação entre os diversos agentes que participam do sistema realizando as seguintes tarefas: controle das requisições de conexões dos clientes, inicialização dos agentes, gerenciamento e roteamento de mensagens e armazenamento dos endereços de cada agente.

5.2 Módulo cliente

O módulo cliente constitui-se de três applets sendo estes responsáveis pela entrada de dados e consultas para o usuário. O primeiro applet (figura 5.1) é responsável pela manutenção da base de conhecimento dos agentes. Nesta tela são informados o tipo de agente que se deseja inserir no ambiente (agente fábrica ou mercado), o nome do agente e as expressões, onde cada expressão constitui uma linha única na base de conhecimento do agente.

O segundo applet é responsável pela manutenção da base de distâncias. Nesta tela são informadas todas as combinações de distâncias entre agentes fábricas e mercados. As informações referentes à base de distâncias são armazenadas nos agentes do tipo fábrica sendo necessárias para o processo de escolha onde os agentes decidem para quem enviar determinado produto levando-se em conta o menor custo de distribuição. O último applet possibilita a consulta do resultado da otimização por parte do usuário.

Figura 5.1 - Tela para manutenção da base de conhecimento dos agentes.

5.3 Módulo agente

Este módulo tem instâncias de agentes do tipo fábrica ou mercado e tem como funções o armazenamento da base de conhecimento dos agentes do sistema, o armazenamento das distâncias entre os pontos de origem e destino.

Na resolução do problema, cada agente se comporta conforme o protocolo de comunicação especificado. Os agentes tipo fábrica tomam iniciativa na resolução do problema oferecendo certa quantidade de produtos para as requisições feitas pelos mercados. A troca de mensagens se repete até que todos os agentes do tipo mercados tenham suprimidos suas demandas ou que os agentes fábricas não possuam mais ofertas de seus produtos. Após o término, o agente servidor terá a informação do resultado da otimização sendo então possível a consulta.

6. Conclusões

Este trabalho apresenta uma introdução a IAD, tendo como enfoque principal a utilização de Sistemas Multiagentes na solução de problemas reais. O problema de distribuição de produtos foi implementado utilizando-se de um modelo logístico onde cada fábrica e mercado constitui um agente que compartilha informações buscando uma solução global.

Cada agente dentro do sistema possui sua própria base de conhecimento sendo composta por produtos, quantidades de oferta e custos unitários para agentes do tipo fábrica e de produtos e quantidades de demanda para agentes do tipo mercado. Para chegarem a uma solução os agentes fábricas guardam uma base de todos os agentes do sistema possibilitando assim identificar a solução para o problema de distribuição.

Para a implementação do trabalho utilizou-se a linguagem Java devido as suas características distribuídas possibilitando a implementação de agentes executando sob uma rede TCP/IP. O sistema foi implementado utilizando-se de comunicação síncrona onde cada agente (Fábrica ou Mercado) possui uma ligação com o agente Servidor.

Um fator importante para o sistema é o protocolo de comunicação entre os agentes. Neste trabalho foi apresentado um modelo utilizando-se de diagramas de transição de estados (DTE) onde a comunicação entre os agentes é realizada pela troca de mensagens sendo que os agentes mudam de estados sob determinadas condições.

O estudo de caso apresentado constitui-se em um modelo que considera quatro restrições: a oferta, a demanda, o custo unitário de cada produto e a distância entre as várias fábricas e mercados. Contudo estas restrições permitem que os agentes apenas efetuem procedimentos de escolha simples e não negociações para chegarem a uma solução. Restrições de negociação poderiam ser fatores de credibilidade do cliente ou prazos de entrega.

A partir da experimentação realizada verificou-se que, para o problema de logística colocado, um Sistema Multiagente gera uma boa solução em um tempo de resposta excelente. Além disso, a principal vantagem desta abordagem de especificação é a semelhança do funcionamento do modelo implementado com a realidade.

7. Referências

Logística empresarial

[BON88] BOND, A.H.; GASSER, L. (Eds.) Readings in distribuited artificial intelligence. California : Morgan Kaufmann, 1988.

[GAS88] GASSER, Les. Distribution and coordination of tasks among intelligent agents. In: PROCEEDINGS OF THE IJCAI'88. Scandinavian Conference on AI. Amsterdam, Springfield, 1988.

[GAS90] GASSER, Les. Social conceptions of knowledge and action: DAI foundations and open systems semantics, In: ARTIFICIAL INTELLIGENCE, 47. Elsevier Science Publishers, University of Southern California, Los Angeles, 1990. p. 107-138.

[JEN94] JENNINGS, Nick. Cooperation in industrial multi-agent systems. Singapore : World Scientific, 1994.

[WOO94] WOOLDRIDGE, Michael J.; JENNIGS, Nicholas R. Agent theories, architectures, and languages: a survey. In: PROCEEDINGS OF ECAI 94 WORKSHOP ON AGENT THEORIES, ARCHITECTURES & LANGUAGES. Amesterdam The Netherlands, 1994. p. 1-32.