Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

343 lines (282 sloc) 21.184 kB
\chapter{Trabalhos Relacionados}
\label{chap:related}
Acho melhor colocar algo como: Este capitulo analisa arquiteturas de sistemas
multi-agentes propostas na literatura e que posseum objetivos similares ao do
proposto neste trabalho. Em especial, propostas de implementação de agentes diretamente em
{\it{hardware}} são discutidas.
Esta análise é importante pois ela serve como base para a criação da arquitetura
proposta na utilização de partes dos trabalhos aqui introduzidos, tanto no uso do
mesmo {\it{framework}} quanto na reutilização das ideias propostas como maneira de se propor
o modelo de arquitetura deste trabalho.
\section{Agilla}
Agilla é um {\it{middleware}} para programação de nós sensores em RSSF \cite{AGILLA2}. A ideia
geral da proposta é distribuir os nós sensores fisicamente na área de interesse e configurar posteriormente
a rede conforme a necessidade. A rede é programada com uma arquitetura de agentes móveis
utilizando-se uma plataforma dedicada. Esta arquitetura tem como base a plataforma de nós sensores chamada
de Mica2 \cite{MICA2} e a nível de sistema operacional é utilizado o TinyOS \cite{TINYOS}.
Este de tipo de arquitetura aumenta consideravelmente a flexibilidade da RSSF pois permite a reprogramação dinâmica dos
nós sensores após a sua distribuição física no ambiente.
\subsection{Modelo de Agente}
O modelo proposto pode ser visto na Figura {\ref{fig:agilla_model}}.
Cada agente mantém um espaço de tuplas e uma lista de vizinhos sendo que eles tem suporte à múltiplos agentes.
O espaço de tuplas é local e é dividido pelos agentes que estão residindo no nó sensor
em um dado momento do tempo. Instruções especiais permitem que os agentes acessem remotamente
o espaço de tuplas de outros nós. A lista de vizinhos contem os endereços de todos
os nós que estão separados por um {\it{hop}}. Os agentes podem migrar carregando seu
código e estado, mas o espaço de tuplas não é carregado.
\begin{figure}[ht]
\centering
\includegraphics[width=.6\textwidth]{agilla_model}
\caption{Modelo de agente proposto no Agilla \cite{AGILLA2}.}
\label{fig:agilla_model}
\end{figure}
Uma aplicação Agilla consiste em um vários agentes autônomos, possivelmente de
diferentes tipos, distribuídos pela RSSF. Em \cite{Agilla} é mostrado um exemplo
para detecção de queimadas em florestas, com diversos tipos de agentes se comunicando
com a finalidade de detectar o incêndio o mais rapidamente possível. A comunicação
entre os agentes torna-se um ponto importante no modelo pois é o gargalo da troca
de informações entre os agentes e tipicamente é a parte que mais consome energia
no nó sensor, conforme já foi discutido no Capítulo~\ref{chap:rssf} deste trabalho. Esta
comunicação no modelo do Agilla é feita através do espaço de
tuplas. O espaço de tuplas do Agilla é oferecido através de um modelo de memória
compartilhada onde um dado é uma tupla.
Um espaço de tuplas é uma implementação do paradigma de memória associativa para
computação paralela e distribuída. Ele provê um repositório de tuplas que pode
ser acessado concorrentemente e pode ser visto como uma forma de memória compartilhada
distribuída. Um exemplo simples seriam dois grupos de processadores, um produzindo
e outro consumindo dados. Os produtores colocam os dados no espaço de tuplas enquanto
os consumidores buscam os dados que combinam com um certo padrão. Existe uma metáfora
para isso, chamada de metáfora do {\it{blackboard}} \cite{BLACKBOARD}, onde um grupo de especialistas
colabora em um quadro-negro para criar uma solução para um problema complexo
cooperativamente. O processo todo se dá com os especialistas colaborando e colocando
parte da resolução do seu problema no quadro-negro até que o problema seja resolvido.
Espaço de tuplas são a base teórica da linguagem Linda \cite{Linda_Tuples} desenvolvida
por David Gelernter e Nicholas Carriero na universidade de Yale.
O espaço de tuplas provê um alto nível de desacoplamento que garante que cada
agente continue autônomo e fornece uma maneira conveniente de um agente descobrir
seu contexto. Por exemplo, visto que cada nó pode ter um diferente número de
sensores, Agilla cria tuplas especiais dentro do espaço de tuplas indicando
que tipo de sensores estão disponíveis. O Agilla ainda adiciona reações ao
espaço de tuplas, criando uma espécie de agente reativo, que é responsável
por avisar outros agentes quando uma determinada tupla é
inserida no sistema. Isso evita o constante
monitoramento entre os agentes e, consequentemente, diminui o tráfego na rede.
\subsection{Arquitetura do Middleware}
A arquitetura do Agilla pode ser dividida em três grandes camadas, sendo
que a mais alta contem os agentes, a camada do meio contem os componentes
do {\it{middleware}} enquanto que a camada de baixo é onde se situa o sistema
operacional TinyOS. O {\it{middleware}} da arquitetura consiste de um gerenciador
de agentes ({\it{agent manager}}), gerenciador de contexto ({\it{context manager}}), gerenciador
de instruções ({\it{instruction manager}}), gerenciador de espaço de tuplas ({\it{tuple space manager}})
e também a máquina de execução do Agilla ({\it{agilla engine}}), o que pode ser visto na Figura \ref{fig:agilla_arch}.
\begin{figure}[ht]
\centering
\includegraphics[width=.6\textwidth]{agilla_arch}
\caption{Arquitetura do Agilla \cite{AGILLA2}.}
\label{fig:agilla_arch}
\end{figure}
O {\it{agent manager}} é responsável por manter o contexto dos agentes, alocar
memória para um agente que está chegando na plataforma e desalocar esta memória
quando este agente é terminado ou quando ele migra. Ele também é responsável
por determinar quando um agente está pronto para ser executado. Por {\it{default}}
o gerenciador de agentes suporta no máximo 4 agentes, mas isso é facilmente alterado
sendo que os fatores que limitam são a velocidade do processador e a memória
física disponível no sistema.
O {\it{context manager}} determina a localização do nó sensor bem como a de
seus vizinhos. Ele utiliza {\it{beacons}} para descobrir os vizinhos e armazena
o local dos vizinhos em uma lista que é acessível aos agentes através de instruções
especiais.
O {\it{instruction manager}} tem um papel muito importante na arquitetura do Agilla
visto que o TinyOS não provê alocação dinâmica de memória, este bloco é responsável
por fazer a gerência de memória do nó sensor. Quando um agente migra e chega
no nó sensor, ele especifica quando de memória de instrução é necessária para
que ele seja executado, então o gerenciador de instruções aloca um valor mínimo
de um bloco de 22 blocos de 1 {\it{byte}} para armazenar o código do agente. Eles chegaram
a este valor mínimo empiricamente baseado no {\it{overhead}} necessário para que a maioria
dos códigos da arquitetura fossem executados.
O {\it{tuple space manager}} implementa todas as operações não bloqueantes
no espaço de tuplas e também a característica reativa das mesmas. Este bloco
também é responsável por alocar dinamicamente a memória para o espaço de
tuplas, e por {\it{default}} é alocado um valor de 600 {\it{bytes}} sendo que uma tupla pode
ter até 25 {\it{bytes}}, para que uma tupla consiga ficar dentro do valor máximo de uma mensagem,
que é 27 {\it{bytes}}.
O {\it{agilla engine}} serve como um {\it{microkernel}} que controla todas as execuções
concorrentes dos agentes no nó. Ele implementa uma política de escalonamento
do tipo {\it{round-robin}} onde cada agente pode executar um numero finito de
instruções (4 instruções) antes de chavear de contexto. Quando um agente migra, o
Agilla o divide em diversas mensagens. Uma migração requer no mínimo duas mensagens, sendo
que uma é de estado e outra de código. Muitos agentes requerem mais mensagens, visto que eles podem
ter dados no {\it{stack}} e no {\it{heap}}. Se uma única mensagem for perdida, a migração
vai falhar, e para minimizar este problema, os agentes migram entre nós que distam no máximo
de um {\it{hop}}.
O {\it{middleware}} suporta dois tipos básicos de migração de agentes que são chamadas
de {\it{soft migration}} e {\it{hard migration}}. O primeiro tipo faz com que o agente
migre sem carregar seu contexto de execução. A execução do agente é parada no nó de
origem e seu código é migrado, começando novamente a execução do seu início no
nó de destino. Isso é semelhante a uma operação de {\it{clone}} que é utilizada
no {\it{framework}} do Jade. No segundo tipo de migração, o agente carrega junto com
seu código de execução o seu contexto, podendo continuar a ser executado no nó destino
do mesmo ponto onde foi parado antes da migração.
\subsection{Arquitetura do Agente}
A arquitetura do agente Agilla pode ser vista na Figura \ref{fig:agilla_agent} e
ele é basicamente composto por um {\it{stack}}, um {\it{heap}} e diversos
registradores. O {\it{heap}} é uma unidade de armazenamento que permite que o agente
armazene até 12 variáveis. O agente também conta com três registradores de 16 bits. Um contendo
a identificação do agente (ID), outro contendo o contador de programa (PC) e finalmente um registrador
que armazena um código de condição do agente. O ID é único para cada agente e é mantido
quando um agente migra de um nó para outro. O PC é o endereço da próxima instrução a
ser executada. O registro de condição guarda o estado de execução do agente, que é
usado internamente pela arquitetura do Agilla.
\begin{figure}[ht]
\centering
\includegraphics[width=.6\textwidth]{agilla_agent}
\caption{Formato do agente Agilla \cite{AGILLA2}.}
\label{fig:agilla_agent}
\end{figure}
\subsection{Resumo}
A arquitetura do Agilla define um modelo próprio de agente que é fortemente atrelado à arquitetura do sistema operacional (SO)
e do {\it{hardware}} onde este agente está inserido. Dentro das suas limitações ligadas ao {\it{hardware}} e ao SO, o Agilla
fornece uma solução de alta performance para o tipo de problema está sendo resolvido pela sua
arquitetura. É possível, com a arquitetura do Agilla, ter agentes móveis e customizados ainda contendo um tamanho
muito pequeno, diminuindo assim o tamanho das mensagens trocadas entre os agentes, e, consequentemente, aumentando
a vida útil da bateria do nó sensor. O Agilla permite a migração de agentes com ou sem carregar o contexto do agente
durante a migração, que são chamadas de {\it{hard migration}} e {\it{soft migration}} respectivamente.
O Agilla introduz conceitos que são úteis no desenvolvimento deste trabalho. A migração de agentes em RSSFs onde são carregados
o escopo da tarefa é um conceito importante e de onde foram tiradas algumas ideias para o desenvolvimento deste
trabalho. O conceito de {\it{middleware}} também tem um papel importante, pois ele cria um ambiente abstrato
para o desenvolvimento dos agentes, fazendo que a programação do sistema seja simples para o usuário. Este trabalho
também utiliza conceitos do modelo de agente do Agilla onde cada nó é capaz de suportar vários agentes se comunicando e
ainda cada agente conhece os serviços oferecidos pelos outros agentes.
\section{Agentes em Hardware}
Diversos trabalhos se propõe a utilizar uma arquitetura reconfigurável em {\it{hardware}} para a implementação
de agentes. Em \cite{HW_AGENTS} é desenvolvida uma arquitetura de agentes em hardware baseada em
modelos BDI. É definida uma camada em software para fazer a gerência do ambiente, a qual é responsável
por controlar a comunicação entre os agentes em hardware, coordenar o trabalho cooperativo
entre eles, gerenciar as propriedades dos agentes bem como monitorar o hardware procurando possíveis
falhas. É uma interface com o usuário escrita em uma linguagem de alto nível (Java) que serve como um
gerenciador de agentes. A arquitetura proposta consiste em um microcontrolador (${\mu}C$) implementado
em lógica programável (PL) dentro do FPGA ligado diretamente aos módulos que implementam o agente. A Figura
\ref{fig:hw_agent_arch1}, adaptada de \cite{HW_AGENTS}, mostra esta arquitetura.
\begin{figure}[ht]
\centering
\includegraphics[width=.45\textwidth]{hw_agent_arch1}
\caption{Arquitetura de uma proposta de agentes em hardware \cite{HW_AGENTS}.}
\label{fig:hw_agent_arch1}
\end{figure}
A estruturação dos agentes em {\it{hardware}} é feita de forma horizontal utilizando-se de diferentes unidades
funcionais separadas por camadas. Essas camadas são divididas em nível físico, no processamento
das informações dos sensores, nível de conhecimento, onde são processadas as metas dos agentes e em nível
social com a cooperação entre os agentes. Os agentes se comunicam com a interface de gerência que controla
a organização destes agentes na arquitetura. Habilidades sensoriais e cognitivas bem como as reativas
são características dos agentes e implica em se ter interfaces especiais bem como blocos de processamento
de sinal dentro do agente. Para fazer o ajuste automático, foi implementado um núcleo de um microcontrolador
A8M que integra os módulos desenvolvidos em lógica programável.
Outra arquitetura é a proposta em \cite{FPGA_MOB_ROBOT} que define uma plataforma de agentes
em {\it{hardware}} utilizada em sistemas com requisitos de tempo real. Neste trabalho, é proposto
um modelo de agente do tipo BDI com uma interface de comunicação chamada {\it{On Demand Message Passing}}
(ODMP), que é a proposta central deste trabalho pois os resultados mostram uma redução na complexidade
dos agentes devido ao uso desta interface. O modelo BDI proposto pode ser visto na Figura
\ref{fig:hw_agent_bdi} sendo que existe uma correlação entre {\it{beliefs}} e {\it{desires}} pois
eles influenciam um ao outro e ambos influenciam {\it{intentions}}. O modelo inclui 3 portas externas
utilizadas para comunicação entre os agentes, controle e também entrada e saída de dados. A porta
de controle é utilizada para o sincronismo dos agentes com o sistema, a porta de entrada e saída é utilizada
para trocar informações com o ambiente onde os agentes estão inseridos e finalmente a porta
para comunicação entre agentes é utilizada para a troca de informações diretamente
com outros agentes do sistema.
\begin{figure}[ht]
\centering
\includegraphics[width=.45\textwidth]{hw_agent_bdi}
\caption{Agentes BDI em hardware.}
\label{fig:hw_agent_bdi}
\end{figure}
Agentes são geralmente projetados para um propósito específico e eles podem fazer
uma ou até muitas tarefas em paralelo. Caso os agentes devam executar mais tarefas
em paralelo, é possível ou aumentar a complexidade dos agentes, o que pode
fazer aumentar o esforço de desenvolvimento, ou ainda fazer com que eles trabalhem
cooperativamente. Geralmente, uma tarefa complexa de tempo real pode
ser construída como um conjunto de agentes, onde cada agente tem a sua própria
intenção e seu próprio conjunto de metas. Visto que os agentes podem trabalhar
de maneira assíncrona, mensagens somente serão transmitidas por demanda, o que
leva ao desenvolvimento do protocolo ODMP proposto neste trabalho \cite{FPGA_MOB_ROBOT}.
Este protocolo é basicamente uma fila do tipo {\it{First-In/First-Out}} (FIFO) com
prioridades, onde as mensagens marcadas como urgentes são colocadas no início
da fila.
Para a implementação do módulo de reconfiguração, foi criado um módulo chamado de
reconfiguração virtual de agente (VAR). Este método consiste de um número virtual
de estados que cada agente pode estar durante seu tempo de vida. Estes estados são definidos
pelos {\it{bitstreams}} que são carregados na memória do FPGA na sua inicialização. Assim, neste
esquema de configuração do FPGA os registradores são fixos em tempo de execução, e o dispositivo
é reconfigurado somente selecionando um estado ativo no multiplexador de entrada. Este tipo
de abordagem reduz significativamente a latência devido à reprogramação do módulo.
Um estudo de caso foi feito sobre o sistema de visão de um robô móvel navegando em um
ambiente com obstáculos e se deslocando entre dois pontos em uma sala. Foi feita uma proposta
de {\it{codesign}} dos agentes em {\it{hardware}} e em {\it{software}} sendo que o projeto
de cada módulo foi feito separadamente pois o foco do trabalho está na arquitetura
do sistema multi-agente, e não nas tarefas que os agentes executam.
%\subsection{Resumo}
\section{Trabalhos diversos}
Existem inúmeros trabalhos que fazem o uso do conceito de agentes móveis tanto em {\it{software}}, utilizando
algum {\it{framework}} padrão, tanto como em {\it{hardware}}, fazendo uso da reconfigurabilidade dinâmica
em FPGAs. Em \cite{HW_SENSOR_FUSION} é feita a fusão de sensores utilizando-se agentes em FPGA sendo que cada
{\it{bitstream}} corresponde a um agente que pode conter diversos tipos de comportamento. Os agentes podem ser alterados
em tempo de execução dada a reprogramação dinâmica oferecida pelos FPGAs. Em \cite{HW_AGENTS2} são criados agentes móveis
em {\it{hardware}} na criação de sistemas que são capazes de se auto monitorarem e se auto diagnosticarem. Os agentes em
{\it{hardware}} são utilizados para trocar-se o comportamento do sistema para regiões onde existem falhas.
O uso de Jade como arquitetura dos sistemas multi-agente se aplica em diversas áreas de aplicação. Em
\cite{JADE_EPSD} é proposto um protótipo de sistema multi-agente para reconfiguração de sistemas
elétricos de potência. Agentes são utilizados para reconfigurar o sistema elétrico de potência
quando alguma falha ocorre. Já em \cite{JADE_RTSCHED} é proposto uma extensão ao JADE para suportar escalonamento
de tempo real sobre aplicações rodando usando a plataforma do Jade. Ter a possibilidade de se executar tarefas
em tempo real aumenta a gama de aplicações possíveis utilizando-se a plataforma do Jade. Em
\cite{JADE_SPEECH_REC} é proposta uma arquitetura de agentes utilizada para se fazer reconhecimento
distribuído de voz utilizando-se a plataforma do Jade.
Neste último trabalho, o uso de uma arquitetura
de agentes móveis é utilizada devido a motivação da diminuição do tráfego de dados proporcionado pelo
uso de agentes. Diferentes campos de aplicação se beneficiam da plataforma do Jade, o que demonstra que ela
é uma plataforma versátil. A interoperabilidade do Jade devido ao uso de mensagens compatíveis com as
normas da FIPA facilita e também motiva o uso deste {\it{framework}}.
\section{Conclusão}
Neste capítulo foram analisadas arquiteturas que utilizam o conceito de agentes móveis tanto em
{\it{software}} quanto em {\it{hardware}} com o objetivo de relacioná-las com a proposta deste trabalho.
O Agilla é uma arquitetura que oferece diversos aspectos que podem ser aproveitados conceitualmente
neste trabalho. O conceito de agentes em {\it{hardware}} já foi introduzido em alguns trabalhos
sendo que idealmente é utilizada a reconfiguração dinâmica de FPGAs para a troca de agentes
em {\it{hardware}}. Conforme mencionado na Seção {\ref{sec:jade}}, o Jade é uma plataforma
de desenvolvimento de agentes que permite a criação de agentes móveis com o comportamento
desejado. O Jade é de fácil uso pois não requer conhecimentos muito aprofundados dos conceitos
de agentes, criando uma interface em java que encapsula os agentes. O Jade ainda implementa uma
linguagem de comunicação entre agentes normatizada pela FIPA. A Tabela~{\ref{tab:related_characteristics}}
mostra as principais características apresentadas por cada trabalho analisado e que serão
aproveitadas neste trabalho.
\begin{table}[ht]
\centering
\caption{Principais características dos sistemas analisados.}
\label{tab:related_characteristics}
%\begin{tabular}{|c|p{.5\textwidth}|}
\begin{tabular}{|c|c|}
\hline
{\bf{Arquitetura}} & {\bf{Características}} \\ \hline
\multirow{2}{*}{Agilla} & Modelo agente móvel para RSSFs. \\
& Alta performance. \\ \hline
\multirow{3}{*}{Agentes em hardware} & Reconfiguração dinâmica. \\
& Reconfiguração parcial. \\
& Agentes móveis. \\ \hline
\multirow{3}{*}{Jade} & FIPA-ACL. \\
& Migração de agentes. \\
& Abstração do hardware. \\ \hline
\end{tabular}
\end{table}
O uso de arquiteturas reconfiguráveis dinamicamente permite que se altere o comportamento de um sistema durante
o seu uso. As arquiteturas reconfiguráveis em {\it{software}} já permitem este tipo de configuração, o que garante
a flexibilidade dos sistemas. Ter disponível este tipo de configuração a nível de {\it{hardware}} aumenta a quantidade
de aplicações que podem se beneficiar da reconfiguração do sistema.
Entre os trabalhos analisados que utilizavam reconfiguração dinâmica do {\it{hardware}}
para a troca de agentes, normalmente utiliza-se um microcontrolador ou microprocessador
para a reprogramação do FPGA através das portas internas de configuração. Nos trabalhos
analisados, não existe a migração de agentes de {\it{software}} para {\it{hardware}} e
vice-versa bem como a comunicação só é feita entre agentes do mesmo tipo. Na proposta
deste trabalho, que é descrita no Capítulo~\ref{chap:prop}, são levadas em consideração
as arquiteturas aqui analisadas para a criação de um modelo de agente que seja
capaz de se comunicar transparentemente tanto com agentes em {\it{software}} quanto
como com agentes em {\it{hardware}}, bem como estes agentes são capazes de migrar
entre as diferentes plataformas carregando o escopo da sua tarefa.
Jump to Line
Something went wrong with that request. Please try again.