CIC284 - Inteligência Artificial em Controle e Automaçãowalderson.com/2010-2/univag/intartaplicada/01-Apostila.pdf · UNIVERSIDADE FEDERAL DE OURO PRETO INSTITUTO DE CIÊNCIAS

UNIVERSIDADE FEDERAL DE OURO PRETO

INSTITUTO DE CIÊNCIAS EXATAS E BIOLÓGICAS DEPARTAMENTO DE COMPUTAÇÃO

Apostila

CIC284 - Inteligência Artificial em Controle e Automação

Álvaro Guarda

Ouro Preto - MG Março de 2005

Inteligência Artificial em Controle e Automação Álvaro Guarda 2

Sumário



1. Introdução

O termo “Inteligência Artificial” (IA) desperta interesse e muitas expectativas, freqüentemente equivocadas. Além do termo que é um tanto ambicioso, existe muito sensacionalismo sobre IA em revistas, jornais e inclusive em livros. Alguns exemplos de afirmações exageradas são:

� "O homem vai tentar reproduzir o computador à sua imagem". Artigo "A revolução da IA" (Estado de Minas, 18/11/96).

� "O objetivo principal da IA é construir uma pessoa, ou mais humildemente, um animal", Charmiak e McDermott. � "Um computador é inteligente se possui qualquer uma das habilidades mentais que fazem uma pessoa ser

considerada inteligente" [Araribóia88].

Assim, como as expectativas não são realistas, os resultados que são obtidos na área freqüentemente são muito mais tímidos do que se esperava. Isto gera uma certa de desconfiança por parte de pesquisadores de outras áreas e acaba até prejudicando o desenvolvimento da IA. Entretanto, a IA já desenvolveu muitas técnicas que são úteis nas mais diversas áreas: otimização, datamining, jogos, tradução automática, processamento de imagens, interface homem-máquina, etc. 1.1. Objetivos do Curso No curso alguns tópicos são estudados procurando aprofundar os aspectos importantes, permitindo que o aluno possa dar continuidade ao estudo da área e aplicar os conhecimentos adquiridos de forma autônoma. Outros pontos são apresentados sem caráter formativo, mas procurando dar uma visão abrangente da área e de suas aplicações. Ao final do curso o aluno deverá dominar diversos pontos da IA clássica e conhecer razoavelmente bem alguns tópicos avançados em IA, interessantes para a área de automação e controle. Em algumas partes do curso, além do conhecimento teórico, são abordados aspectos práticos, fazendo experimentações e/ou implementando diversas técnicas. 1.2. Evolução da Inteligência Artificial

. . . . - 1960 Pré-IA Lisp Sistemas de Produção (evolução de sistemas genéricos).

1960 - 1965 Período do entusiasmo Macsyma, Dendral

1965 - 1970 Período das Trevas Conscientização das limitações

1970 - 1975 Período da renascença Hearsy, Mycin (ajudava a diagnosticar doenças no sangue, tinha 450

regras e fazia análise do sangue), Prospector (fazia prospecção geológica), Prolog

1975 - 1980 Período da associação Áreas de aplicação

1980 - . . . . Período do empreendimento Popularização de SE Ferramentas e Ambientes

1.3. Áreas de Pesquisa da IA � Processamento do Conhecimento (simbólico)

o Modelagem e Representação o Métodos de Inferência o Sistemas Baseados em Conhecimento o Aquisição de Conhecimento


o Aprendizado Computacional � Redes Neuronais � Sistemas e Linguagens para IA � Arquiteturas Específicas para IA � Processamento de Linguagem Natural � Robótica Inteligente o Síntese de Voz o Percepção o Manipulação o Planejamento

1.4. Referências O conteúdo desta apostila é fortemente baseado na bibliografia básica do programa da disciplina, CIC284 – Inteligência Artificial em Controle e Automação, [Nascimento00], [Rich93] e [Mitchell97] e em alguns livros da bibliografia complementar como [Bratko90]. Diversas partes do texto também foram baseadas no material de aula do Prof. Elton Silva.


2. Caracterização 2.1. Discussão e Tentativa de Definição O termo “Inteligência Artificial” não é de fácil definição e há controvérsias entre vários pesquisadores. Abaixo são apresentadas algumas definições para as palavras que compõem o termo retirado do Dicionário Michaelis e outros.

Artificial • Produzido por arte ou indústria do homem e não por causas naturais. • Que envolve artifício. • Contrafeito, fingido, postiço. • Feito pelo homem. • Imitação. • Oposto de natural. • Tenta imitar o comportamento humano.

Inteligência • Faculdade de entender, pensar, raciocinar e interpretar; entendimento, intelecto. • Compreensão, conhecimento profundo. • Pessoa de grande esfera intelectual. • Habilidade em fazer determinada coisa. • Faculdade ou capacidade de aprender, compreender. • Facilidade de adaptação. • Intelectualidade. • Destreza mental, perspicácia. • Habilidade mental medida pelo QI (capacidade de manipulação simbólica).

A inteligência deve ser compreendida não apenas como aptidão para o manejo de símbolos e números, mas sobretudo como habilidade para interagir com o meio ambiente, lidar com situações inesperadas, fazer uso de analogias, metáforas e abstrações.

Os grandes gênios da humanidade ajudaram a fixar na cultura ocidental um padrão de "homem inteligente". Entretanto, este padrão apresenta alguns problemas:

• Albert Einstein : Maltratava a mulher como uma escrava particular, era excessivamente rabugento.

• Sigmund Freud : Sofria do complexo de Édipo, era obcecado pela mãe.

• Karl Max : Queria demolir o capitalismo, mas era um gastador inveterado, não sabia administrar as suas finanças e vivia pedindo dinheiro aos amigos.

• Charles Darwin : Pesquisador compulsivo, tinha síndrome de pânico. Tinha crises de vômito com medo da Teoria da Evolução.

Assim, a inteligência passou a ser vista e discutida sob vários aspectos:

• Inteligência racional (acadêmica): geralmente associada a aptidões lingüísticas e numéricas.

• Inteligência intra-pessoal : conhecer-se a si mesmo.

• Inteligência social : relações humanas, entender os outros.

• Inteligência corporal : relacionamento com o espaço (ex.: Garrincha, Pelé, Barishnikov).

• Inteligência emocional : autocontrole, zelo, persistência, capacidade de se motivar, etc. Atualmente há um consenso de que um alto QI não é garantia de sucesso e passou-se a adotar o que chamamos de

Inteligência Emocional (IE) juntamente com o QI. A habilidade de lidar com características avaliadas pela IE pode dar a verdadeira medida da inteligência humana: autocontrole, zelo, persistência, capacidade de se motivar, etc. Hoje em dia as empresas estão valorizando muito essas capacidades em seus futuros empregados.

Neste contexto surge a questão da necessidade e da possibilidade de se prover capacidades emocionais em máquinas. Desconsiderando esta questão, apesar de parecer que as definições apresentadas são suficientes, a definição de inteligência é superficial, descrevendo apenas qualidades ou apresentando sinônimos. Nem mesmo os pesquisadores em Psicologia Cognitiva sabem como a inteligência funciona, como é formada e o que é necessário para que ela se manifeste.

Existem muitas discussões filosóficas sobre o assunto. Para muitos cientistas, a inteligência está relacionada com vontade própria, intencionalidade, e existem outras esferas de discussão:


Criacionista :

• ser inteligente transcende a criação. • Inteligência ligada ao conceito de alma, espírito. • Capacidade de auto-avaliação, não agir só por instinto.

Evolucionista : • Alma = cérebro • A mente seria um efeito complexo das leis que governam as partículas físicas que compõe o cérebro. • homem seria apenas um robô biológico.

Alguns cientistas da computação enfatizam que os computadores são "idiotas" com capacidade de processar informação em altíssima velocidade, seguindo exatamente as "ordens" dos seus programadores.

Russel e Norvig [Russel95] propõem uma organização de diferentes definições de IA variando em duas dimensões principais e formando quatro categorias como apresentado na Figura 1. A dimensão ocupando o eixo horizontal trata da forma de funcionamento: humano x máquina (racionalmente). A dimensão no eixo vertical trata da ação: pensar x agir.

Sistemas que pensam como humanos Sistemas que pensam racionalmente “The exciting new effort to make computers think ... machines with minds, in the full and literal sense” [Haugeland75]

“The study of mental faculties through the use of computational models” [Charniak85]

“[The automation of] activities that we associate with human thinking, activities such as decision-making, problem solving, learning, …” [Bellman78]

“The study of the computations that make it possible to perceive, reason, and act” [Winston92]

Sistemas que agem como humanos Sistemas que agem racionalmente “The art of creating machines that perform functions that require intelligence when performed by people” [Kurzweil90]

“A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes” [Schalkoff90]

“The study of how to make computers do things at which, at the moment, people are better” [Rich91]

“The branch of computer science that is concerned with the automation of intelligent behavior” [Luger93]

Figura 1 - Classificação de algumas definições de IA


2.2. Comparação entre IA e Computação Convencional

A Figura 2 apresenta as principais características que diferenciam um sistema de IA e um sistema construído de forma convencional.

IA Computação Convencional Não algorítmico Algorítmico

Processamento Simbólico Processamento Numérico Não Determinista Determinista Fácil Modificação Difícil Modificação

Estrutura Estrutura

Figura 2 - IA x Computação Convencional

2.3. Automação de Atividades

A Figura 3 mostra uma classificação das atividades que são executadas nas empresas e o tipo de automação que é utilizado em cada caso.

Figura 3 - Perfil das atividades em relação à mão-de-obra

Dados + Programas

Estrutura de Controle

Resultados

Dados

Programas

Resultados

Trabalhos pouco Estruturados

Trabalhos Estruturados

Trabalhos não Estruturados

COMPUTAÇÃO INTELIGENTE

COMPUTAÇÃO CONVENCIONAL


3. Resolução de Problemas

Neste capítulo serão estudadas duas abordagens que permitem resolver a maior parte dos problemas: • resolução utilizando Espaço de Estados; • resolução por Decomposição de Problemas.

A escolha da abordagem depende do problema, como será visto mais adiante. 3.1. Espaço de Estados

Nesta abordagem a modelagem do problema é elaborada conforme a Figura 4. Partindo-se de um estado inicial deseja-se chegar a um estado final utilizando-se um conjunto de operações de transformação de estados.

Figura 4 Representação do problema. 3.1.1. Representação do Problema em Espaço de Estados

Para facilitar a assimilação dos conceitos, a introdução ao assunto será feita através do mundo dos blocos. O mundo dos blocos proposto para estudo possui apenas três blocos (A, B e C) e uma mesa. Os blocos podem estar sobre a mesa ou empilhados. O problema é elaborar um plano para re-arranjar a disposição dos blocos de acordo com o desejado. Assim, um plano é uma seqüência de movimentos de blocos que, partindo de uma situação inicial, leva a uma situação desejada.

A Figura 5 apresenta um problema específico, onde estão definidas a situação inicial e a situação desejada. A definição do mundo estabelece uma classe de problema, pois é possível definir para o mesmo mundo novos problemas através da escolha de outras situações inicial e desejada.

Figura 5 Um problema de re-arranjo de blocos (baseado em [Bratko2001]).

Neste problema, a modelagem utilizando a abordagem Espaço de Estados é natural: a situação inicial dos blocos é o estado

inicial, a situação desejada é o estado final e a seqüência de movimentos é uma seqüência de operações válidas do conjunto de operações de transformação de estados. O conjunto de operações pode ser formado pelas operações apresentadas na Figura 6.

(1) coloque o bloco A sobre a mesa; (2) coloque o bloco A sobre o bloco B; (3) coloque o bloco A sobre o bloco C; (4) coloque o bloco B sobre a mesa; (5) coloque o bloco B sobre o bloco A; (6) coloque o bloco B sobre o bloco C; (7) coloque o bloco C sobre a mesa; (8) coloque o bloco C sobre o bloco A; (9) coloque o bloco C sobre o bloco B.

Figura 6 Um possível conjunto de operações para o problema da Figura 5.

Uma operação é válida quando ela respeita as restrições impostas na definição do problema. As restrições de movimentos no

problema proposto são bastante simples: é permitido mover apenas um bloco de cada vez, não pode haver outros blocos em cima do bloco a ser movimentado nem do bloco sobre o qual se quer colocar um bloco em cima. Por exemplo, para aplicar a operação (2) não poder haver blocos em cima do bloco A nem do bloco B. Desta forma, partindo da situação inicial do problema apresentado na Figura 5, existe apenas um movimento legal: coloque o bloco C sobre a mesa. Na nova situação, após o

Estado Inicial

Estado Final

Operações

seqüência de movimentos B

A C

B A

C

situação inicial situação desejada


movimento, existem três movimentos legais possíveis: coloque o bloco A sobre a mesa, coloque o bloco A sobre o bloco C ou coloque o bloco C sobre o bloco A.

Os estados do problema e as operações de transformação de estados formam um grafo dirigido chamado espaço de estados, onde os nodos são os estados e os arcos são as operações. Como o mundo dos blocos sobre o qual se está estudando possui um número limitado de elementos, então a classe de problemas e o espaço de estados são finitos, conforme a Figura 7.

Figura 7 Representação gráfica do espaço de estados para a classe de problemas em estudo (baseado em

[Bratko2001]). O problema apresentado na Figura 5 está em evidência: o estado inicial está com linha mais grossa, o estado final está com linha dupla concêntrica e uma solução possível é o caminho com setas maiores.

Encontrar uma solução equivale a achar um caminho no espaço de estados que, partindo do estado inicial, chega ao estado

final. A interpretação da solução no problema do mundo dos blocos é uma seqüência de movimentos de blocos, ou seja, um plano para re-arranjar a pilha de blocos de acordo com a definição do problema.

Resumindo, um problema pode ser descrito formalmente utilizando a abordagem Espaço de Estados pelos seguintes elementos:

1. especificação do espaço de estados; 2. definição de um ou mais estados neste espaço de estados que descreva situações de partida do processo de solução do

problema, são os estados iniciais de uma problema; 3. definição de um ou mais estados que poderiam ser aceitos como solução do problema, são os estados finais, metas ou

objetivos de um problema e servem para determinar quando se chegou a uma solução. Isto pode ser feito através de uma condição.

No item (1), o espaço de estados pode ser especificado de forma extensiva, contendo todas as possíveis configurações dos

objetos relevantes, conforme a Figura 7, entretanto, normalmente, isto é inviável. Assim, a forma usual é feita apenas através da definição do conjunto de operações de transformação de estados (regras do jogo) e o espaço de estados fica implícito.

Alguns pontos a serem considerados nesta atividade são: • Que hipóteses não declaradas explicitamente estão presentes na descrição não-formal do problema? • Quão geral devem ser as operações?

Por exemplo, no lugar das nove operações definidas para o problema da Figura 5 poderia-se definir apenas duas operações:

(1) coloque o bloco X sobre a mesa; (2) coloque o bloco X sobre o bloco Y.

• Quanto do trabalho necessário para resolver o problema deve ser pré-computado e representado nas operações? Por exemplo, as restrições podem estar representadas explicitamente nas operações:

(1) se X está no topo de uma pilha então coloque o bloco X sobre a mesa; (2) se X e Y estão no topo de pilhas coloque o bloco X sobre o bloco Y.

��

��

��

� � �

��

� � �

��

� ��

��

��

��

� ��

� � �


Em um outro exemplo, as restrições são implicitamente representadas nas operações, conforme a Figura 8.

Figura 8 Conjunto de operações onde as restrições estão implicitamente representadas. 3.1.2. Implementação da Representação do Problema em Espaço de Estados

A implementação da representação depende da linguagem. Em Prolog, no caso do problema da Figura 5, os estado podem ser representados como uma lista de pilhas. Se houver no máximo três pilhas e uma pilha for representada também como uma lista, sendo que o topo é primeiro elemento da lista, então a representação final dos estados é [[<bloco no topo>, <bloco abaixo do topo>, ... , <bloco na base>], [<bloco no topo>, <bloco abaixo do topo>, ... , <bloco na base>], [<bloco no topo>, <bloco abaixo do topo>, ... , <bloco na base>]]. Desta forma, o estado inicial do problema é representado como a lista [[c, a, b], [], []] e o estado final pode ser representado como a lista [[a, b, c], [], []] ou [[], [a, b, c], []] ou [[], [], [a, b, c]]. A cláusula abaixo é uma implementação para se identificar quando se atinge o objetivo.

objetivo(Estado) :- member([a, b, c], Estado).

O(s) estado(s) sucessor(es) de um estado qualquer pode(m) ser definido(s) pela cláusula sucessor(<estado atual>, <estado sucessor>). Com esta sintaxe, o conjunto de operações da Figura 8 pode ser implementado como apresentado na Figura 9.

sucessor([[a, b, c], [], []], [[b, c], [a], []]). sucessor([[a, b, c], [], []], [[b, c], [], [a]]). sucessor([[],[a, b, c], []], [[a], [b, c], []]). sucessor([[],[a, b, c], []], [[], [b, c], [a]]). . . .

Figura 9 Uma implementação do conjunto de operações Figura 8.

Entretanto, esta implementação não é muito adequada porque exige escrever todas as configurações possíveis de pilhas. Uma implementação mais econômica é apresentada abaixo:

sucessor(Estado, [Pilha1, [Topo1 | Pilha2] | OutrasPilhas]) :- remove([Topo1 | Pilha1], Estado, EstadoAux), remove(Pilha2, EstadoAux, OutrasPilhas). remove(Pilha, [Pilha | RestoEstado], RestoEstado). remove(Pilha, [Paux | RestoEstado], [Paux | Resto]) :- remove(Pilha, RestoEstado, Resto).

3.1.3. Métodos de Busca Cegos em Espaço de Estados A busca de uma solução é feita através da procura de um caminho no espaço de estados que leva do estado inicial para o

estado final. Os métodos cegos fazem uma pesquisa sistemática do espaço de estados, porém não utilizam nenhum conhecimento para guiar a busca. Os dois principais métodos cegos são a “busca em profundidade” e a “busca em extensão”.

A ação de percorrer o espaço de estados é feita de acordo com uma estratégia de controle que seleciona um estado e um operador que será aplicado ao estado para gerar os estados subseqüentes. A aplicação dos operadores nos estados iniciais e

�

�

�

� (1) Se estado atual é então o estado atual é alterado para

�



�


. . .

(30) Se estado atual é então o estado atual é alterado para �


intermediários é feita até que se chegue a um estado objetivo. Este processo, à medida que vai sendo executado, vai gerando a árvore de busca. Quando se encontra o estado final o processo é interrompido com sucesso. Dependendo do problema, a solução pode ser o próprio estado final ou o caminho entre o estado inicial e o estado final. A Figura 10 apresenta uma parte da árvore de busca para o problema da Figura 5.

Figura 10 Árvore de pesquisa para o problema da Figura 5, utilizando o conjunto de operações da Figura 6.

3.1.3.1. Busca em Profundidade A busca em profundidade explora um ramo da árvore de cada vez, ou seja, todos os nodos de um caminho da árvore são

examinados antes dos nodos dos outros caminhos. A estrutura de dados associada é uma pilha, pois deve visitar primeiro os nodos mais recentes, aqueles que estão mais distantes da raiz. É necessário armazenar apenas o caminho que está sendo explorado e os caminhos já explorados podem ser descartados. A exploração dos caminhos alternativos pode ser feita através do retrocesso. No algoritmo abaixo não está previsto nenhum mecanismo de retrocesso.

Algoritmo: 1. Se o estado inicial é um estado objetivo, pare e retorne sucesso. 2. Senão, faça o seguinte até o sucesso (ou insucesso):

a) Gere um sucessor "E" do estado inicial. Se não há mais sucessores, assinale insucesso.

b) Senão, chame BUSCA EM PROFUNDIDADE com E como estado inicial. c) Se sucesso então é retornado sucesso

Senão, continue o passo 2.

Abaixo é apresentada uma implementação em Prolog bastante simples e, portanto fácil de entender. A desvantagem desta implementação é que a mesma permite ciclos, o que pode conduzir a pesquisa a um ramo sem saídas.

pesquise(N, [N]) :- objetivo(N). pesquise(N, [N | Caminho]):-

sucessor(N, Naux), pesquise(Naux, Caminho).

A consulta em Prolog tem a sintaxe pesquise(<início>, <solução>). A solução <solução> é uma lista de estados, partindo

do estado <início> até um dos estados objetivos. Para o problema da Figura 5 a consulta é expressa como a seguir:

��

� �

��

� �

� �

��

� �

��

� �

� �

� �

� �

� �

� �

��

� �

� �

��

(7)

(1) (8) (3)


-? pesquise([c, a, b], [], []], Solução).

3.1.3.2. Busca em Profundidade Acíclica A implementação abaixo evita ciclos. Entretanto ainda podem existir na árvore de pesquisa ramos infinitos que não

contenham a solução. Esta situação é plausível em problemas cujo espaço de estados é infinito. pesquise(N, Solução) :- profundidade([], N, Solução). profundidade(Caminho, N, [N | Caminho]) :- objetivo(N). profundidade(Caminho, N, Solução) :- sucessor(N, Naux), not(member(Naux, Caminho)), profundidade([N | Caminho, Naux, Solução).

3.1.3.3. Busca em Extensão (Largura)

Todos os nodos de um nível da árvore são examinados antes dos nodos do nível seguinte. A estrutura de dados associada é uma fila, pois deve visitar primeiro os nodos mais antigos, ou seja, aqueles mais próximos da raiz.

Algoritmo: 1. Crie uma variável chamada "LISTA_DE_NODOS" e faça-a igual ao estado inicial. 2. Até que (um estado objetivo seja encontrado) ou (LISTA_DE_NODOS seja vazia) faça:

a) Remova o primeiro elemento de LISTA_DE_NODOS e o chame "E". Se LISTA_DE_NODOS estava vazia, fim.

b) Para cada maneira que cada regra combina com o estado descrito em E faça: i) Aplique a regra para gerar um novo estado. ii) Se o novo estado é um estado objetivo, pare e retorne este estado iii) Senão, adicione o novo estado ao final de LISTA_DE_NODOS.

Abaixo é apresentada uma implementação em Prolog. % solve( Start, Solution): % Solution is a path (in reverse order) from Start to a goal solve( Start, Solution) :- breadthfirst( [ [Start] ], Solution). % breadthfirst( [ Path1, Path2, ...], Solution): % Solution is an extension to a goal of one of paths breadthfirst( [ [Node | Path] | _], [Node | Path]) :- goal( Node). breadthfirst( [Path | Paths], Solution) :- extend( Path, NewPaths), append( Paths, NewPaths, Paths1), breadthfirst( Paths1, Solution). extend( [Node | Path], NewPaths) :- bagof( [NewNode, Node | Path], ( sucessor( Node, NewNode), not(member( NewNode, [Node | Path] )) ), NewPaths), !. extend( _, [] ). % Nodo não tem sucessores (bagof falhou!)

3.1.3.4. Comparação: Busca em Profundidade x Busca em Extensão

Busca em profundidade:


• Mesmo que haja uma solução, não há garantias de encontra-la, pois pode explorar um caminho infinito que não contém a solução.

• Por sorte, pode achar uma solução sem examinar muito o espaço de estado. • É adequada quando existe solução na maioria dos ramos. • Requer menos memória.

Busca em Extensão: • Se houver solução, garante a obtenção da solução de menor caminho. • Não corre o risco de examinar por longo tempo becos sem saída. • Não é muito adequada quando o fator de ramificação é muito alto, pois exige armazenar muitos caminhos alternativos. • Consome muita memória.

3.1.3.5. Outros Exemplos de Problemas e de Modelagem utilizando Espaço de Estados Exemplo 1: Torre de Hanói A representação gráfica do problema da Torre de Hanói é apresentada na Figura 11.

Figura 11 Torre de Hanói.

a) Estados Sintaxe: (Menor, Média, Maior)

Menor = Número do poste onde está a argola menor. Média = Número do poste onde está a argola média. Maior = Número do poste onde está a argola maior.

Assim os estado inicial e final podem ser representados como: Estado inicial : (1,1,1). Estado final : (3,3,3).

b) Operações

Sintaxe: move (poste de origem, poste de destino) move (1,2) move (1,3) move (2,1) move (2,3) move (3,1) move (3,2)

Nesse caso devemos sempre observar as restrições do problema e a validade das operações. A Figura 12 apresenta a árvore de pesquisa deste problema.

Figura 12 Árvore de pesquisa para o problema da Torre de Hanói. Exemplo 2: Jogo dos 8 A Figura 13 mostra a representação gráfica para o problema do jogo dos 8.

(1,1,1) move(1,3) move(1,2)

(2,1,1) move(2,3) move(1,3)

(3,1,1) move(3,2) move(1,2)

(2,3,1) (3,1,1) (3,2,1) (2,1,1)

1 2 3 1 2 3

Estado Inicial Estado Final


Figura 13 Representação do problema para o jogo dos 8.

É possível modelar as operações de diversas maneiras, mas a forma mais eficiente consiste em aplicar operações na casa vazia, o que possibilita que sejam necessárias apenas quatro operações:

(1) Mover a casa vazia para cima. (2) Mover a casa vazia para baixo. (3) Mover a casa vazia para esquerda. (4) Mover a casa vazia para direita.

Figura 14 Árvore de pesquisa para o jogo dos 8. Exemplo 3: Jogar Xadrez 1. Especificar a posição inicial do tabuleiro

Matriz 8x8, onde cada posição contendo um símbolo que representa a peça apropriada (ou indicação de casa vazia) na posição oficial de abertura do jogo.

2. Definir as operações que representam movimentos legais As operações também podem ser definidas como um conjunto de regras de produção da forma :

LADO.ESQ → LADO.DIR onde LADO.ESQ : Padrão a ser comparado antes de uma jogada. LADO.DIR : Descreve a mudança a ser feita.

Exemplo: Regra "move peão branco" peãobranco em posição (j, i) ∧ posição (j, i+1) está vazia ∧ posição (j, i+2) está vazia → move peão branco de posição (j, i) para posição (j, i+2).

3. Definir posições que representam vitória Qualquer posição do tabuleiro na qual o oponente não tenha um movimento legal, e seu rei esteja sendo atacado.

2

1

8

6

3

4

7 5

11 8

2

3

4

7 6 5

Estado Inicial Estado Objetivo

2 1

8 6

7

3

5 4

2 1

8 6

7

3

5 4

2 1

8

7 6

3

5 4

2 1

8 6

7 5

3

4

2

8 6

1 7

3

5 4

2 1

8

7 6

3

5 4

2

8 1

7 6

3

5 4

2 1

8 4

7 6

3

5

2 1

8 6

7 5

3

4

(1)

(1) (1) (3)

(4)

(1)

(3)

(4)

Operações


3.2. Resolução de Problemas como Busca por Redução de Problemas Na resolução de problemas utilizando como enfoque a busca por redução de problemas, a idéia utilizada é a da decomposição

de problemas em subproblemas com complexidade menor que a do problema original. A modelagem do problema é feita através da definição dos seguintes elementos:

• Descrição do problema inicial. • Conjunto de operações de transformação de problemas. • Conjunto de problemas primitivos (problemas que têm solução imediata, conhecida).

A solução é um conjunto de Problemas Primitivos encontrados a partir da aplicação das operações no problema inicial e nos subproblemas já gerados.

O espaço de busca é representado graficamente por um grafo E/OU. Neste grafo, os nodos contêm a descrição dos problemas (subproblemas) e os arcos indicam relações entre os problemas, isto é, como os problemas são decompostos. As folhas da árvore podem ser problemas primitivos ou nodos terminais (problemas insolúveis). Os nodos intermediários, sucessores de um determinado nodo, são do tipo OU, indicando que os nodos sucessores são problemas alternativos, ou do tipo E, indicando que os nodos sucessores são problemas conjuntivos.

A busca é a construção sistemática do grafo E/OU através da aplicação das operações que vão decompondo os problemas. Exemplo 1: Torre de Hanói A representação gráfica do problema da Torre de Hanói é apresentada na Figura 11. Representação do problema

Sintaxe: [<TAM. PILHA>,<PINO DE SAÍDA>,<PINO DE CHEGADA>] Problema inicial : [3,1,3]

Problema primitivo : mover uma pilha de tamanho 1.

Operação

Para diferentes pinos I, J e K, o problema de mover uma pilha de argolas de tamanho n>1 do pino I para o pino K pode ser substituído por 3 subproblemas:

• Mover uma pilha de tamanho n-1 de I para J. • Mover uma pilha de tamanho 1 de I para K. • Mover uma pilha de tamanho n-1 de J para K.

Grafo E/OU A Figura 15 apresenta o grafo E/OU que é o espaço de busca para problemas representados por Redução de Problemas.

Figura 15 - Grafo E/OU para o problema da Torre de Hanói. Solubilidade dos nodos Um nodo é solúvel se: • É um problema primitivo. • É um nodo "E" cujos sucessores são todos solúveis. • É um nodo "OU" onde pelo menos um dos sucessores é solúvel Um nodo é insolúvel se: • É um nodo terminal. • É um nodo "E" onde pelo menos um dos sucessores é insolúvel. • É um nodo "OU" cujos sucessores são todos insolúveis.

[3,1,3]

[2,1,2] [2,2,3] [1,1,3]

[1,1,3] [1,3,2] [1,1,2] [1,2,1] [1,1,3] [1,2,3]


A Figura 16 apresenta uma árvore E/OU e como é a feita a busca em profundidade de uma solução. Os nodos são numerados por ordem de visita, sendo que os nodos marcados com T são problemas terminais e os nodos marcados com P são problemas primitivos. A Figura 17 apresenta como é feita a busca em extensão.

Figura 16 Exemplo de busca em profundidade em uma árvore E/OU. A solução é o conjunto de problemas primitivos {P2, P5}.

Figura 17 Exemplo de busca em extensão em uma árvore E/OU. A solução é o conjunto de problemas primitivos {P1, P3}.

3.3. Métodos de Busca Heurística

Os métodos de busca vistos anteriormente fazem uma pesquisa sistemática do espaço de estados ou do espaço de problemas, porém não são adequados para muitos problemas reais devido à explosão combinatória.

Os métodos heurísticos(1) utilizam alguma forma de conhecimento para orientar a busca e evitar a explosão combinatória. Entretanto, a eficiência depende fortemente em como o conhecimento é explorado.

O conhecimento a ser utilizado pode ser inserido manualmente, ou através de aprendizado automático. (1) Heurística vem da palavra grega “heuriskein” que signific a descobir.

1

2 3

4 5 7

12 T 9

T

11

T

1

2

3 8 P1

P3

P5

T 5

P4 T

9

T P6

P2

P1

P3

P4 P5 P6

P2


Tipos de heurística no processo de busca a) Heurística genérica:

Diferentes aspectos gerais do problema são considerados e avaliados de modo que o valor resultante da função heurística seja uma boa estimativa de quão efetivo pode ser o estado para alcançar a solução. Os métodos que utilizam apenas heurísticas genéricas, úteis a muitos tipos de problemas, são denominados métodos fracos e não são capazes de evitar a explosão combinatória.

Freqüentemente, esta medida consiste em uma estimativa da distância da solução. Por exemplo, no Jogo dos 8 a heurística pode ser o número de peças que estão fora do lugar. b) Heurística específica:

Apresenta as convicções dos especialistas em uma determinada área. A maioria das regras dos Sistemas Especialistas pertence a essa classe. É extremamente eficiente se bem utilizada.

Função Heurística Nos métodos de busca, o conhecimento sobre o problema é utilizado para compor uma função heurística. Esta função heurística tem a forma f(Estado) e é aplicada aos estados para atribuir notas indicando a proximidade do estado em relação à solução. 3.3.1. Subida da encosta ("Hill-Climbing")

A idéia deste método é maximizar a nota fornecida pela função heurística. A busca é feita com a geração de um estado sucessor do estado corrente. Se o estado sucessor tiver uma nota melhor, então ele passa a ser o estado corrente.

Algoritmo: 1. Estado corrente ← estado inicial 2. Repita até que o estado corrente seja a solução ou não existam operadores a serem aplicados ao estado corrente

a) Escolha um operador que ainda não tenha sido aplicado ao estado corrente e aplique-o para produzir um novo estado. b) Avalie o novo estado.

i) Se for a solução (um estado meta) retorne-o e encerre. ii) Se for melhor que o estado corrente então Estado corrente ← novo estado.

Características: • Seleciona o primeiro vizinho que seja melhor. • Problema: tende a convergir para uma solução que é um máximo local e não para o máximo global. • É irrevogável (sem retrocesso).

Exemplo: Mundo dos Blocos

A Figura 18 apresenta o problema no qual será aplicado o método da subida da encosta.

Figura 18 Representação gráfica de um problema do Mundo dos Blocos

Os operadores são: (1) Pegue um bloco e coloque-o sobre a mesa (2) Pegue um bloco e coloque-o sobre outro

A função heurística que será utilizada faz o seguinte cálculo: some um ponto para cada bloco em cima do bloco em que ele deva esta e subtraia um ponto para cada bloco que estiver sobre o bloco errado.

Com esta heurística os estados inicial e final recebem as notas: f(estado inicial) = 1 e f(estado meta) = 5. A árvore de busca é apresentada na Figura 19.

B C D E A

B C D E

A

Estado Inicial Estado Meta


Figura 19 Árvore de busca para o problema da Figura 18 utilizando o método Subida da Encosta. A utilização desta função heurística, neste problema em particular, conduz a busca a um máximo local. Isto corresponde à

situação onde a vizinhança (sucessores) possui nota menor que o estado e não consegue encontrar uma solução. O motivo para este problema é que a heurística é local, não observando o contexto.

Uma função heurística melhor, que leve em conta o contexto global, pode ser implementada da seguinte forma: quando o bloco tem a estrutura de apoio correta, some um ponto para cada bloco da estrutura de apoio; para cada bloco com estrutura de apoio incorreta subtraia um ponto.

Esta nova função heurística permite que o processo de busca chegue a uma solução, como sugere a Figura 20. 3.3.2. Subida da encosta para a trilha mais íngreme ("Stepest-Hill-Climbing")

A idéia é a mesma do método anterior, porém examina toda a vizinhança e seleciona o melhor. Este método também é denominado busca do gradiente.

A heurística é aplicada localmente, ou seja, o caminho a ser seguido é selecionado apenas entre os nodos recém gerados, sendo a escolha baseada no resultado da aplicação da função heurística. A implementação pode ser feita ordenando-se o conjunto de nodos sucessores recém avaliados antes de incluí-los na pilha de nodos abertos. O campo de ordenação é a nota resultante da avaliação da função heurística, sendo que deve ficar no topo da pilha o nodo com a melhor nota, daqueles recém gerados.

Algoritmo: 1. Estado corrente ← Estado inicial. 2. Repita até que estado corrente seja a solução ou não haja mudança no estado corrente.

a) Sucessor ← pior absoluto b) Para cada operador aplicável ao estado corrente.

i) aplique o operador e gere um novo estado. ii) Avalie o novo estado.

Se for a solução retorne-o e encerre Se for melhor então sucessor ← novo estado

c) Se sucessor for melhor que estado corrente Então Estado corrente ← sucessor

Características:

B C D E A

f(e) = 1

B C D E

A

f(e) = 3

B C D

E A

f(e) = 1

B C D E A

f(e) = 1 B C D

E A

(1)

(1) (2)

(2)

Para a busca aqui

f(e) = 1


• Seleciona o melhor vizinho, desde que seja melhor que o estado corrente. • Problema: tende a convergir para uma solução que é um máximo local e não para o máximo global. • É irrevogável (sem retrocesso).

Figura 20 Árvore de busca para o problema da Figura 18 utilizando o método Subida da Encosta com uma função heurística mais adequada.

3.3.3. Busca pela melhor escolha ("Best-First")

A heurística é aplicada globalmente, isto é, o caminho a ser seguido é selecionado entre todos os nodos abertos até o momento. O nodo aberto com a melhor nota é escolhido para a expansão. Exemplo: Achar o Menor Trajeto

Definição do Problema: Procurar o menor trajeto, ou uma alternativa aceitável, entre a cidade a e a cidade z. Mapa:

Representação do Estado: Nome da cidade Representação do Espaço de Estados: O próprio mapa ou um grafo Estado Inicial: a Estado Final: z

a b

e c

z

d

5 3

2

3

4

1

6

início

fim

2

1

2 k

4

5

B C D E A

f(e) = -15

B C D E

A

f(e) = -9

B C D

E A

f(e) = -7 f(e) = -15 B C D

E A

(1)

(1) (2)

(2)

f(e) = -6

B C D E A


Operações: percorrer uma estrada até uma cidade vizinha Função Heurística (faz parte da modelagem do problema) f(x) = g(x) + h(x)

onde g(x) = distância percorrida da cidade a até a cidade x (somatório dos números próximos às estradas) h(x) = distância em linha reta da cidade x até a cidade z (números em negrito, próximos às cidades)

Problema: Achar o Menor Trajeto Exemplos de Aplicação da Função Heurística

f(b) = g(b) + h(b) = 1 + 6 = 7 f(c) = g(c) + h(c) = 3 + 2 = 5 f(e) = g(e) + h(e) = 5 + 1 = 6

Árvore de Busca: os números próximos aos nodos indicam a ordem de expansão dos mesmos.

A solução encontrada pode eventualmente não ser o menor trajeto, dependendo do problema, mas pode ser uma solução bastante aceitável.

Exemplo: Achar o Menor Trajeto

Representação em Prolog objetivo: goal(z).

sintaxe das operações: s( <nodo>, <nodo sucessor>, <custo>) onde <custo> é a distância entre as cidades

s(a,b,1). s(a,c,3). s(a,e,5). s(b,c,4). s(c,d,3). s(d,z,2). s(e,k,4).

a

b e c

z

d

f=7

c k

d

z

z

f=5 f=6

f=7 f=8

f=10

f=14

f=10

f=8 f=16

4

1

3 2

5

6


s(k,z,7). Funções heurísticas:

g(x) é calculado a partir de <custo> h(x) é definido como abaixo

h(b,6). h(c,2). h(d,2). h(e,1). h(k,5). h(z,0).

Consulta e resultado:

?- bestfirst(a, Sol), showsol(Sol). ---a ---c ---d ---z Sol = [z, d, c, a]

Representação do Jogo dos 8 Definição do Problema

Representação em Prolog Posições das peças: coordenadas cartesianas X/Y

Tabuleiro: Lista onde 1° elemento: casa vazia 2° elemento: peça 1 3° elemento: peça 2 . . . 9° elemento: peça 8 A cláusula showsol apresenta a solução como uma seqüência de posições do tabuleiro.

?- bestfirst([2/2,1/3,3/2,2/3,3/3,3/1,2/1,1/1,1/2], Solução), showsol(Solução).

1 3 4

8 2

7 6 5

1 2 3

8 4

7 6 5

3 1 2 3 O estado inicial é representado como: 2 8 4 [2/2, 1/3, 3/2, 2/3, 3/3, 3/1, 2/1, 1/1, 1/2] 1 7 6 5 1 2 3

3 1 2 3 O estado final é representado como: 2 8 4 [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2] 1 7 6 5 1 2 3


Implementação: A implementação em Prolog é apresentada abaixo e é baseada no algoritmo A*. Principal Predicado: expand( Path, Tree, Bound, Tree1, Solved, Solution)

Parâmetros: Path: caminho entre o nodo inicial e a sub-árvore Tree Tree: sub-árvore corrente, que está sendo vizitada Bound: limite para a expansão de Tree (f-value da próxima melhor alternativa) Tree1: árvore expandida dentro do limite (bound) Solved: yes - Solution é instanciado

no - Tree1 = Tree expandida, mas f-value > limite never - indica que Tree é ramo sem saída

Solution: caminho entre o nodo inicial e o estado final

Cláusulas:

Caso 1: o nodo a ser expandido é um nodo final �Conclui a busca

Caso 2: o nodo é folha e f-value < limite (bound) �

Gera sucessores e os expande enquanto não atinge o limite Caso 3: o nodo não é folha e f-value < limite �

Percorre a árvore até chegar ao nodo folha c/ f-value < limite Caso 4: o nodo não é folha e não possui sub-árvores �

Não deve ser expandido, pois é um ramo sem saída Caso 5: o nodo com f-value > limite �

Não deve ser expandido, pois há opções mais interessantes

Representação da Árvore Nodos em Aberto (folhas):

l( <estado> , <f(<estado>)>/<g(<estado>) )

Nodos Internos ((sub-)árvores) t( <estado> , <f(<estado>)>/<g(<estado>), <lista de sub-árvores> )

bestfirst(Start, Solution):- expand([], l(Start, 0/0), 9999, _, yes, Solution). % Assume que 9999 é maior que qualquer f-value % expand( Path, Tree, Bound, Treel, Solved, Solution): Path is path between start node of search and subtree Tree, % Treel is Tree expanded within Bound, if goal found then Solution is solution path and Solved = yes % Case 1: goal leaf-node, construct a solution path

expand(P, l(N, _), _, _, yes, [N | P]):- goal(N).

% Case 2: leaf-node, f-value less than Bound - Generate successors and expand them within Bound


expand(P, l(N, F/G), Bound, Tree1, Solved, Sol) :- F =< Bound, (bagof(M/C, (s(N, M, C), not(member(M, P))), Succ), !, % Node N has successors succlist(G, Succ, Ts), % Make subtrees Ts bestf(Ts, F1), % f-value of best successor expand(P, t(N, F1/G, Ts), Bound, Tree1, Solved, Sol) ; Solved = never % N has no successors - dead end ).

% Case 3: non-leaf, f-value less than Bound % Expand the most promising subtree; depending on results, procedure continue will decide how to proceed

expand(P, t(N, F/G, [T | Ts]), Bound, Tree1, Solved, Sol):- F =< Bound, bestf(Ts, BF), min(Bound, BF, Bound1), expand([N | P], T, Bound1, T1, Solved1, Sol), continue(P, t(N, F/G, [T1 | Ts]), Bound, Tree1, Solved1, Solved, Sol).

% Case 4: non-Leaf with empty subtrees - This is a dead end which will never be solved

expand( _, t(_, _, []), _, _, never, _):- !. % Case 5: value greater than Bound - Tree may not grow

expand( _, Tree, Bound, Tree, no, _):- f(Tree, F), F> Bound.

% continue(Path, Tree, Bound, NewTree, SubtreeSolved, TreeSolved, Solution)

continue( _, _, _, _, yes, yes, Sol). continue(P, t(N, F/G, [T1 | Ts]), Bound, Tree1, no, Solved, Sol):- insert(T1, Ts, NTs), bestf(NTs, F1), expand(P, t(N, F1/G, NTs), Bound, Tree1, Solved, Sol). continue(P, t(N, F/G, [_ | Ts]), Bound, Tree1, never, Solved, Sol):- bestf(Ts, F1), expand(P, t(N, F1/G, Ts), Bound, Tree1, Solved, Sol).

% succlist(G0, [Nodel/Cost1, ...], [l(BestNode. BestF/G), ...]): make list of search leaves ordered by their f-values

succlist(_,[],[]). succlist(G0, [N/C | NCs], Ts):- G is G0 + C, h(N, H), % Heuristic term h(N) F is G + H, succlist(G0, NCs, Ts1), insert(l(N, F/G), Ts1, Ts).

% Insert T into list of trees Ts preserving order with respect to f-values

insert(T,Ts,[T|Ts]):- f(T, F), bestf(Ts, F1), F =< F1,!. insert(T, [T1 | Ts], [T1 | Ts1]):- insert(T, Ts, Ts1).


% Extract f-value

f(l(_,F/_), F). % f-value of a leaf f(t(_,F/_,_), F). % f-value of a tree bestf([T|_],F):- % Best f-value of a list of trees f(T, F). bestf([], 9999). % No trees: bad f-value min(X,Y,X):- X =< Y,!. min(X, Y, Y).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Procedimentos específicos para o jogo dos 8 % s( Node, SuccessorNode, Cost)

s([Empty | Tiles], [Tile | Tiles1], 1):- % All arc costs are 1 swap(Empty, Tile, Tiles, Tiles1). % Swap Empty and Tile in Tiles swap(Empty, Tile, [Tile | Ts], [Empty | Ts]):- mandist(Empty, Tile, 1). % Manhattan distance = 1 swap(Empty, Tile, [T1 | Ts], [T1 | Ts1]):- swap(Empty, Tile, Ts, Ts1). mandist(X/Y, X1/Y1, D):- % D is Manh. dist. between two squares dif(X, X1, Dx), dif(Y, Y1, Dy), D is Dx + Dy. dif(A,B,D):- % D is |A-B| D is A-B, D >= 0,! ; D is B-A.

% Heuristic estimate h is the sum of distances of each tile from its 'home' square plus 3 times 'sequence' score

h([Empty | Tiles], H):- goal([Empty1 | GoalSquares]), totdist( Tiles, GoalSquares, D), % Total distance from home squares seq(Tiles, S), % Sequence score H is D + 3*S. totdist([], [], 0). totdist([Tile | Tiles], [Square | Squares], D):- mandist(Tile, Square, D1), totdist(Tiles, Squares, D2), D is D1 + D2.

% seq(TilePositions, Score): sequence score

seq([First | OtherTiles], S):- seq([First | OtherTiles], First, S).


seq([Tilel, Tile2 | Tiles], First, S):- score(Tilel, Tile2, S1), seq( [Tile2 | Tiles], First, S2), S is S1 + S2. seq([Last], First, S):- score(Last, First, S). score(2/2, _, 1). % Tile in centre scores 1 score(1/3, 2/3, 0):- !. % Proper successor scores 0 score(2/3, 3/3, 0):- !. score(3/3, 3/2, 0):- !. score(3/2, 3/1, 0):- !. score(3/1, 2/1, 0):- !. score(2/1, 1/1, 0):- !. score(1/1, 1/2, 0):- !. score(1/2, 1/3, 0):- !.

score(_, _, 2). % Tiles out of sequence score 2 goal([2/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,1/2]). % Goal squares for tiles

% Display a solution path as a list of board positions

showsol([]). showsol([P | L]):- showsol(L), nl, write('---'), showpos(P).

% Display a board position

showpos([S0,S1,S2,S3,S4,S5,S6,S7,S8]):- member(Y, [3,2,1]), % Order of Y-coordinates nl, member(X, [1,2,3]), % Order of X-coordinates member(Tile-X/Y, % Tile on square X/Y [0-S0,1-S1,2-S2,3-S3,4-S4,5-S5,6-S6,7-S7,8-S8]), write(Tile), fail % Backtrack to next square ; true. % All squares done

3.3.4. Têmpera Simulada ("Simulated Annealing")

Método de busca inspirado no processo de temperar metais: inicia com uma temperatura elevada, permitindo transições de alto nível de energia, depois, gradualmente, a temperatura é resfriada até alcançar um estado sólido, onde apenas transições de baixo nível de energia são permitidas. O objetivo é alcançar uma estrutura molecular com um mínimo de energia.

Neste processo, as substâncias físicas tendem a acomodar-se em configurações de baixa energia, mas sempre existe uma certa probabilidade de ocorrer uma transição para um estado de maior energia, calculada pela fórmula: p = e(-∆E/kT) onde,

∆E = |E' - E2| = mudança positiva de energia; k = constante de Boltzmann, escreve a relação entre as unidades de energia e

temperatura; T = temperatura.


No processo de resolução de problemas, os valores energia e temperatura não têm o mesmo sentido que na física, assim k deixa de ser necessário e o cálculo da probabilidade fica: p = e(-∆E/T). A diferença de energia é medida pela diferença da aplicação da função-objetivo (função heurística) no estado corrente e no novo estado.

A mudança de temperatura no decorrer do processo chama-se "cronograma de têmpera" e tem três componentes: 1. Valor inicial 2. Critério(s) para decidir quando a temperatura deve ser reduzida. 3. Valor da redução (quanto)

A maneira como a temperatura diminui influencia no resultado do processo, se T esfriar muito rápido, provavelmente será encontrado um mínimo local e não global, se T esfriar muito lentamente haverá muita perda de tempo.

Figura 21 Analogia: dispositivo onde uma esfera fica encerrada em uma caixa com vidro na face da frente e

na face de trás e um elemento sólido formando uma curva. Quando o dispositivo fica na vertical a esfera tende a acomodar-se ao fundo de um vale. Uma temperatura alta equivale a agitar o dispositivo, permitindo que a esfera suba colinas.

Algoritmo: 1. Estado Corrente ← Estado Inicial. 2. Melhor ← Estado Corrente 3. T ← cronograma (inicio) 4. Repita até que Estado Corrente seja a solução ou não haja mudança no Estado Corrente.

a) Escolha um operador que ainda não tenha sido aplicado ao Estado Corrente e aplique-o para produzir um Novo Estado b) Analise o Novo Estado

i) Se for a solução (um estado meta) retorne-o e encerre. ii) Se for melhor que Estado Corrente

então faça Estado Corrente ← Novo Estado Se Novo Estado for melhor que Melhor então Melhor ← Novo Estado

senão faça ∆E ← f(Estado Corrente) – f(Novo Estado) p ← e(-∆E/T) Se p é maior que número aleatório no intervalo [0; 1] então Estado Corrente ← Novo Estado

c) T ← cronograma 5. Retorne Melhor como resposta do problema.

3.3.5. Computação Evolucionista É um conjunto de técnicas de otimização inspiradas na teoria da evolução. A principal idéia da teoria da evolução é a seleção natural, onde uma população de indivíduos evolui durante gerações devido à maior probabilidade daqueles mais aptos terem uma prole mais numerosa, resultando em indivíduos cada vez melhores. As técnicas estabelecem uma analogia onde um indivíduo é visto como sendo um candidato à solução de um problema, assim uma população de soluções é melhorada durante um certo número de gerações até chegar a uma solução ótima ou que um outro critério de parada seja satisfeito. A população evolui porque as melhores soluções (indivíduos mais aptos) de uma geração têm uma chance maior de serem selecionados para


contribuir para a próxima geração. A forma mais utilizada para a seleção dos indivíduos é baseada na probabilidade: a chance de um indivíduo ser selecionado é proporcional à sua aptidão. Esta abordagem remonta o início da computação, entre os anos 50 e 60, quando vários cientistas da computação estudaram sistemas evolucionários com a idéia de que a evolução poderia ser usada como um ferramenta de otimização para problemas na engenharia, entretanto o interesse na sua utilização cresceu muito nos meados da década de 80. As principais técnicas que foram desenvolvidas são: programação evolucionista, estratégia evolucionista, sistemas classificadores, algoritmos genéticos e programação genética. A técnica mais conhecida são os algoritmos genéticos, inventados por John Holland nos anos 60 e desenvolvidos por ele e seus alunos na Universidade de Michigan em meados de 1970. A seguir está técnica é vista com mais detalhes. Algoritmos Genéticos (AGs) Nesta técnica a analogia com os sistemas biológicos é mais forte, pois, além de ser baseado nos mecanismos de seleção natural, também se baseia na genética. Cada hipótese de solução (indivíduo) é representada por uma cadeia binária de tamanho fixo, como se fosse a cadeia genética do indivíduo. A criação dos indivíduos para a próxima geração é feita através de operações como cruzamento entre indivíduos, mutação e clonagem (ver anotações de aula). Algoritmo algoritmo_genetico( TamPop)

1. Pop � �� "!$#&%(')%('+*,%�-.�0/1�('2�(34%0�5#&��-6�4��7%�8,#&%

2. Avalie Pop (população inicial): para cada hipótese H pertencente a Pop, calcule a sua aptidão f(H)

3. Evolua a população Pop uma geração (faça até que satisfaça alguma condição de término)

3.1. Crie a nova população NovaPop (faça até gerar completamente a nova população)

3.1.1. Escolha um operador genético

3.1.2. Selecione hipóteses (a quantidade depende do operador a ser aplicado) probabilidade de que uma hipótese H seja selecionada: 3.1.3. Aplique o operador genético sobre a(s) hipótese(s) selecionada(s) gerando nova(s) hipótese(s): Hnova 9 :�;"<�=.>0?1:�=.@BADC 3.1.4. Adicione a(s) hipótese(s) resultante(s) na nova população: NovaPop E FHGJI"K�L�G�MONQP nova

3.2. Atualize a população: Pop R FHGJI"K�L�G�M

3.3. Avalie Pop: para cada hipótese H pertencente a Pop, calcule a sua aptidão f(H)

4. Retorne como resultado a hipótese com a maior aptidão de todas as gerações.

( ) ( )( )∑

∈

=

PopH

ii Hf

HfHp


4. Sistemas Baseados em Conhecimento

A evolução da pesquisa em resolução de problemas pode ser dividida em três fases distintas. Durante a primeira fase procurava-se imitar a capacidade do homem de resolver problemas, ou seja, buscava-se compreender e reproduzir a capacidade de raciocínio e de representação de problemas do homem. Um exemplo de sistema que foi desenvolvido nesta fase é o GPS (General Problem Solver). O grande problema desta abordagem é a explosão combinatória quando se tenta resolver problemas mais complexos.

A segunda fase surgiu a partir do reconhecimento de que a habilidade dedutiva do homem resulta menos de sua capacidade de raciocínio do que de sua habilidade de armazenar experiências anteriores e adaptá-las a novas situações. Nesta fase passou-se a utilizar os sistemas de produção e surgiram os sistemas baseados em conhecimento (cognitivos). Nos sistemas baseados em conhecimento a ênfase deixa de ser o método de busca e a forma de representar o conhecimento passa a ter um papel fundamental.

A terceira fase iniciou-se a partir da percepção de que o conhecimento geral é muito extenso e pouco útil para problemas específicos. Para permitir que os problemas sejam tratáveis em tempo hábil surgem os sistemas especialistas. Quanto maior a quantidade e a qualidade de conhecimento específico (relativo ao problema) embutido nestes sistemas, melhor a performance do sistema.

Figura 22 - Modelagem da realidade

Conforme está esquematizado na Figura 22, uma parte da realidade, correspondendo a um problema, pode ser modelada utilizando-se uma forma (linguagem) de representação do conhecimento e a seguir pode-se inferir “novos” fatos que podem conter a solução para o problema modelado. Os possíveis tipos de inferência que podem ser efetuados dependem da forma de representação do conhecimento. 4.1. Propriedades de Sistemas de Representação do Conhecimento

S Adequação Representacional - Permite representar todos os tipos de conhecimento necessários ao domínio do problema que se quer solucionar.

S Adequação Inferencial - Permite manipular estruturas representacionais gerando “novos” conhecimentos, dentre os quais, possíveis soluções.

S Eficácia Inferencial - Permite representar meta-conhecimento visando melhorar os mecanismos de inferência. S Eficácia de Comunicação - Permite facilmente entender o conhecimento armazenado, adquirir novos conhecimentos e

fornecer “explicações”. 4.2. Formas de Representação do Conhecimento S Sistemas de Produção S Sistemas Baseados em Regras

Modelagem

REALIDADE

FATOS’ FATOS’’

Representação do Conhecimento

Inferência Fatos

Solução


T Lógica - Convencional - Não-monotônica - Difusa ou nebulosa (“fuzzy”) - Temporal - Senso-comum

... T Raciocínio Probabilístico T Árvores de Decisão T Redes Semânticas T Quadros (“frames”) T Roteiros (“scripts”)

4.3. Sistemas de Produção (SP) SP foram inicialmente propostos por Post em 1943 para modelar o processamento da informação a partir da noção

estímulo/resposta, simulando os processos mentais de raciocínio e utilização do conhecimento. Desde então SP tiveram um grande desenvolvimento e atualmente é um formalismo que descreve um grupo de sistemas baseados em pares condição-ação denominados regras de produção.

Figura 23 - Arquitetura básica de um SP

A Figura 23 apresenta a arquitetura de um SP com os seus principais componentes: T Base de Dados: também chamado, memória de trabalho ou contexto, contém dados informados pelo usuário sobre o

problema ou gerados pelas próprias regras durante a execução (estado). T Regras de Produção: conjunto de regras que operam sobre a base de dados, modificando-a. T Estratégia de Controle: também denominado, interpretador de regras, é o módulo responsável pela execução do sistema

e pela identificação da solução sinalizando quando o sistema deve parar. Este processo possui 3 fases:

1) casamento (“matching”) – seleciona as regras aplicáveis comparando as condições (lado esquerdo) das regras com o estado da Base de Dados, as regras que casarem são selecionadas;

2) resolução de conflitos – apenas uma regra de cada vez pode ser ativada e quando mais de uma regra é aplicável, ocorre um conflito, sendo que a forma mais óbvia de se resolver um conflito é ativar a primeira regra que foi satisfeita;

3) ação – ativa as regras executando as ações (lado direito) das mesmas, o que normalmente altera o Banco de Dados.

Características de SP

T Monotônico – a aplicação de uma determinada regra nunca impede a posterior aplicação de outra regra que também poderia ter sido aplicada quando a primeira regra foi selecionada;

Estratégia de Controle

Base de

Dados

Regras de Produção

Condição Ação Condição Ação º º º º º º

Condição Ação


U Parcialmente Comutativo – se a aplicação de uma seqüência particular de regras transforma o estado x no estado y, então qualquer permutação dessas regras que seja viável também transforma o estado x no estado y;

U Comutativo - é um sistema que é monotônico e parcialmente comutativo.

Exemplo 1: SP para representar um numero inteiro (x VXW"Y,Z\[�]_^1`1]7[�a.bca.b�]7d�^"b�e Base de Dados: variável x armazenando inicialmente o valor a ser convertido; o resultado será impresso. Estratégia de Controle: f testar as condições das regras em ordem arbitrária até que uma seja satisfeita; f executar a ação correspondente; f repetir indefinidamente. Regras de Produção:

1) (x = 0) g hji(k5l�mon)p0qsrct�n6t"u�v6m4r$wxpyh{z4p(m4k0hB|}wjw 2) (x > 39) ~ �j�(�5��o�)�0�s�$�"��&��.��"�1�� 3) (10 ≤ x ≤ 39) � �{� ��1�6� �7�s�� ¡x¢s�B£¥¤ ¦§£ – 10) 4) (x = 9) ¨ ©{ª «�¬16ª «7®y¯0°&±�²�³ 5) (5 ≤ x ≤ 8) ´ µ{¶ ·�¸1¹6¶ ·7ºs»�¼�½�¾x¿yµBÀÂÁ Ã§À – 5) 6) (x = 4) ÄÅµ{¶ ·�¸1¹6¶ ·7ºy»0Æ&¼�½�¾ 7) (1 ≤ x ≤ 3) ÄÅµ{¶ ·�¸1¹6¶ ·7ºs»�Æ{½�¾\¿sµBÀÂÁ ÃXÀ – 1)

Exemplo 2: SP para solucionar o problema das jarras.

O objetivo deste problema é, tendo-se duas jarras, uma com capacidade de 3 litros e a outra de 4 litros, chegar-se a um volume de dois litros na jarra de 3 litros. Pode-se colocar ou retirar água das jarras, porém os únicos volumes conhecidos são os das capacidades das jarras. Base de Dados: Par de valores (x, y), onde o primeiro elemento representa o volume de água contido na jarra de 4 litros e o segundo elemento representa o volume de água contido na jarra de 3 litros. Assim, o estado inicial (as duas jarras vazias) é representado como (0, 0) e o estado final como (x, 2). Regras de Produção:

1) (x, y) | x < 4 Ä ÇÉÈ"ÊJË,Ì 2) (x, y) | y < 3 Í ÎBÏÑÐ,Ò,Ó 3) (x, y) | x > 0 Ô ÎBÏ -d, y) 4) (x, y) | y > 0 Ô ÎBÏÑÐJÕ -d) 5) (x, y) | x > 0 Ô Î{Ö1ÐJÕ,Ó 6) (x, y) | y > 0 Ô ÎBÏÑÐ1Ö$Ó 7) (x, y) | x+y >= 4 e y > 0 Ô ÎÉ×"ÐJÕ -(4-x)) 8) (x, y) | x+y >= 3 e x > 0 Ô ÎBÏ -(3-y), 3) 9) (x, y) | x+y <= 4 e y > 0 Ô ÎBÏ}ØÑÕ}Ð1Ö$Ó 10) (x, y) | x+y <= 3 e x > 0 Ô Î{Ö1Ð$Ï}ØÑÕ,Ó 11) (0, 2) Ô ÙÉÚ�Û1Ü$Ý 12) (2, y) Þ Ù{Ü1Û�ß$Ý

º º º

Deve ser definido um número mínimo de regras que modele adequadamente o problema, permitindo que se chegue à solução. Além disso, é desejável inserir regras adicionais, mais especializadas, que representem “atalhos” na procura da solução.


4.4. Sistemas Baseados em Regras Os sistemas baseados em regras surgiram a partir dos Sistemas de Produção e evoluíram utilizando resultados das pesquisas

em lógica. As regras têm a forma geral se <condições> então <conclusões> e os mecanismos de inferência utilizados para gerarem novos fatos são baseados na lógica.

A maior aplicação dos sistemas baseados em regras são os Sistemas Especialistas (SE). Evidentemente os SE podem utilizar qualquer uma das formas de representação do conhecimento citadas anteriormente, porém a grande maioria deles utiliza regras. Isto acontece porque a maioria do conhecimento utilizado em problemas de IA é diretamente representável em expressões gerais de implicação, além de serem facilmente compreensíveis pelos usuários.

No capítulo 6 os sistemas baseados em regras são aprofundados através do estudo dos SE, pois estes últimos representam um dos maiores marcos comercias na exploração da Inteligência Artificial.


5. Lógica

à Procura modelar formalmente o raciocínio humano. à Possui sintaxe e semântica bem definidas. à Esquema geral de funcionamento:

É estabelecida uma teoria (conjunto de axiomas) e procura-se provar se um determinado teorema é consistente com a teoria. A teoria pode ser vista como um conjunto de declarações que modela um problema e o teorema como uma afirmação que deve ser provada em relação à teoria. Do ponto de vista de um sistema baseado em conhecimento, a teoria é uma base de conhecimento e o teorema uma consulta.

à Existem vários métodos para se provar um teorema, porém em um sistema computacional a maneira clássica é feita por refutação:

− Nega-se o teorema; − Acrescenta-se à teoria; − Procura-se uma contradição.

Uma contradição, conforme mostra a Figura 24, é a afirmação e a negação do mesmo fato.

Figura 24 - Esquema de prova por refutação, gerando uma contradição.

5.1. Breve Histórico A lógica foi intoduzida no século III AC por Aristóteles para representar os processos do raciocínio, com enfoque em

filosofia. No século XIX houve importantes avanços com o desenvolvimento da álgebra booleana (Boole, De Morgan e outros), associando a lógica à matemática.

A programação em lógica surgiu no início da década de 70 como resultado direto de pesquisas nas áreas de prova automática de teoremas e de inteligência artificial. Após os trabalhos de Herbrand em 1930, houve muitas pesquisas em prova de teoremas no início da década de 60 com os trabalhos de Prawitz, Gilmore, Davis, Putnam e outros. Este esforço culminou, em 1965, no trabalho de Robson, introduzindo a regra de resolução, uma regra de inferência particularmente adequada para a automação em computadores. Pelo lado da inteligência artificial, a linguagem PLANNER, desenvolvida por Hewitt em 1972, para fazer planejamento em robótica, pode ser considerada a linguagem precursora da programação em lógica.

Os pesquisadores que desenvolveram no início da década de 70 a idéia de utilizar a lógica como linguagem de programação foram Kowalski na Universidade de Edinburgo (lado teórico), van Emden em Edinburgo (demonstração experimental), Roussel e Colmerauer em Marselha (implementação).

Pesquisas recentes envolvem a implementação de “const raint logic programming” (CLP), programação em lógica com facilidades para processamento de restrições.

5.2. Lógica Proposicional

A lógica proposicional é baseada em proposições, ou seja, declarações que podem ser verdadeiras ou falsas. Sintaxe

a) Proposição simples (átomo)

i) Constantes : “Está chovendo.” → chove. “João é homem.” → joão_homem. “João é filho de Maria.” → joão_filho_maria.

ii) Variáveis : P, Q, R, ... (maiúsculas)

Teoria +

¬¬ Teorema

Contém ou

Pode gerar

Fato. ¬¬ Fato.


b) Proposição composta (fórmula bem formada, expressão)

i) Elementos :

− Conectivos (em ordem de prioridade): ¬ ∧ ∨ → ↔

− Parênteses.

ii) Fórmula bem formada (FBF) :

(1) Um átomo é uma FBF.

(2) Se P é uma FBF, então ¬P é uma FBF.

(3) Se P e Q são FBF, então P ∧ Q, P ∨ Q, P → Q, P ↔ Q são FBF.

Semântica A semântica de uma FBF é estabelecida através da definição da função ωω : proposição →→ {v, f}, como segue :

(1) ω(¬P) = v se ω(P) = f; ω(¬P) = f se ω(P) = v.

(2) ω(P∧Q) = v se ω(P) = v e ω(Q) = v; caso contrário ω(P∧Q) = f.

(3) ω(P∨Q) = f se ω(P) = f e ω(Q) = f; caso contrário ω(P∨Q) = v.

(4) ω(P→Q) = f se ω(P) = v e ω(Q) = f; caso contrário ω(P→Q) = v.

(5) ω(P↔Q) = v se ω(P) = ω(Q); caso contrário ω(P↔Q) = f.

Em uma FBF contendo n átomos diferentes, existem 2n interpretações, isto é, maneiras possíveis de associar valores verdade aos átomos na fórmula. Definições

Tabela Verdade: enumeração de todas as interpretações e correspondentes avaliações para uma FBF.

Fórmula Válida ou Tautologia: fórmula verdadeira para todas as interpretações possíveis.

Fórmula Inconsistente (insatisfatível): fórmula falsa para todas as interpretações possíveis; também chamada contradição.

Fórmula Consistente (satisfatível): aquela que não é inconsistente.

Modelo: uma interpretação em que ω(fórmula) = v.

Contra-exemplo: uma interpretação em que ω(fórmula) = f.

Equivalência: duas fórmulas F e G são chamadas equivalentes, F≡G, se ω(F) = ω(G) para todas as interpretações.

Leis de Equivalência

Negação Dupla: ¬(¬F) ≡ F

Comutativas: F∨G ≡ G∨F F∧G ≡ G∧F

Associativas: (F∧G)∧H ≡ F∧(G∧H) (F∨G)∨H ≡ F∨(G∨H)

Distributivas: F∨(G∧H) ≡ (F∨G)∧(F∨H) F∧(G∨H) ≡ (F∧G)∨(F∧H)


Morgan: ¬(F∧G) ≡ ¬F ∨ ¬G ¬(F∨G) ≡ ¬F ∧ ¬G

Outras: F→G ≡ ¬F ∨ G F↔G ≡ (F→G) ∧ (G→F) Conseqüência Lógica Uma formula G é uma conseqüência lógica de um conjunto de fórmulas F = {F1, F2,..., Fn}, n ≥1, denotada por F áãâ G, se para cada interpretação ω, para o qual ω(F1∧F2∧ ... ∧ Fn) = v, temos ω(G) = v.

F ≡ G equivale a F äæå G e G äæå F. Exemplo

ç Teoria (conjunto de axiomas ou Base de Conhecimento): (1) garganta_inflamada. (2) ¬ garganta_inflamada ∨ ¬resfriado ∨ gripe. (3) ¬doi_corpo ∨ resfriado. (4) ¬coriza ∨ resfriado. (5) coriza.

ç Teorema (consulta): gripe.

ç Prova por refutação:

èêé Teoria + negação do teorema: (1) garganta_inflamada. (2) ¬ garganta_inflamada ∨ ¬resfriado ∨ gripe. (3) ¬doi_corpo ∨ resfriado. (4) ¬coriza ∨ resfriado. (5) coriza. (6) ¬gripe.

ë�ì Tentativa de encontrar uma contradição:

(2) ¬ garganta_inflamada ∨ ¬resfriado ∨ gripe (6) ¬gripe

¬ garganta_inflamada ∨ ¬resfriado (1) garganta_inflamada

(4) ¬coriza ∨ resfriado ¬resfriado

¬coriza (5) coriza � (cláusula vazia: contradição) Observações:

− Explicação do primeiro passo da procura por uma contradição: a proposição (2) precisa ser verdadeira, como os seus elementos estão unidos por “ ∨”, então basta que apenas um deles seja verdadeiro: ¬garganta_inflamada, ¬resfriado


ou gripe. Conforme a proposição (6), ¬gripe está valendo, assim ¬garganta_inflamada ou ¬resfriado deve ser verdadeiro.

− A teoria original é: (1) garganta_inflamada. (2) (garganta_inflamada ∧ resfriado) → gripe. (3) (doi_corpo ∨ coriza) → resfriado. (4) coriza.

entretanto, a manipulação para procurar uma contradição fica mais fácil se todas as proposições tiverem apenas os conectores ¬ e ∨. Assim, a base de conhecimento foi alterada utilizando-se as leis de equivalência.

Resolução (simplificada para a lógica proposicional)

A resolução é uma regra de inferência que prova se uma proposição P (teorema) é verdadeira em relação a um conjunto de axiomas T (teoria). Abaixo são apresentadas algumas definições preliminares e o algoritmo da resolução.

Literal: é um átomo ou a negação de um átomo.

Cláusula: é uma FBF na forma L1 ∨ L2 ∨... ∨ Ln.

Cláusula vazia: representada pelo símbolo �, a indica a presença de uma contradição.

Algoritmo da Resolução:

1. Converta todas as proposições de T para a forma clausal.

2. Negue P e converta o resultado para a forma clausal. Acrescente-o ao conjunto de cláusulas obtido na etapa 1.

3. Repita os passos abaixo até que uma contradição (cláusula vazia) seja encontrada ou até que nenhum progresso a mais possa ser feito.

a. Selecione duas cláusulas. Chame-as de cláusulas-pai.

b. Resolva as duas juntas: a cláusula resultante, chamada resolvente, será a disjunção de todos os literais de ambas cláusulas-pai com exceção dos literais redundantes e dos literais complementares (L e ¬L).

c. Se o resolvente for a cláusula vazia, então foi encontrada uma contradição. Caso contrário, acrescente-o ao conjunto de cláusulas disponíveis.

Algoritmo de transformação de uma FBF para a forma clausal:

1. Elimine as implicações. Para isto utilize as leis de equivalência: F↔G ≡ (F→G) ∧ (G→F) e F→G ≡ ¬F ∨ G

2. Reduza o escopo dos operadores de negação, de modo que cada ¬ esteja restrito a um único átomo. Leis de equivalência: negação dupla e Morgan.

3. Transforme-a para a forma normal conjuntiva: F1 ∧ F2 ∧ ... ∧ Fn, onde cada Fi está na forma L1 ∨ L2 ∨ ... ∨ Lm e cada Lj é um literal. Leis de equivalência: distributivas e associativas.

4. Transforme-a em um conjunto de cláusulas substituindo fórmulas na forma F1 ∧ F2 ∧ ... ∧ Fn em {F1, F2,..., Fn}, onde as fórmulas Fi estão na forma disjuntiva.

Exercício: Transforme para a forma clausal a fórmula P ∨ ¬(¬Q → R) ∧ (S →P). Teorema 1 (“soundness” da resolução) Uma coleção de regras de inferência é saudável se ele preserva os valores verdade sob as operações de derivação (|-). Considere duas cláusulas C1 e C2 contendo literais complementares. Qualquer resolvente C de C1 e C2 é uma conseqüência lógica de {C1, C2}. Isto é, se {C1, C2} í î C então {C1, C2} ïæð C.


Obs.: ñ ò deriva (deduz) pela aplicação de uma regra de inferência. Teorema 2 A resolução é completa, isto é, todas as conseqüências lógicas de um dado conjunto de fórmulas podem ser derivadas. Se S ñæó F então S ñ ò F. 5.3. Lógica de Predicados

É mais expressiva que a lógica proposicional: − permite descrever propriedades e relações de / entre objetos; − permite expressar declarações mais gerais.

Sintaxe

a) Símbolos da linguagem

i) Objetos : são os elementos do universo do discurso (inicia com maiúscula).

ii) Predicados : são relações entre os objetos do universo (inicia com maiúscula). Ex. : Homem(José). Pai(José, Maria). Sobre(BlocoA, BlocoB).

Obs. : Aridade é o número de elementos (argumentos) de um predicado. Proposição possui aridade 0.

iii) Variáveis : expressam genericamente elementos do universo (minúsculas).

iv) Funções : são mapeamentos de elementos do universo (minúsculas).

v) Conectivos lógicos : os mesmos da lógica proposicional : ¬ ∧ ∨ → ô

vi) Quantificadores : ∀ universal e ∃ existencial.

vii) Símbolos auxiliares : parênteses, vírgula, ... .

b) Definições

i) Termo : é definido como : (1) uma constante ; (2) uma variável ; (3) se f é uma função de aridade n e t1, t2, ..., tn são termos, então f(t1, t2, ..., tn) é um termo.

ii) Fórmula atômica, ou simplesmente átomo, é uma expressão da forma P(t1, t2, ..., tn) onde P é um predicado n-ário, n õ\ö1÷,øúù 1, t2, ..., tn são termos.

Exemplos : P(x), Q(f(y), C, g(f(x), z))

iii) Fórmula composta, é formada com átomos ligados por conectivos lógicos e junto com quantificadores.

iv) Fórmula bem formada (FBF) : (1) um átomo é uma FBF ; (2) se P é uma FBF então ¬P é uma FBF ; (3) se P e Q são FBF, então P ∧ Q, P ∨ Q, P → Q, P ↔ Q são FBF ; (4) se P é uma FBF então ∀x P e ∃x P são FBF.

v) Escopo de quantificador : é a área de influência do quantificador.

vi) Variável livre : variável que ocorre em uma FBF e não é quantificada.

vii) Fórmula fechada (sentença): não possui variáveis livres.

viii)Fórmula livre : possui variáveis livres. Ex. : ∀x (P(x,y) → ∃y (R(x, y))) o y em negrito não é quantificado.

Semântica Na lógica de predicados a semântica é dada em cinco etapas :


1) Definir um domínio de aplicação D, denominado universo do discurso. 2) Atribuir a cada variável livre um elemento do domínio D. 3) Atribuir a cada função uma aplicação de Dn em D. 4) Atribuir a cada proposição o valor v ou f. 5) Atribuir a cada predicado uma aplicação de Dm em {v, f}.

Leis de Equivalência para Quantificadores ¬∃x P(x) ≡ ∀x ¬P(x) ¬∀x P(x) ≡ ∃x ¬P(x) ∀x (P(x) ∧ Q(x)) ≡ ∀x P(x) ∧ ∀x Q(x) ∃x (P(x) ∨ Q(x)) ≡ ∃x P(x) ∨ ∃x Q(x) ∀x P(x) ≡ ∀y P(y) ∃x P(x) ≡ ∃y P(y) Cuidado : ∀x (P(x) ∨ Q(x)) ≠ ∀x P(x) ∨ ∀x Q(x) ∃x (P(x) ∧ Q(x)) ≠ ∃x P(x) ∧ ∃x Q(x) Forma Clausal da Lógica de Predicados

a) Cláusula é uma fórmula fechada disjuntiva ∀x1, ∀x2, ..., ∀xs (L1∨ L2∨... ∨ Lm) onde cada Li (i =1..m; m≥0) é um literal em que Li ≠ Lj (i ≠ j) e x1, ..., xs (s≥0) são variáveis ocorrendo em (L1∨...∨ Lm).

b) Forma Normal PRENEX é quando uma FBF tem o seguinte formato : Q1 x1 ... Qn xn M onde Qi (i =1..n; n≥0) é um dos quantificadores ∀ ou ∃, e M é a fórmula onde os quantificadores ocorrem.

c) Uma fórmula F na forma normal PRENEX está na Forma Normal Conjuntiva se a matriz M de F for da forma F1 ∧ F2 ∧ ... ∧ Fn, onde cada Fi (i =1..n; n≥1) for uma disjunção de literais L1 ∨ L2 ∨ ... ∨ Lm.

Exemplos : ∀x (P(x) ∨ ∃y Q(x,y)) Não está na forma normal PRENEX devido à presença do quantificador existencial ∀x ∃y ∀z ((P(x) ∧ Q(x,y)) ∨ ¬R(x)) PRENEX ∀x ∃y ((¬P(x) ∨ Q(x,y)) ∧ (P(x) ∨ R(x))) Forma normal conjuntiva

Algoritmo de transformação de uma FBF para a forma clausal:

1. Elimine as implicações. Para isto utilize as leis de equivalência: F↔G ≡ (F→G) ∧ (G→F) e F→G ≡ ¬F ∨ G.

2. Reduza o escopo dos operadores de negação, de modo que cada ¬ esteja restrito a um único átomo. Leis de equivalência: negação dupla, Morgan e dos quantificadores.

3. Individualize as variáveis para que cada quantificador fique vinculado a uma variável única. Leis de equivalência: ∀x P(x) ≡ ∀y P(y) e ∃x P(x) ≡ ∃y P(y) Exemplo: ∀x F(x) ∧ ∀x G(x) fica ∀x F(x) ∧ ∀y G(y)

4. Elimine os quantificadores existenciais através das funções de Skolen (skolenização). ∃x P(x) fica P(C) onde C é uma constante não utilizada antes. ∀x (∃y P(x, y)) fica ∀x P(x, g(x)) onde g é uma função não utilizada antes.

Obs. : - É utilizado x como argumento da função porque o escopo de x é maior, então y pode ser funcionalmente dependente de x.

- As fórmulas não são equivalentes lógico, porém F é SAT sse Fs é SAT.

5. Transforme a fórmula em forma normal PRENEX, movendo os quantificadores ∀ para a esquerda da fórmula, sem alterar a sua ordem relativa.

6. Transforme-a para a forma normal conjuntiva: F1 ∧ F2 ∧ ... ∧ Fn, onde cada Fi está na forma L1∨ L2∨...∨ Lm e cada Lj é um literal. Leis de equivalência: distributivas e associativas.

7. Desconsidere o prefixo e transforme a matriz em um conjunto de cláusulas substituindo fórmulas na forma F1 ∧ F2 ∧ ... ∧ Fn em {F1, F2,..., Fn}, onde as fórmulas Fi estão na forma disjuntiva.


Exercício: Transforme a FBF abaixo na forma clausal. ∀x(∃yP(x,y)∨¬∃y(¬Q(x,y)→R(f(x,y)))) 1. ∀x(∃yP(x,y)∨¬∃y(Q(x,y)∨R(f(x,y)))) eliminação de implicações 2. ∀x(∃yP(x,y)∨∀y(¬Q(x,y)∧¬R(f(x,y)))) redução do escopo das negações 3. ∀x(∃yP(x,y)∨∀z(¬Q(x,z)∧¬R(f(x,z)))) individualização das variáveis 4. ∀x(P(x,g(x))∨∀z(¬Q(x,z)∧¬R(f(x,z)))) eliminação dos quantificadores existenciais 5. ∀x∀z (P(x,g(x))∨ (¬Q(x,z)∧¬R(f(x,z)))) transformação na forma normal PRENEX 6. ∀x∀z ((P(x,g(x))∨ ¬Q(x,z))∧(P(x,g(x))∨¬R(f(x,z)))) transformação na forma normal conjuntiva 7. {P(x,g(x))∨ ¬Q(x,z), P(x,g(x))∨¬R(f(x,z))} forma clausal Resolução na Lógica de Predicados Unificação

É um procedimento que procura tornar 2 expressões iguais através da substituição de variáveis. Definições

Substituição simples é a expressão x/t onde se lê “ x substituído por t”, x é uma variável e t um termo.

Substituição é um conjunto finito β de substituições simples, onde nenhum dos primeiros elementos das substituições simples coincidem.

Instância Sejam E uma expressão e β={x1/t1, …, xn/tn} uma substituição. Eβ é uma instância de E, obtida substituindo-se em E cada ocorrência de xi por ti, ∀i. Se E for um conjunto de expressões, então Eβ é uma instanciação de todas as expressões de E por β. A instanciação da cláusula C por substituição β é obtida fazendo Cβ e eliminando-se as ocorrências repetidas do mesmo

literal.

Composição de substituições A composição da substituição θ={x1/t1, …, xm/tm} com a substituição β={y1/s1, …, yn/sn} é θβ={ x1/t1β, …, xm/tmβ,

y1/s1, …, yn/sn} – {xi/tiβ | xi=tiβ} – {yj/sj | yj ∈{x1, …, xm}}

Seja β, θ e ϕ substituições, então E(ββ) = Eβ E(ϕβ)θ = Eϕ(βθ) associativa Eβθ ≠ Eθβ não é comutativa

Exemplo E = Q(x, f(y), g(z, x)) θ = {x/f(y), y/z} β = {x/A, y/B, z/y} θβ = {x/f(B), z/y} { x/f(y)β, y/zβ, x/A, y/B, z/y} → {x/f(B), y/y, x/A, y/B, z/y} → {x/f(B), z/y} Eθβ = Q{f(B), f(y), g(y, f(B))) Unificador é uma substituição β onde, dado um conjunto de expressões {E1, …, Em}, E1β= … = Emβ.

Unificador Mais Geral (UMG) é um unificador θ de um conjunto de expressões E={E1, …, Em}, onde para todo unificador β de E existe uma substituição λ tal que β=θλ. Exemplo: E={R(x, f(A, g(y))), R(B, f(z, w))} β1={x/B, z/A, w/g(C), y/C} R(B, f(A, g(C)))


β2={x/B, z/A, y/f(A), w/g(f(A))} R(B, f(A, g(f(A)))) β3={x/B, z/A, w/g(y)} R(B, f(A, g(y))) β3 é um UMG: β3{y/C}=β1 Obs.: λ={y/C} β3{y/f(A)}=β2 Exercício: Encontre o unificador mais geral para E={x, f(x)}. Algoritmo de Unificação

Unifica(L1, L2):conjunto retorna o UMG como resultado ou fracasso 1. Se L1 e L2 forem ambos constantes e/ou variáveis, então

a) Se L1 e L2 forem idênticos, então retorne {}. vazio b) Se L1 for uma variável então

Se L1 ocorrer em L2 então retorne fracasso senão retorne {L1/L2}.

c) Se L2 for uma variável então Se L2 ocorrer em L1 então retorne fracasso senão retorne {L2/L1}.

d) Se L1 e L2 forem constantes então retorne fracasso. 2. Se os símbolos de predicado de L1 e L2 não forem idênticos então retorne fracasso. 3. Se as aridades de L1 e L2 forem diferentes então retorne fracasso. 4. UMG ← nulo 5. Para n ← 1 até aridade de L1

a) S ← Unifica(n-ésimo argumento de L1, n-ésimo argumento de L2). b) Se S = fracasso então retorne fracasso. c) Se S ≠ {} então

i) aplique S ao que resta em L1 e L2. ii) UMG ← UMG + S.

6. Retorne UMG. Algoritmo de Resolução Prova(P, T) Prova P com respeito a um conjunto de axiomas T

1. Cláusulas ← Converte(T). 2. Cláusulas ← Cláusulas + Converte(¬P). 3. Faça até ÿ ∈ Cláusulas ou nenhum progresso for feito

a) Selecione 2 cláusulas Ci e Cj ∈ Cláusulas. Depende de uma estratégia. b) Resolvente ← Resolve(Ci, Cj). c) Cláusulas ← Cláusulas + Resolvente.

Obs.: Se parou porque encontrou ÿ então existe uma contradição. Assim, P é verdadeiro em relação a T com as substituições

que foram efetuadas para derivar ÿ . Resolve(Ci, Cj): cláusula

1. Selecione L1 ∈ Ci, L2 ∈ Cj, onde L1 ou L2 é negado nas cláusulas e L1 e L2 são unificáveis. 2. UMG ← Unifica(L1, L2). 3. Retorne o resolvente: disjunção de todos os literais de Ci e Cj, após a aplicação do UMG, com exceção dos literais

redundantes e dos literais complementares L1 e ¬L2 (ou ¬L1 e L2). Exercício:

Dado os axiomas abaixo, já na forma clausal, prove que Marcos odeia alguém. Isto é, odeia(marcos, x).


1. Homem(Marcos) 2. Pompeano(Marcos) 3. ¬Pompeano(x1) ∨ Romano(x1) 4. Soberano(César) 5. ¬Romano(x2) ∨ Leal_a(x2, César) ∨ Odeia(x2, César) 6. Leal_a(x3, f1(x3)) 7. ¬Homem(x4) ∨ ¬Soberano(y1) ∨ ¬Tenta_assassinar(x4, y1) ∨ ¬Leal_a(x4, y1) 8. Tenta_assassinar(Marcos, César)

Resposta: 9. ¬Odeia(Marcos,x) 10. ¬Romano(Marcos) ∨ Leal_a(Marcos, César) 9 e 5 {x2/Marcos, x/César} 11. ¬Pompeano(Marcos) ∨ Leal_a(Marcos, César) 3 e 10 {x1/Marcos} 12. Leal_a(Marcos, César) 2 e 11 {} 13. ¬Homem(Marcos) ∨ ¬Soberano(César) ∨

¬Tenta_assassinar(Marcos, César) 7 e 12 {x4/Marcos, y1/César} 14. ¬Soberano(César) ∨

¬Tenta_assassinar(Marcos, César) 1 e 13 {} 15. ¬Tenta_assassinar(Marcos, César) 4 e 14 {} 16. ÿ 8 e 15 {}

A cláusula vazia foi derivada, então está provado que Marcos odeia alguém. Como a variável do teorema está instanciada com César, então Marcos odeia César. 5.4. Estratégia de Resolução

É a forma de escolha das cláusulas que serão “resolvidas”. As estratégi as serão apresentadas com exemplos da lógica proposicional, porém os conceitos são os mesmos para a lógica de predicados.

A forma mais rápida é usando a nossa inteligência, selecionando as cláusulas que geram a cláusula vazia com o menor esforço. Veja o exemplo abaixo.

Sejam a teoria {P, ¬P∨Q, ¬P∨¬Q∨R} e o teorema R a ser provado, aplicando o algoritmo de resolução a cláusula vazia é derivada e fica provado R.

Cláusulas: 1. P 2. ¬P∨Q 3. ¬P∨¬Q∨R 4. ¬R

5. ¬P∨R 2 e 3 6. R 1 e 5 7. ÿ 4 e 6

1) Resolução por Saturação (exploração em extensão) Faz a seleção das cláusulas de maneira sistemática, na ordem em que as mesmas aparecem, sendo que as cláusulas selecionadas devem ter literais complementares. Para evitar trabalho desnecessário, os resolventes que já estão presentes no conjunto de cláusulas não são acrescentados novamente. Esta estratégia de seleção é completa, mas ineficiente. Abaixo é apresentada a seqüência de cláusulas geradas com esta estratégia para o problema anterior:

5. Q 1 e 2 6. ¬Q∨R 1 e 3 7. ¬P∨R 2 e 3 8. ¬P∨¬Q 3 e 4 9. ¬Q 4 e 6

10. ¬P 4 e 7 11. R 5 e 6 12. ¬P 5 e 8 13. ÿ 5 e 9

2) Resolução com o Conjunto de Suporte Esta estratégia utiliza o conhecimento de que o conjunto de cláusulas original (teoria ou axiomas) é sempre consistente. Assim, somente é possível derivar a cláusula vazia, provando a inconsistência, utilizando-se pelo menos uma cláusula que não pertença ao conjunto de cláusulas original. Definição: Um subconjunto T de um conjunto de cláusulas S é um conjunto de suporte de S se e somente se S - T é consistente. T contém inicialmente a cláusula a ser provada e a cada passo o resolvente é acrescentado a T.


Na aplicação desta estratégia, pelo menos um dos pais faz parte do conjunto de suporte T. Esta estratégia é eficiente porque previne a geração de resolventes que não contribuem para a prova, diminuindo a explosão combinatorial. Veja abaixo a seqüência de cláusulas geradas com esta estratégia para o problema anterior:

5. ¬P∨¬Q 4 e 3 T={4} 6. ¬Q 5 e 1 T={4, 5} 7. ¬P 5 e 2 T={4, 5, 6} 8. ÿ 7 e 1 T={4, 5, 6, 7}

3) Resolução Linear A cláusula pai é inicialmente a negação da cláusula a ser provada e nos demais passos é o último resolvente. A outra cláusula é a cláusula auxiliar (outra cláusula qualquer). A seqüência de cláusulas geradas com esta estratégia para o problema anterior é:

5. ¬P∨¬Q 4 e 3 6. ¬Q 5 e 1 7. ¬P 6 e 2 8. ÿ 7 e 1

Exercício: 1) Prove P(h(x), x, h(S)) com relação ao conjunto de cláusulas { P(f(x,y), x, y), ¬P(x, g(x, y), y), ¬P(x, y, u) ∨ P(y, z, v) ∨ ¬P(x, v, w) ∨ P(u, z, w) }, utilizando as estratégias:

(a) resolução por saturação; (b) resolução com conjunto de suporte; (c) resolução linear. 4) Estratégia Linear de Entrada

A cláusula pai é inicialmente a negação da cláusula a ser provada e nos demais passos é o último resolvente. A cláusula auxiliar (outra cláusula) é uma das cláusulas do conjunto de entrada (cláusulas originais + a negação do teorema a ser provado). Veja abaixo a seqüência de cláusulas geradas com esta estratégia para o problema anterior:

5. ¬P∨¬Q 4 e 3 6. ¬Q 5 e 1 7. ¬P 6 e 2 8. ÿ 7 e 1

5) Resolução LSD (Linear com função de Seleção para cláusulas Definidas) Esta estratégia trabalha com um conjunto de cláusulas consistindo de uma ou mais cláusulas definidas e de uma cláusula objetivo. Definições:

(a) cláusula definida é aquela contendo exatamente um literal positivo, isto é, uma expressão da forma: L ∨ ¬M1 ∨ ¬M2 ∨ . . . ∨ ¬Mn ou L , onde L, M1, M2, . . ., Mn são átomos. (b) cláusula objetivo é a cláusula vazia ou uma cláusula com todos os literais negativos, isto é, uma expressão

da forma: ¬M1 ∨ ¬M2 ∨ . . . ∨ ¬Mn

(c) f é uma função de seleção sse f mapeia cada cláusula objetivo em um literal da cláusula.

A aplicação desta estratégia funciona da seguinte forma: Sejam A’ uma cláusula objetivo, da forma “ ¬N1 ∨ ¬N2 ∨ . . . ∨ ¬Nm”;

A’’ uma cláusula definida, da forma “L ∨ ¬M1 ∨ ¬M2 ∨ . . . ∨ ¬Mk”; β uma re-nomeação de A’’ em presença de A’; f uma função de seleção, padrão, tal que f(¬N1 ∨ ¬N2 ∨ . . . ∨ ¬Nm) = N1;

o resolvente é uma cláusula objetivo A sse existe um UMG θ do conjunto de literais {L, N1} tal que A é da forma (¬M1 ∨ ¬M2 ∨ . . . ∨ ¬Mk ∨ ¬N2 ∨ . . . ∨ ¬Nm )θ

Note que:

û a cláusula A’ é denominada cláusula -pai e é sempre o último resolvente ou, na primeira vez, o teorema negado; û a cláusula A’’ é denominada cláusula auxiliar e pertence ao conjunto de cl áusulas de entrada;


ü não há liberdade de escolha dos literais; ü o resolvente sempre é uma cláusula objetivo; ü esta estratégia utiliza um subconjunto da lógica de predicados, chamado “cláusulas de Horn”, permitindo apenas

cláusulas do tipo: (a) L. ≡ L ← (b) L ∨ ¬M1 ∨ ¬M2 ∨ . . . ∨ ¬Mn ≡ L ← M1 ∧ M2 ∧ . . . ∧ Mn (c) ¬M1 ∨ ¬M2 ∨ . . . ∨ ¬Mn ≡ ← M1 ∧ M2 ∧ . . . ∧ Mn ≡ ¬∃ (M1 ∧ M2 ∧ . . . ∧ Mn)

A seqüência de cláusulas geradas com esta estratégia para o problema anterior é:

5. ¬P∨¬Q 4 e 3 6. ¬Q 5 e 1 7. ¬P 6 e 2 8. ÿ 7 e 1

Exercícios: 1) Prove P(B) com relação ao conjunto de cláusulas { P(x) ∨ R(x) ∨ P(B), P(A) ∨ R(B), ¬P(A), ¬R(A)},

utilizando as estratégias: (a) resolução por saturação; (b) resolução com conjunto de suporte; (c) resolução linear.

2) Prove o Depende(A,E) com relação ao conjunto de cláusulas { Chama(A,B), Usa(B,E), Depende(x,y) ∨ ¬Chama(x,y), Depende(x,y) ∨ ¬Usa(x,y), Depende(x,y) ∨ ¬Chama(x,z) ∨ ¬Depende(z,y) }, utilizando as estratégias:

(a) resolução por saturação; (b) resolução com conjunto de suporte; (c) resolução linear; (d) resolução linear de entrada; (e) resolução LSD.

Solução do exercício 1): (a) resolução por saturação:

1. P(x) ∨ R(x) ∨ P(B) 2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A) 5. ¬P(B) 6. R(A) ∨ P(B) 1 e 3 {x/A} 7. P(A) ∨ P(B) 1 e 4 {x/A} 8. R(B) 1 e 5 {x/B} 9. P(B) 3 e 7 {} 10. R(A) 5 e 6 {} 11. P(A) 5 e 7 {} 12. ÿ 5 e 9 {}

(b) resolução com conjunto de suporte: 1. P(x) ∨ R(x) ∨ P(B) 2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A) 5. ¬P(B) 6. R(B) 5 e 1 {x/B} Não é mais possível avançar, então tenta outra alternativa pegando o literal P(B) da cláusula 1. 6. P(x) ∨ R(x) 5 e 1 {} 7. R(A) 6 e 3 {x/A} 8. P(A) 6 e 4 {x/A}


9. R(B) 6 e 5 {x/B} 10. ÿ 7 e 4 { }

(c) resolução linear:

1. P(x) ∨ R(x) ∨ P(B) 2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A) 5. ¬P(B) 6. R(B) 5 e 1 {x/B} Não é mais possível avançar, então tenta outra alternativa pegando o literal P(B) da cláusula 1. 6. P(x) ∨ R(x) 5 e 1 {} 7. R(A) 6 e 3 {x/A} 8. ÿ 7 e 4 { }

Solução do exercício 2):

(a) resolução por saturação: 1. Chama(A,B) 2. Usa(B,E) 3. Depende(x,y) ∨ ¬Chama(x,y) 4. Depende(x,y) ∨ ¬Usa(x,y) 5. Depende(x,y) ∨ ¬Chama(x,z) ∨ ¬Depende(z,y) 6. ¬Depende(A,E) 7. Depende(A,B) 1 e 3 {x/A, y/B} 8. Depende(A,y) ∨ ¬Depende(B,y) 1 e 5 {x/A, z/B} 9. Depende(B,E) 2 e 4 {x/B, y/E} 10. ¬Chama(z,y) ∨ ¬Chama(z,z) 3 e 5 {x/z} 11. ¬Chama(A,E) 3 e 6 {x/A, y/E} 12. ¬Chama(B,y) ∨ Depende(A,y) 3 e 8 {x/B} 13. ¬Usa(z,y) ∨ ¬Chama(z,z) 4 e 5 {x/z} 14. ¬Usa(A,E) 4 e 6 {x/A, y/E} 15. ¬Usa(B,y) ∨ Depende(A,y) 4 e 8 {x/B} 16. ¬Chama(A,z) ∨ ¬Depende(z,E) 5 e 6 {x/A, y/E} 17. Depende(x,B) ∨ ¬Chama(x,A) 5 e 7 {z/A, y/B} 18. ¬Chama(B,z) ∨ ¬Depende(z,y) ∨ Depende(A,y) 5 e 8 {x/B} 19. Depende(x,y) ∨ ¬Chama(x,A) ∨ ¬Depende(B,y) 5 e 8 {z/A} 20. Depende(x,E) ∨ ¬Chama(x,B) 5 e 9 {z/B, y/E} 21. Depende(x,y) ∨ ¬Chama(x,A) ∨ ¬Chama(B,y) 5 e 12 {z/A} 22. Depende(x,y) ∨ ¬Chama(x,A) ∨ ¬Usa(B,y) 5 e 15 {z/A} 23. ¬Chama(x1,z) ∨ ¬Depende(z,E) ∨ ¬Chama(A,x1) 5 e 16 {z/x1, x/x1,y/E} 24. Depende(x,B) ∨ ¬Chama(x,z) ∨ ¬Chama(z,A) 5 e 17 {x1/z, y/B} antes, a variável x da 17

foi renomeada para x1 . . .

(b) resolução com conjunto de suporte:

1. Chama(A,B) 2. Usa(B,E) 3. Depende(x,y) ∨ ¬Chama(x,y) 4. Depende(x,y) ∨ ¬Usa(x,y) 5. Depende(x,y) ∨ ¬Chama(x,z) ∨ ¬Depende(z,y) 6. ¬Depende(A,E)


7. ¬Chama(A,E) 6 e 3 {x/A, y/E} 8. ¬Usa(A,E) 6 e 4 {x/A, y/E} 9. ¬Chama(A,z) ∨ ¬Depende(z,E) 6 e 5 {x/A, y/E} 10. ¬Depende(B,E) 9 e 1 {z/B} 11. ¬Chama(A,x) ∨ ¬Chama(x,E) 9 e 3 {z/x, y/E} 12. ¬Chama(A,x) ∨ ¬Usa(x,E) 9 e 4 {z/x, y/E} 13. ¬Chama(x,z) ∨ ¬Depende(z,E) ∨ ¬Chama(A,x) 9 e 5 {z1/x, y/E} antes, a variável z da 9

foi renomeada para z1 14. ¬Chama(B,E) 10 e 3 {x/B, y/E} 15. ¬Usa(B,E) 10 e 4 {x/B, y/E} 16. ¬Chama(B,z) ∨ ¬Depende(z,E) 10 e 5 {x/B, y/E} 17. ¬Chama(A,B) 12 e 2 {x/B} 18. ¬Depende(B,E) ∨ ¬Chama(A,A) 13 e 1 {x/A, z/B} 19. ¬Chama(z,z) ∨ ¬Chama(A,z) ∨ ¬Chama(z,E) 13 e 3 {x/z, y/E} 20. ¬Chama(x,z) ∨ ¬Chama(A,x) ∨ ¬Usa(z,E) 13 e 4 {x1/z, y/E} antes, a variável x da 4

foi renomeada para x1 21. ¬Chama(x,x1) ∨ ¬Chama(A,x) ∨ ¬Chama(x1,z1) ∨ 13 e 5 {z/x1, y/E} antes, a variável z da 5 foi

¬Depende(z1,E) renomeada para z1; e a x da 5 para x1

22. ÿ 15 e 2 {}

(c) resolução linear, resolução linear de entrada e resolução LSD, para este problema, têm a mesma solução: 1. Chama(A,B) 2. Usa(B,E) 3. Depende(x,y) ∨ ¬Chama(x,y) 4. Depende(x,y) ∨ ¬Usa(x,y) 5. Depende(x,y) ∨ ¬Chama(x,z) ∨ ¬Depende(z,y) 6. ¬Depende(A,E) 7. ¬Chama(A,E) 6 e 3 {x/A, y/E} Não é mais possível avançar 7. ¬Usa(A,E) 6 e 4 {x/A, y/E} Não é mais possível avançar 7. ¬Chama(A,z) ∨ ¬Depende(z,E) 6 e 5 {x/A, y/E} 8. ¬Depende(B,E) 7 e 1 {z/B} 9. ¬Chama(B,E) 8 e 3 {x/B, y/E} Não é mais possível avançar 9. ¬Usa(B,E) 8 e 4 {x/B, y/E} 10. ÿ 9 e 2 {x/B}

Árvore de Busca A escolha da estratégia de resolução define como é explorada a árvore de busca para encontrar a cláusula vazia. A Figura 25 apresenta a árvore de busca para o problema do exercício 1. Os nodos da árvore de busca contêm o conjunto de cláusulas corrente, sendo que a raiz contém o conjunto de cláusulas de entrada.


Figura 25 - Árvore de busca. Árvore de Refutação A escolha da estratégia de resolução define como é explorada a árvore de busca para encontrar a cláusula vazia. A árvore contendo apenas os nodos visitados durante o processo de busca da cláusula vazia é denominada árvore de refutação. A Figura 26 apresenta a árvore de refutação para o problema do exercício 2 utilizando a estratégia de resolução LSD. Para as estratégias Linear, Linear de Entrada e LSD a árvore pode ser simplificada colocando-se nos nodos apenas a cláusula objetivo corrente (cláusula pai). A raiz normalmente contém apenas a cláusula objetivo (teorema negado), mas pode conter o conjunto de cláusulas de entrada por questões de clareza. Como a cláusula objetivo sempre participa na resolução das cláusulas, o seu número pode ser omitido nos arcos.

. . .

1. P(x) ∨ R(x) ∨ P(B)

2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A)

1. P(x) ∨ R(x) ∨ P(B)

2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A) 5. ¬P(B) 6. R(A) ∨ P(B)

1 e 3 {x/A}

1. P(x) ∨ R(x) ∨ P(B)

2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A) 5. ¬P(B) 6. P(x) ∨ P(B)

1. P(x) ∨ R(x) ∨ P(B)

2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A) 5. ¬P(B) 6. P(x) ∨ R(x)

1 e 4 {x/A} 1 e 5 {}

1. P(x) ∨ R(x) ∨ P(B)

2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A) 5. ¬P(B) 6. R(B)

2 e 3 {}

1. P(x) ∨ R(x) ∨ P(B) 2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A) 5. ¬P(B) 6. R(A) ∨ P(B) 7. P(x) ∨ P(B)

1. P(x) ∨ R(x) ∨ P(B) 2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A) 5. ¬P(B) 6. R(A) ∨ P(B) 7. P(x) ∨ R(x)

1 e 4 {x/A} 1 e 5 {}

1. P(x) ∨ R(x) ∨ P(B) 2. P(A) ∨ R(B) 3. ¬P(A) 4. ¬R(A) 5. ¬P(B) 6. R(A) ∨ P(B) 7. R(B)

2 e 3 {}

. . . . . .

. . . . . . . . .


Figura 26 - Árvore de Refutação.

6. ¬Depende(A,E)

7. ¬Chama(A,E)

7. ¬Usa(A,E) 7. ¬Chama(A,z) ∨ ¬Depende(z,E)

8. ¬Depende(B,E)

9. ¬Chama(B,E) 9. ¬Usa(B,E)

10. ÿ

2 {x/B}

3 {x/B, y/E}

1 {z/b}

5 {x/A, y/E}

4 {x/B, y/E}

4 {x/A, y/E} 3 {x/A, y/E}


6. Introdução aos Sistemas Especialistas

Sistemas Especialistas (SE) são sistemas de Inteligência Artificial, baseados em conhecimento, que emulam um especialista humano na resolução de um problema significativo em um domínio específico.

Assim, os SE solucionam problemas que normalmente são solucionados por especialistas humanos. Para solucionar tais problemas, os sistemas especialistas precisam acessar uma substancial base de conhecimento do domínio da aplicação, que precisa ser criada de modo mais eficiente possível. Eles também precisam explorar um ou mais mecanismos de raciocínio, para aplicar aos problemas que têm diante de si. Depois eles precisam de um mecanismo para explicar o que fizeram aos usuários que dele dependem.

O termo especialista freqüentemente leva as pessoas a terem expectativas irrealistas do desempenho de um SE. É importante lembrar que o termo especialista originalmente representa uma limitação na capacidade de representação e armazenamento de conhecimento do sistema. Na verdade, um SE trata de um determinado conhecimento específico sobre um domínio de problema, ao contrário de um solucionador geral de problemas. Quanto mais geral a classe de problemas que podem ser resolvidos por um sistema, mais insatisfatória será a solução produzida.

Os problemas com os quais lidam os sistemas especialistas são altamente diversificados. Há questões gerais que surgem em vários domínios. Os sistemas especialistas que fizeram mais sucesso comercialmente estão na classe de problemas em que dado um conjunto de fatos observados, o sistema infere possíveis problemas, detecta resultados relevantes, apresenta alternativas de projeto, etc. Características de SE ý Possuem conhecimento especializado em alta qualidade e quantidade; ý O conhecimento pode ser incompleto, subjetivo e inexato; ý O Banco de Conhecimento é independente da Estrutura de Controle; ý Explicam o raciocínio utilizado na resolução do problema; ý Incluem tratamento de incerteza; ý Podem adquirir novos conhecimentos. Tipos de SE ý Classificação ý Diagnose - infere mal-funções. ý Interpretação - compreende situações. ý Predição - infere conseqüências de situações. ý Projeto - configura objetos sob restrições. ý Planejamento - projeta seqüência de ações. ý Depuração - prescreve “remédios” para mal -funções. ý Reparo - executa um plano para administrar um “remédio” prescrito. ý Instrução - diagnose, depuração e reparo para deficiências de estudantes. ý Controle - interpretação, predição, reparo, e monitoramento de comportamento de sistemas. O SE e seu Ambiente

A Figura 27 mostra o ambiente de um SE, onde há dois momentos distintos: a construção e a utilização. O profissional encarregado de construir um SE é o engenheiro de conhecimento, o qual deve dominar as ferramentas de desenvolvimento e as linguagens de representação de conhecimento. O conhecimento pode ser privado, obtido através de entrevistas com especialistas no assunto relativo ao problema, ou público, obtido pela consulta em livros e revistas especializadas.

Quando o SE estiver em produção, ele pode ser utilizado para resolver problemas de usuários não especialistas no assunto.

6.1. Componentes Básicos de um SE Existe um consenso sobre a arquitetura geral de um sistema especialista. Quase todos eles podem ser separados em três

componentes distintos: a Base de Conhecimento, o Motor de Inferência (Inference Engine) e a Interface com o Usuário. Base de Conhecimento

Consiste na parte central de um SE. É a representação do conhecimento no domínio no problema em questão, geralmente extraída de um ou vários especialistas, de forma declarativa, e livre de detalhes de controle e implementação. Idealmente ela é composta de declarações, em algum formalismo de representação de conhecimento disponível, descrevendo o domínio da aplicação. Memória de Trabalho Armazena as informações fornecidas pelo usuário e todo o conhecimento inferido pelo sistema durante uma consulta. Ao final da consulta esta informações são apagadas.


Figura 27 - Ambiente de um SE Motor de Inferência

O motor de inferência, também chamado máquina de inferência, é responsável pela manipulação da base de conhecimento durante a resolução de problemas. É chamado de motor de inferência porque ele usa o conhecimento da base e os fatos relativos a uma determinada consulta para obter conclusões. A natureza do motor de inferência irá depender do formalismo utilizado para representar a base de conhecimento e da estratégia de solução de problemas considerada apropriada pelo projetista do sistema. Por exemplo, se o formalismo de representação escolhido for regras de produção, o motor de inferência irá necessariamente tomar a forma de um interpretador de regras.

A arquitetura do motor de inferência está intimamente relacionada com a linguagem de representação do conhecimento e inclui os elementos: Mecanismo de Inferência, Estratégia de Controle, Métodos de tratamento da Incerteza e Métodos de tratamento de Conhecimento Incompleto, os quais serão detalhados mais adiante. Interface com o Usuário

Todo sistema especialista é interativo. e precisa de um componente para gerenciar a interação entre o usuário e o sistema A interação básica numa sessão de uso de um SE consiste no sistema perguntar questões relevantes. apresentar conselhos, respostas e prover explicações requeridas pelo usuário

Dois tipos de explicação que são freqüentemente fornecidas pelo SE são aquelas a perguntas do tipo Por que?, e explicações de como o sistema chegou a determinada conclusão, ou seja Como? 6.2. Arquitetura do Motor de Inferência Mecanismo de Inferência O mecanismo de inferência gera novas conclusões a partir da manipulação do conhecimento existente na base de conhecimento e na memória de trabalho. O mecanismo depende da forma de representação de conhecimento. Em sistemas baseados em regras o mecanismo encontrado com mais freqüência é o “modus ponens”: se as premissas de uma regra são verdadeiras, então é pode-se acreditar que as suas conclusões também o são, assim as conclusões podem ser acrescentadas no conhecimento existente. Conforme o exemplo mostrado na Figura 28, o fato B é derivado a partir do fato A e da Regra A → B. Uma das vantagens do “modus ponens” é a sua simplicidade, entretanto é importante ressaltar que ele não conclui todas as inferências válidas.

especialistas

SE

engenheiro de conhecimento

Resposta

Consulta

usuário

?


Figura 28 - Exemplo de aplicação do “modus ponens”

Em formalismos de representação do conhecimento orientados a objetos um dos mecanismos de inferência utilizados é a herança. No capítulo sobre formas de representação conhecimento são estudadas outros mecanismos de inferência. Estratégia de Controle É composto por vários elementos:

þ Modo de seleção de “peças” de conhecimento (regras, quadros, roteiros, nodos, ...) - é feito através de casamento de padrões.

þ Direção do raciocínio - é a direção em que é feita a busca em um espaço de soluções. No caso de regras é a direção como é feito o encadeamento das regras:

o Encadeamento progressivo (encadeamento para frente, “forward”, ”data -driven”, ”bottom -up”) As regras da base de conhecimento são selecionadas com base no conhecimento existente (fatos da base de conhecimento, informações do usuário e conhecimento já inferido), comparando-se o lado esquerdo das regras (condições), e ativadas para gerar novos fatos até encontrar a solução. Equivale à busca em espaço de estados, onde o estado é o banco de conhecimento. A Figura 29 mostra um exemplo de encadeamento progressivo. Os números associados aos arcos da árvore de pesquisa correspondem à aplicação das regras da base de conhecimento. No início a regra 1 não é aplicável, talvez será no decorrer da pesquisa.

o Encadeamento regressivo (encadeamento para trás, “backward”, ”goal -directed”, ”top -down”) As regras da base de conhecimento são selecionadas a partir dos objetivos, comparando-se o lado direito das regras (conclusões), e ativadas para gerar novos objetivos até encontrar a solução. Equivale à busca por redução de problemas, onde os problemas (objetivos) são “quebrados” em subproblemas (novos objetivos). A Figura 30 apresenta um exemplo de encadeamento regressivo, onde os nodos da árvore de pesquisa em cinza são os problemas primitivos, já resolvidos, e os nodos em branco são problemas em aberto, ainda não resolvidos.

Figura 29 - Exemplo de encadeamento progressivo.

A. A → B. ...

Modus Ponens

A. A → B. B. ...

Banco de Conhecimento 1) Se B e C então A. 2) Se D ou E então B. 3) Se F e D então C. 4) D. 5) F.

Objetivo (problema inicial)

A

Árvore de Pesquisa

Obs.: o usuário pode ser tratado como uma extensão do Banco de Conhecimento.

2) 3)

Se B e C então A. Se D ou E então B. Se F e D então C. D. F.

. . . . . .

Se B e C então A. Se D ou E então B. Se F e D então C. D. F. B.

Se B e C então A. Se D ou E então B. Se F e D então C. D. F. C.


Figura 30 - Exemplo de encadeamento regressivo.

A escolha da direção do raciocínio depende de vários aspectos: o quantidade de fatos iniciais x quantidade de conclusões alternativas o quantidade média de regras elegíveis a cada ciclo o necessidade de processamento interativo o necessidade de justificar o resultado o natureza do problema:

− deduzir conseqüências a partir de fatos; − comprovar hipóteses buscando indícios.

ÿ Estratégia de Pesquisa - pode ser: o em profundidade; o em extensão; o heurística.

ÿ Utilização de Meta-conhecimento - é o conhecimento do especialista de como deve ser utilizado o conhecimento, influindo no modo como o conhecimento deve ser tratado em alguma parte do raciocínio. Exemplo: ativação de um conjunto de regras e fatos específicos sob uma certa condição.

ÿ Análise de diferença - identifica regras que diminuem a diferença entre o conhecimento atual e o objetivo. Métodos de tratamento de Conhecimento Incompleto O tratamento de conhecimento incompleto pode ser feito com a introdução da noção de valores “default” e com operações lógicas com o desconhecido, conforme a tabela verdade abaixo.

A B ¬¬A A e B A ou B F F V F F F V V F V F D V F D V F F F V V V F V V V D F D V D F D F D D V D D V D D D D D

Figura 31 - Tabela verdade incluindo o valor desconhecido (D).

Banco de Conhecimento Se B e C então A. Se D ou E então B. Se F e G então C. D. F.

Objetivo (problema inicial)

A. ? ?

A

B C

F G E D

Árvore de Pesquisa

Obs.: o usuário pode ser tratado como uma extensão do Banco de Conhecimento.


Métodos de tratamento da 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 implementação é feita pela quantificação do grau de certeza do conhecimento, conforme o exemplo apresentado na Figura 32.

Fator de Certeza Significado 100 Definitivamente certo 80 Quase Certo 60 Provável 30 Há evidências 20 0

-20 Ignorado

-40 Há evidências contra -60 Provavelmente não -80 Quase certo que não

-100 Definitivamente não

Figura 32 - Escala do grau de certeza do conhecimento no MYCYN Forma de Inferência

� Fator de certeza (FC) da conclusão de uma regra = (FC(conjunto de antecedentes) * FC(regra)) / 100 � FC(conjunto de antecedentes) = min(FCs dos antecedentes) se antecedentes conjuntivos (unidos pelo “E”) ou

= max(FCs dos antecedentes) se antecedentes disjuntivos (unidos pelo “OU”) � Várias regras inferem a mesma conclusão - abaixo são apresentadas três formas de cálculo com um exemplo na

figura Figura 33.

a) FC(conclusão) = max(FCs das conclusões das regras)

b) FC(conclusão) = média(FCs das conclusões das regras)

c) FC(conclusão) = x + ((100 – x) * y / 100) se ambos (x e y) são positivos (técnicas probabilísticas)

Figura 33 - Exemplo de cálculo quando várias regras inferem a mesma conclusão. 6.3. Alguns Exemplos de Sistemas Especialistas

Banco de Conhecimento Resultado do cálculo do FC das Conclusões Formas de tratar a situação Observação Como pode ser observado, as diferentes formas de tratar a situação apresentam uma grande variação.

1. Se A então B FC(80). 2. Se A e C então B FC(70). 3. Se A ou D então B FC(60). 4. B FC(60). 5. B FC(30). 6. B FC(40).

Regra FC(B) 1. 48 2. 21 3. 36

Forma FC(B) a) Max 48 b) Média 35 c) Probabilidade 74


Os sistemas especialistas representam uma área onde a IA conseguiu bons resultados. Alguns sistemas fizeram, e continuam fazendo, muito sucesso comercialmente, resolvendo de maneira bastante satisfatória os problemas para os quais eles foram criados. MYCIN

O MYCIN foi um dos primeiros e mais conhecidos sistemas especialistas e é considerado um marco na IA. Foi criado inicialmente para diagnosticar e sugerir tratamento para doenças no sangue e desenvolvido na Universidade de Stanford, a partir de 1972. A principio era essencialmente um projeto acadêmico, mas influenciou enormemente a maioria dos sistemas especialistas que estavam por vir.

O MYCIN usa o encadeamento para trás (backward) para descobrir que organismos estavam presentes no sangue; depois ele usava o encadeamento para frente (forward) para raciocinar sobre o regime de tratamento.

O MYCIN tenta atingir seu projeto de recomendar uma terapia para um determinado paciente encontrando primeiro a causa da doença do paciente. Para atingir objetivos de nível mais alto do diagnóstico, ele procura regras cujos lados direitos sugiram doenças. Depois ele usa os lados esquerdos dessas regras (as precondições) para definir sub-objetivos cujos êxitos permitirão que as regras sejam invocadas. Esses sub-objetivos são novamente casados com as regras, e suas precondições são usadas para estabelecer mais sub-objetivos. PROSPECTOR

O PROSPECTOR é um sistema especialista que dá conselhos sobre a exploração de minerais. Foi criado no final da década de 70 pela SRI International. É um sistema digno de ser mencionado pelas seguintes razões: primeiro, ele se propõe a resolver problemas de extrema dificuldade, até mesmo os melhores especialistas disponíveis (geólogos principalmente) não executam essa tarefa com um alto grau de certeza; segundo, ele ilustra uma abordagem bastante diferente para sistemas especialistas (manipulação de probabilidades).

As regras no PROSPECTOR são do tipo Se: magnetita ou pinta em forma disseminada ou em veios está presente Então: (2,-4) há mineralização e textura favoráveis ao estágio propilítico.

No PROSPECTOR, cada regra contém duas estimativas de confiança. que variam de -5 a 5. A primeira indica até que ponto a

presença da evidência descrita na condição da regra sugere a validade da conclusão da regra. Na regra do PROSPECTOR mencionada, o número 2 indica que a presença da evidência é suavemente encorajadora. A segunda estimativa de confiança mede até que ponto a evidência é necessária para a validade da conclusão, ou em outras palavras, até que ponto a falta da evidência indica que a conclusão não é válida. No exemplo anterior, o número -4 indica que a ausência de evidência é fortemente desencorajadora para a conclusão. XCON ou R1

Enquanto o MYCIN influenciava bastante o desenvolvimento de sistemas especialistas na área acadêmica, um outro sistema clássico, o Ri, depois chamado XCON, despertou mais o interesse no mundo comercial. Trata-se de um sistema que configura os sistemas DEC VAX. Suas regras são do tipo: Se: o contexto mais atual é a distribuição de dispositivos barramento massbus, E há um drive de disco de porta única que ainda não foi atribuído a um barramento massbus, E não há nenhum drive de disco de porta única sem designação, E

o número de dispositivos que cada barramento massbus deve suportar é conhecido, E há um barramento massbus ao qual foi atribuído pelo menos um drive de disco e que deve suportar drives adicionais,

E o tipo de cabo necessário para conectar o drive de disco ao dispositivo anteriormente no barramento massbus é

conhecido Então: atribua o drive ao barramento massbus DENDRAL

O META-DENDRAL, criado em 1978, foi o primeiro programa a usar técnicas de aprendizagem para construir automaticamente regras para um sistema especialista. Ele criava regras para serem usadas pelo DENDRAL, cuja tarefa era determinar a estrutura de compostos químicos complexos. O META-DENDRAL era capaz de induzir suas regras com base em um conjunto de dados sobre espectrometria de massa: desse modo, ele conseguia identificar as estruturas moleculares com precisão bastante alta. 6.4. Ferramentas de Desenvolvimento de Sistemas Especialistas


Inicialmente, cada sistema especialista era criado a partir do nada, em geral em E/SE. Mas, depois de vários sistemas terem sido desenvolvidos, ficou claro que esses sistemas tinham muito em comum. Em particular. devido ao fato de os sistemas serem construídos como um conjunto de representações declarativas (em sua maioria, regras) combinadas com um interpretador dessas representações, era possível separar o interpretador do conhecimento específico do domínio da aplicação e assim criar uni sistema que podia ser usado para elaborar novos sistemas especialistas através da adição de novos conhecimentos, correspondentes ao novo domínio do problema. Os interpretadores resultantes são chamados de shell (ferramenta). No início, um exemplo de ferramenta que teve grande influência é o EMYCIN (Empty MYCIN), derivado do MYCIN.

Existem atualmente vários novas ferramentas comercialmente disponíveis, que servem de base para muitos dos sistemas especialistas que estão sendo desenvolvidos correntemente. Com essas ferramentas, a representação do conhecimento e o raciocínio são muito mais flexíveis do que nos primeiros sistemas especialistas criados. Elas tipicamente suportam regras, quadros, sistemas de manutenção da verdade e uma série de outros mecanismos de raciocínio.

As primeiras ferramentas de sistemas especialistas ofereciam mecanismos para a representação do conhecimento, raciocínio e explicações. Mais tarde, foram acrescentadas ferramentas para a aquisição de conhecimento. Mas, com o aumento das experiências com esses sistemas para solucionar problemas do mundo real, ficou claro que as ferramentas dos sistemas especialistas precisavam fazer alguma coisa a mais. Eles precisavam, por exemplo, facilitar a integração dos sistemas especialistas com outros tipos de programas. acessar bancos de dados de corporações; e esse acesso precisa ser controlado como em outros sistemas. Eles em geral estão embutidos em programas aplicativos maiores, que usam praticamente técnicas de programação convencional. Então, uma das características importantes que uma ferramenta precisa ter é uma interface entre o sistema especialista, escrita com a ferramenta e que seja fácil de usar, e um ambiente de programação maior e provavelmente mais convencional.

A Figura 34 classifica os diferentes software que podem ser utilizados no desenvolvimento de SE. As linguagens de alto nível são orientadas para a manipulação simbólica, dando flexibilidade e permitindo ajustar o SE às particularidades de cada domínio de problemas, entretanto exige grande experiência em computação. Os ambientes são um meio termo entre as linguagens de alto nível e as ferramentas, e oferecem código testado e depurado para implementar coisas úteis na construção de SE. As ferramentas já possuem uma forma de representação de conhecimento e uma máquina de inferência bem definidos, assim são fáceis de utilizar e permitem uma grande velocidade de desenvolvimento, permitindo que o pessoal envolvido se concentre na montagem da base de conhecimento.

Figura 34 - Software para o desenvolvimento de SE

FLEXIBILIDADE AJUSTE

LINGUAGENS DE Pascal ALTO NÍVEL Lisp Prolog Interlisp AMBIENTES OPS5 Kee, Lops, Art FERRAMENTAS Emycin, S1, M1

FACILIDADE

VELOCIDADE DE DESENVOLVIMENTO


6.5. Aquisição de Conhecimento Como são construídos os sistemas especialistas? Tipicamente, um engenheiro do conhecimento entrevista um especialista no

domínio da aplicação para tentar extrair o conhecimento especialista, que é então traduzido em regras. Depois que o sistema inicial estiver pronto. ele precisa ser iterativamente refinado até aproximar-se do nível de desempenho de um especialista. Este processo é caro e lento, portanto vale a pena procurar maneiras mais automatizadas de construir bases de conhecimento especialistas. Embora ainda não exista nenhum sistema de aquisição de conhecimento totalmente automatizado, há muitos programas que interagem com os especialistas dos domínios para extrair conhecimento especializado com eficiência. Estes programas oferecem suporte às seguintes atividades:

� Inserção de conhecimento; � Manutenção da consistência da base de conhecimento; � Garantia de completeza da base de conhecimento.

6.6. Problemas

Alguns dos principais problemas enfrentados pelos sistemas especialistas atuais são: � Fragilidade: Como os sistemas especialistas só têm acesso a conhecimentos altamente específicos do domínio, eles não

podem contar com conhecimentos mais genéricos quando a necessidade surge. Por exemplo, suponha que cometamos um erro na entrada de dados para um sistema especialista médico e que descrevamos um paciente com 130 anos e 20 quilos. A maioria dos sistemas não seria capaz de adivinhar que podemos ter invertido os dois campos. já que os valores não são muito plausíveis. Alguns sistemas representam uma tentativa de remediar esse problema fornecendo um substrato de conhecimentos de senso comum, sobre o qual sistemas especialistas específicos podem ser criados.

� Falta de Meta-conhecimento Os sistemas especialistas não têm conhecimentos muito sofisticados sobre sua própria operação. Eles normalmente não conseguem raciocinar sobre seu próprio escopo e restrições, dificultando ainda mais a tarefa de lidar com a sua fragilidade.

� Aquisição de Conhecimento Apesar do desenvolvimento de ferramentas, a aquisição ainda continua sendo um dos maiores obstáculos à aplicação da tecnologia dos sistemas especialistas a novos domínios.

� Validação: Medir o desempenho de um sistema especialista é difícil, porque não sabemos como quantificar o uso do conhecimento. Certamente é impossível apresentar provas formais de correção para sistemas especialistas. Uma coisa que podemos fazer é comparar esses sistemas com especialistas humanos em problemas do mundo real Por exemplo. o MYCIN participou de um painel de especialistas para avaliar dez casos selecionados de meningite, obtendo resultados melhores do que qualquer um de seus concorrentes humanos.

6.7. Conclusões

Desde a metade da década de 60, quando começaram os trabalhos sobre os sistemas que hoje conhecemos como especialistas, muito progresso foi feito na construção de tais programas. As experiências obtidas com esses esforços sugerem as seguintes conclusões.

� Esses sistemas derivam sua potencialidade de uma grande quantidade de conhecimento especifico do domínio, e não de uma única técnica poderosa.

� Os sistemas bem-sucedidos têm muito conhecimento bem-definido sobre uma determinada área. Isto contrasta com o conhecimento amplo e de difícil definição que chamamos de senso comum. E mais fácil criar sistemas especialistas do que sistemas com senso comum.

� Um sistema especialista em geral é construído com a ajuda de um ou mais especialistas, que precisam estar dispostos a transferirem o seu conhecimento para o sistema.

� A transferência de conhecimento ocorre gradualmente, através de muitas interações entre o especialista e o sistema. O especialista nunca fornece de pronto o conhecimento correto ou completo.

� A quantidade de conhecimento exigida depende da tarefa. Ela pode variar de 40 regras a milhares delas. � A escolha da estrutura de controle para um determinado sistema depende das características especificas do sistema. � É possível extrair partes não-especificas do domínio, de sistemas especialistas existentes, e usá-las como ferramentas

para a criação de novos sistemas e novos domínios.

7. Engenharia de Conhecimento

O objetivo da Engenharia de Conhecimento é desenvolver sistemas de IA baseados em conhecimento através da modelagem dos processos cognitivos para resolução de problemas utilizados pelos especialistas em algum domínio.

A Engenharia de Conhecimento é uma tarefa artesanal, pois os métodos utilizados pelos especialistas são particulares e, as atividades dependem do tipo e do domínio do problema. Os profissionais envolvidos são

� Especialista; � Engenheiro de Conhecimento; � Programador.

7.1. Metodologias de Desenvolvimento

� Prototipação Construção incremental de protótipos do sistema, até que se torne funcional.

� Estruturado Projeto planejado e realizado em etapas que partindo das especificações chega diretamente à versão operacional do sistema.

� Misto O sistema é desenvolvido de forma estruturada, porém alguns módulos ou funções são construídos utilizando prototipação.

7.2. Atividades em um Sistema com IA

Figura 35 - DFD nível o do ciclo de vida de um projeto estruturado

5 Integração

de Sistemas

8 Análise do Hardware

3 Projeto da

Base Dados

7 Teste de Aceitação

6

Implementação Estruturada

4 Projeto

Estruturado

2 Análise

Estruturada

1 Integração

de Sistemas Usuário

Plano de Treinamento e Reorganização

Pedido ao Fabricante

Módulos Estruturados Estudo /

Viabilidade

Especificação

Estruturada

Interface com Usuário

Necessidades de Hardware

Entrada do Usuário

Configuração

Projeto de Consolidação

Plano de Testes

BD Lógico BD Físico

Sistema de Produção


Figura 36 - DFD nível o do ciclo de vida de um projeto com IA Objetivos adicionais por fase

1. Levantamento � Selecionar domínios apropriados para aplicações da IA. � Propor estratégias de curto e longo prazo para a integração da tecnologia de IA. � Analisar a relação custo / benefício da aplicação ao domínio. � Definir a abrangência e resultados. � Iniciar a definição da Base de Conhecimento (viabilidade).

5 Integração

de Sistemas

8 Análise do Hardware

3 Projeto da

Base Dados

7 Teste de Aceitação

6

Implementação Estruturada

4 Projeto

Estruturado

2 Análise

Estruturada

1 Integração

de Sistemas Usuário

Plano de Treinamento e Reorganização

Pedido ao Fabricante

Módulos Estruturados Estudo de

Viabilidade

Especificação Estruturada

Interface com Usuário

Necessidades de Hardware

Entrada do Usuário

Configuração

Projeto de Consolidação

Plano de Testes

BD Lógico

BD Físico

Módulo IA

10 Projeto da

BC

11 Projeto IA

9 Aquisição

do Conhecim.

12 Implement.

IA

Especificação BC física

Base de Conhecimento

Especificação BC lógica

Projeto IA

Especificação IA

Sistema de Produção


2. Análise Estruturada

� Elaborar um conjunto de DFDs com descrições narrativas dos processos (tarefas do especialista) e um dicionário de dados.

� Especificar os requerimentos de interface com o usuário. � Especificar os requerimentos de desempenho.

3. Projeto do Banco de Conhecimento

� Definir a forma de representar o conhecimento.

4. Projeto Estruturado � Definir a forma de raciocínio. � Definir a interface com o usuário. � Escolher o instrumento (linguagem, ambiente ou ferramenta).

5. Integração de Sistemas

6. Implementação

� Codificação do conhecimento de acordo com o método da ferramenta.

7. Teste de Aceitação 8. Análise do Hardware

9. Aquisição do Conhecimento

7.3. Etapas na Construção de um pequeno SE

Ainda não existe uma metodologia consolidada para a construção de SE, entretanto abaixo são enumerados as etapas com alguns detalhes do processo de construção de um SE pequeno. É importante observar que na construção de um SE pequeno freqüentemente os passos 1 e 2 são invertidos, pois é mais fácil identificar um problema que seja adequado a uma ferramenta previamente selecionada do que o contrário.

1. Selecionar um instrumento. Implica em comprometer-se implicitamente com vários aspectos relacionados ao desenvolvimento de um SE. No caso de uma ferramenta, os aspectos são: − Paradigma de consulta - corresponde ao tipo de problema que será solucionado, sendo os principais: diagnóstico

/ prescrição, planejamento e projeto. − Forma de Representação do Conhecimento: regras, objetos, etc. − Formas de Inferência. − Interface com o usuário: tipo, qualidade, tratamento de dúvidas, etc.

2. Identificar um problema e analisar as suas características. As principais características a serem avaliadas são: − Tempo de solução. − Tipo de comunicação. − Tipo de conhecimento que o sistema deverá incluir. − Volume de alternativas de solução.

3. Projetar o sistema. Esta etapa é a mais trabalhosa e demorada. Exige estudar e levantar o conhecimento que será utilizado pelo SE, o que implica fazer diversas entrevistas com os especialistas para identificar como eles trabalham ou raciocinam para resolver os problemas. − Descrição do sistema. − Diagramas de fluxo de consulta. − Tabelas.


4. Desenvolver um protótipo. − Criar o banco de conhecimento, o que exige conhecimento da sintaxe da linguagem de representação de

conhecimento. − Verificar fazendo algumas consultas. Esta atividade é importante porque serve para validar empiricamente o SE.

Além de entrar com situações reais para verificar se as soluções apresentadas pelo sistema são válidas, é necessário entrar com valores inválidos e utilizar várias alternativas de resposta, como “Por que?” ou indicar dúvida (incerteza).

5. Expandir, verificar e revisar o sistema até cumprir o seu papel. − Incluir novas “peças” de conhecimento (regras, . ..). − Incluir o tratamento de conhecimento incompleto. − Incluir ou alterar o tratamento de incerteza. − Incluir ou refinar os mecanismos de ajuda ou explicação.

6. Manter e atualizar o sistema. Exemplo de desenvolvimento de um protótipo de SE: Este exemplo foi desenvolvido até a quanta etapa, portanto o protótipo apresenta várias deficiências que seriam corrigidas no decorrer da quinta etapa.

1. Selecionar um instrumento. O instrumento selecionado é o SINTA, uma ferramenta de desenvolvimento de SE bastante fácil de ser utilizada, permitindo

que o engenheiro de conhecimento se concentre na aplicação. O paradigma de consulta do Sinta é diagnóstico / prescrição, sendo que este paradigma pode ser utilizado na solução de uma

gama bastante grande de problemas. A forma de representação do conhecimento é baseada em regras, permitindo a definição de fatores de certeza. A inferência é

feita através de encadeamento regressivo das regras. A interface com o usuário tem uma forma padrão de pergunta, quando é necessário consultar o usuário sobre o valor de uma

variável, entretanto permite que cada pergunta seja alterada. A interface possui também tratamento de dúvidas através de um mecanismo de explicação. A explicação padrão é a apresentação da linha de raciocínio utilizada que exigiu a consulta ao usuário. Entretanto, o engenheiro de conhecimento pode incluir uma explicação não padrão.

2. Identificar um problema e analisar as suas características. O problema que será utilizado no exemplo é a seleção de meios instrucionais adequados para diferentes tipos de treinamento.

As características deste problema são: − Tempo de solução: até 30 minutos; − Tipo de comunicação: o especialista apresenta uma proposta verbalmente ou por escrito; − Tipo de conhecimento: o especialista utiliza regras e cálculos simples; − Volume de alternativas de solução: poucas alternativas, da ordem de dezenas de possibilidades.

O problema é adequado à ferramenta que foi selecionada. Para problemas com um grau de complexidade grande, o Sinta não poderia ser utilizado.

3. Projetar o sistema. O SE terá como objetivo aconselhar um cliente a respeito da seleção de meios instrucionais para um determinado

treinamento. Assim, é necessário estudar o assunto através de livros especializados e reunir-se com especialistas na área de treinamento para determinar os principais atributos da seleção de meios instrucionais. Segundo Tosti e Ball (em “A behavioral approach to instructional design and media selection”), é necessário discutir os aspectos do problema de treinamento, considerar como estes aspectos se relacionam com as características dos meios e indicar um ou mais meios instrucionais que resolvam o problema.

A 0 apresenta um diagrama do fluxo de consulta sobre meios instrucionais. Para elaborar este diagrama é necessário entender como o especialista trabalha e identificar quais são e a ordem das perguntas que ele faz ao cliente para resolver o problema. O diagrama facilita a elaboração das tabelas e a construção da base de conhecimento. No nosso caso, o especialista começa perguntando sobre a tarefa que os treinandos cumprirão após o treinamento. Depois, sobre como simular a execução da tarefa, pois um programa de treinamento ideal procura fazer com que se pratique as atividades previstas na tarefa. A seguir são considerados os aspectos instrucionais e as restrições orçamentárias. Ao final são recomendados de um a três meios eficazes respeitando o custo.


As tabelas servem para organizar o conhecimento que vai sendo levantado junto às fontes utilizadas. A tabela da Figura 38 apresenta os principais fatores que o especialista leva em conta para decidir quais meios são recomendados.

A Figura 39 faz uma análise levantando algumas das possíveis relações entre as ponderações apresentadas na Figura 38 e as recomendações que o especialista faria.

Se o especialista utilizar apenas estes fatores, é possível identificar quantas situações diferentes existem, através da multiplicação dos números de alternativas (respostas) de cada fator: 4 x 2 x 6 x 2 x 4 x 3 = 1152.

Figura 37 Fluxo de Consulta sobre meios instrucionais

Tarefa

Como simular a tarefa

Restrições orçamentárias

Considerações instrucionais

1 a 3 meios eficazes


Ponderações

de trabalho ou tarefa de ensino �

Situação do Estímulo o Ambiental o Pictória o Simbólica o Verbal

�Realimentação Instrucional

o Sim o Não

�Duração do Estimulo

o Breve o Persistente

�

Modificação da Apresentação o por Resposta o por Módulo o por Curso o Nenhuma �

Resposta Apropriada o Oculta o Seletiva o Construída o Oral o Motora o Afetiva

�

Orçamento de Treinamento o Pequeno (até R$ 10.000,00) o Médio (até R$ 50.000,00) o Grande (mais de R$ 10.000,00)

Figura 38 - Ponderações do modelo Tosti-Ball (simplificado)

N° Situação do Estímulo

Duração do Estímulo

Resposta Apropriada

Realimentação Instrucional

Modificação da

Apresentação

Orçamento de Treinamento

Recomendações

1 verbal breve oculta não nenhuma pequeno livro 2 verbal persistente seletiva

construída sim resposta

módulo pequeno estudo pessoal

3 verbal breve oculta não curso médio aula 4 verbal

simbólica pictória

breve oculta não curso médio aula com dispositivos

5 verbal pictória

breve oculta não módulo médio videocassete

6 verbal breve oral afetiva

sim módulo pequeno médio

prática com realimentação verbal

7 verbal breve oral afetiva

sim módulo médio grande

prática com reali-mentação por vídeo

8 ambiental persistente motora não módulo curso

grande Laboratório com experiências

9 verbal breve oculta não nenhuma pequeno áudio cassete 10 simbólica

verbal breve todas sim resposta médio

grande tutor humano

Figura 39 - Análise matricial de escolha do meio instrucional


A situação de estímulo é ... quando envolve ... ambiental modelo físico

estrutura objeto máquina instrumento

pictória figura fotografia diagrama ilustração vista

simbólica gráfico esquema números fórmulas

verbal ouvir conversa diálogo leitura texto

Figura 40 - Tabela de detalhamento da situação do estímulo.

A resposta apropriada é ... quando envolve ... oculta ouvir

ler observar meditar imaginar pensar

seletiva múltipla escolha associação

construída escrever desenhar datilografar

verbal

dizer algo conversar falar cantar

atividade motora edificar montar mover construir organizar dançar

afetiva emocionar-se simpatizar sentir mostrar afeição compreensivo manter a calma

Figura 41 - Tabela de detalhamento da resposta apropriada.


4. Desenvolver um protótipo. Esta etapa envolve criar o banco de conhecimento e verificar fazendo algumas consultas. O Sinta exige que se defina as variáveis e os respectivos domínios antes de entrar com as regras. O objetivo do SE é estabelecer uma ou mais recomendações, então criou-se uma variável chamada “Recomendação” cujo

domínio são as possíveis recomendações dos especialistas, conforme a tabela da Figura 39. Para se criar as regras, inicialmente foi utiliza a tabela da Figura 39, resultando nas regras de 1 a 10, como listado abaixo. Na

lógica o operador de conjunção (“E”) possui maior precedência que o operador de disjunção (“OU”), entretanto, para facilitar a formação das regras, o Sinta utiliza como padrão o inverso: o operador de disjunção possui maior precedência que o operador de conjunção.

As tabelas da Figura 40 e da Figura 41 foram utilizadas para criar as demais regras: de 11 a 20. REGRAS Regra 1 - Recomendação é livro SE situação do estímulo = verbal E duração do estímulo = persistente E resposta apropriada = oculta E realimentação instrucional = não E modificação da apresentação = nenhuma E orçamento de treinamento = pequeno OU orçamento de treinamento = médio ENTÃO recomendação = livro Regra 2 - Recomendação é estudo pessoal SE situação do estímulo = verbal E duração do estímulo = persistente E resposta apropriada = seletiva E resposta apropriada = construída E realimentação instrucional = sim E modificação da apresentação = por resposta OU modificação da apresentação = por módulo E orçamento de treinamento = pequeno ENTÃO recomendação = estudo pessoal Regra 3 - Recomendação é aula SE situação do estímulo = verbal E duração do estímulo = breve E resposta apropriada = oculta E realimentação instrucional = não E modificação da apresentação = por curso E orçamento de treinamento = pequeno OU orçamento de treinamento = médio ENTÃO recomendação = aula Regra 4 - Recomendação é aula com dispositivos SE situação do estímulo = verbal OU situação do estímulo = simbólica OU situação do estímulo = pictória E duração do estímulo = breve E resposta apropriada = oculta E realimentação instrucional = não E modificação da apresentação = por curso


E orçamento de treinamento = médio ENTÃO recomendação = aula com dispositivos Regra 5 - Recomendação é videocassete SE situação do estímulo = verbal OU situação do estímulo = pictória E duração do estímulo = breve E resposta apropriada = oculta E realimentação instrucional = não E modificação da apresentação = por módulo E orçamento de treinamento = médio ENTÃO recomendação = videocassete Regra 6 - Recomendação é prática com realimentação verbal SE situação do estímulo = verbal E duração do estímulo = breve E resposta apropriada = verbal OU resposta apropriada = afetiva E realimentação instrucional = sim E modificação da apresentação = por módulo E orçamento de treinamento = pequeno OU orçamento de treinamento = médio ENTÃO recomendação = prática com realimentação verbal Regra 7 - Recomendação é prática com realimentação por vídeo SE situação do estímulo = verbal E duração do estímulo = breve E resposta apropriada = verbal OU resposta apropriada = afetiva E realimentação instrucional = sim E modificação da apresentação = por módulo E orçamento de treinamento = médio OU orçamento de treinamento = grande ENTÃO recomendação = prática com realimentação por vídeo Regra 8 - Recomendação é laboratório com experiências SE situação do estímulo = ambiental E duração do estímulo = persistente E resposta apropriada = motora E realimentação instrucional = não E modificação da apresentação = por módulo OU modificação da apresentação = por curso E orçamento de treinamento = grande ENTÃO recomendação = laboratório com experiências Regra 9 - Recomendação é áudio cassete SE situação do estímulo = verbal E duração do estímulo = breve E resposta apropriada = oculta E realimentação instrucional = não E modificação da apresentação = nenhuma E orçamento de treinamento = pequeno ENTÃO recomendação = audio cassete Regra 10 - Recomendação é tutor humano


SE situação do estímulo = simbólica OU situação do estímulo = verbal E duração do estímulo = breve E resposta apropriada = afetiva OU resposta apropriada = construída OU resposta apropriada = motora OU resposta apropriada = oculta OU resposta apropriada = seletiva OU resposta apropriada = verbal E realimentação instrucional = sim OU modificação da apresentação = por resposta E orçamento de treinamento = médio OU orçamento de treinamento = grande ENTÃO recomendação = tutor humano Regra 11 - Situação de estímulo é ambiental SE estímulo = modelo físico OU estímulo = estrutura OU estímulo = objeto OU estímulo = máquina OU estímulo = instrumento OU estímulo = ambiental ENTÃO situação do estímulo = ambiental Regra 12 - Situação de estímulo é pictória SE estímulo = figura OU estímulo = fotografia OU estímulo = diagrama OU estímulo = ilustração OU estímulo = vista OU estímulo = pictória ENTÃO situação do estímulo = pictória Regra 13 - Situação de estímulo é simbólica SE estímulo = gráfico OU estímulo = esquema OU estímulo = números OU estímulo = fórmulas OU estímulo = simbólica ENTÃO situação do estímulo = simbólica Regra 14 - Situação de estímulo é verbal SE estímulo = ouvir OU estímulo = conversa OU estímulo = diálogo OU estímulo = leitura OU estímulo = texto OU estímulo = verbal ENTÃO situação do estímulo = verbal Regra 15 - Resposta apropriada é oculta SE resposta = ouvir OU resposta = ler OU resposta = observar OU resposta = meditar


OU resposta = imaginar OU resposta = pensar OU resposta = oculta ENTÃO resposta apropriada = oculta Regra 16 - Resposta apropriada é seletiva SE resposta = múltipla escolha OU resposta = associação OU resposta = seletiva ENTÃO resposta apropriada = seletiva Regra 17 - Resposta apropriada é construída SE resposta = escrever OU resposta = desenhar OU resposta = datilografar ENTÃO resposta apropriada = construída Regra 18 - Resposta apropriada é verbal SE resposta = dizer algo OU resposta = conversar OU resposta = falar OU resposta = cantar OU resposta = verbal ENTÃO resposta apropriada = verbal Regra 19 - Resposta apropriada é motora SE resposta = edificar OU resposta = montar OU resposta = mover OU resposta = construir OU resposta = organizar OU resposta = dançar OU resposta = atividade motora ENTÃO resposta apropriada = motora Regra 20 - Resposta apropriada é afetiva SE resposta = emocionar-se OU resposta = simpatizar OU resposta = sentir OU resposta = mostrar aveição OU resposta = comprensivo OU resposta = calma ENTÃO resposta apropriada = afetiva PERGUNTAS Variável:duração do estímulo Pergunta:"Qual é a duração do estímulo?" Variável:estímulo Pergunta:"Qual é a situação do estímulo que a pessoa receberá?" Variável:modificação da apresentação Pergunta:"Quando é feita a modificação da apresentação (se houver) ?" Motivo:"Informar se o modo de apresentação do conteúdo do "curso é alterado e em que momento isto é feito. " "Exemplo: se a apresentação do conteúdo deve ser


"alterada conforme a resposta do aluno, então escolha "a opção "por resposta". Variável:orçamento de treinamento Pergunta:"Qual é o orçamento do treinamento?" Motivo:"Informe " ""pequeno" se será gasto menos de R$ 100,00 ""médio" se será gasto menos de R$ 1.000,00 ""grande" se será gasto mais de R$ 1.000,00 Variável:realimentação instrucional Pergunta:"Existe realimentação instrucional?" Variável:resposta Pergunta:"Qual é o tipo de resposta que a pessoa deve fornecer?"

Documents

CIC284 - Inteligência Artificial em Controle e Automaçãowalderson.com/2010-2/univag/intartaplicada/01-Apostila.pdf · UNIVERSIDADE FEDERAL DE OURO PRETO INSTITUTO DE CIÊNCIAS