| |
| Acadêmico(a): Fernando dos Santos |
| Título: Implementação Distribuída do Algoritmo Adopt |
| |
| Introdução: |
| A ´area de Inteligˆencia Artificial (IA) tem assistido nos ´ultimos anos um significativo avan¸co cient´ifico no que diz respeito a Sistemas Multi-Agentes (SMA). Com o advento das redes de computadores, muitas informa¸c˜oes, antes centralizadas, encontram-se distribu ´idas entre v´arios computadores interligados. Com isso, muitos problemas existentes na IA e at´e ent˜ao resolvidos com computa¸c˜ao centralizada tiveram que ser revistos, pois agora estavam localizados em um ambiente distribu´ido que nem sempre permite a centraliza ¸c˜ao das informa¸c˜oes. Na maioria dos novos paradigmas e algoritmos desenvolvidos para solucionar este problema, o conceito de SMA ´e aplicado, proporcionando a expans˜ao do universo dos SMA tamb´em para a ´area de Computa¸c˜ao Distribu´ida. Agentes de um SMA que antes eram executados em um ´unico computador e disputavam o mesmo processador agora podem ser distribu´idos em diversos computadores interligados, proporcionando um paralelismo de execu¸c˜ao ainda maior. Uma das classes de problemas que foi revista para operar em ambientes distribu´idos foi a dos problemas de satisfa¸c˜ao de restri¸c˜ao. Simplificadamente, um Constraint Satisfaction Problem (CSP) consiste de um conjunto de vari´aveis e um conjunto de restri¸c˜oes que influenciam a determina¸c˜ao dos valores para estas vari´aveis, cuja solu¸c˜ao ´e encontrada quando cada vari´avel assume um valor que satisfa¸ca as restri¸c˜oes. Graficamente, costuma-se representar um CSP atrav´es de um grafo de restri¸c˜oes, conforme ´e apresentado na fig. 1.1, que ilustra um CSP com trˆes vari´aveis({x1, x2, x3}) e duas restri¸c˜oes (v´ertices e arestas do grafo, respectivamente). Quando um CSP est´a em um ambiente distribu´ido, ´e chamado de Distributed Constraint Satisfaction Problem (DCSP), e Yokoo (2001) apresenta trˆes algoritmos ass´incronos distintos para solucionar um DCSP, denominados Asynchronous Backtracking (AB), Asynchronous Weak Commitment (AWC) e Branch and Bound (BB). O GRUPO DE INTELIGˆENCIA ARTIFICIAL DA FURB (2005) disponibiliza um framework, chamado dynDCSP, com a implementa¸c˜ao destes trˆes algoritmos, realizadas de maneira a possibilidar sua execu¸c˜ao em ambientes distribu´idos compostos por v´arios hosts. Por´em, um CSP (e conseq¨uentemente um DCSP) n˜ao ´e suficiente para especificar determinados tipos de problemas onde ´e necess´ario encontrar a melhor solu¸c˜ao, e n˜ao apenas qualquer solu¸c˜ao (como ocorre por exemplo no problema de agendamento de tarefas). Nestes casos, ´e necess´ario utilizar uma extens˜ao de CSP, denominada de problema de otimiza¸c˜ao de restri¸c˜oes. Um Constraint Optimization Problem (COP) considera um custo para cada solu¸c˜ao poss´ivel, e o objetivo ´e encontrar uma solu¸c˜ao de custo ´otimo. Para se solucionar um COP, Tsang (1993, p. 301) apresenta um algoritmo centralizado, denominado BB, cujo princ´ipio de funcionamento ´e baseado em um custo global que serve de parˆametro para poda em uma busca em profundidade. Um COP em ambiente distribu´ido ´e denominado de Distributed Constraint Optimization Problem (DCOP). Modi (2003b, p. 20) comenta que um algoritmo existente para solucionar um DCOP ´e o Synchronous Branch and Bound (SBB). Por´em, como o pr´oprio nome do algoritmo revela, ´e s´incrono, o que faz com que o algoritmo n˜ao utilize o potencial do paralelismo de uma execu¸c˜ao distribu´ida. Em fun¸c˜ao disto, Modi (2003b) apresenta o primeiro algoritmo ass´incrono para solucionar DCOP, denominado Asynchronous Distributed Optimization (Adopt). O algoritmo Adopt utiliza o conceito de limiares (inferior e superior) de solu¸c˜ao parcial para refinar a busca e otimizar o backtrack. Em Modi (2003a), o autor disponibiliza uma implementa¸c˜ao na linguagem Java do algoritmo Adopt. Por´em, esta implementa¸c˜ao utiliza threads para representar os agentes, e n˜ao disp˜oe de um mecanismo de comunica¸c˜ao que permita a comunica¸c˜ao entre os agentes quando os mesmos est˜ao localizados em diferentes hosts. Para disponibilizar uma implementa¸c˜ao do algoritmo Adopt que esteja apta a operar em ambientes efetivamente distribu´idos, surge a proposta de especificar e implementar este algoritmo a partir do framework dynDCSP. Para apresentar uma aplica¸c˜ao pr´atica do algoritmo Adopt ´e utilizado o problema de modelagem molecular. A expectativa ´e diminuir o tempo necess´ario para determina¸c˜ao de modelos moleculares (disposi¸c˜ao tri-dimensional dos ´atomos de uma mol´ecula) em fun¸c˜ao do paralelismo que uma execu¸c˜ao distribu´ida pode proporcionar, al´em de verificar a viabilidade da abordagem atrav´es de DCOP para o problema de modelagem molecular. |
| |
|
