Inteligencia Artificial

Prévia do material em texto

INTELIGÊNCIA ARTIFICIAL
João Luís Tavares da Silva
2INTELIGÊNCIA ARTIFICIAL
SUMÁRIO Esta é uma obra coletiva organizada por iniciativa e direção do CENTRO SUPERIOR 
DE TECNOLOGIA TECBRASIL LTDA – 
Faculdades Ftec que, na forma do art. 5º, 
VIII, h, da Lei nº 9.610/98, a publica sob sua 
marca e detém os direitos de exploração 
comercial e todos os demais previstos em 
contrato. É proibida a reprodução parcial 
ou integral sem autorização expressa e 
escrita.
CENTRO UNIVERSITÁRIO UNIFTEC
Rua Gustavo Ramos Sehbe n.º 107. 
Caxias do Sul/ RS 
REITOR
Claudino José Meneguzzi Júnior
PRÓ-REITORA ACADÊMICA
Débora Frizzo
PRÓ-REITOR ADMINISTRATIVO
Altair Ruzzarin
DIRETORA DE EDUCAÇÃO A DISTÂNCIA (EAD)
Lígia Futterleib
Desenvolvido pela equipe de Criações para o 
ensino a distância (CREAD)
Coordenadora e Designer Instrucional 
Sabrina Maciel
Diagramação, Ilustração e Alteração de Imagem
Julia Oliveira
Revisora
Luana dos Reis
SISTEMAS DE INFORMAÇÃO INTELIGENTES 3
Conceitos Básicos 5
Dado-Informação-Conhecimento 6
Representação do conhecimento 9
Estados e busca heurística 10
Lógica 10
Regras de produção 12
Frames e scripts 13
Redes semânticas 14
Computação Evolutiva 17
Síntese 18
RESOLUÇÃO DE PROBLEMAS 20
Formulação do problema 23
Técnicas de resolução 25
Busca competitiva 40
Síntese 47
SISTEMAS ESPECIALISTAS 50
Síntese 63
ALGORITMOS GENÉTICOS 66
Princípios básicos 69
Síntese 81
APRENDIZAGEM AUTOMÁTICA 83
Aprendizagem supervisionada 86
Redes neurais artificiais 93
Síntese 108
AGENTES INTELIGENTES E SISTEMAS MULTIAGENTES 111
Síntese 147
Referências 150
3INTELIGÊNCIA ARTIFICIAL
SISTEMAS DE 
INFORMAÇÃO 
INTELIGENTES
Esta disciplina tem como objetivo introduzir 
os alunos no contexto de Inteligência Artificial, 
compreendendo seus conceitos teóricos e 
aplicando-os a problemas reais.
4INTELIGÊNCIA ARTIFICIAL
Iniciamos pela apreciação de Russel e Norvig sobre a In-
teligência Artificial:
“We call ourselves Homo sapiens – man the wise – because our 
intelligence is so important to us. For thousands of years, we have 
tried to understand how we think; that is, how a mere handful 
of matter can perceive, understand, predict, and manipulate a 
world far larger and more complicated than itself. The field of 
artificial intelligence, or AI, goes further still: it attempts not 
just to understand but also to build intelligent entities” (Russel 
& Norvig, 2004).
Se você ainda não entendeu esta apreciação, copie e cole 
o parágrafo no Google Translator para ter uma ideia de uma 
pequena parte da IA em ação.
Agora, podemos recuar um pouco no tempo e descobrir 
que construir entidades inteligentes não é um campo novo na 
história da humanidade. Por exemplo, o brilhante matemático 
e astrônomo Gerbert d’Aurillac (945-1003), que subiu ao trono 
papal como Silvestre II em 999 D.C., constrói um oráculo na 
forma de uma cabeça mecânica em bronze, provável ancestral 
dos modernos robôs (LaGrandeur, 2013).
Depois que Blaise Pascal cria a Pascalene, primeira má-
quina de calcular em 1642, e Leibniz inclui a multiplicação e 
a divisão (1673), surgem brinquedos mecânicos simulando a 
vida através dos chamados autômatos, como por exemplo, o 
pato mecânico de Jacques de Vaucanson (1738). 
Independente da tecnologia, a curiosidade sobre o fun-
cionamento da vida sempre motivou o homem a buscar uma 
forma de imitação da criação. O advento eletrônico estimula 
o conhecimento humano e os computadores já surgem com 
perspectivas inteligentes. Embora os primeiros computadores, 
a válvula eletrônica, tenham surgido na década de 1940; já em 
1950 Marvin Misky e Deam Edmonds, alunos de Harvard, 
constroem o primeiro computador de rede neural, o SNARC 
https://translate.google.com.br/?hl=pt-BR
5INTELIGÊNCIA ARTIFICIAL
(Stochastic Neural Analog Reinforcement 
Calculator) e no mesmo ano, Alan Turing 
publica seu seminal artigo na “Compu-
tational Machinery and Intelligence”, 
onde ele questiona sobre a inteligência 
dos computadores e apresenta seu famoso 
Teste de Turing (Russel & Norvig, 2004).
Conceitos Básicos
 Definir inteligência é uma tarefa 
árdua e a Medicina, Psicologia e Ciências 
Cognitivas têm desvelado total esforço e 
energia ao longo de décadas nesta tarefa. 
Desde a ideia da faculdade ou capacidade 
de aprender e compreender, culminan-
do nas inteligências múltiplas (Howard 
Gardner) e coletivas (Émile Durkheim, 
Pierre Lévy, entre outros).
Russel e Norvig definem a Inteligên-
cia Artificial segundo duas tendências 
básicas: baseado no pensamento e raciocí-
nio onde o objetivo é desenvolver sistemas 
que pensam como seres humanos ou que 
pensam racionalmente; e, baseado no 
comportamento, onde o objetivo é de-
senvolver sistemas que atuam como seres 
humanos ou que atuam racionalmente.
 Neste sentido, os conceitos variam 
conforme a abordagem adotada. Na Ta-
bela 1, a dimensão horizontal representa 
a atividade de Pensar e Agir, enquanto 
a dimensão vertical determina se estas 
atividades são imitação dos seres huma-
nos ou uma metáfora de comportamento 
racional.
Tabela 1. Abordagens conceituais sobre 
Inteligência Artificial
Como seres humanos Racionalmente
Pe
ns
an
do
“Um esforço novo e interessante 
para fazer os computadores 
pensarem (…) máquinas com 
mentes, no sentido total e literal” 
(Haugeland, 1985).
“A 'automatização' de atividades 
que associamos ao pensamento 
humano, atividades como a 
tomada de decisões, a resolução 
de problemas, o aprendizado…” 
(Bellman, 1978).
“Inteligência Artificial é o estudo 
das faculdades mentais através do 
uso de modelos computacionais” 
(Charniak e McDermott, 1985).
“É o estudo das computações 
que tornam possível perceber, 
raciocinar e agir” (Winston, 1992).
“Uma máquina é inteligente 
se ela é capaz de solucionar 
uma classe de problemas que 
requerem inteligência para serem 
solucionados por seres humanos” 
(McCarthy e Hayes, 1987). 
Ag
in
do
“É o estudo de como fazer os 
computadores realizarem tarefas 
em que, no momento, as pessoas 
são melhores” (Rich & Night, 
1990).
“A arte de criar máquinas que 
executam funções que exigem 
inteligência quando executadas 
por pessoas” (Kurzweil, 1990).
“Inteligência Artificial é a parte 
da ciência da computação que 
compreende o projeto de sistemas 
computacionais que exibam 
características associadas, quando 
presentes no comportamento 
humano, à inteligência” (Barr & 
Feigenbaum, 1981).
6INTELIGÊNCIA ARTIFICIAL
Para que os métodos de Inteligência Artificial possam ser 
utilizados para resolver um determinado problema, é impor-
tante considerar:
• a necessidade de que a solução para o problema em questão 
requeira a incorporação de conhecimento especializado sobre 
o domínio da aplicação;
• qual o tipo de conhecimento envolvido e quais as principais 
ideias a serem consideradas;
• a identificação das fontes do conhecimento a serem utilizadas 
e, como essas fontes podem ser acessadas;
• qual a melhor forma de representar o conhecimento e como 
realizar o processo de aquisição e representação deste co-
nhecimento.
Em geral, problemas cuja soluções demandem uma sequên-
cia de passos rígidos e bem definidos não são adequados para 
serem resolvidos com recursos de IA. Nestes casos deve-se 
pensar na possibilidade de codificação da solução, utilizando 
alguma técnica tradicional e alguma linguagem de programação 
orientada a objetos ou mesmo estruturada.
Dado-Informação-Conhecimento
Quais são os aspectos conceituais relacionados?
Dado:
 » isolado;
 » independente do contexto;
 » fatos (símbolo, texto, figura).
 » Armazenados em sistemas de processamento de dados:
• databases;
• arquivos (imagens, texto).
Informação:
 » dado combinado;
 » dado em contexto;
 » dado estruturado, (exemplo: por tópico);
 » catálogo (diretórios).
Conhecimento:
 » individual (humano);
 » informação baseada em interpretação, cognição, experiência.
7INTELIGÊNCIA ARTIFICIAL
Dado 
É um conjunto de fatos distintos e objetivos, relativos aos 
eventos (Davenport e Prusak, 1998). Uma sequênciade letras e 
números, figuras, palavras sem contexto (Wiig, 1993). Valores 
obtidos de sensores (Siemieniuch et al., 1999). Resumindo, um 
conjunto de elementos brutos, sem significado, desvinculado 
da realidade, de interpretação e contexto.
Informação
É um elemento cuja existência independe de atividades 
interpretativas, de entidades subjetivas (Dretske, 1981). São 
dados com significado, relevância e propósito (Drucker, 1999) 
ou contextualizados para fornecer uma solução em situações 
de decisão. Também se definem como dados aos quais foram 
atribuídos um contexto (Wiig,1993; Siemieniuch er al.,1999).
Conhecimento
O conhecimento inclui, mas não está limitado, às descri-
ções, hipóteses, conceitos, teorias, princípios e procedimentos 
que são úteis ou verdadeiros. O conhecimento distingue-se da 
mera informação porque está associado a uma intencionalida-
de. Consiste em verdades e crenças, perspectivas e conceitos, 
julgamentos e expectativas, metodologias e know-how. O co-
nhecimento é acumulado, organizado, integrado e armazenado 
para aplicações específicas (Wiig, 1993).
Sabedoria
Se estendermos a noção contextual do próprio conheci-
mento, atinge-se um estado da mente humana caracterizada 
por uma profunda compreensão e insight. A “sabedoria” é, 
frequentemente, mas não necessariamente, acompanhada por 
um extensivo conhecimento formal.
8INTELIGÊNCIA ARTIFICIAL
Dado
Informação
Conhecimento
Sabedoria
Aprendizagem de situações históricas para 
previsão de catástrofes ou soluções.
Usado conforme o contexto:
• especulador no mercado futuro de frutas;
• município atingido por uma cheia;
• companhia de distribuição de energia elétrica;
• operadores de agências de viagem.
Uma tempestade (fora de época) atingiu o 
estado de Pernambuco.
100 ml de água
Tabela 2. Pirâmide da hierarquia de representação
9INTELIGÊNCIA ARTIFICIAL
Representação do conhecimento
Computadores conhecem apenas a linguagem binária. A 
comunicação com os usuários é constantemente traduzida por 
compiladores. Como um artefato com vocabulários e linguagem 
tão reduzidos pode compreender o funcionamento do mundo?
Para que uma entidade “artificial” consiga determinar 
as consequências de um ato pelo pensamento ao invés de sua 
realização, é preciso substituir o objeto ou fenômeno real por 
uma representação adequada.
Portanto, a Representação de Conhecimento (RC) nada 
mais é do que uma aplicação da disciplina de Linguagens 
Formais para expressar de forma eficiente os conhecimentos 
de especialistas para serem acessados por usuários de um sis-
tema inteligente. É um conjunto de combinações sintáticas e 
semânticas que nos possibilitam descrever uma determinada 
aplicação. A representação sintática define os símbolos que po-
dem ser usados na representação do conhecimento e as maneiras 
como estes símbolos podem ser conseguidos. A representação 
semântica, por outro lado, determina qual significado está 
incorporado naqueles símbolos representados pela sintaxe.
Qualquer que seja a forma de representação do conheci-
mento, esta deve dispor de algum mecanismo computacional 
que possa processar o conhecimento representado. Quais são 
os principais mecanismos de representação do conhecimento 
para máquinas artificiais?
• Estados e busca heurística.
• Lógica.
• Regras de produção.
• Frames e scripts.
• Redes semânticas.
• Computação evolutiva.
• Redes neurais artificiais.
10INTELIGÊNCIA ARTIFICIAL
Estados e busca heurística
A representação por estados de busca constrói estrutura 
de grafos onde o conhecimento específico do problema está 
na escolha do próximo nó a ser expandido. Uma função de 
avaliação estima o custo do caminho do nó atual até o objetivo 
(conhecida como heurística). A partir da estrutura construída, 
algoritmos percorrem o grafo usando várias técnicas de cami-
nhamento, exemplificado na Figura 1.
Figura 1: Exemplo de árvore de busca simples
QUAL É O MELHOR PERCURSO
ITU --> UBA
I
C
S
S
S
U
130km
80km
180km
180km
150km
230km
160km
100km
90km
100km
Lógica
A lógica matemática é usada para representar o conhe-
cimento através de sentenças. Estas sentenças seguem regras 
sintáticas e semânticas específicas a cada corpo de dedução. 
Uma lógica define o significado destas sentenças. A se-
mântica determina a “verdade” de cada sentença (lembram de 
Platão?) relativo a um mundo possível. Por exemplo, a semân-
tica para a aritmética especifica que a sentença “x + y = 4” é 
verdadeira no mundo em que x=2 e y=2, mas é falsa em outro 
mundo, onde x=1 e y=1 (Russel & Norvig, 2004). Assim, cada 
sentença deve ser verdadeira ou falsa em cada mundo possível.
Existem vários tipos de lógicas utilizadas para realizar 
deduções automáticas. Na lógica de predicados de primeira 
ordem, as proposições são formadas por predicados, argumen-
tos, quantificadores e variáveis. A lógica de primeira ordem é 
de grande importância para a representação do conhecimento 
11INTELIGÊNCIA ARTIFICIAL
e tem sido o instrumento mais utilizado para a formalização 
do conhecimento em IA.
Assim, o conhecimento é expresso na forma de sentenças 
que são provadas na forma de teoremas. Por exemplo, para 
provar o teorema “herbívoro(zebra)”, a partir das premissas:
• animal(zebra);
• vegetal(grama);
• come (zebra, grama);
Basta criar uma Regra de Inferência semântica que a teste 
em algum mundo possível (dados pelos três fatos acima):
• xy[animal(x) AND come (x, y) AND vegetal(y)  herbív
Na lógica, a manipulação de símbolos representando as 
entidades, relações, eventos de domínio de aplicação deve ser 
um processo de construção plausível (sound) de novas sentenças 
a partir de outras sentenças, conforme esquema na Figura 2 
(Russel & Norvig, 2004).
Figura 2: Exemplo da tradução entre entidades no mundo real 
com sua representação simbólica
12INTELIGÊNCIA ARTIFICIAL
Regras de produção
A tomada de decisão humana pode também ser moldada 
por meio de regras de condição do tipo SE-ENTÃO. As regras 
expressam relacionamentos lógicos e equivalentes de definições 
para simular o raciocínio humano. Um exemplo simples pode 
ser ilustrado pela afirmativa: 
• “SE está chovendo ENTÃO carregue uma sombrinha”.
Portanto, como comentado anteriormente, regras de pro-
dução são estruturas do seguinte tipo:
• SE <condições> ENTÃO <conclusões> FAÇA <ações>
Onde: SE é uma lista de condições a serem satisfeitas (an-
tecedente); ENTÃO é uma lista de conclusões; e FAÇA são 
as ações a serem executadas. Conclusões e ações são chamadas 
de consequentes.
Em um processo de inferência, cada uma das condições 
da “lista de condições” deve ser verificada. Caso todas sejam 
satisfeitas, as conclusões serão consideradas verdadeiras e as 
ações serão executadas.
Exemplo da análise de restritivos em instituições bancárias:
 SE
 tipo-restritivo = Ação de busca
 E pessoa analisada = Jurídica 
 E quantidade de ocorrências < 2
 ENTÃO
 Análise Restritivo = Não Relevante
13INTELIGÊNCIA ARTIFICIAL
Frames e scripts
O modelo de frames e scripts foi introduzido em 1975 na 
representação do conhecimento por Marvin Minsk (Russel & 
Norvig, 2004).
Um frame é um agrupamento de conhecimentos relevan-
tes a uma coisa, um indivíduo, uma situação ou um conceito 
(Minsky, 1975). Os frames integram conhecimento declarativo 
sobre objetos, eventos e conhecimento procedimental sobre 
como recuperar informações ou calcular valores. Um frame 
possui um nome que identifica o conceito por ele definido e 
consiste de um conjunto de atributos, chamados slots. 
Cada slot possui um nome que o identifica e um conjunto 
de atributos que apresentam propriedades que dizem respeito 
ao tipo de valores e às restrições de número que podem ser 
associadas a cada atributo. Essas propriedades são chamadas 
facetas. Um exemplo de representação está ilustrado na Figura 3.
Figura 3: Exemplo de representação usando Frames 
(Luger,2013)
14INTELIGÊNCIA ARTIFICIAL
Redes semânticas
As Redessemânticas representam o conhecimento através 
de modelos formulados como grafos:
• os nodos representam objetos (conceitos, ou situações);
• os arcos representam relações binárias entre objetos.
Originalmente, os nodos representam substantivos, adjeti-
vos, pronomes e nomes próprios. Os arcos representam verbos 
transitivos e preposições.
Indivíduos podem ser representados com nodos anônimos 
e indicando a inclusão destes indivíduos em sua respectiva 
classe. Permitem hierarquias de hereditariedade, através da 
transitividade da relação “é_um” (is_a). A Figura 4 exibe a 
modelagem da memória humana, segundo (Quillian, 1968).
Figura 4: Modelagem da memória humana, segundo (Quillian, 
1968).
Concept-1
Concept-2
Concept-3
Concept-4
Concept-4
15INTELIGÊNCIA ARTIFICIAL
Exemplo de representação para três diferentes definições 
da palavra “Planta”:
• Estrutura viva que não é um animal, geralmente possui 
folhas e alimenta-se de água, terra ou ar.
• Aparato usado para qualquer processo na indústria.
• Colocar (uma semente, uma planta, etc.) na terra – Verbo 
“Plantar”.
Representação gráfica:
16INTELIGÊNCIA ARTIFICIAL
As redes semânticas se originam de estruturas Objeto-A-
tributo-Valor que determinam os valores de certos atributos 
de um objeto: 
Por exemplo: representação de um carro da marca Fiat de 
cor verde:
Algumas extensões possíveis para as redes semânticas são as:
Objeto Atributo Valor
possui
has
é
is
Carro Marca
Cor
Fiat
Verde
possui é
é
possui
a. Relações de classificação: relações “é_um” (is_a).
b. Relações de pertinência: relações “é_parte_de” (is_part).
17INTELIGÊNCIA ARTIFICIAL
Combinando as estruturas Objeto-Atributo-Valor com as 
relações de classificação e pertinência, as redes semânticas 
modelam relações que podem representar o conhecimento do 
mundo. A Figura ilustra um extrato de conceito para alguns 
personagens conhecidos de desenho animado.
Computação Evolutiva
A computação evolutiva é um método probabilístico de 
busca para resolução de problemas (otimização), inspirada na 
teoria da evolução. A representação do conhecimento é feita 
através de conjuntos atributo-valor e o raciocínio é indutivo, 
durante uma fase de treinamento, dedutivo ou abdutivo durante 
a fase de aplicação, utilização.
No paradigma evolutivo, a aquisição do conhecimento é 
feita através de aprendizagem e é baseada na Natureza, onde 
seres mais adaptados ao ambiente sobrevivem e suas caracte-
rísticas genéticas são herdadas. A formalização básica é que 
o indivíduo representa a solução de um problema e o sistema 
faz evoluir um conjunto de indivíduos mais adaptados através 
de funções de cruzamento; e mutação através de sucessivas 
gerações.
18INTELIGÊNCIA ARTIFICIAL
Síntese
Neste primeiro contato com a área de Inteligência artificial, resumiu-se algumas técnicas prin-
cipais de representação do conhecimento. Baseado nos conceitos apresentados aqui e nas premissas 
iniciais de que uma máquina é inteligente se ela é capaz de solucionar uma classe de problemas que 
requerem inteligência para serem solucionados por seres humanos, esta unidade focou na forma como 
uma representação do mundo deve ser definida para que um artefato artificial consiga perceber os 
elementos de resolução de um problema complexo.
Ao mesmo tempo, algumas áreas principais foram apresentadas, as quais serão aprofundadas nos 
próximos encontros, sem abranger todos os temas da Inteligência artificial.
19INTELIGÊNCIA ARTIFICIAL
Execícios
• Baseado no conteúdo acima, construa exemplos de dado-informação-conhecimento mais próximos do seu cotidiano.
• Diferencie atributos e elementos em cada exemplo dos enunciados que você criou, que possam caracterizar o conhecimento, 
diferenciando-o de dado ou informação.
• Pesquise a definição clássica de conhecimento de Platão. Esta definição de Platão pode ser formalizada como proposições na 
concepção de Aristóteles? Descubra...
20INTELIGÊNCIA ARTIFICIAL
RESOLUÇÃO DE 
PROBLEMAS
Resolver problemas é a habilidade básica de 
um ser inteligente. Veremos como encontrar 
uma sequência de ações que atinja um 
objetivo, quando nenhuma ação isolada é 
capaz de fazê-lo.
21INTELIGÊNCIA ARTIFICIAL
“Para poder sobreviver, um organismo necessita ou blin-
dar-se (como uma árvore ou um marisco) e ‘esperar pelo me-
lhor’, ou então desenvolver métodos para escapar de possíveis 
danos, indo para vizinhanças melhores. Se você escolher esta 
última opção, você se confrontará com o problema primordial 
que todo agente precisa continuamente resolver: e agora, o que 
devo fazer?” (Dennett, 1991).
De um modo informal, problemas estão relacionados à 
resolução de tarefas humanas, tais como:
• aquisição de informações (sentidos); 
• processamento de informações (raciocínio); e,
• ações no meio exterior (capacidade de agir).
Mais formalmente, um problema constitui-se em uma 
coleção de informações (conhecimento, regras, objetivos) que 
serão usadas para decidir o que fazer (solução). Apenas alguns 
exemplos ilustrativos de problemas típicos são:
Toy Problems:
Jogos de tabuleiros: 
• problema das n rainhas, 
• Damas, Xadrez, Go, Gamão, etc.
Jogos combinatórios: 
• n-puzzle ou Taquin;
• Criptoaritmética, Palavras cruzadas; 
• Canibais e missionários.
Problemas reais:
Cálculo de rotas:
• rotas em redes de computadores;
• sistemas de planejamento de viagens;
22INTELIGÊNCIA ARTIFICIAL
• planejamento de rotas de aviões;
• caixeiro viajante;
• jogos de computadores (rotas dos personagens).
Alocação (Scheduling):
• Salas de aula;
• máquinas industriais (job shop).
Projeto de VLSI:
• Cell layout;
• Channel routing.
Navegação de Robôs
Sequência de montagem.
São características da definição de problemas:
• Decomponível: pode ser dividido em subproblemas.
• Passos podem ser desfeitos ou ignorados: deve-se avaliar o 
custo de voltar atrás.
• Universo do problema é imprevisível: pode-se fazer uso da 
probabilidade.
• Solução absoluta ou relativa: existem problemas com solu-
ções ótimas.
• A base de conhecimento é consistente internamente: modelo 
da realidade confere com o objeto ou é uma aproximação, 
ou se apenas restringe a busca.
• Grande volume de conhecimento.
• Interage com o usuário.
23INTELIGÊNCIA ARTIFICIAL
A atividade de resolução de problemas consiste em decidir 
o que fazer, encontrando sequências de ações que levem a um 
objetivo (estado) desejado. Podemos planejar a resolução de 
qualquer problema seguindo as seguintes etapas:
• Formular o problema.
• Analisar o problema.
• Identificar o conhecimento necessário.
• Escolher a técnica de resolução mais adequada.
Formulação do problema
O primeiro passo para solucionar um problema é criar uma 
descrição formal manipulável para o problema. Esta descrição 
deve conter:
• definição de um espaço de estados possíveis;
• especificação dos estados iniciais;
• especificação de um conjunto de estados que sejam aceitáveis 
como soluções (estados objetivos);
• especificação do conjunto de ações disponíveis (regras ou 
operadores).
Mais formalmente em IA, um problema é definido em 
termos de:
• um espaço de estados possíveis, incluindo:
◊	um estado inicial;
◊	um (ou mais) estado finais = objetivo.
 » Exemplo: dirigir de Porto Alegre a Caxias do Sul.
 » Estado inicial: estar em Porto Alegre.
 » Estado final: estar em Caxias do Sul.
 » Espaço de estados: todas as cidades (x,y) da região.
24INTELIGÊNCIA ARTIFICIAL
◊	A descrição de um conjunto de ações disponíveis ao agente 
de resolução. Por exemplo, move(x,y), in(z), etc.
◊	Descrição do que cada ação faz, ou seja, um modelo de 
transição de estados, que permita passar de um estado a outro.
 » Exemplo: {in(x), move(x,y) = in(y)}, considerando 
que existe um caminho válido entre x e y.
◊	Um teste objetivo para se determinar se o estado atual 
pertence ao conjunto de estados finais.
◊	Uma função de utilidade, ou função de custo de caminho, 
que indique a qualidade do resultado.
Geralmente a solução de um problema é representadopelo cami-
nho que parte do estado inicial até um dos estados finais (objetivos).
Vamos a um exemplo mais completo, formulando o pro-
blema do Jogo de Xadrez:
• Espaço de estados: uma matriz 8x8 (numerados 1-8 e a-h) 
onde cada posição possui um símbolo representando uma peça.
• Operadores: regras de movimentação do xadrez, por exemplo, 
1.d4 d5 2. c4 c6 3. cxd5 cxd5 4. Cc3 Cc6 5. Cf3 Cf6; etc.
• Estado inicial: posição oficial de abertura do xadrez:
• Estado final: qualquer estado onde o rei adversário está sendo 
atacado e o adversário não possui movimentos válidos.
• Teste objetivo: um estado pertencente ao conjunto de estados 
finais, a partir dos operadores: 1-0, 0-1 ou ½-½.
• Custo do caminho: quantidade de posições examinadas, 
(Shannon, 1949):
• cerca de 35 movimentos legais (fator de ramificação);
• em média, cada jogador poderá realizar 40 movimentos;
• exame da árvore completa: ~3580 posições.
25INTELIGÊNCIA ARTIFICIAL
Técnicas de resolução
Em geral, o espaço de solução de um problema ou o espaço 
de estados é computacionalmente representado por meio de um 
grafo, onde cada vértice corresponde a um estado e as arestas 
indicam transições entre dois estados. A busca pela solução 
de um problema compreende a navegação pelos vértices do 
grafo de estados associados, a fim de encontrar o(s) vértice(s) 
cujo(s) estado(s) corresponde(m) a solução do problema. Por 
exemplo, a Figura 6 ilustra exemplos de grafos de busca para 
o problema da viagem.
Figura 6: Exemplo grafo para o problema da viagem
P
P
S
N
F
C
1
2
8
7
9
3
4
6
5
26INTELIGÊNCIA ARTIFICIAL
As principais técnicas de resolução deste tipo de problema 
podem ser enumeradas como:
• Busca: método de resolução de um problema sem abordagem 
direta, mas com uma estrutura disponível.
• Utilização do conhecimento: método de resolução de 
problemas complexos explorando a estrutura dos objetos 
envolvidos.
• Abstração: método que separa características e variações 
importantes de outras irrelevantes no processo de resolução.
O modo como as regras a serem aplicadas são selecionadas 
é crítico para a rapidez da resolução e para a possibilidade de 
encontrar alguma solução para o problema, portanto, uma 
estratégia de busca deve, sobretudo: 
• Causar movimento: movimentar o processo de resolução 
dentro do espaço de estados.
• Ser sistemática: explorar o espaço de estados de modo que 
evite repetir caminhos já percorridos e/ou desnecessários.
• Tratar o problema da possível explosão combinatória na 
exploração.
As estratégias de resolução se adequam ao tipo de pro-
blema, definido em função do conhecimento do sistema, que 
tradicionalmente estão subdivididos em:
• Problemas de estado único (single-state problems).
• Problemas de múltiplos estados (multiple-state problems).
• Problemas de contingência (contingence problems).
• Problemas exploratórios (exploratory problems).
27INTELIGÊNCIA ARTIFICIAL
Problemas de estado único
Este tipo de problema é caracterizado por ter um mundo 
observável (pelo menos o estado inicial), determinístico, estático 
e discreto. O conhecimento associado ao problema indica que o 
agente sempre sabe em que estado ele está (mundo totalmente 
acessível), conhece o efeito de cada uma de suas ações e sabe 
se localizar depois de uma sequência qualquer de ações. Cada 
ação leva a um único estado possível do espaço de estados 
definidos na formulação original do problema.
Vamos a um exemplo para o projeto de um robô aspirador 
de pó. Informalmente este problema é descrito através de um 
ambiente simples composto por duas salas A e B, onde um 
robô aspirador de pó precisa perceber se as salas estão limpas 
ou sujas e tem por objetivo manter as duas salas limpas. O robô 
também precisa se locomover entre as duas salas e executar a 
operação de aspiração como ilustrado na Figura 7.
Figura 7: Mundo simples do robô aspirador
Problemas de múltiplos estados
As características deste tipo de problema possuem um mundo 
parcialmente observável (estado inicial não observável), determinís-
tico, estático e discreto. Neste caso, o agente não tem conheci-
mento total do ambiente, não sabe seu estado inicial (percepção 
deficiente), mas sabe o efeito de suas ações. Ou, de outra forma, 
pode não conhecer o efeito das ações (execução deficiente), mas 
conhece seu estado inicial. Aqui podemos fazer um paralelo com 
28INTELIGÊNCIA ARTIFICIAL
a famosa lei de Murphy: o robô pode correr o risco de aspirar 
poeira existente e pode jogar poeira quando o quarto já estiver 
limpo. Em todo caso, a principal questão envolvendo a resolução 
deste tipo de problema é garantir que o agente consiga raciocinar 
sobre os conjuntos de estados aos quais ele pode chegar pelas 
ações. A técnica utilizada ainda é a busca no grafo de estados.
Problemas de contingência
Nos problemas do tipo contingência, o mundo é parcial-
mente observável (estado inicial não observável), não-deter-
minístico e dinâmico. Neste caso, o agente não conhece o 
ambiente inteiro ou não sabe o efeito das ações, por exemplo, 
o nosso robô enxerga apenas o quarto onde está. Não há uma 
sequência prévia de ações que garanta a solução do problema 
e, portanto, é necessário intercalar busca e execução em uma 
técnica tradicional de Planejamento. Neste contexto é neces-
sário construir uma árvore de ações, onde cada ramo lida com 
uma possível contingência.
Problemas exploratórios
Nos problemas exploratórios, além das características dos 
problemas de contingência, os estados e as ações do ambiente 
são desconhecidos. O agente deve atuar e descobri-los. Ele não 
possui conhecimento dos possíveis estados e não possui conhe-
cimento sobre o efeito de suas ações, por exemplo, um robô 
perdido em uma cidade desconhecida, sem mapa. Neste caso 
é necessário explorar o ambiente, descobrindo gradualmente 
o resultado das possíveis ações e os estados existentes. Se o 
agente “sobreviver”, terá aprendido um mapa do ambiente, que 
poderá ser reutilizado em problemas subsequentes, portanto, a 
única técnica possível de resolução destes problemas é através 
da aprendizagem.
29INTELIGÊNCIA ARTIFICIAL
Vamos voltar a formulação de problema para nos fixarmos 
melhor na importância da formulação. Teremos como exemplo, 
o jogo das n Rainhas (n-queens), considerando um total de 8 
rainhas no nosso tabuleiro. O objetivo deste problema é dispor 
8 rainhas no tabuleiro de forma que nenhuma delas possa se 
“atacar” mutuamente. Ou seja, não pode haver mais de uma 
rainha em uma mesma linha, coluna ou diagonal. Neste caso, 
somente o custo da busca conta, pois não existe custo de caminho.
Neste caso existem diferentes esta-
dos e operadores possíveis onde a escolha 
pode ter consequências boas ou ruins na 
complexidade da busca ou no tamanho 
do espaço de estados. Vamos considerar 
alguns exemplos de formulações possíveis 
e suas características:
• Formulação A:
• estados: qualquer disposição com n (n ≤ 8) rainhas;
• estado inicial: nenhuma rainha no tabuleiro;
• operadores: adicionar uma rainha a qualquer quadrado livre. Nes-
te caso tem-se 648 possibilidades, cuja execução irá até o final para 
testarmos se dará certo.
• Formulação B:
• estados: disposição com n (n ≤ 8) rainhas, uma por coluna nas n 
colunas mais à esquerda, sem ataque mútuo (teste gradual);
• operadores: adicionar uma rainha na coluna vazia mais à esquerda em 
que não possa ser atacada. Assim teremos apenas 2057 possibilidades, 
mas poderemos chegar a um ponto em que não haja ações possíveis;
• Formulação C:
• estados: disposição com 8 rainhas, uma em cada coluna;
• operadores: mover uma rainha atacada para outra casa, na mesma 
coluna. Esta busca de estados completa precisa de 8x7 sucessores para 
cada estado.
30INTELIGÊNCIA ARTIFICIAL
Tipos de estratégia de resolução de problemas
Os principais tipos de estratégias aplicadas na resolução 
de problemas são:
• Busca não-informada ou “cega”.
• Busca em amplitude.
• Busca com custo uniforme.
• Busca em profundidade.• Busca em profundidade limitada.
• Busca em profundidade iterativa.
• Busca bi-direcional.
• Busca informada ou pela melhor escolha (Best-First).
• Busca “gulosa” (Greedy).
• Busca A*.
• Busca com limite de espaço.
• Busca IDA (A* interativo).
• Subida de encosta (HillClimbing).
Existem quatro métricas para avaliação das estratégias de 
resolução de problemas:
• Completude: a estratégia sempre encontra uma solução 
quando existe alguma? 
• Custo do tempo: quanto tempo será gasto para encontrar 
uma solução?
• Custo de espaço: quanta memória é necessária para realizar 
a busca?
• Qualidade (optimality) da solução: a estratégia encontra a 
melhor solução quando existem diferentes soluções? Menor 
custo de caminho?
31INTELIGÊNCIA ARTIFICIAL
Busca em amplitude
Na busca em largura, amplitude ou Breadth-first, o grafo 
da solução é construído em níveis. Cada nó, a partir do nó raiz, 
é expandido para todos os sucessores do nó raiz e depois os 
sucessores desses nós, e assim por diante. Em geral, todos os 
nós, em dada profundidade no grafo de busca, serão expandidos 
antes que todos os nós no nível seguinte sejam expandidos.
Em termos estruturais, os nós do grafo podem guardar 
mais informação do que apenas o estado, por exemplo: o estado 
correspondente, o seu nó pai, o operador aplicado para gerar o 
nó (a partir do pai), a profundidade do nó, o custo do nó (desde 
a raiz) e os nós sucessores, como exemplificado na Figura 8.
Figura 8: Busca em amplitude com a marcação do nó expandido 
a cada nível
O exemplo do algoritmo da Busca em largura retorna uma 
solução ou falha.
Os métodos usados neste algoritmo são:
• MAKE-QUEUE (estado inicial): coloca o estado inicial na fila.
• REMOVE-FIRST (nodos): remove os primeiros nodos da fila.
• GOAL-TEST (nodo): testa se o nodo atual é nodo final.
• EXPAND (nodo): retorna uma lista de nodos que representam os estados, 
resultando da aplicação dos operadores ao nodo atual.
• ADD-QUEUE (nodos, novos-nodos): coloca estes nodos na fila de busca.
32INTELIGÊNCIA ARTIFICIAL
Um exemplo de resolução usando o algoritmo Breadth-First 
é exemplificado na execução da Figura 9. Considerando que o 
estado inicial é A e um dos estados finais é K, a sequência de 
execuções sobre a árvore é ilustrada pela sequência numérica 
em vermelho na Figura 9, onde o caminho resultante do estado 
inicial até o objetivo é {A,B,C,D,E,F,G,H,I,J,K}.
Figura 9: Exemplo de árvore de busca usando o algoritmo 
Breadth-First
Em relação as quatro métricas de avaliação de algoritmos 
de busca apresentadas anteriormente, a busca em amplitude 
fica assim avaliada:
• Completude: é completa.
• Qualidade: ótima, se os operadores sempre têm o mesmo 
custo.
• Custo do Tempo: O(bd) nodos explorados, onde
• b = fator de ramificação
• d = profundidade do estado final (objetivo)
• O(bd) = 1 + b + b2 + b3 + .... + bd
• Custo do espaço: O(bd) nodos armazenados, ou seja, todos 
os estados a serem expandidos devem permanecer na me-
mória e o resultado é bom quando a profundidade da árvore 
de busca é pequena.
O(x) é a notação assintótica, que significa “complexidade exponencial”, ou seja, o algoritmo leva um 
tempo exponencial em função do comprimento da entrada (x) para encontrar uma solução.
33INTELIGÊNCIA ARTIFICIAL
Exemplo de complexidade, considerando que b = 10, à 
1000 nodos por segundo e 100 bytes por nodo:
(b = 10, 1000 nodos por segundo, 100 bytes por nodo)
Profundidade Nodos Tempo Memória
0 1 1ms 100B
2 111 0,1s 11KB
4 11.111 11s 1MB
6 106 18min 111MB
8 108 31hs 11GB
12 1012 35 anos 111TB
14 1014 3500 anos 11.111TB
Busca em amplitude com custo uniforme
A estratégia de busca uniforme continua expandindo os 
sucessores, mas ao invés de pegar o primeiro nó expandido, 
será escolhido o nó que possui o menor custo (g(n)), onde a 
função g(n) é uma representação do custo do caminho.
O exemplo do algoritmo da Busca em largura com custo 
uniforme, a seguir, retorna uma solução ou falha.
Notem que a diferença na expansão dos sucessores é a fun-
ção SORT(...), que ordena a prioridade dos nodos com menor 
34INTELIGÊNCIA ARTIFICIAL
custo. Neste caso é preciso agregar informação adicional ao 
problema, por exemplo, o custo do caminho pode ser a distância 
entre cidades, a quantidade de números fora de posição em um 
quebra-cabeças, etc. 
Um exemplo de resolução usando o algoritmo Breadth-First 
com Custo Uniforme é exemplificado na execução da Figura 9. 
Considerando que o estado inicial é A e um dos estados finais 
é K, a sequência de execuções sobre a árvore é ilustrada pela 
sequência numérica em vermelho na Figura 9, onde o caminho 
resultante do estado inicial até o objetivo é {A,D,C,B,L,K}.
Figura 10: Exemplo de árvore de busca usando o algoritmo 
Breadth-First com custo uniforme.
Busca em profundidade
Na busca em profundidade ou Depth-first, o grafo da 
solução é construído em profundidade, onde cada nó, a partir 
do nó raiz, é expandido sempre o filho mais à esquerda até a 
profundidade máxima.
O exemplo do algoritmo da Busca em profundidade, a 
seguir, retorna uma solução ou falha.
Nesta busca, apenas os nodos da borda (próximos a raiz) 
do grafo comportam-se como uma fila FIFO (First-In, First-
35INTELIGÊNCIA ARTIFICIAL
-Out), executados pela função ADD-START-QUEUE (nodos, 
novos-nodos).
Um exemplo de resolução usando o algoritmo Depth-First 
é exemplificado na execução da Figura10. Considerando que o 
estado inicial é A e um dos estados finais é K, a sequência de 
execuções sobre a árvore é ilustrada pela sequência numérica 
em vermelho na Figura10, onde o caminho resultante do estado 
inicial até o objetivo é {A,B,E,F,G,C,H,I,J,D,K}.
Figura 11: Exemplo de árvore de busca usando o algoritmo 
Depth-First.
O algoritmo de busca em profundidade sempre expande 
os nós mais profundos na borda atual da árvore de busca. À 
medida que os nós são expandidos, eles são marcados como 
visitados, não fazendo mais parte da estrutura que guarda a 
borda das subárvores. Um exemplo de progresso gradual é 
ilustrado na Figura12.
Figura 12: Progresso da busca em profundidade, com nós 
inexplorados em cinza claro
36INTELIGÊNCIA ARTIFICIAL
Busca informada ou heurística
Pode-se melhorar a performance da busca através de uma 
função h(n) que representa uma avaliação do custo para atingir 
o estado final, para cada nodo n do espaço de busca.
A função h(n) é chamada função heurística ou informada, 
pois é dependente do problema, já que utiliza informação adicio-
nal para melhorar a busca, podendo representar, por exemplo, a 
minimização do custo para se atingir um objetivo ou a estimativa 
do menor caminho de um estado n até um estado objetivo.
Tipos de busca heurística:
• Busca pela melhor escolha (Best-First)
• Busca gulosa (Greedy)
• Busca A*
• Busca com limite de espaço
• Busca IDA (A* interativo)
• Subida de encosta (Hill Climbing)
Busca gulosa de melhor escolha
A busca gulosa (Greedy) procura expandir sempre o nodo 
mais próximo do objetivo, caracterizando uma escolha de melhor 
local. Esta busca usa a função de avaliação h(n) como sendo a 
estimativa do custo do nodo atual ao objetivo. No exemplo da 
Figura 13, o objetivo é partir da cidade de Arad e chegar até 
a cidade de Bucareste na Romênia e a heurística h(n) usada é 
a distância em linha reta até o objetivo.
Figura 13: Exemplo de grafo de possibilidades contendo uma estimativa 
da distância em linha reta de todas as cidades até Bucharest
37INTELIGÊNCIA ARTIFICIAL
O algoritmo expande primeiro o nó, que aparentemente é 
o mais próximo do objetivo, de acordo com h(n). A Figura14 
ilustra um resultado possível usando h(n).
Figura 14: Etapas da busca gulosa para Bucareste. Os nós são 
rotulados com a distância em linha reta até o destino (h)
Uma análise preliminar do resultado da busca gulosa de-
monstra que: 
• Completude: não, pois pode ficar em loop, a menos que o 
espaço de estados seja finito e exista um teste de estados 
repetidos.
• Qualidade (ótimo): não.
• Custodo tempo: Os(bd) nós explorados, onde b = fator de 
ramificação e d = profundidade do estado final (objetivo).
• Custo do espaço: Os(bd) nós armazenados.
38INTELIGÊNCIA ARTIFICIAL
Busca A*
A busca A* (A Estrela), procura conciliar as vantagens da 
busca em amplitude e profundidade, avaliando os nós através 
da combinação do custo para alcançar o nó (g(n)) e do custo 
para ir do nó até o objetivo (h(n)), ou seja f(n) = g(n) + h(n).
Figura 15: Etapas da busca usando A*, onde os nós são 
rotulados com f(n) = g(n) + h(n)
A Figura15 ilustra o exemplo do caminho de busca para 
o exemplo anterior. Se tomarmos agora a distância real per-
corrida entre cada trecho, h(n), perceberemos que a estratégia 
A* produz o seguinte caminho de solução: Arad -> Sibiu -> 
Rimnici Vilcea -> Pitesti -> Bucharest, resultando em um 
custo total de (140+80+97+101 = 418). Enquanto que a estra-
tégia Gulosa, da Figura14, gera o caminho solução: Arad -> 
Sibiu -> Fagaras -> Bucharest, resultando em um custo total de 
(140+151+178 = 469), embora tenha percorrido menos cidades. 
Ou seja, a estratégia A* encontra uma solução ainda melhor 
que a estratégia Gulosa.
A principal diferença dos algoritmos de busca cega para os 
algoritmos de busca informada é a expansão do próximo nó a 
ser analisado. Um algoritmo genérico para buscas informadas, 
a seguir, retorna uma solução ou falha.
39INTELIGÊNCIA ARTIFICIAL
Onde o método GET-BEST-NODE (nodos) implementa 
a função f(n) = g(n) + h(n) para o algoritmo A*, e a função f(n) 
= h(n) para o algoritmo Guloso.
A análise do resultado do algoritmo A* demonstra que: 
• Completude: sim, pode ficar em loop; a menos que o espaço 
de estados seja finito e exista um teste de estados repetidos.
• Qualidade (ótimo): sim, se f(n) é admissível.
• Custo do Tempo: os(bd) nós explorados, onde b = fator de 
ramificação e d = profundidade do estado final (objetivo).
• Custo do Espaço: os (bd) nós armazenados.
Admissibilidade de uma função heurística
Uma heurística é admissível se, para cada nodo, o valor 
retornado por esta heurística nunca ultrapasse o custo real do 
melhor caminho deste nodo até o objetivo. Dado que h(n) é 
estimativa de custo de n até a solução, g(n) é custo real de n até 
a solução, então se h(n) ≤ g(n), então h é admissível e, portanto, 
o algoritmo será ótimo, ou seja, sempre encontra o caminho 
mais curto até a solução.
40INTELIGÊNCIA ARTIFICIAL
Busca competitiva
O que existe em comum entre negociações internacionais, 
decisões estratégicas de executivos de empresas concorrentes, 
uma partida de xadrez e as estratégias de busca vistas até agora?
Quando mais de um ator participa de uma resolução de 
problemas, geralmente surgem conflitos em ambientes com-
petitivos, dando origem a problemas de busca competitiva ou 
jogos, como vimos no início deste capítulo.
No contexto de problemas de busca competitiva, alguns 
jogos possuem características que podem ser formuladas como 
competições abstratas, por exemplo:
• representados por estados e regras claramente definidos;
• programas para alguns jogos podem ser derivados de mé-
todos de busca, onde alguns precisam da incorporação de 
conhecimento e informações adicionais
Definições preliminares
Um Jogo é um modelo teórico de conf litos de interesse 
(decisões possíveis, resultados possíveis) entre duas ou mais 
pessoas que têm motivações conflitantes. Um Jogador é um 
participante ativo e racional em um jogo, cujas ações afetam 
os demais. Movimentos são decisões disponíveis aos jogadores 
(simultaneamente ou não): são seguidos de uma ação, resultan-
do em um ganho (outcome, payoff, utility), podendo ser um 
evento probabilístico.
Nas interações competitivas, as escolhas são alternativas 
particulares selecionadas por jogador e uma jogada é uma se-
quência destas escolhas. Estratégias são descrições das decisões 
a tomar em todas as situações possíveis e o resultado destas 
jogadas resulta em valor ou pagamento de uma ação (Payoff / 
Utility / Ganho) ou ainda uma expressão de preferência.
41INTELIGÊNCIA ARTIFICIAL
Taxonomia de jogos
1. Segundo o payoff:
a. Jogos de soma zero: soma dos payoffs dos participantes 
é zero (Nim, Pôquer, Xadrez, etc.).
b. Jogos de soma não zero: resultados dos payoffs  zero 
(dilema do prisioneiro, etc.).
2. Segundo a informação:
a. Jogos com informação perfeita: a cada jogada, todos os 
jogadores têm conhecimento das jogadas que já ocorreram 
( Jogo da velha, Nim, Xadrez, Go, etc.).
b. Jogos com informação imperfeita: conhecimento é parcial (Pôquer).
3. Duração: jogos infinitamente longos, aplicados por mate-
máticos teóricos.
4. Simultaneidade: 
a. Jogos simultâneos cujos movimentos são paralelos e des-
conhecidos pelos oponentes.
b. Jogos sequenciais, com movimentos intercalados.
5. Simetria: 
a. Jogos simétricos: onde os payoffs para uma dada estratégia 
dependem de outras estratégias empregadas.
b. Jogos assimétricos: não existe um conjunto idêntico de 
estratégias para ambos os jogadores.
42INTELIGÊNCIA ARTIFICIAL
Formulação de problemas competitivos
Geralmente, quando um jogo é formulado em termos de 
estratégias de busca, ocorre um ambiente onde os agentes são 
considerados hostis (competitivos) e a representação de jogos 
como busca torna-se:
• relativamente fácil;
• com operadores bem definidos;
• os oponentes introduzem incertezas;
• com resolução complexa (por exemplo, no xadrez, fator médio 
de ramificação 35 e árvore com 35100 nodos);
• limitado em tempo e espaço.
Tradicionalmente, a definição formal de um jogo requer 
a representação de um estado inicial (de um tabuleiro, das 
posições das peças e do iniciador do jogo). É preciso descrever 
os operadores, como as ações definem os movimentos permiti-
dos. E, definir um teste final para determinar quando o jogo 
termina, o cálculo do resultado (vitória, empate ou derrota), o 
cálculo da função de utilidade (payoff) e um valor numérico 
para cada resultado do jogo.
Segundo Russel & Norvig (2013), um jogo pode ser de-
finido formalmente como uma espécie de problema de busca 
com os seguintes componentes:
• S0: o estado inicial, designando como o jogo é inicialmente 
criado.
• JOGADORES(s): define qual jogador deve se mover em 
um estado.
• AÇÕES(s): retornam o conjunto de movimentos válidos 
em um estado.
• RESULTADO (s, a): o modelo de transição que define o 
resultado de um movimento.
43INTELIGÊNCIA ARTIFICIAL
• TESTE DE TÉRMINO(s): retorna verdadeiro quando 
o jogo termina, onde os estados são chamados estados ter-
minais.
• UTILIDADE (s, p): uma função de utilidade ou objetivo 
que define o valor numérico para um jogo que termina no 
estado terminal s por um jogador p. Por exemplo, no xadrez, 
o resultado é uma vitória, uma derrota ou um empate, com 
valores +1, 0 ou ½.
a. Desta forma, o estado inicial S0, a função AÇÕES(s) 
e a função RESULTADO (s, a) definem a árvore de jogo, 
onde os nós são estados do jogo e as bordas são movimentos. 
Considerando que os jogadores são nomeados como MAX e 
MIN. A Figura 16 ilustra parte de uma árvore de jogo para 
o Jogo da Velha. A partir do estado inicial, MAX tem nove 
movimentos possíveis. O jogo se alterna entre a colocação 
de um X por MAX e a colocação de um O por MIN até 
que os nós folhas (ou estados terminais) sejam alcançados. 
O número em cada nó de folha indica o valor de utilidade 
do estado terminal, do ponto de vista de MAX. Neste caso, 
a estratégia básica é MAX tentando maximizar seu ganho e 
MIN tentando minimizar os efeitos das jogadas de MAX.
Figura 16: Exemplo de árvore de busca (parcial) para o Jogo da 
velha
44INTELIGÊNCIA ARTIFICIAL
Para o problema do Jogo da velha, a 
árvore tem o tamanho de aproximadamen-
te 9! = 362.880 nós terminais. Portanto, 
trivial de implementar, mas o Xadrez, por 
exemplo, já apresenta mais de 1040 nós. 
Portanto, não é uma busca trivial e nem 
ótima do ponto de vista de completude. 
Portanto, a visualização em árvore deste 
tipo de problema é apenas teórica.
Na Figura 17 seráilustrada uma 
parte da árvore de escolhas para MAX 
(representado por ) e o outro jogador, 
MIN (representado por ). Os nós ter-
minais mostram os valores de utilidade 
para MAX. A seta vermelha indica o 
melhor movimento de MAX na raiz, 
através da ação A1, porque leva a um 
estado com o mais alto valor minimax.
Figura 17: Exemplo de uma árvore parcial 
de jogo de duas jogadas
O que é este tal de “minimax”?
A partir da árvore de jogo, uma es-
tratégia ótima para a escolha das ações 
é determinada pelo valor minimax de 
cada nó. O valor minimax de um nó é a 
utilidade que MAX conhece de se en-
contrar no estado correspondente, supon-
do-se que ambos os jogadores tenham 
desempenho ótimo desde esse estado 
até o fim do jogo. O valor minimax de 
um estado terminal é simplesmente sua 
utilidade. MAX sempre terá a tendên-
cia de se mover para um estado de valor 
máximo, enquanto MIN preferirá um 
estado de valor mínimo, ou seja, dado 
que minimax é VALOR-MINIMAX(n):
O algoritmo MinMax-VALOR, 
ilustrado abaixo, calcula a decisão mi-
nimax a partir do estado atual (“estado”). 
De forma recursiva, o algoritmo percorre 
todo o caminho descendente até as folhas 
da árvore e, depois, os valores minimax 
são propagados de volta pela árvore, à 
medida que a recursão retorna.
45INTELIGÊNCIA ARTIFICIAL
No exemplo da Figura17, o algoritmo MinMax-VALOR, 
primeiro percorre todo o caminho desde o nó raiz até o nó 
terminal mais à esquerda, no terceiro nível de profundidade da 
árvore. Retorna com a função UTILIDADE (estado) sobre eles 
para descobrir que seus valores são 3, 12 e 8, respectivamente. 
Em seguida, calcula o mínimo desses valores, 3, e o devolve 
como valor propagado de volta para o nó B. Um processo se-
melhante fornece os valores propagados de volta de 2 para C 
e 2 para D. Por fim, tomamos o valor máximo entre 3, 2 e 2 
para obter o valor propagado de volta igual a 3 para o nó raiz.
O algoritmo minimax explora completamente árvore de jogo 
em profundidade. A complexidade de tempo e espaço do algoritmo 
é O(bm), para uma profundidade máxima de m e b movimentos 
válidos, caso todos os sucessores sejam gerados de uma vez. A 
complexidade de espaço será O(m) quando as ações forem geradas, 
uma de cada vez. Em jogos reais, o custo de tempo é totalmente 
impraticável, pois a busca é exponencial em relação ao número 
de movimentos. Uma estratégia importante é a possibilidade de 
calcular a decisão minimax correta sem examinar todos os nós 
na árvore de jogo. Esta estratégia se chama Poda Alfa-Beta.
A poda Alfa-Beta é um processo de eliminar ramificações 
da árvore sem examiná-las, descartando os que não contenham 
bons movimentos. Aplica-se a ambos os jogadores e α (Alfa) 
denota a melhor escolha para MAX, enquanto β (Beta) denota 
a melhor escolha para MIN.
A partir da Figura 18, o princípio da Poda Alfa-Beta 
define que:
46INTELIGÊNCIA ARTIFICIAL
• se o valor α representa o melhor valor encontrado para MAX 
(ou MIN), e se ѵ é pior do que β, MAX/MIN já achou uma 
jogada boa e pode evitar a ramificação para v.
Figura 18: Exemplo de princípio da poda alfa-beta
Um algoritmo para a Poda Alfa-Beta é ilustrado a seguir:
47INTELIGÊNCIA ARTIFICIAL
Síntese
Este capítulo introduziu métodos de resolução de problemas através de processos de busca, definindo es-
tratégias que um agente pode usar para selecionar ações em ambientes determinísticos, observáveis, estáticos e 
completamente conhecidos. A identificação de um objetivo e a formulação de um problema são etapas crítica 
na resolução de problemas. A formulação através da definição de um estado inicial, um conjunto de ações, um 
modelo de transição, a função de teste de objetivo e as métricas de custo são indispensáveis para um agente 
planejar a resolução.
Algoritmos genéricos de busca consideram todos os caminhos possíveis em estratégias de buscas em árvores, 
enquanto que, se considerarmos a busca em grafos, podemos evitar a construção de caminhos redundantes. Analisar 
os algoritmos em termos de sua completude, otimização e complexidade em tempo e espaço é uma importante 
etapa da determinação da performance do algoritmo e na definição da qualidade das soluções encontradas.
Os Toy Problems aqui apresentados e suas estratégias de solução constituem experimentos e esforço de 
pesquisa de aplicação em problemas no mundo real. Determinar voos ótimos de linhas aéreas, aplicação do pro-
blema do caixeiro-viajante, entre outros, constituem aplicação direta de uma estratégia combinatória-padrão em 
Computação. Aproximações do problema do caixeiro-viajante são utilizadas em desenho de layouts de circuitos 
VLSI (Very-Large-Scale Integration) e em problemas de navegação e montagem de robôs.
48INTELIGÊNCIA ARTIFICIAL
Exercícios
Formulação de problemas
Procure construir a formulação dos pro-
blemas (espaço de estados, estados inicial e 
finais, teste objetivo, operadores e custo do 
caminho) abaixo, ilustrando com um grafo 
parcial de busca:
Robô aspirador: como exercício, pro-
cure definir uma formulação adequada para 
o problema do robô aspirador, construindo 
o espaço de estados possíveis, os estados 
inicial e final, as ações do robô (regras ou 
operadores), o teste de término e o custo 
do caminho.
Jogo de 8-números: também conhecido 
como n-puzzle, consiste em um tabuleiro 
den×ncasas, contendo n*n-1números ini-
cialmente desordenados arranjados aleato-
riamente em cada casa do tabuleiro. Tome 
como exemplo um tabuleiro de 3×3 casas, 
distribuídos a seguir:
Início:
O objetivo é alcançar uma configura-
ção com os números ordenados através de 
movimentos que só podem ser feitos para a 
casa que está sempre vazia:
Final:
Problema dos vasilhames com água: 
existem 2 vasilhames, 1 de 4 litros e outro 
de 3 litros, sem medidas. Uma torneira pode 
ser utilizada para enchê-los. O objetivo é 
colocar exatamente 2 litros de água no va-
silhame de 4 litros.
Problema dos canibais e missionários: 
três canibais e três missionários estão via-
jando juntos e chegam à margem de um rio. 
Eles desejam atravessar para a outra margem 
e desta forma, continuar a viagem. O único 
meio de transporte disponível é um barco 
que comporta no máximo duas pessoas. Há 
uma outra dificuldade: em nenhum momen-
to o número de canibais pode ser superior ao 
número de missionários, pois desta forma, 
os missionários estariam em grande perigo 
de vida. Como administrar a travessia?
4 5 8
1 6
7 2 3
1 2 3
4 5 6
7 8
49INTELIGÊNCIA ARTIFICIAL
Estratégia busca não-informada ou cega
1. Escreva os algoritmos para busca em profundidade limitada 
e busca em profundidade iterativa, sabendo que:
• Na busca com profundidade limitada, a busca não ultrapassa 
um valor limite de profundidade. A solução deve encon-
trar-se dentro desse limite. Esse tipo de busca não tem uma 
solução ótima.
• Na busca em profundidade iterativa, tenta-se primeiro uma 
busca em profundidade com limite de profundidade 0; se 
não existe uma solução, repete-se o procedimento com pro-
fundidades 1, 2, ..., n até alcançar uma solução.
2. Baseado na análise da busca em amplitude, faça a análise 
das buscas em profundidade, profundidade limitada e pro-
fundidade iterativa (sem os exemplos de complexidade).
Busca competitiva
1. Construir a árvore minimax com os payoffs indicados nos 
nodos terminais para o Jogo dos 5 palitos:
• Objetivo do jogo: de um conjunto de 5 palitos, pegar 1 ou 
2 palitos e não ser o último a jogar.
• Exemplo de Cenário 1:
• Jogador 1: retira 2 palitos
• Jogador 2: retira 2 palitos
• Jogador 1: retira o último (perde).
• Exemplo de Cenário 2:
• Jogador 1: retira 1 palito.
• Jogador 2: retira 2 palitos.
• Jogador 1: retira 1 palito.
• Jogador 2: retira o último (perde).
2. Construa o caminho dos nós da árvore na Figura 17, usan-
do a Poda Alfa-Beta, indicando os caminhos que serão 
descartados.
50INTELIGÊNCIA ARTIFICIAL
SISTEMAS 
ESPECIALISTAS
Existem problemas cujo domínio está apenas 
na cabeça das pessoas, não formalizado.Neste caso, é preciso resolver problemas com 
a ajuda de um especialista e a simulação de 
sua inteligência.
51INTELIGÊNCIA ARTIFICIAL
Sistemas especialistas armazenam e processam conheci-
mento adquirido a partir da interação com especialistas em uma 
área de conhecimento. Inicialmente, constituem apoio à decisão, 
usando conhecimentos sobre áreas específicas, de acordo com 
comportamento humano diante destas situações. Geralmente, 
os sistemas especialistas usam métodos inferenciais na resolução 
de problemas complexos, a partir da experiência humana.
Antes de mais nada, é preciso que o sistema incorpore algum 
conhecimento humano para poder tomar decisões, responden-
do questões através de um processo de tomada de decisão ou, 
simplesmente, dividindo esse processo por meio de interações 
com o especialista.
Basicamente, como qualquer abordagem de IA, um sistema 
especialista simula o comportamento humano. Um especialista 
se baseia em fatos estabelecidos para formular hipóteses a fim 
de tomar uma decisão sobre um determinado assunto. Para isto, 
busca em sua memória um conhecimento previamente armaze-
nado, no período de sua formação ou no decorrer de sua vida 
profissional, sobre esses fatos e hipóteses. Finalmente, usa sua 
experiência sobre os fatos e hipóteses para emitir uma decisão.
Sistemas especialistas podem ser diretamente aplicados a 
vários tipos de tarefas de resolução de problemas:
• Tarefas de diagnóstico: processo de encontrar falhas em 
um sistema ou doenças em seres vivos. Exemplo: MYCIN 
diagnóstico de infecção sanguínea (Shortlife, 1973).
• Tarefas de interpretação: análise de dados para determinar 
seu significado. Exemplo: PROSPECTOR (Duda et al., 
1977) interpretação de dados geológicos como evidência 
para depósitos minerais.
• Tarefas de monitoramento: interpretação contínua de sinais 
em um sistema com objetivo de diagnosticar ou dar um alarme. 
Exemplo: NAVEX monitoramento de dados de radar para 
estimar velocidade e posição do Space Shuttle (Marsh, 1984).
52INTELIGÊNCIA ARTIFICIAL
• Tarefas de projeto (design): produção de especificações de 
sistemas que satisfaçam a requerimentos particulares. Exem-
plo: R1/XCON configuração de sistemas VAX baseada nas 
necessidades do cliente (McDermott, 1980).
• Tarefas de planejamento: produção de uma sequência de 
ações para atingir um objetivo específico. Exemplo: MOL-
GEN planejamento de processos químicos para análise e 
síntese de DNA (Stefik, 1981).
• Tarefas de predição: previsão de eventos futuros usando 
um modelo baseado em dados do passado e do presente. 
Exemplo: PLANT, previsão dos danos esperados quando 
determinada praga atacava o milho (Boulanger, 1983).
Alguns exemplos de sistemas especialistas históricos:
1965: DENDRAL (Stanford): Inferência sobre estruturas químicas.
 MACSYMA (MIT): Análise de equações simbólicas diferenciais.
HERSAY (Carnegie-Mellon): Interpretação de conjuntos fonéticos 
em linguagem natural.
1972: MYCIN (Stanford): Diagnóstico de doenças sanguíneas.
 PROSPECTOR (Stanford): Exploração e identificação de minérios.
1980: R1/XCON (Carnegie-Mellon): Configuração de computadores DEC.
Um rápido exemplo de uma aplicação do MYCIN (Da-
vis et al., 1977) é um modelo para diagnosticar meningite 
e outras infecções bacterianas, e prescrever tratamento:
• Representação de conhecimento baseada em regras 
probabilísticas (em torno de 500).
• Acima de 90% de acerto.
• Introduziu explicação e boa interface com usuário.
• Exemplo de regra:
53INTELIGÊNCIA ARTIFICIAL
Arquitetura de um sistema especialista
Existem várias estruturas e arquiteturas possíveis em que 
se pode organizar um sistema especialista. Geralmente, os 
principais elementos constituintes de um sistema especialista 
genérico são os exemplificados na Figura 19. 
Figura 19: Arquitetura geral de um sistema especialista básico
O Usuário é o elemento responsável pela verificação e 
validação do comportamento do sistema. Pode ser o especia-
lista que adiciona conhecimento ou modifica o conhecimento 
armazenado no sistema. Realiza as interações para obter res-
postas do sistema ou desenvolver especialidade relacionada ao 
domínio, extraindo conhecimento organizado.
A Base de Conhecimento (BC) constitui o repositório das 
primitivas de conhecimento: fatos, regras e heurísticas. O 
projeto deste dispositivo inf luencia o projeto e mecanismo de 
inferência, o processo de atualização do conhecimento e o me-
canismo de atualização. Para seu desenvolvimento, utilizam-se 
técnicas de representação do conhecimento, tais como: regras 
de produção, redes semânticas, frames, scripts, etc.
O processo de construção de uma base de conhecimento 
específico ao domínio é tarefa de um especialista conhecido 
como Engenheiro do Conhecimento.
54INTELIGÊNCIA ARTIFICIAL
AQUISIÇÃO
NÍVEL DE CONHECIMENTO
NÍVEL LÓGICO
NÍVEL DE IMPLEMENTAÇÃO
FORMULAÇÃO
IMPLEMENTAÇÃO
REFINAMENTO BC
O processo de aquisição do conhecimento pressupõe um 
levantamento de requisitos de conhecimento, isto é, extrair, 
estruturar e organizar o conhecimento de uma ou mais fontes. 
É a atividade inicial do processo de engenharia de conhecimen-
to, e indispensável para que as informações essenciais sejam 
coletadas e o conhecimento chave fique disponível para ser 
organizado, representado, implementado e validado através de 
um sistema. Geralmente, aplicam-se técnicas de pesquisa quali-
tativas: entrevistas, questionários, narrativas, técnicas manuais, 
semiautomáticas ou automáticas, como algoritmos de extração 
de conteúdo de documentos, mineração de dados, raciocínio 
baseado em casos, aprendizado de máquina, entre outras.
Nos sistemas especialistas, o aprendizado ocorre com a in-
corporação de novas regras nas bases de conhecimento. A cada 
processamento da base de conhecimento, o sistema especialista 
assume como verdade o conhecimento ali formalizado. Isto é pos-
sível em virtude da estrutura modular da base de conhecimento, 
permitindo a adição ou deleção de novos elementos sem alterar 
a lógica global do sistema.
Na etapa de formulação e implementação, o engenheiro precisa 
formalizar na Base de Conhecimento, podendo ser representado, 
por exemplo, através de regras de produção. Um conjunto de regras 
de produção pode ser mapeado em árvores de decisão, que são 
representações mais simples do conhecimento e, um meio efi-
ciente de construir classificadores que predizem classes baseadas 
nos valores de atributos de um conjunto de dados. Tecnicamente, 
árvores de decisão são grafos acíclicos que consistem de nodos 
que representam os atributos de arcos, provenientes destes nodos 
e que recebem os valores possíveis para estes atributos, e de no-
dos-folha, que representam as diferentes classes de um problema.
55INTELIGÊNCIA ARTIFICIAL
O Motor de Inferência é o componente do SE que aplica um 
conjunto de regras lógicas sobre a BC para deduzir informações 
novas, fornecendo elementos para a aprendizagem e explanação 
do problema. 
A capacidade do motor de inferência é baseada em um inter-
pretador capaz de percorrer a BC e buscar fatos que, deduzidos por 
regras de inferência lógicas, consegue inferir novo conhecimento. 
Duas estratégias de raciocínio são comumente usadas: 
• Forward chaining: encadeamento progressivo que inicia pelas 
condições e vai em direção aos objetivos.
• Backward chaining: encadeamento regressivo que inicia pelos 
objetivos e vai em direção às condições.
Estas regras são armazenadas na base 
de conhecimento no formato SE/ENTÃO, 
usando a seguinte gramática simplificada:
O motor de inferência pode processar estas regras usando 
encadeamento regressivo, se começar com a solução, e verifi-
car tal solução fazendo perguntas ao usuário para verificar o 
resultado. As perguntas feitas ao usuário são apenas para obter 
informações que não estão na base de conhecimento.
O encadeamento progressivo acontece no questionamen-
to ao usuário por toda a informação necessária. Em seguida, 
esta informação é usada com diferentesregras para ver se ela 
se ajusta a quaisquer dos problemas previamente descritos. Se 
ajustar, ela repassa a possível solução ao usuário.
Sendo um mecanismo genérico de causa e efeito (SE-
-ENTÃO), o motor de inferência pode ser reutilizado em 
vários contextos. Os demais componentes variam em função 
da aplicação. O motor de inferência é o módulo do sistema 
responsável pelo processo de inferência que é aplicado sobre o 
conhecimento disponível na base de conhecimento em função 
dos fatos informados via interface ou obtidos da base de dados.
SE
 <Condição 1>
 <Condição 2>
ENTÃO
 <Conclusão 1>
 <Conclusão 2>
56INTELIGÊNCIA ARTIFICIAL
Modo de raciocínio
Em um sistema especialista baseado em regras, o conhe-
cimento do domínio é todo representado em relações de con-
sequência por regras de produção no formato SE-ENTÃO 
agrupados em um conjunto “Regras (MR)”. Os dados são 
representados por um conjunto de fatos sobre a situação cor-
rente “Fatos (MF)”. A máquina de inferência compara cada 
regra a partir dos fatos armazenados na base de conhecimento, 
através de um mecanismo de “Pattern Matching”. Quando a 
parte da condição “SE” combina com algum fato na base de 
conhecimento, a regra é disparada e a ação na parte “ENTÃO” 
é executada. A combinação de regras com os fatos determina 
uma cadeia de inferência ou modo de raciocínio que pode alterar 
a base de conhecimento, descobrindo fatos novos, conforme o 
f luxo desta Figura:
Regras (MR) Fatos (MF) 
Conjunto de Conflitos (CC)
Pattern Matching
Resolução de conflitos
Disparo da(s) regra(s)
Regra(s) escolhida(s)
Alterações em MF (MR)
Eventualmente, um conjunto de fatos pode disparar a 
mesma regra, ou um fato pode fazer parte de várias regras na 
parte de condição, neste caso, um Conjunto de Conflitos (CC) 
é gerado. Quando isto ocorre, um mecanismo de resolução de 
conflitos deve ser acionado a fim de desambiguar as regras e 
definir uma geração determinística de fatos.
57INTELIGÊNCIA ARTIFICIAL
Vamos a um exemplo prático. Su-
ponha que seja necessário construir um 
sistema especialista para oferta de em-
prego especializado:
• Variáveis:
• Descoberta: o candidato fez alguma 
descoberta?
• Experiência: quantos anos de ex-
periência tem o candidato?
• Média: qual a nota média do can-
didato em seu curso superior?
• Posição: que posição deve ser ofe-
recida ao candidato?
• Qualifica: o candidato se qualifica 
para uma posição?
Após esta etapa de aquisição do co-
nhecimento, as variáveis que conciliarão a 
base de fatos, podem ser assim formuladas:
Variáveis de entrada com respectivos valores:
Descoberta: Sim / Não.
Diploma: Sim / Não.
Experiência (em anos): um número. 
Média (nota média do histórico): um número.
Variáveis de saída com valores possíveis: 
Posição: Nenhuma / Pesquisa / Eng. De Serviço / 
Eng. De Produto.
Qualifica: Sim / Não.
Seja o conjunto de regras assim assi-
nalado, formando a Memória de Regras 
(MR):
R1: SE (Diploma = Não)
 ENTÃO (Posição <-- Nenhuma).
R2: SE (Diploma = Sim) 
 ENTÃO (Qualifica <-- Sim).
R3: SE (Diploma = Sim) E (Descoberta = Sim) 
 ENTÃO (Posição <-- Pesquisa).
R4: SE (Qualifica = Sim) E (Média <= 7,0) E (Experiência 
>= 2)
 ENTÃO (Posição <-- Eng. De Serviço).
R5: SE (Qualifica = Sim) E (Média < 7,0) E (Experiência 
> 2) 
 ENTÃO (Posição <-- Não).
R6: SE (Qualifica = Sim) E (Média > 7,0) 
 ENTÃO (Posição <-- Eng. de Produto).
O conjunto de fatos iniciais, forman-
do a Memória de Fatos (MF) é assim 
inicializado:
F0: (Diploma = Sim).
F1: (Experiência = 1,5).
F2: (Média = 8,0).
F3: (Descoberta = Não).
O modo de inferência usando Fo-
rward-Chaining, apresenta o seguinte 
algoritmo:
58INTELIGÊNCIA ARTIFICIAL
A execução completa do algoritmo, até que nenhuma regra 
seja mais disparada, constrói as três épocas abaixo:
O modo de inferência usando Backward-Chaining, apre-
senta o seguinte algoritmo:
Neste caso, a cadeia de inferência será:
Fatos iniciais (M0):
F0: (Diploma = Sim).
F1: (Experiência = 1,5).
F2: (Média = 8,0).
F3: (Descoberta = Não).
Inferência 1: Dispara R2.
F4: (Qualifica = Sim).
Fatos iniciais (M1):
F0: (Diploma = Sim).
F1: (Experiência = 1,5).
F2: (Média = 8,0).
F3: (Descoberta = Não).
F4: (Qualifica = Sim).
Inferência 2: Dispara R6.
F5: (Posição = Eng. de Produto).
Fatos iniciais (M2):
F0: (Diploma = Sim).
F1: (Experiência = 1,5).
F2: (Média = 8,0).
F3: (Descoberta = Não).
F4: (Qualifica = Sim).
F5: (Posição=Eng.de Produto).
Não dispara mais regras.
59INTELIGÊNCIA ARTIFICIAL
Tratamento de incerteza
O tratamento da incerteza lida com o raciocínio inexato e 
pode ser feito através da utilização de valores intermediários 
entre os valores verdadeiro e falso. A forma clássica de imple-
mentação é feita pela quantificação do grau ou fator de certeza 
do conhecimento, conforme alguma escala convencionada pelo 
especialista.
Um exemplo de escala para o grau de incerteza do conhe-
cimento utilizado no sistema MYCIN (Davis et al., 1977) é 
apresentado na Tabela: Fator de Certeza Significado
100 Definitivamente certo
80 Quase certo
60 Provável
30 Há evidências
20 Ignorado
0 Ignorado
-20 Ignorado
-40 Há evidências contra
-60 Provavelmente não
-80 Quase certo que não
-100 Definitivamente não
Os Fatores de Certeza (FC), usados para tratamento de 
incerteza, foram originalmente definidos como a diferença 
entre a crença e a descrença, onde a partir de uma hipótese 
(H) dada a evidência (E), envolve o cálculo das funções:
• MC[H, E]: grau de aumento da crença na hipótese H, se E for ob-
servada.
• MD[H, E]: grau de aumento da descrença na hipótese H, se E for 
observada.
Ambas as medidas MC e MD serão definidas em função de:
• p(H): probabilidade a priori de H;
• p(H|E): probabilidade a posterior de H ou probabilidade condicional, 
dada a evidência E.
Logo, o fator de crença FC na hipótese H dada a evidência 
E é calculado por:
• FC [H, E] = MC[H, E] – MD[H, E]
60INTELIGÊNCIA ARTIFICIAL
A partir desta abordagem é possível combinar crença e descrença 
em uma medida de utilidade, por exemplo, se um paciente tem cer-
tos sintomas os quais sugerem diversas doenças possíveis, a doença 
com um alto FC poderia ser a primeira a ser investigada pelos testes 
ordenados.
O FC representa uma rede de crenças em uma hipótese sobre 
alguma evidência, onde um FC positivo significa que a evidência 
suporta a hipótese desde que MC > MD. Um FC=1 significa que a 
evidência definitivamente prova a hipótese enquanto um FC=0 pode 
significar:
• que não existe evidência ou ela é irrelevante (MC=MD=0);
• a crença é cancelada pela descrença, pois as duas são igualmente 
fortes ou fracas (MC=MD≠0).
Em contrapartida, um FC negativo significa que a evidência favo-
rece a negação da hipótese, desde que MC < MD, ou seja, existem mais 
razões para a descrença em uma hipótese do que para a crença nela.
Sistema de explanação
O sistema de explanação é usado quando um usuário 
precisa de uma explicação sobre a cadeia de inferência 
realizada de SE, exibindo “por que” e “como” o sistema 
chegou a determinada conclusão, rumo à solução do 
problema analisado. O processo é caracterizado por uma 
busca inversa, percorrendo as trilhas utilizadas e mar-
cadas durante a sessão de consulta, apresentando todos 
os argumentos que o levaram à solução apresentada. 
O processo de explanação também pode ser utili-
zado como instrumento de treinamento do usuário, já 
que apresenta conceitos teóricos e aplicações práticas, 
reforçando a tese da importância das interfaces na apli-
cação de sistemas especialistas.
Para fornecer explanações, um SE necessita utilizar 
“metaconhecimento”, conhecimento sobre o seu próprio 
61INTELIGÊNCIA ARTIFICIAL
conhecimento e, “introspecção”, observação sobre o seu próprio 
modo de operação. Muitas vezes estas explicações são feitas listando 
as regras que estão sendo utilizadas.
O objetivo da explanação é apresentar o comportamento do 
SE através de questões como:
• Por que uma certa pergunta foi feita pelo SE?
• Como a conclusãofoi alcançada?
• Por que alguma alternativa foi rejeitada?
• Qual é o plano para alcançar a solução?
Por exemplo, para responder à pergunta “por que é necessário 
saber o preço?”, o sistema de explanação navega pela árvore da ca-
deia de inferência buscando as informações contidas no conjunto de 
regras. Assim, uma explanação pode ser a apresentação da própria 
regra que disparou alguma condição:
REGRA #5
 SE preço = importante E pagamento = prestação
 ENTÃO
 pagamento mensal é determinado
Ferramentas de sistemas especialistas
Atualmente, a própria IA se confunde com Sistemas 
especialistas, por este ser apenas uma técnica de aplica-
ção, muitas ferramentas foram criadas especificamente 
para modelar sistemas especialistas, tal como foi abor-
dado neste capítulo. O quadro ilustrará alguns exemplos 
de ferramentas, sistemas e abordagens que podem ser 
usados em aplicações de sistemas especialistas:
62INTELIGÊNCIA ARTIFICIAL
Ferramenta Descrição Acesso
BABYLON Permite desenvolver frames, regras de produção, lógica (PROLOG) e restrições. Requer o Common Lisp instalado.
https://www.cs.cmu.edu/afs/cs/project/ai-repository/
ai/areas/expert/systems/babylon/0.html
CLIPS (C Language Integrated 
Production System)
Baseado em forward-chaining, escrito em C. Desenvolvido pela NASA. 
Plataformas: DOS, Windows, VMS, Mac e UNIX. http://www.clipsrules.net/Documentation.html
DYNACLIPS (DYNAamic CLIPS 
Utilities)
Conjunto de ferramentas constituído por blackboard, troca de conhecimento 
dinâmico e agentes que podem ser linkados com CLIPS.
https://www.cs.cmu.edu/afs/cs/project/ai-repository/
ai/areas/expert/systems/clips/dyna/0.html
FuzzyCLIPS CLIPS com conceitos nebulosos (fuzzy) e raciocínio. https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/fzclips/0.html
Jess the Rule Engine for Java Ambiente para máquina de regras declarativas em Java. https://herzberg.ca.sandia.gov/jess/
Expert SINTA
Representação do conhecimento baseado em regras de produção e fatores de 
confiança. Motor de inferência compartilhado: construção automática de telas e 
menus, tratamento de incerteza e utilização de explicações sensíveis ao contexto. 
http://www.lia.ufc.br/~bezerra/exsinta/
PIKE - Python knowledge engine Através de regras de forward/backward chaining através de código python. http://pyke.sourceforge.net
EZ-Xpert 3.0 Sistema baseado em regras que apresentam rápido desenvolvimento, grande velocidade e precisão, implementado sem um mecanismo de inferência. http://www.ez-xpert.com/index.html
LPA (Logic Programming 
Associates) Plataforma para desenvolvimento de Sistemas especialistas. http://www.lpa.co.uk/pro_exp.htm
IBM Watson Conjunto de ferramentas de IA, entre elas, sistemas baseados em regras. www.ibm.com/watson/br-pt
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/babylon/0.html
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/babylon/0.html
http://www.clipsrules.net/Documentation.html
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/dyna/0.html
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/dyna/0.html
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/fzclips/0.html
https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/fzclips/0.html
https://herzberg.ca.sandia.gov/jess/
http://www.lia.ufc.br/~bezerra/exsinta/
http://pyke.sourceforge.net/
http://www.ez-xpert.com/index.html
http://www.lpa.co.uk/pro_exp.htm
http://www.ibm.com/watson/br-pt
63INTELIGÊNCIA ARTIFICIAL
Síntese
Neste capítulo abordamos detalhes dos vários temas pertencentes ao estudo de 
Sistemas multiagentes, principalmente aliando questões conceituais com aplicações 
práticas e introdução a algoritmos básicos de comportamento de sistemas de agentes. 
Estudos mais recentes integram comportamentos cognitivos com representação de 
objetos inativos do ambiente, artefatos simbólicos de atuação do agente e repre-
sentação de questões normativas para comportamento social. A área de simulação 
atrai bastante atenção para a simulação de modelos matemáticos através de com-
portamentos reativos e deliberativos de múltiplas entidades interagentes.
As questões aqui abordadas são base para aplicações, envolvendo tomadas de 
decisão, planejamento autônomo, elaboração de metas, avaliação de atividades co-
ordenadas e inteligência distribuída.
64INTELIGÊNCIA ARTIFICIAL
Exercícios
Problema 1: Diagnóstico de falha de automóveis
O usuário expõe o problema, dizendo que “tentou ligar o 
carro hoje e o motor não funcionou”!
• Procure modelar o problema utilizando regras de produção 
a partir da seguinte explicação do especialista:
• Quando o motor de um carro não arranca, minha primeira 
suspeita é de que o carro esteja sem gasolina. Porém, se 
há cheiro de gasolina quando se tenta arrancar, ou se tem 
a certeza que o tanque está cheio, suspeito que a gasolina 
pode não chegar ao carburador, logo, a mangueira pode estar 
bloqueada. Se até aqui tudo está bem, tente ligar os faróis 
para testar a bateria ou algum problema elétrico.
Problema 2: Diagnóstico médico
Três diagnósticos distintos são identificados através dos 
seguintes conjuntos de sintomas e problemas associados.
• Modele o problema de forma que o conjunto de regras 
possa inferir as recomendações segundo as evidências. Como 
existem evidências compartilhadas, acrescente fatores de certeza 
para inferir múltiplas recomendações por ordem de certeza.
Gripe
• espirros
• febre
• dores no corpo
• coriza
• cansaço
Recomendação: 
vitamina C, repouso
Recomendação: 
antibiótico, repouso
Recomendação: 
antibiótico, xarope, 
repouso
Amidalite
• dor ao engolir
• febre
• amídalas inchadas e 
avermelhadas
Bronquite
• tosse seca
• febre
• cansaço
• amidalite
65INTELIGÊNCIA ARTIFICIAL
Problema 3: Diagnóstico financeiro
Um banco está disponibilizando aos seus clientes um empréstimo de R$20.000,00 para compra de au-
tomóveis. Os clientes que solicitam o empréstimo são avaliados pela instituição, verificando se tem ou não 
direito ao benefício.
• Apresente a modelagem dos fatos e das regras de produção para inferência da avaliação dos clientes.
• Escolha uma das ferramentas de desenvolvimento de sistemas especialistas deste capítulo e procure 
implementar o módulo de avaliação do problema financeiro.
Características essenciais de clientes habilitados
• Residência = Porto Alegre
• Renda acima de R$ 1500,00
• Outras características de clientes habilitados
• Emprego com carteira assinada
• Estado civil = casado, divorciado
• Casa própria
• Carro quitado
• Idade superior a 25 anos
66INTELIGÊNCIA ARTIFICIAL
ALGORITMOS 
GENÉTICOS
É possível encontrar soluções cada vez 
melhores a partir da evolução das gerações 
anteriores, baseando-se nos processos 
naturais de evolução. Computação evolutiva 
determina a sobrevivência dos melhores 
candidatos, construindo uma população de 
soluções ótimas.
67INTELIGÊNCIA ARTIFICIAL
Algoritmos genéticos representam um tipo de estratégia 
de busca de soluções em que os estados sucessores são gerados 
pela combinação de dois estados, ao invés da geração ocorrer 
tradicionalmente apenas sobre um único estado.
As estratégias de busca vistas até agora exploravam sistema-
ticamente espaços de busca, mantendo-se um ou mais caminhos 
na memória, registrando as alternativas exploradas em cada 
ponto do caminho. A solução encontrada é o caminho completo 
até o estado objetivo. Nem sempre a solução necessária é este 
caminho, problemas de otimização baseados em n-queens, por 
exemplo, tais como projeto de circuitos integrados, leiaute de 
instalações industriais, escalonamento de jornadas de trabalho, 
programação automática, otimização de rede de telecomunica-
ções, roteamento de veículos, gerenciamento de carteiras, entre 
outros, buscam uma configuração final otimizada das rainhas 
(ou recursos) e não a ordem em que elas são posicionadas.
Algoritmosde busca local têm duas vantagens: (1) usam 
pouquíssima memória — normalmente um valor constante; 
e (2) frequentemente podem encontrar soluções razoáveis em 
grandes ou infinitos (contínuos) espaços de estados para os 
quais os algoritmos sistemáticos são inadequados.
A Figura 20 ilustra uma topologia de espaço de estados 
em que a “posição” é definida pelo estado e a “elevação” é de-
finida pelo valor da função de custo da heurística ou da fun-
ção objetivo. Se o custo do problema corresponder à elevação, 
então o objetivo será encontrar o vale mais baixo – um míni-
mo global; se a elevação corresponder a uma função objetivo, 
então o objetivo será encontrar o pico mais alto – um máximo 
global. Os algoritmos de busca local exploram essa topologia. 
Um algoritmo de busca local completo sempre encontra um 
objetivo, caso ele exista; um algoritmo ótimo sempre encontra 
um mínimo/máximo global.
68INTELIGÊNCIA ARTIFICIAL
Figura 20: Exemplo de topologia de espaço de estados 
unidimensionais
Pensando nas aplicações locais de otimização, o objetivo 
ideal é encontrar o melhor estado de acordo com uma função 
objetivo, mas as estratégias de busca vistas até agora, como por 
exemplo, a busca Gulosa é oportunista quando encontra um 
caminho parcial menos custoso. Geralmente caem em um vale 
e podem ficar presos em um máximo local, como no exemplo 
da Figura 20, onde o círculo representando o estado corrente 
sobe em direção a uma solução não tão boa.
Algoritmos genéticos (Goldberg, 1989; Mühlenbein, 1992; 
Whitley, 1994) são estratégias bioinspiradas, baseados em 
abordagens evolutivas, onde, por exemplo, a natureza fornece 
uma função objetivo, que é a adaptação reprodutiva tentando 
otimizar do ponto de vista da evolução de Darwin, mas sem 
nenhum “teste de objetivo” ou “custo de caminho” para esse 
problema. Conforme o próprio Darwin (1859): “quanto melhor 
um indivíduo se adaptar ao seu meio ambiente, maior será sua 
chance de sobreviver e gerar descendentes”.
Função objetivo
Máximo global
Máximo local
Máximo local “plano”
Espaço de estados
Estado corrente
planície
69INTELIGÊNCIA ARTIFICIAL
Princípios básicos
Os principais componentes de estratégias baseados em 
abordagens evolutivas são:
• Definição de indivíduos (representação).
• Função de avaliação ou aptidão (fitness).
• Representação da população.
• Mecanismo de seleção de progenitores.
• Operadores de manipulação de população e indivíduos (variação, 
recombinação e mutação).
• Mecanismo de seleção de sobreviventes.
Algoritmos genéticos guiam-se principalmente por alguns 
princípios básicos de funcionamento:
• Manipulação de uma população de indivíduos.
• Indivíduos são soluções candidatas do problema.
• Os indivíduos são combinados (crossover) uns com os outros, produ-
zindo filhos que podem sofrer ou não mutação.
• Populações evoluem através de sucessivas gerações até encontrar uma 
solução ótima.
• Uma função de aptidão (fitness) testa os indivíduos como a natureza 
testa a todos nesta vida.
• São estocásticos (não-determinísticos).
• Trabalham com uma população de soluções simultaneamente (evolução).
• Utilizam apenas informações de custo e recompensa.
• São facilmente hibridizados com outras técnicas.
• Funcionam com parâmetros contínuos ou discretos.
A principal característica dos algoritmos genéticos é o fato 
deles serem algoritmos de busca:
• Cega: sem conhecimento específico do problema, exceto à função objetivo.
• Codificada: trabalha com representações dos elementos do domínio 
do problema.
• Múltipla: executa busca simultânea em um conjunto de candidatos.
• Estocástica: combina em proporção variável regras probabilísticas e 
determinísticas. Esse conceito refere tanto as fases de seleção como 
as de transformação.
70INTELIGÊNCIA ARTIFICIAL
Funcionamento do algoritmo genético
Em abordagens evolutivas, o problema precisa ser repre-
sentado com base em operações e comportamentos biológicos, 
conforme estabelecido por John Holland (1992) ao desenvolver 
os primeiros AGs na Universidade de Michigan. A codificação 
do problema do mundo real é representada pelos componentes:
• Fenótipo: problema do mundo real.
• Genótipo: codificação.
• Espaço fenotípico: constitui o espaço de soluções possíveis 
contendo as soluções candidatas, fenótipo e indivíduo.
• Espaço genotípico: cromossomo e indivíduo.
• Elementos dos indivíduos: variável, locus, gen, onde um 
objeto deste espaço pode ser um valor ou alelo.
A partir da formulação dos componentes “biológicos” do 
problema, um algoritmo de busca genético consiste, informal-
mente, no seguinte conjunto de passos:
1. Gerar a população inicial.
2. Avaliar cada indivíduo da população. 
3. Enquanto não alcançar o critério de parada:
• 3.1. Selecionar os indivíduos mais aptos. 
• 3.2. Criar indivíduos aplicando os operadores crossover e mutation.
• 3.3. Armazenar os novos indivíduos em uma nova população.
• 3.4. Avaliar cada cromossomo da nova população.
71INTELIGÊNCIA ARTIFICIAL
Uma representação em pseudocódigo de um algoritmo 
genético clássico é ilustrada a seguir, onde t é a geração atual, 
d é um critério de término (sucesso) e P, a população inicial 
de indivíduos.:
Examinaremos cada passo do funcionamento de um algo-
ritmo genético através de um exemplo simples. O problema é 
maximizar a função f(x)=x2 no intervalo x ∈ [0,31], conforme 
ilustrado no gráfico a seguir:
1000
800
600
400
200
0 5 10 15 20 25 30
72INTELIGÊNCIA ARTIFICIAL
Codificação
Cada indivíduo de uma população representa um candidato 
em potencial à solução do problema. No algoritmo genético 
clássico a codificação das soluções candidatas são feitas em 
arranjos binários de tamanho fixo. Segundo Holland (1992), 
este tipo de codificação auxilia no paralelismo implícito ine-
rente ao algoritmo genético. Outros problemas de otimização 
numérica com parâmetros reais, geralmente usam representa-
ção em ponto f lutuante, apresentando desempenho superior à 
codificação binária.
No nosso problema de maximização da função quadrática, 
os cromossomos serão representados através de um alfabeto 
binário com 5 bits:
0 = 00000
31 = 11111
Para a função de aptidão, pode-se usar a própria função 
objetivo, por exemplo:
 aptidão (00011) = f (3) = 9
A População Inicial do algoritmo é gerada de forma ale-
atória, embora um conhecimento mais apropriado da aplicação 
também possa definir uma população inicial. No caso do nosso 
exemplo, será inicialmente aleatória.
73INTELIGÊNCIA ARTIFICIAL
Mecanismos de seleção
Após a definição aleatória da população inicial, o AG pre-
cisa gerar novas populações e, para isto, são usados mecanismos 
de seleção. O AG clássico utiliza um esquema de seleção de 
indivíduos para a próxima geração, chamado Roulette Wheel 
(MICHALEWICZ, 1996).
O mecanismo Roulette Wheel atribui a cada indivíduo de uma 
população uma probabilidade de passar para a próxima geração 
proporcional a sua aptidão, em relação à somatória do fitness de 
todos os indivíduos da população. Quanto maior o fitness de um 
indivíduo, maior a probabilidade dele passar para a próxima geração. 
Para evitar se perder o melhor indivíduo na seleção, uma alternativa 
é escolher como solução o melhor indivíduo encontrado em todas 
as gerações do algoritmo. Assim, 
para nosso exemplo, a probabi-
lidade de seleção é proporcional 
à aptidão, desta forma:
Sem usar o mecanismo de seleção ainda, um exemplo de 
probabilidade de seleção é dado na tabela a seguir:
Um exemplo de algoritmo para considerar o mecanismo de 
Roulette Wheel com a seleção do melhor indivíduo em todas 
as gerações é exemplificado a seguir:
Cromossomos x Aptidão f(x)=x2 Prob. Seleção
A1=011001 25 625 54,54%
A2=001111
A3=001110
15
14
225
196
19,63%
17,10%
A4=001010 10 100 8,73%
74INTELIGÊNCIA ARTIFICIAL
Assim, a seleção Roulette Wheel para nosso exemplo pode 
funcionar conforme o esquema a seguir:
Onde os escolhidos nesta etapa seriam, na ordem, os in-
divíduos A1,A2,A3 e A4.
Uma abordagemalternativa é chamada SUS (Stochastic 
Universal Sampling), que seleciona k indivíduos utilizando k 
agulhas igualmente espaçadas, girando-as em conjunto, ob-
tendo resultados menos variantes que a Roulette Wheel clássica 
(Baker, 1987).
Outro mecanismo é a Seleção por torneio, um processo 
mais refinado, onde os indivíduos são ordenados em ordem 
crescente em relação a sua aptidão (comparado ao de seu opo-
nente). A menor aptidão recebe o valor 1, enquanto a maior 
recebe o valor N (ou seja, o número de indivíduos). O indivíduo 
é escolhido gerando um número aleatório entre 1 e a soma do 
Ranking.
75INTELIGÊNCIA ARTIFICIAL
Um exemplo de algoritmo para considerarmos o mecanismo 
de Seleção por torneio é ilustrado a seguir:
Um exemplo de seleção por torneio no problema da ma-
ximização da função é ilustrado a seguir:
Outros mecanismos de seleção: Seleção por diversidade, 
Seleção bi-classista, Seleção aleatória.
Operadores genéticos
Os operadores genéticos têm por função executar a recom-
binação de genes ou características dos indivíduos para produzir 
novos indivíduos na população. A operação de Cruzamento 
(Crossover) é o operador genético predominante, onde novas 
gerações são criadas misturando características de dois indi-
víduos. A operação envolve a troca de cadeias de genes de um 
indivíduo pela cadeia de genes equivalente do outro indivíduo.
As técnicas de cruzamento mais utilizadas são: Ponto único, 
2-pontos, Múltiplos pontos e Uniforme.
No Cruzamento de ponto único os indivíduos (μp1 e μp2) 
são particionados em um 
ponto e trocam uma cadeia 
de genes, gerando os indiví-
duos (μf1 e μf2), como ilus-
trado no esquema a seguir:
Torneios Pais selecionados Indivíduos Aptidão
A4 x A1 A1 A1 625
A3 x A2 A2 A2 225
A4 x A2 A2 A3 196
A3 x A3 A3 A4 100 
76INTELIGÊNCIA ARTIFICIAL
No Cruzamento de 2-pon-
tos, os indivíduos (μp1 e μp2) 
são particionados em dois pon-
tos e trocam as cadeias de genes, 
gerando os indivíduos (μf1 e 
μf2), conforme exemplificado 
no esquema :
No Cruzamento 
uniforme os indiví-
duos (μp1 e μp2) são 
particionados baseado 
em uma máscara, con-
forme Syswerda (1989), 
gerando os indivíduos 
(μf1 e μf2), como ilus-
trado no esquema:
Um exemplo da aplicação de uma técnica de cruzamento 
é aplicado com uma dada probabilidade denominada taxa de 
crossover (60% a 90%), por exemplo:
Neste exemplo, quando a operação de cruzamento é apli-
cada, os pais trocam as cadeias de genes gerando dois filhos, 
caso contrário, os dois filhos serão cópias exatas dos pais.
77INTELIGÊNCIA ARTIFICIAL
Outras técnicas alternativas de Cruzamento (Eshelman et 
al., 1989), especialmente desenvolvidas para utilização em pro-
blemas de otimização numérica restritos e codificação em ponto 
f lutuante são o cruzamento aritmético (Michalewicz,1996), o 
cruzamento geométrico e o cruzamento esférico, descritos em 
Michalewicz & Schoenauer (1996) e Bäck et al. (2000).
O segundo operador genético para combinação de indivíduos 
é a mutação, que provoca uma perturbação na convergência da 
população para manter a heterogeneidade. Na operação de muta-
ção apenas um indivíduo é escolhido para ter o valor de um dos 
seus genes modificados, gerando um novo indivíduo. Existem 
várias técnicas de seleção da característica (gen) a ser mutada: 
A Mutação Swap seleciona randomicamente duas posições 
no cromossomo e permuta os valores, como exemplificado no 
esquema a seguir:
A Mutação Insert seleciona randomicamente uma posi-
ção apenas no cromossomo e o insere em outra posição, como 
exemplificado no esquema a seguir:
Na Mutação Scramble um subconjunto de gens é ran-
domicamente selecionado e seus valores são misturados ou 
embaralhados, também randomicamente, como exemplificado 
no esquema a seguir:
78INTELIGÊNCIA ARTIFICIAL
Portanto, voltando ao nosso exemplo e aplicando algumas 
das técnicas acima de Cruzamento e Mutação genética, será 
possível gerar uma primeira geração do problema a partir do 
exemplo ilustrado na figura a seguir:
Para o restante das gerações futuras, as sucessivas transfor-
mações poderão produzir subpopulações, tais como os exemplos 
nas tabelas a seguir. Esta tabela ilustra uma subpopulação inicial 
de tamanho fixo (n=5), exibindo a probabilidade de seleção 
conforme a função de aptidão resultante de cada indivíduo. 
Conforme algum mecanismo de seleção escolhe os melhores 
indivíduos, operadores genéticos são aplicados para gerar a 
próxima subpopulação, exemplificada na Geração K e assim, 
sucessivamente.
GERAÇÃO INICIAL
Comossomos x f(x) Prob. seleção
011011 27 729 35,53%
011001 25 625 30,46%
010111 23 529 25,78%
001101 13 169 8,24%
GERAÇÃO K
Comossomos x f(x) Prob. seleção
011011 27 729 35,53%
011001 25 625 30,46%
010111 23 529 25,78%
001101 13 169 8,24%
79INTELIGÊNCIA ARTIFICIAL
Critérios de parada
Os critérios de parada de um algoritmo genético são:
• Número de gerações: se a solução é conhecida pode-se determinar um 
número máximo de gerações até encontrar o objetivo. A determinação 
deste número é heurística, pois um número de gerações muito pequeno 
pode prejudicar o desempenho do AG, interrompendo prematuramente 
o ciclo e, consequentemente, obtendo-se uma solução subótima. Por 
outro lado, valores grandes aumentam o processamento, mas obtêm uma 
avaliação melhor do espaço de busca do problema, evitando a conver-
gência para soluções locais. 
• Convergência da função de avaliação: pode-se interromper o processa-
mento quando não ocorre melhoria significativa na solução durante um 
dado número de gerações.
• Perda de diversidade da população.
80INTELIGÊNCIA ARTIFICIAL
Parâmetros genéticos
Na implementação de AGs, consideraremos seus parâmetros 
genéticos que podem impactar na evolução do AG e afetar a 
solução do problema analisado. Um valor ótimo de parâmetros 
de ajuste depende das características específicas do problema 
analisado. Os parâmetros podem também ser reajustados em 
função das características da população, devido a dinamicidade 
do processo de busca dos AGs. Os principais parâmetros que 
inf luenciam o desempenho do AG são:
• Tamanho da população: se for pequena, tem um menor 
desempenho, pois fornece uma pequena cobertura do espaço 
de busca do problema; se for grande, fornece uma cobertura 
representativa do domínio do problema, além de prevenir con-
vergências prematuras para soluções locais ao invés de globais. 
• Taxa de cruzamento: quanto maior a taxa, mais rapidamente 
novas estruturas serão introduzidas na população. Taxas altas 
substituem a maior parte da população (perda de estruturas 
de alta aptidão), enquanto taxas baixas tornam o algoritmo 
muito lento.
• Tipo de cruzamento: influencia nos indivíduos resultantes 
e na performance da população global. Cruzamentos está-
ticos tendem a homogeneizar a população e cruzamentos 
dinâmicos tornam o algoritmo mais lento.
• Taxa de mutação: determina a probabilidade em que uma 
mutação ocorrerá. Prevenir a saturação da população com 
cromossomos semelhantes (convergência prematura). Baixas 
taxas de mutação previnem a estagnação de um valor; altas 
taxas tornam a população muito aleatória, aumentando a 
possibilidade de que uma boa solução seja destruída. A 
melhor taxa dependente da aplicação.
81INTELIGÊNCIA ARTIFICIAL
Síntese
Neste capítulo vimos que os algoritmos genéticos representam uma classe de modelos computa-
cionais inspirados na evolução, incorporando soluções potenciais para um problema específico, usando 
uma estrutura semelhante a um cromossomo, aplicam-se operadores de seleção e “cross-over” a essas 
estruturas, de forma a preservar informações críticas relativas à solução do problema. Normalmente, 
os AG’s são vistos como otimizadores de funções, embora a quantidade de problemas para o qual os 
AG’s se aplicam seja bastante abrangente. 
Algoritmos genéticos oferecem a vantagem da simplificação na formulação e solução de problemas 
de otimização. Normalmente trabalham com descrições de entrada formadas por cadeias de bits de 
tamanhofixo ou com cadeias de bits de tamanho variável. AG’s também possuem um paralelismo 
implícito decorrente da avaliação independente de cada uma dessas cadeias de bits, ou seja, pode-se 
avaliar a viabilidade de um conjunto de parâmetros para a solução do problema de otimização em 
questão. Este tipo de abordagem é normalmente indicado para a solução de problemas de otimização 
complexos, NP-Completos, como o “caixeiro viajante”, que envolvem muitas variáveis e, consequente-
mente, espaços de soluções de dimensões elevadas. Além disso, em muitos casos onde outras estratégias 
de otimização falham na busca de uma solução, os AG’s convergem. Os AG’s são numericamente 
robustos, ou seja, não são sensíveis a erros de arredondamento no que se refere aos seus resultados.
82INTELIGÊNCIA ARTIFICIAL
Exercícios
1. Definir uma representação apropriada usando as técnicas 
de AGs para os seguintes problemas:
a. 4-Rainhas:
b. Caixeiro Viajante com 6 Cidades:
Definir: os cromossomos, os gens, a população, fornecendo 
exemplos de gerações.
NQP
•
•
•
•
4
5
3
6
2
1
2. Implementar um dos problemas acima usando algoritmo genético.
83INTELIGÊNCIA ARTIFICIAL
APRENDIZAGEM 
AUTOMÁTICA
Agentes artificiais podem melhorar seu 
comportamento e aprender a resolver 
novas situações ou formas melhores de 
resolução, através do estudo de suas próprias 
experiências.
84INTELIGÊNCIA ARTIFICIAL
Um indício básico de inteligência caracteriza-se pela adap-
tação de um ser ao meio ambiente e a forma melhorada de 
resolver problemas neste ambiente. Aprendizagem é uma forma 
básica de interação com o meio através da experimentação e 
descoberta.
Várias ações subjacentes se relacionam com a capacidade 
de aprender, por exemplo, aprender novos fatos por meio de 
observação e exploração; através do uso da experiência e da 
memória do passado; simplesmente melhorar habilidades mo-
toras/cognitivas por meio de prática ou da derivação de regras 
gerais ou, simplesmente, organizar novo conhecimento em 
representações efetivas e gerais.
O fato é que se pode definir aprendizagem através de 
“qualquer mudança num sistema que melhore o desempenho 
de um agente na segunda vez em que ele repetir a mesma ta-
refa ou uma outra tarefa na mesma população” (Simon, 1983).
Já a Aprendizagem automática (ou Aprendizagem de má-
quina ), designa a construção de sistemas computacionais que:
• melhoram seu desempenho por meio de experiência;
• aprendem automaticamente a partir de grandes volumes de 
dados, gerando hipóteses a partir dos dados;
“Um sistema/agente tem a capacidade de aprender através 
da experiência E, em relação a um conjunto de tarefas T, se a 
sua performance, medida com a função P, nas tarefas T, me-
lhoram com a experiência E” (Mitchell, 1997).
Nestes termos, um “Problema de Aprendizagem” pode ser 
caracterizado como a capacidade de Definir <T, P, E>.
85INTELIGÊNCIA ARTIFICIAL
Por exemplo, definir a aprendizagem de um jogador de damas:
• T: Jogar Damas;
• P: % de vitórias;
• E: jogar contra si próprio.
Definir um problema de reconhecimento de escrita:
• T: reconhecimento e classificação das palavras, nas imagens;
• P: % de palavras classificadas corretamente;
• E: uma base de dados de imagens de palavras e a sua correta 
classificação.
Depois de definido o problema de aprendizagem, estabelecer 
que a aprendizagem melhora o comportamento de um agente de-
pende de quatro fatores principais:
• Um componente a ser melhorado.
• O conhecimento prévio que o agente já tem.
• A representação é usada para os dados e para o componente.
• O feedback está disponível para aprendizagem.
Russel e Norvig (2013) afirmam que a aprendizagem 
de uma função geral ou regra (possivelmente incorreta) 
a partir de pares específicos de entrada-saída é realizada 
usando raciocínio indutivo.
A indução é a operação mental que consiste em se 
estabelecer uma verdade universal ou uma proposição ge-
ral com base no conhecimento de certo número de dados 
singulares ou de proposições de menor generalidade, ou 
seja, é inferência de uma função que mapeia o conjunto de 
entrada em suas respectivas saídas. Neste modo de apren-
dizagem, os tipos de feedback determinam os principais 
tipos de aprendizagem: 
• Aprendizagem supervisionada: caracterizada por pos-
suir um conjunto de dados, utilizados como exemplo 
do que o algoritmo analisará. O resultado obtido é 
comparado com os parâmetros contidos nos exem-
plos, e a partir dessa comparação decide o que deve 
86INTELIGÊNCIA ARTIFICIAL
ser modificado para que ocorra a minimização do erro. Essa 
abordagem é usada em problemas de classificação, quando 
possuem bases de dados catalogados, como na identificação 
de padrões em imagens, sons ou textos.
• Aprendizagem por reforço: todas as ações do agente são 
avaliadas por um valor de esforço utilizado ao realizar a ação, 
assim como seu fator de recompensa. Esse tipo de aborda-
gem é utilizado em veículos autônomos, onde o carro pode 
analisar um ambiente desconhecido e determinar o melhor 
percurso a ser percorrido.
• Aprendizagem não supervisionada: o agente aprende pa-
drões na entrada, embora não seja fornecido nenhum fee-
dback explícito. A tarefa mais comum de aprendizagem não 
supervisionada é o agrupamento: a detecção de grupos de 
exemplos de entrada potencialmente úteis.
• Aprendizagem semissupervisionada: são dados poucos 
exemplos rotulados e deve-se fazer o que puder de uma 
grande coleção de exemplos não rotulados. Geralmente, 
esses exemplos são mais difíceis de serem encontrados, ne-
cessitando de especialistas para a análise.
Aprendizagem supervisionada
O algoritmo de aprendizado (indutor) recebe um conjunto 
de exemplos de treinamento onde os rótulos da classe associada 
são conhecidos. Cada exemplo (instância ou padrão) é descri-
to por um vetor de valores (atributos) e pelo rótulo da classe 
associada. O objetivo do indutor é construir um classificador 
que possa determinar corretamente a classe de novos exemplos 
ainda não rotulados. Para rótulos de classe discretos, este é 
um problema de classificação e para valores contínuos, é um 
problema de regressão.
87INTELIGÊNCIA ARTIFICIAL
A indução mediante árvores de decisão é uma das formas 
mais simples de algoritmos de aprendizagem. Toma como en-
trada um objeto ou situação, descrito através de um conjunto 
de propriedades ou atributos. Gera como saída uma decisão 
do tipo: sim / não, podendo representar funções Booleanas, 
realizando a indução a partir de exemplos.
Na indução a partir de exemplos, um exemplo descreve os 
valores dos atributos e o valor do predicado objetivo. O valor do 
predicado objetivo é a classificação do exemplo. Os exemplos 
que resultam num valor verdadeiro são exemplos positivos, 
enquanto os exemplos que resultam num valor falso são exem-
plos negativos. Finalmente, o conjunto de exemplos usados na 
construção da árvore é chamado de conjunto de treinamento.
Em uma Árvore de Decisão, os nodos internos são rotulados 
com atributos e os arcos saindo de um nodo A são rotulados 
com cada um dos possíveis valores do atributo A. Nodos-folha 
são rotulados com classificações. Um exemplo de árvore de 
decisão para um problema de escolher deve ser jogado depen-
dendo das condições climáticas, como ilustrado na Figura 21.
Figura 21: Exemplo de elementos em uma árvore de decisão
O problema exemplo consiste na decisão em sair para jogar 
dependendo das condições climáticas, que pode ser representado 
através da definição de Problema de aprendizagem (<T, P, E>), como:
• T: Decidir se saímos para jogar dependendo do clima (sim/não).
• E: Atributos:
• Aparência: como está o tempo {sol, chuva, nuvens}?
• Temp: temperatura externa {quente, frio, morno}.
• Umidade: umidade do ar {alta, normal}.
88INTELIGÊNCIA ARTIFICIAL
Vento: velocidade do vento {forte, fraco}.
• Meta - Jogar: {sim, não}.
Exemplos de possibilidades de valores dos atributos:
Tabela 1: Lista de atributos para o problema “Sair para jogar”.
Uma árvore de decisão parcialpossível para este problema 
será ilustrada na Figura 22. 
Figura 22: Exemplo de árvore de decisão parcial para o 
problema de “Sair para jogar”
Exemplo
Atributos Meta
Aparência Temp Umidade Vento Jogar?
X1 Sol Quente Alta Fraco Não
X2 Sol Quente Alta Forte Não
X3 Nuvens Quente Alta Fraco Sim
X4 Chuva Morno Alta Fraco Sim
X5 Chuva Frio Normal Fraco Sim
X6 Chuva Frio Normal Forte Não
X7 Nuvens Frio Normal Forte Sim
X8 Sol Morno Alta Fraco Não
X9 Sol Frio Normal Fraco Sim
X10 Chuva Morno Normal Fraco Sim
X11 Sol Morno Normal Forte Sim
X12 Nuvens Morno Alta Forte Sim
X13 Nuvens Quente Normal Fraco Sim
X14 Chuva Morno Alta Forte Não
89INTELIGÊNCIA ARTIFICIAL
A árvore de decisão pode ser representada por conjunções 
e/ou disjunções de implicações individuais que correspondam 
aos caminhos que vão da raiz até o nó folha Sim. Por exem-
plo, a Figura 23 ilustrará a sentença lógica Aparência (chuva) 
^ Vento(forte).
Figura 23: Fragmento de conjunção lógica na árvore de decisão
A expressividade de uma árvore de decisão pode indicar 
um caminho de inferência em qualquer função dos atributos 
de entrada. Por exemplo, para funções Booleanas as tabelas 
verdadeiras são caminhos para as folhas, como ilustrado na 
Figura 24.
Figura 24: Exemplo de representação da inferência na árvore 
de decisão
90INTELIGÊNCIA ARTIFICIAL
Em termos de expressividade, o objetivo é encontrar a 
árvore que seja consistente com os exemplos e seja a menor 
possível. Porém, encontrar a menor árvore de decisão possível 
e consistente é um problema intratável. É preciso adotar um 
algoritmo com uma estratégia de busca heurística para encon-
trar uma solução aproximada.
Assim, para construir uma árvore de decisão, um algoritmo 
geral deve começar com todos os exemplos de treino e escolher o 
teste (atributo) que melhor divide os exemplos, ou seja, agrupar 
exemplos da mesma classe ou exemplos semelhantes. Para o 
atributo escolhido, criar um nó filho para cada valor possível 
do atributo e transportar os exemplos para cada filho, tendo 
em conta o valor do filho. Repetir o procedimento para cada 
filho não “puro”, um filho em que o atributo X tem o mesmo 
valor em todos os exemplos.
O algoritmo ID3 (Inductive Decision Tree) a seguir, é 
um dos mais utilizados para construção de árvores de decisão:
91INTELIGÊNCIA ARTIFICIAL
Para a construção da menor árvore consistente, a questão 
é: qual melhor atributo escolher? Um bom atributo divide os 
exemplos em subconjuntos, onde todos são positivos (“+”) ou 
negativos (“–”). Para se definir a proporção de exemplos, usa-se 
uma medida de Entropia e Ganho.
A Entropia de uma amostra dos exemplos de treinamento 
S mede a “impureza” de S, onde:
• p+ é a proporção de exemplos positivos em S;
• p– é a proporção de exemplos negativos em S;
• Então a Entropia é:
Generalizando:
No exemplo de “Sair para jogar”, S é uma coleção de 14 
exemplos (ilustrados na Tabela 1), incluindo 9 positivos e 5 
negativos:
• Notação: [9+,5-]
A entropia de S em relação a esta classificação booleana 
é dada por:
Com a Entropia calculada de cada subconjunto dos exem-
plos, pode-se calcular o Ganho (S, A) para cada atributo. O 
Ganho representa a redução esperada da entropia devido a 
“classificação” de acordo com A, dado pela equação:
Voltando ao nosso exemplo de “Sair para Jogar”, segundo 
as possibilidades da Tabela 1. Um exemplo do Ganho calculado 
para cada atributo do sistema é dado por:
Valores (Vento) = {fraco, forte}
SFraco = Entropia ([6+,2-]) --> 6 metas=Sim e 2 metas=Não na Tabela
SForte = Entropia ([3+,3-])
Ganho (S, Vento) = Entropia(S) 
 – 8/14*Entropia (SFraco) 
 – 6/14*Entropia (SForte)
Ganho (S, Vento) = 0.940 
 – 8/14 * 0.811 
 – 6/14 * 1.0 = 0.048
92INTELIGÊNCIA ARTIFICIAL
Depois de calculados Entropias e Ganhos para 
todos os atributos, pode-se definir qual atributo 
deve ser selecionado para ser a raiz da árvore.
No nosso exemplo:
• Ganho (S, Aparência) = 0.247
• Ganho (S, Umidade) = 0.152
• Ganho (S, Vento) = 0.048
• Ganho (S, Temp) = 0.015
Assim, a melhor alternativa para a árvore ini-
cial é definida pelo atributo com maior ganho, e 
será exemplificada na Figura 25
Figura 25: Exemplo de árvore inicial após o cálculo 
da Entropia e Ganho dos atributos
93INTELIGÊNCIA ARTIFICIAL
Redes	neurais	artificiais
Outro paradigma muito usado de aprendizagem supervisio-
nada é seguir exatamente a metáfora de funcionamento físico do 
cérebro humano, através da simulação das Redes Neurais. Uma 
complexa rede de células nervosas (neurônios) é responsável por 
conduzir, receber e transmitir os impulsos nervosos através do 
corpo, fazendo com que este responda aos estímulos do meio, 
por exemplo. Os neurônios também transmitem informações 
entre si através de sinapses, processos que consistem justamente 
na troca de informações entre essas células.
O princípio básico é que dois processos cerebrais elementa-
res, ao passar pelo estado ativos juntos ou em sucessão imediata, 
um deles, ao reocorrer, tende a propagar sua excitação para o 
outro e sucessivamente.
Na Figura 26, os Dendritos recebem os estímulos trans-
mitidos por outros neurônios. O Corpo (ou soma) coleta e 
combina informações vindas de outros neurônios. Enquanto 
o Axônio transmite estímulos para outras células.
Figura 26: Dendritos
Fonte: https://www.significados.com.br/neuronios/
94INTELIGÊNCIA ARTIFICIAL
O primeiro modelo de redes neurais artificiais foi proposto 
por Warren S. McCulloch (psiquiatra e neurofisiologista) e 
Walter Pitts (lógico e matemático), em um artigo publicado 
em 1943 . Em um primeiro trabalho sobre “neurônios formais”, 
eles apresentaram um modelo matemático de simulação do 
processo biológico que ocorre em células nervosas vivas. O 
modelo visava a simulação artificial do comportamento de um 
neurônio natural. Neste modelo, o neurônio artificial possuía 
apenas uma saída, produzida em função do somatório dos va-
lores de suas diversas entradas. Em termos físicos, o trabalho 
consiste em um modelo de resistores variáveis e amplificadores, 
representando conexões sinápticas de um neurônio natural.
Este modelo matemático é baseado em cinco hipóteses:
1. A atividade de um neurônio é binária; o neurônio ou está 
disparando (1), ou não está disparando (0).
2. A rede neural é constituída por linhas (excitatórias ou ini-
bitórias) dirigidas, sem pesos, ligando os neurônios.
3. Cada neurônio tem um limiar fixo , ele só dispara se a 
entrada total, em um dado instante, for maior ou igual a .
4. A chegada de uma única sinapse inibitória em um dado 
instante evita o disparo do neurônio, independentemente 
do número de sinapses excitatórias entrando conjuntamente 
com a sinapse inibitória.
5. Um sinal leva uma unidade de tempo para passar de um 
neurônio da rede para outro, simulando o atraso sináptico.
Figura 27: Neurônio artificial original de McCulloch-Pitts
95INTELIGÊNCIA ARTIFICIAL
Na Figura 27, se pelo menos uma das entradas inibitórias 
(y’s) for igual a 1, em um dado instante de tempo, o neurônio é 
inibido. Se todas as entradas inibitórias forem nulas, o neurô-
nio calcula a soma das entradas excitatórias e a compara com 
o seu limiar θ. Se a soma das entradas excitatórias for maior 
ou igual a θ, ele dispara (1); caso contrário, ele não dispara (0).
O primeiro neurônio artificial do modelo de McCulloch e 
Pitts foi o Perceptron, proposto por Frank Rosenblatt (1958), 
ilustrado na Figura 28. 
Figura 28: Primeiro neurônio artificial (McCulloch e Pitts, 1950)
S f
W1
y
X1
W2
X2
Xn
Wn
O Perceptron nada mais é do que um classificador biná-
rio que mapeia sua entrada x para um valor de saída y = f(x), 
usando uma função f como ativação e a propagação é dada 
pelo somatório das entradas ponderadas, conforme a equação 
a seguir, onde w é um vetor de peso real e wi x xi é o produto 
escalar (soma com pesos).
O termo θ denota o Bias do neurônio que define se um 
hiperplano passa pela origem ou se é deslocado da origem, 
conformeexemplificado na Figura 29.
A função de ativação f mais simples utilizada no perceptron 
é a função degrau (hardlim):
96INTELIGÊNCIA ARTIFICIAL
Figura 29: Exemplo da influência da constante Bias.
Esta função é responsável por determinar a forma e a intensi-
dade de alteração dos valores transmitidos de um neurônio a outro. 
De forma simplificada, um Perceptron procura identificar a 
melhor fronteira que separa um conjunto de dados em classes de 
características similares, ou seja, é uma Função discriminante linear.
Esta função é responsável por determinar a forma 
e a intensidade de alteração dos valores transmitidos de 
um neurônio a outro. 
De forma simplificada, um Perceptron procura iden-
tificar a melhor fronteira que separa um conjunto de 
dados em classes de características similares, ou seja, é 
uma Função discriminante linear.
Função de ativação
No funcionamento básico de um neurônio artificial, 
os sinais são apresentados na camada de entrada (x) e 
cada sinal é multiplicado por um peso (w). Esta soma 
ponderada produz um nível de ativação que, excedendo 
um limite (threshold), faz a unidade produzir uma saída.
Principais funções de ativação:
97INTELIGÊNCIA ARTIFICIAL
• Degrau: função de ativação linear (hard limit), se a soma das 
entradas multiplicadas pelos pesos for maior que um limiar 
(por exemplo 1), o neurônio dispara.
• Linear (identidade): não usa função de ativação (a saída é a 
soma das entradas multiplicadas pelos pesos).
98INTELIGÊNCIA ARTIFICIAL
• Sigmóide: aproximação linear, mas nos extremos ela satu-
ra, pois é assintótica em relação à 0 e 1. A sigmóide tem a 
vantagem de ser integrável.
• Tangente hiperbólica: função diferenciável, mas desta vez é 
assintótica em relação à -1 e 1.
99INTELIGÊNCIA ARTIFICIAL
Arquiteturas
RNAs formadas por neurônios artificiais mais simples possuem 
atributos similares ao sistema biológico humano como, por exemplo, 
a capacidade de aprender e generalizar. As topologias de redes neu-
rais podem ser recorrentes e não-recorrentes. RNAs não-recorrentes 
não possuem realimentação de suas saídas para suas entradas e são 
estruturadas em camadas: RNA de camada única ou RNA multi-
-camada. A RNA multi-camada contém um conjunto de neurônios 
de entrada, uma camada de saída e uma ou mais camadas ocultas. 
A camada de entrada distribui os padrões para a camada de saída 
apresentar um resultado.
RNAs recorrentes são estruturas que apresentam realimentação 
de informação e, portanto, compreendem representações internas e 
dispositivos de memória capazes de processar e armazenar informações 
temporais e sinais sequenciais. A presença de conexões recorrentes 
ou realimentação de informação podem conduzir a comportamentos 
complexos, mesmo com um número reduzido de parâmetros.
Podemos perceber então, que existem algumas classificações 
características da arquitetura ou topologia das redes neurais 
artificiais. Vejamos algumas das mais importantes:
• Redes feedforward de camada única: possuem uma camada 
de entrada e uma camada de saída apresentando neurônios 
lineares, ou seja, que propagam o sinal de entrada para a 
próxima camada. Feedforward é designação para a propa-
gação do sinal apenas da entrada para a saída. 
Exemplos: Perceptron e Adaline.
100INTELIGÊNCIA ARTIFICIAL
• Redes feedforward de múltiplas camadas: redes que pos-
suem uma ou mais camadas intermediárias ou escondidas, 
não-lineares, que aumentam a capacidade de processamento 
da rede. A saída de cada camada intermediária é utilizada 
como entrada para a próxima camada. O algoritmo de trei-
namento para este tipo de rede envolve a retropropagação 
do erro entre a saída da rede e uma saída desejada conhecida.
• Redes recorrentes: redes com uma ou mais camadas, con-
tendo conexões que partem da saída de uma unidade em 
direção a uma outra unidade da mesma camada ou de uma 
camada anterior à esta. Este tipo de rede pode integrar 
modelos que levam em consideração aspectos temporais e 
comportamentos dinâmicos, onde a saída de uma unidade 
depende de seu estado em um tempo anterior. Um tipo 
particular de redes recorrentes são as redes totalmente co-
nectadas, e um exemplo de modelo recorrente de uma única 
camada e totalmente conectado são as redes de Hopfield.
101INTELIGÊNCIA ARTIFICIAL
Algoritmo de aprendizagem
Exemplificaremos o funcionamento de 
uma atividade de aprendizagem usando o 
Perceptron, por ser o modelo mais simples. 
Inicialmente, os pesos são inicializados aleato-
riamente dentro de um intervalo especificado 
(geralmente entre -1 e 1). Assim, a primeira 
vez que o Perceptron for ativado, o valor na 
saída provavelmente não corresponderá ao 
valor desejado, entretanto, a diferença entre o 
valor desejado e o obtido na saída será usado 
para ajustar os pesos sinápticos para que a rede 
aprenda a responder corretamente.
Um exemplo de algoritmo simples para 
aprendizagem através de um Perceptron é 
dado abaixo:
102INTELIGÊNCIA ARTIFICIAL
Digamos que um perceptron seja usado para aprender a 
função lógica AND. Primeiramente os dados de treinamento 
para duas entradas A e B, e uma saída S, poderiam ser:
Ou seja, a própria tabela verdade da função AND. Supo-
nha que os pesos tenham sido inicializados aleatoriamente e 
os seguintes valores foram obtidos:
w1 = 0.1 w2 = 0.64 w0 = 0.19
As saídas correspondentes seriam:
Os erros são usados para ajustar os pesos através da regra delta.
Uma possível interpretação geométrica para este cálculo 
aponta que um neurônio pode ser considerado como uma reta 
que divide os padrões em classes. A equação desta reta é defi-
nida pelos pesos sinápticos w. Para os pesos iniciais definidos 
anteriormente: 
w1 = 0.1 w2 = 0.64 w0 = 0.19
A equação da reta seria:
0.1 * x1 + 0.64 * x2 + 0.19 = 0
Esta equação pode ser plotada no plano 2D, onde x1 é o eixo 
das ordenadas e x2 o das abscissas, desta forma, na figura abai-
xo, a reta inicial divide as classes de forma aleatória, mantendo 
todos os pontos na mesma faixa de classificação, ou seja, acima 
da reta calculada. Esta interpretação indica que qualquer entrada 
corresponde a mesma classificação de saída, incorrendo em erro.
A B S
0 0 0
0 1 0
1 0 0
1 1 1
x1 x2 ∑ obtida alvo erro
0 0 0.19 0.55 0 -0.55
0 1 0.83 0.7 0 -0.7
1 0 0.29 0.57 0 -0.57
1 1 0.93 0.72 1 0.28
103INTELIGÊNCIA ARTIFICIAL
O ajuste iterativo dos pesos, à medida que o algoritmo pro-
cura a classificação correta, leva ao seguinte resultado, usando a 
interpretação geométrica da aprendizagem, ilustrado no gráfico 
a seguir:
Este problema, no entanto, cujo comportamento é line-
armente separável não corresponde à realidade das aplicações 
tradicionais em reconhecimento de padrões.
104INTELIGÊNCIA ARTIFICIAL
Tomemos outro exemplo, a aprendizagem do comportamen-
to da função lógica XOR, cuja tabela verdade é dada a seguir:
Neste caso, uma possível interpretação geométrica do pro-
blema seria exemplificada como:
E, portanto, a solução desejada deve separar linearmente 
as regiões conforme o diagrama abaixo:
Para a rede resolver esta classificação, não é suficiente 
apenas uma camada, pois como visto anteriormente, a única 
camada perceptron é capaz apenas de extrair uma característica 
da classificação linear dos resultados. Como a função boole-
ana XOR é não-linearmente separável, ou seja, não realizável 
por meio de apenas uma reta, precisamos usar perceptrons de 
múltiplas camadas. Assim, uma solução do problema do XOR 
A B R
0 0 0
0 1 1
1 0 1
1 1 0
105INTELIGÊNCIA ARTIFICIAL
equivale a ajustar os pesos dos neurônios ocultos de modo a 
corresponder a mapeamentos intermediários em i₁ e i₂, que 
tornam o problema linearmente separável para a camada de 
saída, dada a representação da rede abaixo:
Um exemplo de rede parcial para uma interpretação da 
primeira linha da tabela: verdade do XOR poderia ser, com 
pesos iniciais aleatórios:
106INTELIGÊNCIA ARTIFICIAL
Para calcular a saída da rede, primeiramente é preciso 
calcular o valor do neurônioescondido (h):
1 * 7.1 + 1 * -2.76 +0 * 7.1 = 4.34
Passando o valor 4.34 na função de ativação, temos 0.987. 
O valor de saída é calculado:
1 * -4.95 + 0 * -4.95 + 0.987 * 10.9 + 1 * -3.29 = 2.52
Passando 2.52 na função de ativação temos a saída igual a 
0.91. Deste modo, temos uma primeira interação para o primei-
ro resultado na camada de saída, ilustrado na figura a seguir:
107INTELIGÊNCIA ARTIFICIAL
Redes de múltiplas camadas são treinadas usando o al-
goritmo de retropropagação de erros, que é baseado na regra 
delta de aprendizado por correção de erro (Werbos, 1998), que 
pode ser visto como uma generalização do algoritmo para um 
único neurônio. O algoritmo informal simplificado pode ser 
visto no quadro abaixo:
Como existem vários neurônios na camada de saída, deve-se 
definir a soma instantânea dos quadrados dos erros em cada nó 
de saída da rede, E(n), quando o n-ésimo vetor de treinamento 
X(n) é apresentado na entrada da rede:
Com o erro quadrado instantâneo na unidade k de saída 
definido por:
Onde ek é o erro numa unidade de saída k, quando o vetor 
X(n) é propagado pela rede:
Onde dk(n) é a saída desejada, correspondente a X(n), e 
yk(n) é a saída instantânea obtida no neurônio de saída k, pela 
propagação de X(n).
108INTELIGÊNCIA ARTIFICIAL
Síntese
Este capítulo lança as bases muito elementares da ideia de aprendizagem de máquina ou automá-
tica, em que um agente computacional tem a capacidade de mudar seu comportamento e percepção 
do mundo de acordo com um conjunto de ações e transformações na sua representação interna. Nos 
limitamos a duas abordagens básicas, árvores de decisão e redes neurais artificiais, por serem as mais 
exploradas em aplicações tradicionais.
O primeiro uso de árvores de decisão já procurava “simular” o conceito humano de comportamento 
(Feigenbaum, 1961) já lançando as bases para o algoritmo ID3 (quinlan, 1979). Foram abordados os 
conceitos dos três principais tipos de aprendizagem: supervisionada, não-supervisionada e por refor-
ço. A indução em árvores de decisão é um dos métodos mais simples de aprendizagem automática.
Redes neurais artificiais constituem uma das formas mais populares e eficazes de aprendizagem. 
Para uma abordagem de aprendizagem que se constitui em aproximações linearmente separáveis, 
as redes neurais podem agrupar funções não lineares complexas em redes de unidades lineares. A 
exemplo do funcionamento do cérebro humano, a arquitetura de uma rede neural com as funções 
de ativação sináptica que definem um conjunto de pesos de treinamento, torna-se uma ferramenta 
poderosa e eficaz de aprendizagem de padrões.
109INTELIGÊNCIA ARTIFICIAL
Exercícios
Sobre árvores de decisão
Problema 01: desenhe árvores de decisão que representem 
os seguintes conceitos (sendo A, B, C e D variáveis booleanas):
a. A ∧ ¬B
b. A ∨ (B ∧ C)
c. A ⊗ B
d. (A ∧ B) ∨ (C ∧ D)
Problema 02: o conjunto de exemplos a seguir pertence 
ao treinamento que descreve o conceito de assinante de uma 
revista hipotética, onde cada exemplo descreve as caracterís-
ticas da pessoa e se é assinante da revista. As características 
consideradas são: o sexo, a idade (abaixo de 26 anos) e se tem 
carro; definidas no quadro a seguir:
a. Calcule o valor da Entropia deste conjunto de treino no 
que diz respeito ao conceito cliente.
b. Calcule o Ganho de informação para o atributo sexo.
c. Desenhe uma árvore de decisão obtida para este conjunto 
de treino, de acordo com o critério de maximização do ganho 
de informação.
SEXO IDADE < 26 TEM CARRO CLIENTE?
X1 M T M SIM
X2 M T T SIM
X3 F T T NÃO
X4 M F T NÃO
X5 F T F NÃO
X6 M T F SIM
X7 M F F NÃO
X8 F F F NÃO
X9 F T F NÃO
X10 F F T NÃO
110INTELIGÊNCIA ARTIFICIAL
Sobre redes neurais
Problema 03: implementar o problema do XOR para duas entradas booleanas A e B. Como se 
trata de um conjunto de treinamento não linearmente separável é mais fácil implementar uma rede 
de perceptrons multicamadas usando o algoritmo backpropagation com a função delta.
111INTELIGÊNCIA ARTIFICIAL
AGENTES 
INTELIGENTES 
E SISTEMAS 
MULTIAGENTES
Problemas complexos precisam de múltiplas 
entidades para resolução. O paradigma do 
comportamento social pode ser simulado em 
agentes artificiais, dotando-os de capacidade 
de comunicação, interação, organização e 
planejamento colaborativo.
112INTELIGÊNCIA ARTIFICIAL
Até o momento verificamos que grande parte do objeto de 
estudos da IA tradicional considera como modelo de inteligência 
o comportamento individual humano, cuja ênfase é colocada 
em representação de conhecimento, métodos de inferência e 
aprendizagem automática individual. Porém, os seres humanos, 
em comunidade, apresentam também um comportamento so-
cial, com ênfase em ações e interações entre vários indivíduos. 
A metáfora utilizada em IA clássica é basicamente de origem 
psicológica, enquanto que aquela utilizada em Inteligência 
Artificial Distribuída (IAD) é de natureza sociológica.
Na vida real, observamos situações onde tomamos um 
comportamento dito inteligente observando entidades coleti-
vas, por exemplo:
• uma empresa competitiva num determinado segmento de mercado;
• uma equipe de futebol buscando objetivos em competições;
• uma colônia de insetos organizados em busca de alimento e 
proteção. 
Uma abordagem deste tipo é interessante quando se de-
seja resolver problemas grandes e complexos, que requeiram 
conhecimento de vários domínios de conhecimentos distin-
tos, que algumas vezes envolvam coleta de dados fisicamente 
distribuídos, por exemplo, em sistemas de controle de espaço 
aéreo. Do ponto de vista estritamente computacional, uma 
abordagem distribuída permite o controle da complexidade, 
uma operação degradada satisfatória e suporte para evoluções 
e eventuais replicações [Chandrasekaran 81].
É neste ponto que a metáfora humana ainda é requisitada 
para a modelagem da inteligência. Programas de computador 
fazem muito, mas espera-se um pouco mais, por exemplo, 
mais autonomia, percepção, persistência, adaptação, criação 
e resolução de objetivos. Neste sentido, podemos dizer que 
um agente racional é aquele que age para atingir os melhores 
resultados ou, sob incerteza, o melhor “resultado esperado”.
113INTELIGÊNCIA ARTIFICIAL
Definição de agente:
Segundo Russel e Norvig (2013), um agente é tudo que 
pode perceber seu ambiente através de sensores e agir neste 
ambiente através de atuadores, como ilustrado na Figura 30.
Figura 30: Representação básica da arquitetura de um agente 
genérico
114INTELIGÊNCIA ARTIFICIAL
Agentes Percepção Ações Objetivos Ambientes
Diagnóstico Médico Sintomas, 
pacientes, exames, 
respostas, etc.
Perguntar, 
prescrever 
exames, testes, 
diagnósticos, 
tratamentos.
Saúde do paciente, 
minimizar custos.
Paciente, hospital, 
equipe.
Sistema de análise 
de imagens de 
satélite
Arrays de pixels 
em cores.
Exibir categoria da 
cena.
Definição correta 
da categoria da 
imagem.
Link de 
transmissão de 
satélite em órbita.
Robô de seleção de 
peças
Câmera, sensores 
angulares 
articulados.
Braço e mão 
articulados.
Porcentagem de 
peças em bandejas 
corretas.
Correia 
transportadora 
com peças, 
bandejas.
Controlador de 
refinaria
Sensores de 
temperatura, 
pressão, produtos 
químicos.
Válvulas, bombas, 
aquecedores, 
mostradores.
Maximizar pureza, 
rendimento, 
segurança.
Refinaria, 
operadores.
Instrutor interativo 
de línguas
Entrada via 
teclado.
Exibir exercícios, 
sugestões, 
correções.
Maximizar nota de 
aluno em teste.
Conjunto de 
alunos, ambiente 
de testes.
Filtrador de emails Mensagens Aceitar ou rejeitar 
mensagens.
Aliviar a carga de 
leitura do usuário.
Mensagens, 
usuários.
Motorista 
autônomo
Imagens, 
velocímetro, sons.
Frear, acelerar, 
dobrar, emitir 
sinais, comunicar 
rotas e problemas.
Segurança, 
rapidez, economia, 
conforto
Ruas, pedestres, 
carros.
De forma genérica podemos 
conceituar um agente como uma 
entidade real ou virtual, inserida 
em um ambiente em que ele é ca-
paz de perceber eagir, podendo se 
comunicar com outras entidades e 
exibir um comportamento autôno-
mo em função destas observações, 
conhecimento e comunicações.
Exemplos de aplicações de agentes:
115INTELIGÊNCIA ARTIFICIAL
Arquiteturas de agentes
Segundo Weiss (1999), as possíveis arquiteturas de agentes 
podem ser classificadas como:
• Agentes reativos: agentes reflexivos e agentes reflexivos 
com estado Russel e Norvig (2013).
• Agentes cognitivos: agentes baseados em metas e agentes 
baseados na utilidade na classificação de Russel e Norvig 
(2013), além de Agentes BDI (Beliefs, Desires, Intentions), 
agentes racionais com representação de crenças, desejos e 
intenções.
• Agentes híbridos: agentes com comportamentos reativos 
e alguma racionalidade.
Agentes reativos
Agentes reativos não possuem uma representação explícita 
do conhecimento e do ambiente. O conhecimento está implícito 
no comportamento baseado na percepção. Não registra um 
histórico das ações e a melhor analogia é com a organização 
etológica, baseada em comportamentos coletivos (insetos, peixes, 
pássaros), cujo sucesso advém do grande número de membros.
O exemplo clássico da organização etológica é o compor-
tamento de bando de aves (Flocking), de cardume de peixes 
(Shoaling) ou de enxame de insetos sociais (Swarm). Craig 
Reynolds (1986) desenvolveu os primeiros simuladores de 
comportamentos reativos, chamados de Boids, que são modelos 
de agentes que imitam os comportamentos de animais sociais.
116INTELIGÊNCIA ARTIFICIAL
A modelagem do comportamento de Flocking pode ser 
resumido a algumas atividades simples:
Manter distância média entre vizinhos:
Manter o alinhamento médio entre vizinhos:
Posicionar no ponto médio entre vizinhos:
117INTELIGÊNCIA ARTIFICIAL
A tendência/probabilidade Tij (sj) de seguir 
o estímulo comporta-se da seguinte maneira:
O comportamento para realizar a tarefa possui 
uma alta probabilidade, quando o estímulo para 
o indivíduo realizar a tarefa é alto (por exemplo, 
1.0), já que 0 ≤ θij < 1.0. Um valor de estímulo 
elevado garante a realização da tarefa, mesmo 
que os agentes não sejam especializados, ou seja, 
com limiar de resposta alto.
Nos outros dois casos, a tendência para rea-
lizar a tarefa é inf luenciada pelo estímulo e pelo 
limiar de resposta do indivíduo quando o estímulo 
é 0.5; enquanto uma tarefa com baixo estímulo 
(por exemplo, próximo a 0), fará com que agentes 
com alto limiar de resposta recusem sua realização.
Quanto à metáfora dos insetos sociais, como por exemplo, formigas, cupins, 
abelhas, vespas, a organização social entre agentes reativos preconiza que indi-
víduos da mesma espécie cooperem nos cuidados com os mais jovens, distri-
buindo a tarefa reprodutiva do trabalho, com indivíduos mais ou menos estéreis, 
normalmente, sobrepondo pelo menos duas gerações no trabalho da colônia. 
A comunicação entre os indivíduos é feita através de processos químicos pelo 
ambiente (feromônio) e pela percepção (movimento).
Vamos a um exemplo de modelo teórico de organização social reativa, se-
gundo Bonabeau (1999):
Seja sj a intensidade de um estímulo associado a uma atividade j em particular 
(por exemplo, número de encontros com outros indivíduos, uma concentração 
química, etc.). Cada indivíduo i possui um limiar de resposta θij de acordo com 
sua pré-disposição de reagir ao estímulo associado com a atividade j. A proba-
bilidade de um indivíduo atender a resposta a um estímulo é dada por Tij (sj), 
conforme a equação:
118INTELIGÊNCIA ARTIFICIAL
Comportamento reativo
O modo como o comportamento re-
ativo das formigas é definido, depende de 
uma grande quantidade de indivíduos co-
brindo a maior área possível. Se o número 
de indivíduos for limitado, é necessária 
muita movimentação de forma a cobrir 
uma região eficientemente.
O processo de resolução das formigas 
pode ser resumido assim:
1. Método de comunicação indireta ba-
seado na liberação de feromônio no 
caminho por onde passam.
2. Formigas isoladas se movem rando-
micamente:
1. grande probabilidade de seguir ou-
tro caminho ao encontrar uma marca 
de feromônio.
3. Uma formiga buscando alimento de-
posita feromônio pelo caminho.
4. Ao encontrar uma fonte de alimento, 
ela retorna ao formigueiro reforçando 
seu trajeto.
5. Processo de retroação positiva: pro-
babilidade aumenta em função da 
concentração de feromônio.
Comportamento otimizado
Se existem dois caminhos, A e B, 
entre um formigueiro e o alimento e, por 
exemplo, o caminho B é mais curto, o 
caminho B terá mais formigas, com per-
curso mais rápido, portanto, com grande 
quantidade de feromônio. A concentração 
de feromônio em B aumenta a probabili-
dade de que outras formigas o escolham 
em relação ao caminho A. Com poucas 
formigas trafegando em A, com feromô-
nio volátil, o caminho A desaparecerá. O 
mesmo acontece se houverem obstáculos 
no caminho, conforme a Figura.
119INTELIGÊNCIA ARTIFICIAL
Figura 31: Resumo do Comportamento: em (A) as formigas 
seguem o caminho entre o alimento e o ninho; em (B) um 
obstáculo aparece no caminho, elas escolhem entre virar à 
direita ou à esquerda com igual probabilidade; em (C,D), o 
feromônio é depositado mais rapidamente no caminho mais 
curto, em pouco tempo todas escolhem este caminho.
Hipóteses de Brooks
Segundo Rodney Brooks (1990), um comportamento inteli-
gente pode ser gerado sem representação simbólica ou raciocínio 
simbólico algum. A inteligência é uma propriedade emergente 
de alguns sistemas complexos, onde o comportamento inteli-
gente é resultado da interação do agente com o ambiente, ou 
seja, “a inteligência está no olho do observador”.
Assim, agentes puramente reativos agem baseados em 
estímulo-resposta:
120INTELIGÊNCIA ARTIFICIAL
Agentes puramente reativos selecionam uma ação apenas 
com base na percepção corrente, onde o ambiente é comple-
tamente observável (ver seção ):
Figura 32: Diagrama esquemático de um agente reativo simples
Nesta abordagem, conforme ilustrado na Figura 32, o 
agente capta as modificações no ambiente através de um con-
junto de sensores e alimenta o mecanismo de Matching das 
regras condição-ação, disparando uma ação selecionada para 
os atuadores, seguindo um loop infinito. Um algoritmo básico 
para implementar este comportamento é exemplificado abaixo:
Esta abordagem usa uma máquina de estados onde:
1. Os agentes iniciam em um estado interno i.
2. Observam o ambiente e geram um ciclo de percepção-ação.
3. O estado interno do agente é atualizado.
4. O agente executa a ação selecionada.
5. Volta ao passo (2).
121INTELIGÊNCIA ARTIFICIAL
Quando o ambiente é parcialmente observável (ver seção), 
o agente reativo precisa manter uma descrição de estado inter-
na, representando um “modelo do mundo”. Uma arquitetura 
básica para este tipo de representação é ilustrada na Figura 33.
Figura 33: Agente reativo baseado em modelo
O Agente reativo recebe as modificações no ambiente 
através dos sensores. Esta informação é enriquecida com as 
informações anteriores armazenadas em sua memória sobre o 
estado atual e sobre as influências das ações no ambiente. Uma 
função Update_state cria uma descrição de estado interna. Em 
seguida, o mecanismo de Matching das regras condição-ação 
dispara uma ação selecionada para os atuadores, seguindo um 
loop infinito. Um algoritmo básico para implementar este 
comportamento é exemplificado abaixo:
Um dos modelos mais conhecidos de agentes reativos com 
estados são baseados nos modelos de funcionalidade emergente 
desenvolvidos por Steels (1990) e Brooks (1986). A Arquitetura 
de Subsunção de Rodney Brooks (1986) envolve a decomposição 
do controle do agente em camadas ou módulos que corres-
pondam a comportamentos elementares. Cada módulo é um 
autômato de estado finito e existe uma hierarquia de prioridade 
entre eles, como exemplificado na Figura 34 a seguir:
122INTELIGÊNCIA ARTIFICIAL
Figura 34: Hierarquia de comportamentos baseado na 
percepção do ambiente
Um exemplo de aplicação destetipo de funcionalidade 
emergente são os robôs mineradores de Luc Steels (1990), onde 
um conjunto de robôs deve encontrar e levar para uma base 
central, amostras de minerais. A localização das amostras e o 
ambiente são desconhecidos e as amostras são agrupadas em 
“depósitos” (Figura 35). 
Figura 35: Exemplo de ambiente reativo aplicado a robôs 
mineradores (Steel, 1990)
Os comportamentos elementares são projetados da seguinte 
forma (Figura 36):
evitar obstáculos
pegar mineral
descarregar mineral na base
ir para a base deixando uma pista
seguir pista em direção ao mineral
realizar movimento randômico
maior
menor
prioridade de 
execução
123INTELIGÊNCIA ARTIFICIAL
As vantagens em usar agentes reativos são a simplicidade de 
comportamento, economia de funções de raciocínio, computação 
e inferência, a tratabilidade computacional de aplicação de regras 
de produção tradicionais e a robusteza contra falhas.
As limitações desta abordagem são que os agentes não pos-
suem modelos explícitos do ambiente e precisam de informação 
disponível do ambiente local. Com isto, a informação não-local 
(visão de curto prazo) não pode ser tratada. É difícil fazer agentes 
reativos aprenderem, pois o comportamento emerge das interações 
no ambiente (sem metodologias básicas de projeto). E, finalmente, 
são necessárias muitas entidades com interações volumosas.
Agentes cognitivos
Agentes cognitivos possuem uma representação explícita do 
conhecimento, do ambiente e dos outros agentes. Eles conseguem 
registrar um histórico das interações e ações passadas, e interagem 
no ambiente usando comunicação direta entre os agentes (envio e 
recepção de mensagens). Um mecanismo de controle deliberativo 
faz com que o agente tome decisões, raciocine sobre metas, escolha 
planos e ações. Uma sociedade de agentes deliberativos para resolu-
ção de problemas complexos geralmente precisa de poucos agentes, 
diferentemente dos modelos reativos (Ferber e Gasser, 1991). 
Tipicamente, agentes cognitivos são agentes baseados em ló-
gica, ou seja, possuem um modelo simbólico do mundo (explícito) 
e as decisões são tomadas sobre ações feitas via raciocínio lógico, 
baseado em reconhecimento de padrões e manipulação simbólica.
Figura 37: Arquitetura clássica de um agente deliberativo 
(Weiss, 1999)
124INTELIGÊNCIA ARTIFICIAL
Na arquitetura clássica de agente deliberativo (Weiss, 1999), 
ilustrado na Figura 37, é preciso modelar uma base de conheci-
mento de fatos, crenças e regras de decisão. Módulos de raciocínio, 
execução e percepção executam sempre sobre esta base. Módulos 
adicionais podem incluir modelos de planejamento, administra-
ção e comunicação mais complexos, envolvendo processamento 
simbólico. Módulos de metas e objetivos precisam definir as 
situações desejáveis, conhecimento explicitamente representado e 
manipulável, onde as ações passadas influenciam decisões futuras.
Figura 38: Agente baseado em modelo e orientado por 
objetivos (Russel e Norvig, 2013).
Nosso modelo básico agrega módulos de raciocínio e ob-
jetivos explícitos que influenciam as ações futuras (Figura 38). 
Com estes módulos é possível medir a qualidade dos objeti-
vos (planos e ações), fazer a seleção de objetivos conflitantes. 
Agregando-se a módulos de utilidade é possível determinar 
esta qualidade e escolha de ações mais adequadas (Figura 39).
Figura 39: Agente baseado em modelo e orientado por utilidade 
(Russel e Norvig, 2013)
125INTELIGÊNCIA ARTIFICIAL
Um algoritmo básico para implementar este comportamento 
de um agente baseado em conhecimento é exemplificado abaixo:
Um exemplo clássico de agente baseado em conhecimento 
com métodos de escolha de ações é um agente de futebol (Fi-
gura 40) com módulo simples de escolha de ações que precisa 
planejar os movimentos de acordo com as modificações no 
ambiente e na sua base de crenças.
Figura 40: Exemplo de arquitetura para um simulador de 
agentes futebolísticos
126INTELIGÊNCIA ARTIFICIAL
Neste exemplo, cada tipo de agente (pa-
pel) possui um conjunto de crenças, desejos 
e intenções diferentes e precisam usar abor-
dagens lógicas para resolução de problemas 
usando técnicas de planejamento, análise de 
meios-fins, entre outros, conforme a Figura 
41.
Figura 41: Exemplo de conjuntos de ações de 
planejamento baseado em árvore de decisão
127INTELIGÊNCIA ARTIFICIAL
Arquiteturas de agentes deliberativos
Shoham (1991) propõe uma abordagem de Programação 
Orientada a Agentes (AOP), baseada em noções de intenção, 
crenças e compromissos dos agentes, contendo três componentes:
• uma lógica para especificar estados mentais;
• uma linguagem de programação interpretada;
• um processo de “agentificação” para converter aplicações 
tradicionais em agentes.
A linguagem de programação para os agentes de Shoham 
é a linguagem AGENT-0, uma extensão da linguagem LISP 
dividida em quatro componentes:
• Conjunto de capacidades (coisas que o agente sabe fazer).
• Conjunto de crenças iniciais.
• Conjunto de compromissos iniciais (coisas que o agente 
FARÁ).
• Conjunto de regras de compromisso (componente chave).
Arquitetura básica do agente deliberativo de Shoham:
Figura 42: Arquitetura Agent-0 (Shoam, 1991)
update
beliefs
beliefs
internal actions
massages out
massages in
update
commitments
commitments
abilities
initialise
execute
128INTELIGÊNCIA ARTIFICIAL
A comunicação usando a linguagem Agent-0 leva em con-
sideração as crenças, compromissos e habilidades do agente em 
relação à tarefa requisitada em um problema. Por exemplo, ao 
receber uma mensagem do agente x que requisita uma ação a no 
tempo t, o agente precisa ter em sua base as seguintes crenças:
• aquele agente é um amigo agora;
• o agente tem a habilidade de fazer a ação a no tempo t;
• o agente “não estou compromissado com outra ação no 
tempo t”, então;
• o agente pode se comprometer com a ação a no tempo t.
Ou, usando a sintaxe da linguagem AGENT-0:
Outra arquitetura genérica para agentes cognitivos foi 
proposta por Demazeau (1990):
Figura 43: Arquitetura genérica de agente deliberativo 
(Demazeau, 1990).
Nesta arquitetura genérica (Figura 43), é importante iden-
tificar o f luxo de percepção/comunicação que atualizará di-
retamente a base de conhecimento do agente a respeito do 
ambiente, dos outros agentes, do problema e de seus próprios 
estados internos. Um conjunto de metas representa as capaci-
dades e habilidades do agente em determinado contexto, que 
129INTELIGÊNCIA ARTIFICIAL
inf luenciarão o módulo de raciocínio em função das modi-
ficações na base de conhecimento. Com a análise do estado 
atual e da atualização do conhecimento conforme a percepção/
comunicação, o agente pode escolher possibilidades de ações 
e habilitar o módulo de decisão na construção de planos para 
atingir as metas correntes. Com base no planejamento feito, 
o módulo executor aciona os atuadores e atualiza o ambiente.
Com base na organização do conhecimento necessária na 
tomada de decisões de agentes deliberativos, outra arquitetura 
bem difundida é a BDI (Beliefs, Desires, Intentions), propos-
ta por Rao e Georgeff (1991). Nesta arquitetura, as crenças 
(Beliefs) representam o que o agente sabe sobre o estado do 
ambiente e dos agentes. Os desejos (Desires) mapeiam os esta-
dos do mundo que o agente quer atingir, onde os objetivos são 
subconjuntos de desejos que são compatíveis entre si (consis-
tentes). Finalmente, as intenções (Intentions) são as sequências 
de ações específicas que um agente se compromete a fazer 
para atingir um determinado objetivo (plano). Uma ilustração 
básica da arquitetura BDI clássica de Rao e Georgeff (1991) 
está na Figura 44.
Figura 44: Exemplo de Arquitetura BDI
130INTELIGÊNCIA ARTIFICIAL
A proposta da abordagem BDI é baseada em uma proposta 
de Lógica BDI, uma lógica não-clássica com conectivos modais 
para representar crenças, desejos e intenções, onde, dado um 
fato φ na base de conhecimento do agente i:
• (Bel i) -> i acredita φ
• (Des i) ->i deseja φ
• (Int i) -> i pretende φ
Agentes BDI precisam de uma linguagem de agentes que 
represente a lógica modal BDI, a fim de fornecer regras se-
guras para o interpretador raciocinar sobre os fatos. Uma das 
linguagens mais conhecidas e empregadas nesta arquitetura de 
agente é a AgentSpeak(L) (Rao, 1996), que é uma extensão 
natural da lógica BDI, contendo uma semântica operacional 
definida em termos da lógica e modalidades BDI.
Basicamente, AgentSpeak(L) define um conjunto de ter-
mos de programação usando uma sintaxe e um interpretador 
específicos, contendo, basicamente:
• Beliefs: fórmula de predicados representando fatos sobre o estado 
do ambiente e dos agentes.
• Goals: equivalentes a chamadas de métodos em linguagens orien-
tadas a objeto, constituem fórmulas de predicado que mapeiam 
eventos em regras de planos, executados por um gerenciador de 
eventos.
• Events: são ações atômicas como adotar crenças, adotar objetivos, 
abandonar crenças, etc. O agente possui uma fila de eventos que 
é selecionado conforme as regras de planejamento do agente.
• Plan Rules: define o comportamento do agente, ou seja, uma 
sequência de operadores de plano. Podem ser equiparados a 
métodos em linguagens tradicionais que operam a partir de 
eventos selecionados.
131INTELIGÊNCIA ARTIFICIAL
A partir dos elementos de AgentSpeak(L), um ciclo básico 
para um interpretador executa os seguintes passos:
1. seleciona um evento e da fila de eventos do agente;
2. encontra uma regra de plano p, cujo evento de acionamento 
corresponde a e em que o contexto é satisfeito;
3. se o evento é uma adoção/abandono de crença, cria uma nova 
intenção para processar o comportamento em p ou atualiza 
a intenção que gerou e, processando o comportamento em p;
4. seleciona uma intenção i e executa o próximo passo;
5. retorna para (1).
A sintaxe básica de um agent AgentSpeak(L) pode ser 
ilustrada a seguir:
AgentSpeak(L) é uma das linguagens de programação de 
agentes mais utilizadas na atualidade. Por este motivo, um 
interpretador da linguagem foi proposto em Bordini et al. 
(2005), chamado JASON, que implementa a semântica dos 
operadores lógicos de AgentSpeak(L) e fornece uma plataforma 
para o desenvolvimento de sistemas multiagentes.
132INTELIGÊNCIA ARTIFICIAL
Um exemplo de fragmento de código de programa de 
AgentSpeak(L) em JASON, através de um editor é ilustrado 
na Figura 45:
Figura 45: Exemplo ambiente de edição de agentes JASON
Sistemas multiagentes
Os Sistemas Multiagentes (SMA), segundo Wooldridge 
(2002), são sistemas formados por vários agentes, que se com-
portam de forma autônoma, interagindo com os outros agentes 
presentes no ambiente e, que, são capazes de:
• agir autonomamente na tomada de decisões levando à satisfação 
dos seus objetivos;
• interagir com outros agentes através de protocolos sociais inspirados 
nas formas de comunicação humana, incluindo as seguintes fun-
cionalidades: coordenação, cooperação, competição e negociação.
A construção de uma sociedade de agentes deve levar em 
conta a gestão das interações e das dependências entre objeti-
vos e atividades dos diferentes agentes no contexto do Sistema 
Multiagentes. Neste contexto, a coordenação desempenha um 
papel fundamental nos SMA, já que estes sistemas são ineren-
temente distribuídos (Lesser, 1999).
133INTELIGÊNCIA ARTIFICIAL
Para que um agente possa operar como parte do sistema, 
é necessário a existência de uma infraestrutura que permita a 
comunicação e/ou interação entre os agentes que compõem o 
SMA, conforme ilustra a Figura 46.
Figura 46: Arquitetura básica de um sistema multiagentes
Portanto, as estruturas fundamentais para modelagem de 
uma sociedade de agentes concentram-se nas formas de intera-
ção, organização e suas relações com o ambiente. Considerando 
que os elementos ativos operando nesta sociedade são os agentes, 
Demazeau (2001) sugere que as formalizações explicativas do 
comportamento e construção de SMAs são relações estruturais 
complexas entre quatro dimensões ortogonais, representadas 
aqui por suas iniciais, A, E, I, O, constituindo sua abordagem 
no modelo chamado L’approche Voyelles (Abordagem Vogais), 
ilustrado na Figura 47.
Figura 47: Estrutura dimensional da abordagem Voyelles de um 
SMA, segundo Demazeau (2001)
134INTELIGÊNCIA ARTIFICIAL
Ambiente
Segundo Russel e Norvig (2013), o ambiente de interação 
entre os agentes pode ser classificado sob diversas dimensões, 
notadamente, sob estes seis tipos: observável, acessível, deter-
minístico, episódico, estático e discreto, conforme particula-
rização na Tabela 2.
Tabela 2: Classificação de ambientes segundo Russel e Norvig 
(2013)
Observável sensores detectam todos os aspectos 
relevantes para escolha da ação.
Acessível informações atualizadas, precisas e 
completas sobre o ambiente.
Determinístico próximo estado é completamente 
determinável.
Episódico ação pode ser dividida em passos 
atômicos.
Estático ambiente não muda enquanto o agente 
escolhe.
Discreto número finito e fixo de ações e 
percepções.
As dimensões complementares a estes ambientes são:
• Completamente observável x Parcialmente observável: se 
os sensores não conseguem detectar todas as particularidades 
do ambiente ou são sujeitos a defeitos e ruídos, a observação 
não será completa. Um Jogo de Xadrez é completamente 
observável, enquanto um Jogo de Pôquer é parcialmente 
observável.
• Acessível x Inacessível: é possível que os agentes não con-
sigam informações completas ou seguras sobre o ambiente. 
• Determinístico x estocástico: quando o próximo estado, 
ação ou percepção não pode ser completamente determinado 
pela informação interna do agente. Um Jogo de Xadrez é 
determinístico e um diagnóstico médico é estocástico.
• Episódico x Sequencial: quando uma decisão corrente afeta 
decisões futuras o ambiente é sequencial. A tarefa de aná-
lise de imagens é episódica, enquanto um Jogo de Gamão 
é sequencial.
135INTELIGÊNCIA ARTIFICIAL
• Estático x Dinâmico: quando o ambiente muda conforme o 
agente executa ações sobre ele. Enquanto o robô de seleção 
de peças está em um ambiente dinâmico, o Jogo de Gamão 
é estático.
• Discreto x Contínuo: um Jogo de Xadrez é um ambiente 
discreto e um motorista autônomo é contínuo.
Interação
As características básicas de um framework para interações 
multiagentes são:
• envio e recebimento de mensagens utilizando uma lingua-
gem de comunicação;
• uso de protocolos de comunicação especificados pelo usuário;
• acompanhamento do funcionamento do sistema;
• facilidades: páginas amarelas, execução remota, interface.
Para um agente interagir com os outros no ambiente, é necessário 
sobretudo a Comunicação. Quando um conjunto de atividades/ações 
é dividido entre vários agentes, a forma de interação é chamada de 
Colaboração. A Coordenação ocorre quando diferentes agentes pre-
cisam organizar suas ações para atingir um objetivo coletivo. Quando 
é preciso resolver conflitos, os agentes lançam mão da Negociação. 
De forma mais genérica, existem duas formas básicas de interação: o 
modo direto e o modo indireto.
Comunicação de modo indireto ocorre entre os agentes através do 
ambiente. Um exemplo clássico é o comportamento dos agentes pura-
mente reativos em uma organização etológica, quando se comunicam 
através de traços no ambiente (percepção). Enquanto o modo direto im-
plica em uma troca de mensagens direta entre os agentes (comunicação).
A comunicação multiagente envolve o comportamento social 
humano através de comandos sensoriais que modificam as crenças 
e comportamentos dos interlocutores. Baseado na teoria clássica de 
Shannon (Shannon et Weaver, 1949) um ato comunicativo corresponde 
136INTELIGÊNCIA ARTIFICIAL
ao envio de informações de um emissor em direção a um destinatário, 
através de um canal de comunicação. Geralmente, a informação trans-
mitida é codificada na emissão e decodificada na recepção, através 
de uma linguagem de compreensão comum.
No caso dos agentes,a linguagem é padronizada através das Te-
orias dos Atos de Fala, de Austin (1962), sobre como a linguagem é 
usada para que as pessoas alcancem suas metas e intenções. Esta teoria 
é baseada em Enunciados Constativos, que descrevem ou relatam um 
estado de coisas, e; Enunciados Performativos, que indicam a execução 
de uma ação. Em termos de interação no SMA, nos ocupamos dos 
enunciados performativos que se subdividem em três atos de fala:
• Locucionário: ato de enunciar cada elemento linguístico que com-
põe a frase.
• Ilocucionário: o ato que se realiza na linguagem.
• Perlocucionário: ato que não se realiza na linguagem, mas pela 
linguagem (produz um efeito no interlocutor).
Vejamos um exemplo: no enunciado “Eu prometo que estarei 
em casa hoje à noite”, o enunciado performativo pode ser traduzido 
através de seus três atos, desta forma:
• pronúncia que produz o som (locucionário);
• ato de promessa (ilocucionário);
• resultado: ameaça, agrado ou desagrado (perlocucionário).
Ainda, segundo John Searle (1969), os atos de linguagem podem 
se classificar em cinco categorias básicas:
• Representativos: mostram a crença do locutor quanto à verdade de 
uma proposição (afirmar, asseverar, dizer).
• Diretivos: tentam levar o alocutário a fazer algo (ordenar, pedir, 
mandar).
• Comissivos: comprometem o locutor com uma ação futura (pro-
meter, garantir).
• Expressivos: expressam sentimentos (desculpar, agradecer, dar bo-
as-vindas).
137INTELIGÊNCIA ARTIFICIAL
• Declarativos: produzem uma situação externa nova (batizar, demitir, 
condenar).
Uma das linguagens multiagentes mais difundida é a KQML 
(Knowledge Query and Manipulation Language), que se trata de 
uma especificação de linguagem de comunicação entre agentes, onde 
qualquer linguagem pode ser usada para descrever o conteúdo da 
mensagem. A informação necessária para a interpretação da mensa-
gem está na própria mensagem e a implementação dos agentes pode 
ignorar o mecanismo de transporte da mensagem (TCP/IP, RMI, 
IIOP, etc.), conforme Finin et al. (1994).
Na camada de linguagem:
• :language <word>: identifica a linguagem de representação do 
conteúdo (Prolog, SQL, KIF, etc...).
• :ontology <word>: especificação do domínio de conhecimento do 
conteúdo da mensagem. 
Na camada de comunicação:
• :sender <word> e :receiver <word>: identificam o agente emissor 
de um performativo e o receptor da mesma.
• :from <word> e :to <word>: parâmetros da mensagem forward, 
identificando a origem e o destino do performativo.
• :reply-with <word> e :in-reply-to <word>: identificador único 
para a mensagem que o agente emissor espera como resposta do 
receptor.
138INTELIGÊNCIA ARTIFICIAL
Na camada de conteúdo:
• :content <expression>: é o que está sendo passado como 
conteúdo da mensagem. O valor de <expression> deve ser 
válido com relação à linguagem de representação do conteúdo.
Alguns exemplos de performativos típicos:
• tell: informa que o conteúdo da mensagem está na base de 
conhecimento do locutor.
• ask-if: o locutor quer saber se o conteúdo de sua mensagem 
é verdadeiro para o receptor.
• advertise: o locutor quer que o receptor saiba que ele pode 
processar mensagens no modelo do seu conteúdo.
• insert: o locutor “pede” ao receptor que adicione o conteúdo 
da mensagem à sua base de conhecimento.
De forma a padronizar a forma de comunicação para SMA, 
a FIPA (Foundation for Intelligent Physical Agents) promove 
tecnologias baseadas em agentes e a interoperabilidade de seus 
padrões com outras tecnologias, produzindo especificações de 
padrões para sistemas baseados em agentes. Nestes padrões, 
um Envelope de Linguagem de Comunicação de Agentes, ou 
Envelope ACL (Agent Communication Language) promove um 
conjunto de especificações padronizado para implementação da 
comunicação multiagentes, como exemplificado na Figura 48.
Figura 48: Exemplo de Envelope FIPA-ACL
139INTELIGÊNCIA ARTIFICIAL
Neste envelope, atos de comunicação e protocolos são descri-
tos a partir de convenções KQML e de atos de fala (Figura 49).
Figura 49: Padrões de nomenclatura para FIPA-ACL
Um exemplo típico de comunicação entre um AGENT1 
e outro AGENT2 será ilustrado na Figura 50.
Figura 50: Exemplo de comunicação entre agentes usando 
FIPA-ACL
Finalmente, o conjunto de templates de mensagens pode 
ser agrupado e organizado através de protocolos que repre-
sentam as intenções perlocutórias dos agentes. Por exemplo, a 
Figura 51 ilustra a representação de um protocolo ACL para 
implementar uma rede de negociações entre vários agentes, 
para que um consenso seja alcançado na solução de uma tarefa.
140INTELIGÊNCIA ARTIFICIAL
Figura 51: Exemplo de protocolo de negociação Organização
Até o momento, as abordagens focalizaram a noção de 
agente e as relações entre os estados internos de um agente e seu 
comportamento, em relação ao ambiente. No momento em que 
a comunicação é confrontada com conflitos e interdependências 
em contextos utilitários de Colaboração, Coordenação e Negocia-
ção, torna-se indispensável levar em consideração uma dimensão 
Social no comportamento em SMAs. Aqui serão apresentadas 
as noções de organização, papéis, grupos, tarefas, etc.
Organizações multiagentes podem existir de forma sub-
jetiva, se a organização só pode ser descrita através de um ob-
servador ou um agente externo, examinando o comportamento 
dos agentes (organização reativa, swarm, etc.); ou, de forma 
objetiva, quando a organização é explícita aos agentes através 
de estruturas, hierarquias e normas. A organização pode sur-
gir por meio de formação de coalizões, distribuição de papéis, 
alocação de tarefas, macroestruturas, entre outras.
141INTELIGÊNCIA ARTIFICIAL
Além disso, as formas objetiva e subjetiva ainda podem 
ser tomadas, segundo a visão do SMA, centradas no agente 
ou centradas na organização.
Figura 52: Diferentes pontos de vista segundo uma concepção 
centrada no agente ou centrada na organização
A Figura 52 ilustra a principal diferença entre as duas 
concepções. Na visão subjetiva, centrada no agente, o agente é 
incapaz de gerar uma representação interna de sua organização. 
É o que acontece, por exemplo, em um formigueiro, os agen-
tes possuem um conhecimento apenas parcial da organização 
através da observação. Os papéis de especialização garantem 
o funcionamento emergente de uma estrutura implícita nas 
atividades individuais de cada papel na sociedade. 
Na visão objetiva, centrada na organização, o agente, como 
observador, consegue “ler” ou identificar uma organização 
previamente institucionalizada, capaz de inf luenciar suas re-
presentações internas de uma organização estruturada.
Assim, as modelagens de organizações multiagentes consi-
derarão fortemente a formalização de elementos como papéis, 
funções, metas, atividades, planos, etc.
142INTELIGÊNCIA ARTIFICIAL
Em nível organizacional, os papéis são protótipos de fun-
ções a serem desempenhados pelos agentes na organização, 
constituindo-se em conjuntos de:
• processos que definem como as metas podem ser alcançadas;
• autoridades que o agente necessita para alcançar as metas;
• habilidades que o agente que pretende assumir o papel deve possuir;
• restrições na execução dos processos, e
• recursos necessários.
Para Ferber e Gutknecht (1998), um esquema básico de mo-
delagem de organizações multiagentes é baseado em um conjunto 
de grupos e agentes com papéis nestes grupos. Um grupo possui 
papéis para funcionar e cada papel é um conjunto de funções 
que os agentes podem assumir. Neste modelo, uma organização 
é praticamente instanciada pelos agentes.
A Figura 53 ilustra o modelo AGR (Agent-Groupe-Rôle), 
um modelo organizacional mínimo baseado nos três conceitos 
primitivos de Agente, Grupo e Papel, os quais estruturam o 
aspecto estático e dinâmico de uma organização multiagentes. 
O aspecto estático estipula que um grupo é definido por um 
conjunto de papéis, que são permitidos em cada grupo e que os 
mesmos possuem características associadas a um grupo,manten-
do comunicação apenas dentro do grupo. O aspecto dinâmico é 
instanciado quando agentes assumem papéis e, automaticamente, 
integram os grupos para os quais os papéis são atribuídos. 
Figura 53: Esquema básico de uma organização AGR (Ferber & 
Gutknecht, 1998)
143INTELIGÊNCIA ARTIFICIAL
Outra abordagem organizacional para SMA é o mode-
lo Moise (Model of Organization for multI-agent SystEm) de 
Hannoun et al. (2000) e suas extensões, Moise+ (Hübner et 
al., 2002) e MoiseInst (Gâteau et al., 2005), que levam em 
consideração os aspectos estruturais, funcionais e normativos 
de uma relação social.
A especificação estrutural estabelece o que os agentes 
podem fazer, definindo os papéis, as relações entre papéis e os 
grupos. A especificação funcional determina como os agentes 
podem fazer suas tarefas/ações, representados através de metas 
globais, missões e planos. A especificação normativa ou de-
ôntica define o que os agentes devem fazer, quais missões um 
papel tem permissão ou obrigação de se comprometer. Uma 
representação arquitetural do modelo Moise+ é ilustrada na 
Figura 54.
Figura 54: Exemplo de arquitetura de Moise+
144INTELIGÊNCIA ARTIFICIAL
Especificação Estrutural no Moise+
Na definição da especificação estrutural, um papel é re-
presentado como um conjunto de restrições comportamentais 
que um agente aceita quando entra em um grupo em relação a 
outros agentes (por exemplo, autoridade) e em relação a tarefas 
comuns (por exemplo, objetivos globais). Esta especificação é 
estabelecida em três níveis: individual, social e coletivo.
O nível individual apresenta a definição dos papéis e as 
relações de herança e interação entre os papéis, conforme exem-
plificado na Figura 55.
Figura 55: Relação de herança entre papéis
O nível social estabelece qual é a ligação entre papéis, 
conforme explicado e detalhado na Figura 56.
Figura 56: Representação das ligações entre os papéis
O Nível coletivo associa agrupamento aos papéis conforme 
ilustrado na Figura 57.
Figura 57: Associação de papéis em grupos
145INTELIGÊNCIA ARTIFICIAL
Especificação Funcional no Moise+
A especificação funcional define um conjunto de esquemas que 
um SMA utiliza para alcançar suas metas. Estes “esquemas sociais” 
são junções de planos com missões capazes de executar a consecução 
de metas e objetivos. Um conjunto de planos determina a coorde-
nação na realização das metas, enquanto um conjunto de missões 
associa os agentes aos planos, conforme exemplificado na Figura 58.
Figura 58: Exemplo de conjunto de missões para atingir 
determinada meta
Em nível coletivo, a definição de esquema funcional em 
Moise+ é representado por uma árvore de decomposição global 
de objetivos. Esta decomposição é feita através dos planos, de 
forma que os elementos principais na especificação do esque-
ma são planos e objetivos. Um plano possui um identificador 
do objetivo, um operador de sequência, escolha ou paralelo e 
uma lista de objetivos associados. Cada objetivo possui um 
identificador único e uma descrição com argumentos opcio-
nais, que pode ser uma instanciação de valores na criação do 
esquema. A Figura 59 ilustrará a representação de uma árvore 
de decomposição de objetivos com planos para suas execuções.
Figura 59: Decomposição funcional de planos para execução de 
objetivos nas missões
146INTELIGÊNCIA ARTIFICIAL
Especificação Deôntica no Moise+
Finalmente, a especificação deôntica ou normativa do Moi-
se+, define a relação entre as especificações estrutural e funcional, 
estabelecendo as responsabilidades dos papéis sobre as missões, 
através de permissões ou obrigações ao comprometimento da 
missão. Um conjunto de permissões determina que um agente, 
investido de um determinado papel, deve se comprometer com 
uma determinada missão. Por sua vez, um conjunto de obrigações 
estabelece que um agente, que possui um determinado papel, é 
obrigado a se comprometer com a missão em um determinado 
período de tempo, como exemplificado na Figura 60. 
Figura 60: Exemplo da especificação deôntica a partir de um 
conjunto de missões e papéis associados
A especificação deôntica exemplificada na Figura 60 pode 
ser representada em formato XML, conforme o exemplo:
147INTELIGÊNCIA ARTIFICIAL
Síntese
Atualmente, Sistemas Multiagentes são considerados suporte básico para aplicações que precisam 
de autonomia e comportamentos colaborativos de resolução distribuída de problemas, disseminados 
por áreas como Robótica, Tomada de Decisão Racional, Integrações com sistemas de IoT (Internet 
das Coisas) e Inteligência Coletiva.
Este capítulo apresentou um pouco dos vários temas pertencentes ao estudo de Sistemas Multia-
gentes, principalmente aliando questões conceituais com aplicações práticas e introdução a algoritmos 
básicos de comportamento de sistemas de agentes. Estudos mais recentes integram comportamentos 
cognitivos com representação de objetos inativos do ambiente, artefatos simbólicos de atuação do 
agente e representação de questões normativas para comportamento social. A área de simulação 
também atrai bastante atenção para a simulação de modelos matemáticos através de comportamentos 
reativos e deliberativos de múltiplas entidades interagentes.
As questões aqui abordadas são base para aplicações, envolvendo tomadas de decisão, planeja-
mento autônomo, elaboração de metas, avaliação de atividades coordenadas e inteligência distribuída.
148INTELIGÊNCIA ARTIFICIAL
Exercícios
Atividade prática sobre agentes reativos:
a. Acesse o seguinte link:
http://www.natureincode.com/code/various/ants.html
Execute os passos para rodar a simulação das formigas 
procurando o recurso e ref lita:
1. Como as formigas convergem em um caminho entre o 
formigueiro e o recurso?
2. Em que problemas reais a metáfora do comportamento das 
formigas pode ser aplicada?
Acesse igualmente estes outros links:
• https://processing.org/examples/flocking.html
• http://hughsk.io/boids/
• http://www.borgelt.net/acopt.html
Examine o código e explique como o comportamento 
coletivo foi implementado?
http://www.natureincode.com/code/various/ants.html
149INTELIGÊNCIA ARTIFICIAL
Atividade prática sobre agentes deliberativos:
Desenvolvimento de um time de agentes cognitivos para ser utilizado no Multiagent Programming Contest: 
• Informações sobre o cenário e o simulador da competição encontram-se no seguinte link: 
https://multiagentcontest.org/2018/ 
Pode ser utilizado qualquer ambiente de desenvolvimento de sistemas multiagentes, como por exemplo, 
o JADE (Bellifemine et al., 2007) ou o arcabouço JaCaMo (Bordini e Hübner, 2014), composto pelas lin-
guagens de programação de agentes JASON (Bordini et al., 2005), de ambientes Cartago e de organizações 
MOISE (Hübner et al., 2002).
Multi-Agent Programming Contest é uma competição em que, simultaneamente, dois times são situ-
ados no mesmo ambiente e competem diretamente num cenário definido pelos organizadores. O cenário 
denominado “Agents in the City”, tem como objetivo maximizar a utilidade obtida por um time de agentes 
ao completar suas tarefas, que consistem em construir poços, comprar, montar e transportar bens. Tarefas 
podem ter preços fixos ou estabelecidas em leilões. Times devem decidir quais tarefas devem completar e 
como executá-las (onde obter os recursos, como navegar na cidade) e de quais leilões devem participar. O 
ambiente consiste em ruas de uma cidade próxima da realidade, mas que representam Marte em 2045.
https://multiagentcontest.org/2018/
http://jade.tilab.com
http://jacamo.sourceforge.net
150INTELIGÊNCIA ARTIFICIAL
Referências
AUSTIN, J.L., 1962. “How To Do Things With Words”, 2nd Edition, ed. J.O. Urmson and M. Sbisá. Cambridge, MA: 
Harvard University Press.
BÄCK, T., Dogel, D.B. & Michalewicz, Z. (eds.) “Evolutionary Computation 2: Advanced Algorithms and Operators”, Ins-
titute of Physics Publishing, 2000.
BAKER, James E. (1987). “Reducing Bias and Inefficiency in the Selection Algorithm”. Proceedings of the SecondInterna-
tional Conference on Genetic Algorithms and their Application. Hillsdale, New Jersey: L. Erlbaum Associates: 14–21.
BARR, A. & E. A. Feigenbaum, The Handbook of Artificial Intelligence, Kaufman, Los Altos, Calif., 1981.
BELLIFEMINE, Fabio Luigi; Giovanni Caire, and Dominic Greenwood. Developing Multi-Agent Systems with JADE. 
Wiley, 2007.
BELLMAN, R. (1978). An introduction to artificial intelligence: can computers think? San Francisco, Boyd & Fraser Pub. Co.
BITTENCOURT, G. Inteligência Artificial. 2ª Ed. Florianópolis: Editora da UFSC, 2006.
151INTELIGÊNCIA ARTIFICIAL
BONABEAU, Eric; Dorigo, Marco and Theraulaz, Guy. “Swarm Intelligence: From Natural to Artificial Systems”. New York, 
NY: Oxford University Press, Santa Fe Institute Studies in the Sciences of Complexity. 1999. ISBN 0-19-513159-2.
BORDINI, R.H.; Hübner, J. F. JaCaMo Project. 2014. http://jacamo.sourceforge.net
BORDINI, R.H., Hübner, J.F., et al.: “Jason: A Java-based agentSpeak interpreter used with saci for multi-agent distribution 
over the net”, manual, version 0.6 edition (Feburary 2005), http://jason.sourceforge.net/
BOULANGER, Albert G. The Expert System Plant/cd: A Case Study in Applying the General Purpose Inference System 
Advise to Predicting Black Cutworm Damage in Corn. Urbana, Ill: Dept. of Computer Science, University of Illinois at Ur-
bana-Champaign, 1983.
BROOKS, R. “A robust layered control system for a mobile robot”. In: IEEE Journal of Robotics and Automation, v. 2, n. 1, 
p. 14-23, march 1986.
BROOKS, R. “Elephants don’t play chess”. In: Robotics and Autonomous Systems. 6: 139–159. doi:10.1016/s0921-8890(05)80025-
9. 1990.
152INTELIGÊNCIA ARTIFICIAL
C. E. Shannon et W. Weaver. The Mathematical Theory of Communication. University of Illinois Press, Urbana, Illinois, 1949.
CHANDRASEKARAN, B. “Natural and social system metaphors for distributed problem solving: introduction to the issue”. 
In: IEEE Transactions on Systems, Man and Cybernetics, v. 11, n. 1, p. 1-5, Jan. 1981.
CHARNIAK, E.; McDermott, D. 1985. Introduction to Artificial Intelligence. Addison-Wesley Longman Publishing Co., 
Inc., Boston, MA, USA.
DAVENPORT, Thomas H., and Laurence Prusak. Working Knowledge: How Organizations Manage What They Know. 
Boston, Mass: Harvard Business School Press, 1998.
DAVIS, T.; Buchanan, B.; Shortliffe, E. Production rules as a representation for a knowledge-based consultation program. 
Artificial Intelligence 8:15-45, 1977.
DEMAZEAU, Y.; Müller, J. P. “Decentralized artificial intelligence”. In: Demazeau, Y. e Müller, J.P. eds. Decentralized A 
I., Amsterdam, Elsevier, 1990.
DEMAZEAU, Y. “VOYELLES. Mémoire d’Habilitation à Diriger des Recherches”, Institut National Polytechnique de Gre-
noble INPG, Avril 2001.
153INTELIGÊNCIA ARTIFICIAL
DENNETT, D. C. (1991). “Consciousness explained”. Boston, Little, Brown and Co.
DRETSKE, F. I. Knowledge and the f low of information. Cambridge, MA: MIT, 1981.
DRUCKER, P. Desafios Gerenciais para o Século XXI. São Paulo: Pioneira, 1999.
DUDA, R., P. E. Hart, N. J. Nilsson, R. Reboh, J. Slocum, and G. Sutherland. Development of a Computer-Based Consultant 
for Mineral Exploration. SRI Report, Stanford Res. Inst., 333 Ravenswood Ave., Menlo Park, CA. 1977.
ESHELMAN, L. J., Caruana, R. A. & Schaffer, J. D. “Biases in the Crossover Landscape”, in Schaffer, J. (ed.), Proceedings 
of the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, 10-19, 1989.
FERBER, J. e Gasser, L. “Intelligence artificielle distribuée”. In: XI International Workshop on Expert Systems & their 
Applications, Avignon, France, 1991, Cours n. 9.
FERBER, J. e Gutknecht, O. “A Meta-Model for the Analysis and Design of Organizations in Multi-Agent Systems”. In Pro-
ceedings of the 3rd International Conference on Multi Agent Systems (ICMAS ‘98). IEEE Computer Society, Washington, 
DC, USA, 1998.
154INTELIGÊNCIA ARTIFICIAL
FININ, T.; Fritzson, R.; McKay, D.; McEntire, R. (1994). “KQML as an agent communication language”. Proceedings of the 
third international conference on Information and knowledge management - CIKM ‘94. p. 456. 
GÂTEAU, B; Boissier, O.; Khadraoui, D. and Dubois, E. “MoiseInst: An organizational model for specifying rights and duties 
of autonomous agents”. In L. Van der torre G. Boella, editor, In 1st International Workshop on Coordination and Organisation 
(CoOrg 2005) affiliated with the 7th International Conference on Coordination Models and Languages, Namur Belgium, 
April 2005.
GOLDBERG, D. E. Genetic Algorithms in search, optimization, and machine learning. New York: Addison-Wesley Pu-
blishing Company, Inc. 1989.
HANNOUN, M.; Boissier, O.; Sichman, J.S.; Sayettat, C. “MOISE: An organizational model for multi-agent systems”. In 
Monard, M.C. and Sichman, J.S. editors, Proceedings of the International Joint Conference, 7th Ibero-American Conference 
on AI, 15th Brazilian Symposium on AI (IBERAMIA/SBIA’2000), Atibaia, SP, Brazil, November 2000, LNAI 1952, pages 
152-161, Berlin, 2000. Springer.
HAUGELAND, J. (1985). “Artificial Intelligence: The Very Idea”. Cambridge: MIT Press.
155INTELIGÊNCIA ARTIFICIAL
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press. Second edition (1992). 
(First edition, University of Michigan Press, 1975).
HÜBNER, J.F.; Sichman, J.S.; Boissier, O. “A model for the structural, functional, and deontic specification of organizations 
in multiagent systems”. In Bittencourt, G. and Ramalho, G. editors, Proceedings of the 16th Brazilian Symposium on Artificial 
Intelligence (SBIA’02), volume 2507 of LNAI, pages 118-128, Berlin, 2002. Springer. 
KURZWEIL, Raymond. 1990. The Age of Intelligent Machines. MIT Press, Cambridge, MA, USA.
LAGRANDEUR, K. Androids and Intelligent Networks in Early Modern Literature and Culture: Artificial Slaves . (Rout-
ledge Studies in Renaissance Literature and Culture, no. 22.) New York: Routledge, 2013. Pp. Xiv, 207.
LAUDON, Kenneth, C. Laudon, Jane P. Sistemas de Informação com Internet. 4ª Ed. São Paulo, 2003.
LESSER, V. “Cooperative Multi-Agent Systems: A Personal View of the State of the Art”, IEEE Transactions on Knowledge 
and Data Engineering, Vol. 11, Nº1, Janeiro/Fevereiro de 1999.
LUGER, G.F. Inteligência artificial. 6 ed. São Paulo: Pearson Education do Brasil, 2013.
156INTELIGÊNCIA ARTIFICIAL
MARSH, A. K. Pace of Artificial Intelligence Research Shows Acceleration. Aviation Week & Space Technology, Dec. 10. 
p. 5, 1984.
MCCARTHY, J.; Hayes, P. J. 1987. Some philosophical problems from the standpoint of artificial intelligence. In Readings 
in nonmonotonic reasoning, Matthew L. Ginsberg (Ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA 26-45.
MCCULLOCH, Warren S.; Pitts, Walter H. “A Logical Calculus of the ideas immanent in nervous activity”. Bulletin of 
Mathematical Biophysics (1943) 5: 115. https://doi.org/10.1007/BF02478259
MCDERMOTT, J.P. R1: The Formative Years. AI Magazine 2:21-9, 1980.
MICHALEWICZ, Z. “Genetic Algorithms + Data Structures = Evolution Programs”, 3rd edition, Springer, 1996.
MICHALEWICZ, Z. & Schoenauer, M. “Evolutionary Algorithms for Constrained Parameter Optimization Problems”, 
Evolutionary Computation, 4(1): 1-32, 1996.
MINSKY, M. (1974). A Framework for Representing Knowledge. A. I. Memo 306, Cambridge, MA: Artificial Intelligence 
Laboratory, Massachusetts Institute of Technology. 
157INTELIGÊNCIA ARTIFICIAL
MINSKY, Marvin (1975). “Minsky’s frame system theory”. In Proceedings of the 1975 workshop on Theoretical issues in na-
tural language processing (TINLAP ‘75). Association for Computational Linguistics, Stroudsburg, PA, USA, 104-116.
MÜHLENBEIN, H. How genetic algorithm really work I. Mutation and Hillclimbing. Parallel problem solving from nature. 
1992.
QUILLIAN, R. Semantic Memory. In M. Minsky (ed) Semantic Processing. MIT Press, Cambridge, MA, 1968.
RAO, A.S. 1996. “AgentSpeak(L): BDI Agents Speak Out in a Logical Computable Language”.Proceedings of Seventh Eu-
ropean Workshop on Modelling Autonomous Agents in a Multi-Agent World (MAAMAW-96).
RAO, A.S.; Georgeff, M.P., “Modeling Rational Agents within a BDI-Architecture”, Second International Conference on 
Principles of Knowledge Representation and Reasoning, Cambridge, Massachusetts, USA, 1991.
RICH, Elaine and Kevin Knight. 1990. Artificial Intelligence (2nd ed.). McGraw-Hill Higher Education.
ROSENBLATT, F. The Perceptron: A Probabilistic Model For Information Storage And Organization In The Brain. Psy-
chological Review, Vol. 65, No. 6, 1958.
158INTELIGÊNCIA ARTIFICIAL
RUSSEL, S.; Norvig, P. “Inteligência Artificial: Uma Abordagem Moderna”. 3a. ed. Rio de Janeiro: Elsevier. 2013.
SEARLE, J. “Speech acts”. Cambridge University Press, 1969.
SHANNON, Claude. (1949). “Programming a Computer for Playing Chess”. In: Philosophical Magazine 41.314.
SHOHAM, Y. “Agent oriented programming”. In: Artificial Intelligence, v. 60, n. 1, p. 51-92, 1991.
SHORTLIFFE, E. H, Axline, S. G, Buchanan, B. G, Merigan, T. C, and Cohen, S. N. “An artificial intelligence program 
to advice physiciancs regarding antimicrobial therapy”, Computers and Biomedical Research, Vol. 6, pp. 544-560. 1973.
SIEMIENIUCH, C. E., Sinclair, M. A., & Loughborough U of Technology, HUSAT Research Inst. (1999). Organization 
aspects of knowledge lifecycle management in manufacturing. International Journal of Human-Computer Studies, 51(3), 517-547.
SIMON, H. (1983). Reason in human affairs. Stanford, CA: Stanford UniversityPress.
STEELS, L. “Cooperation between Distributed Agents through Self-Organization”. In: Decentralized A.I. Demazeau, Y. e 
Muller, J-P. (Eds), North-Holland, Amsterdam, 1990.
159INTELIGÊNCIA ARTIFICIAL
STEFIK, M. Planning and Meta-Planning (MOLGEN Part 2). Artificial Intelligence, 16(2), 141-169, May 1981.
SYSWERDA, G. “Uniform Crossover in Genetic Algorithms”, in Schaffer, J.D. (ed.), Proceedings of the Third International 
Conference on Genetic Algorithms, Morgan Kaufmann Publishers, pp. 2-9, 1989.
WEISS, Gerhard. “Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence”, MIT Press, 1999
WERBOS, Paul J. Backpropagation: basics and new developments. In The handbook of brain theory and neural networks, 
Michael A. Arbib (Ed.). MIT Press, Cambridge, MA, USA 134-139. 1998. 
WHITLEY, D. A Genetic Algorithm tutorial. Springer. 1994.
WIIG, K. M. (1993). Knowledge management foundations : thinking about thinking : how people and organizations create, 
represent, and use knowledge. Arlington (Tex.): Schema press.
WINSTON, P.H. 1984. Artificial Intelligence (2nd Ed.). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
WOOLDRIDGE, Michael, An Introduction to Multi-Agent Systems, John Wiley & Sons, Ltd, 2002.
	Sistemas de Informação Inteligentes
	Conceitos Básicos
	Dado-Informação-Conhecimento
	Representação do conhecimento
	Estados e busca heurística
	Lógica
	Regras de produção
	Frames e scripts
	Redes semânticas
	Computação Evolutiva
	Síntese
	Resolução de problemas
	Formulação do problema
	Técnicas de resolução
	Busca competitiva
	Síntese
	Sistemas especialistas
	Síntese
	Algoritmos genéticos
	Princípios básicos
	Síntese
	Aprendizagem automática
	Aprendizagem supervisionada
	Redes neurais artificiais
	Síntese
	Agentes inteligentes e sistemas multiagentes
	Síntese
	Referências