CPGEI (Mestrado) Fernando Roberto Pereira - 28/07/11

DCOP MOASSÍ: Otimização de Restrição Distribuída em Problemas Contínuos de Fluxo em Rede pela Unificação da Discretização e Resolução

Resumo: Esta dissertação aborda a utilização do paradigma de Sistemas Multi-Agentes (MAS) na resolução do problema de transferência de derivados de petróleo da companhia Petrobrás, denominado Problema Simplificado de Transferência de Derivados de Petróleo em Rede Multimodal (PSTDPRM), que se caracteriza como um problema contínuo de fluxo em rede. O paradigma MAS é parte da subárea de Inteligência Artificial Distribuída (IAD) e tem sido objeto de estudo de pesquisadores nos últimos anos por oferecer meios de modelar e resolver problemas reais distribuindo informações do problema entre os agentes que compõem um sistema. Dentre as técnicas de otimização fundamentadas em agentes, aquelas referentes aos Problemas de Otimização de Restrição Distribuída (DCOP – Distributed Constraint Optimization Problem) têm se destacado por solucionarem problemas discretos com eficiência. Mediante as características do PSTDPRM (i.e. problema com variáveis contínuas), ao empregar-se o formalismo DCOP é necessário discretizar as variáveis contínuas, transformando o problema original em um novo problema, descaracterizando-o. A partir dessa problemática, este trabalho tem por objetivo estender a gama de problemas que podem ser resolvidos por algoritmos DCOP, propondo um modelo e um algoritmo (denominado DCOP MOASSÍ e MOASSÍ, respectivamente) para a resolução de problemas contínuos de fluxo em rede. O algoritmo MOASSÍ discretiza as variáveis contínuas em função de características inerentes ao problema ao mesmo tempo em que o soluciona. O MOASSÍ resolve o problema de maneira distribuída e assíncrona por meio da coordenação das decisões dos agentes no intuito de encontrar a solução ótima global avaliada por uma função objetivo. O presente trabalho compara dois métodos de resolução combinatórios, Dynamic Programming OPtimization (DPOP) e MOASSÍ, em uma série de cenários aplicados no PSTDPRM. Os resultados obtidos na comparação dos algoritmos demonstram que o MOASSÍ obteve resultados equivalentes ou melhores que o DPOP. Como contribuição, o trabalho apresenta um modelo e um algoritmo combinatório formulado com DCOP para resolução de problemas lineares em que as equações e inequações não apresentam coeficientes.
Palavras-chave: Inteligência Artificial Distribuída. Sistemas Multiagentes. Problema de Otimização de Restrições Distribuídas.

DCOP MOASSÍ: Distributed Constraint Optimization in continuous problems of network flow by the unification of the discretization and resolution

Abstract: This work uses the Multi-Agent Systems (MAS) paradigm in the resolution of transporting problems of petrol derivatives at Petrobrás. This problem is nominated as the Simplified Problem of Transporting of Petrol Derivatives in Multimodal Networks (SPPDTMN) and it is characterized as a continuous problem of network flow. The MAS paradigm is part of the Distributed Artificial Intelligence (DAI) and it has been studied by researchers in the last years because it allows for modeling and solving real problems with agents having partial information about the problem to be solved. Among the techniques used for optimization based on agents, those related to the Distributed Constraint Optimization Problem (DCOP) have been highlighted because they are able to efficiently solve discrete problems. By the characteristics of the (SPPDTMN), i.e., a problem with continuous variables, it is necessary to discretize the continuous variables in order to apply the formalism DCOP, thus transforming the original problem into a new one. From this problematic, this work has the purpose of extend the class of problems that can be solved by DCOP algorithms, proposing a model and an algorithm (named as DCOP MOASSÍ and MOASSÍ, respectively) for the resolution of continuous network flow problems. The MOASSÍ algorithm transforms continuous variables into discrete ones (using inherent features of the problem) at the same time that it solves the problem. MOASSÍ solves the problem in a distributed and asynchronous way by coordinating the decisions of the agents with the purpose of finding the global optimal solution evaluated by an objective function. This work also compared two combinatory methods of resolution Dynamic Programming Optimization (DPOP) and MOASSÍ in applied sceneries of the SPPDTMN. The results of the comparison show that the performance of MOASSÍ is equivalent to or better than DPOP. As a contribution, this work presents a model and a combinatory algorithm formulated with the DCOP for the resolution of linear problems where equations and inequations do not present coefficients.
Keywords:
Distributed Artificial Intelligence. Multi-Agent System. Distributed Constraint Optimization Problem.

Lista de publicações:
PEREIRA, F. R. ; BANASZEWSKI, R. F. ; SIMAO, J. M. ; TACLA, C. A. . Método Baseado em Detecção de Mudanças para Determinar Preço de Oferta de Pedidos de Clientes no Ambiente TAC-SCM. In: IV Workshop-Escola de Sistemas de Agentes, seu Ambiente e apliCações, 2010, Rio Grande - RS. IV WESAAC, 2010.