Baixe o app para aproveitar ainda mais
Prévia do material em texto
INTELIGÊNCIA ARTIFICIAL João Luís Tavares da Silva 2INTELIGÊNCIA ARTIFICIAL SUMÁRIO Esta é uma obra coletiva organizada por iniciativa e direção do CENTRO SUPERIOR DE TECNOLOGIA TECBRASIL LTDA – Faculdades Ftec que, na forma do art. 5º, VIII, h, da Lei nº 9.610/98, a publica sob sua marca e detém os direitos de exploração comercial e todos os demais previstos em contrato. É proibida a reprodução parcial ou integral sem autorização expressa e escrita. CENTRO UNIVERSITÁRIO UNIFTEC Rua Gustavo Ramos Sehbe n.º 107. Caxias do Sul/ RS REITOR Claudino José Meneguzzi Júnior PRÓ-REITORA ACADÊMICA Débora Frizzo PRÓ-REITOR ADMINISTRATIVO Altair Ruzzarin DIRETORA DE EDUCAÇÃO A DISTÂNCIA (EAD) Lígia Futterleib Desenvolvido pela equipe de Criações para o ensino a distância (CREAD) Coordenadora e Designer Instrucional Sabrina Maciel Diagramação, Ilustração e Alteração de Imagem Julia Oliveira Revisora Luana dos Reis SISTEMAS DE INFORMAÇÃO INTELIGENTES 3 Conceitos Básicos 5 Dado-Informação-Conhecimento 6 Representação do conhecimento 9 Estados e busca heurística 10 Lógica 10 Regras de produção 12 Frames e scripts 13 Redes semânticas 14 Computação Evolutiva 17 Síntese 18 RESOLUÇÃO DE PROBLEMAS 20 Formulação do problema 23 Técnicas de resolução 25 Busca competitiva 40 Síntese 47 SISTEMAS ESPECIALISTAS 50 Síntese 63 ALGORITMOS GENÉTICOS 66 Princípios básicos 69 Síntese 81 APRENDIZAGEM AUTOMÁTICA 83 Aprendizagem supervisionada 86 Redes neurais artificiais 93 Síntese 108 AGENTES INTELIGENTES E SISTEMAS MULTIAGENTES 111 Síntese 147 Referências 150 3INTELIGÊNCIA ARTIFICIAL SISTEMAS DE INFORMAÇÃO INTELIGENTES Esta disciplina tem como objetivo introduzir os alunos no contexto de Inteligência Artificial, compreendendo seus conceitos teóricos e aplicando-os a problemas reais. 4INTELIGÊNCIA ARTIFICIAL Iniciamos pela apreciação de Russel e Norvig sobre a In- teligência Artificial: “We call ourselves Homo sapiens – man the wise – because our intelligence is so important to us. For thousands of years, we have tried to understand how we think; that is, how a mere handful of matter can perceive, understand, predict, and manipulate a world far larger and more complicated than itself. The field of artificial intelligence, or AI, goes further still: it attempts not just to understand but also to build intelligent entities” (Russel & Norvig, 2004). Se você ainda não entendeu esta apreciação, copie e cole o parágrafo no Google Translator para ter uma ideia de uma pequena parte da IA em ação. Agora, podemos recuar um pouco no tempo e descobrir que construir entidades inteligentes não é um campo novo na história da humanidade. Por exemplo, o brilhante matemático e astrônomo Gerbert d’Aurillac (945-1003), que subiu ao trono papal como Silvestre II em 999 D.C., constrói um oráculo na forma de uma cabeça mecânica em bronze, provável ancestral dos modernos robôs (LaGrandeur, 2013). Depois que Blaise Pascal cria a Pascalene, primeira má- quina de calcular em 1642, e Leibniz inclui a multiplicação e a divisão (1673), surgem brinquedos mecânicos simulando a vida através dos chamados autômatos, como por exemplo, o pato mecânico de Jacques de Vaucanson (1738). Independente da tecnologia, a curiosidade sobre o fun- cionamento da vida sempre motivou o homem a buscar uma forma de imitação da criação. O advento eletrônico estimula o conhecimento humano e os computadores já surgem com perspectivas inteligentes. Embora os primeiros computadores, a válvula eletrônica, tenham surgido na década de 1940; já em 1950 Marvin Misky e Deam Edmonds, alunos de Harvard, constroem o primeiro computador de rede neural, o SNARC https://translate.google.com.br/?hl=pt-BR 5INTELIGÊNCIA ARTIFICIAL (Stochastic Neural Analog Reinforcement Calculator) e no mesmo ano, Alan Turing publica seu seminal artigo na “Compu- tational Machinery and Intelligence”, onde ele questiona sobre a inteligência dos computadores e apresenta seu famoso Teste de Turing (Russel & Norvig, 2004). Conceitos Básicos Definir inteligência é uma tarefa árdua e a Medicina, Psicologia e Ciências Cognitivas têm desvelado total esforço e energia ao longo de décadas nesta tarefa. Desde a ideia da faculdade ou capacidade de aprender e compreender, culminan- do nas inteligências múltiplas (Howard Gardner) e coletivas (Émile Durkheim, Pierre Lévy, entre outros). Russel e Norvig definem a Inteligên- cia Artificial segundo duas tendências básicas: baseado no pensamento e raciocí- nio onde o objetivo é desenvolver sistemas que pensam como seres humanos ou que pensam racionalmente; e, baseado no comportamento, onde o objetivo é de- senvolver sistemas que atuam como seres humanos ou que atuam racionalmente. Neste sentido, os conceitos variam conforme a abordagem adotada. Na Ta- bela 1, a dimensão horizontal representa a atividade de Pensar e Agir, enquanto a dimensão vertical determina se estas atividades são imitação dos seres huma- nos ou uma metáfora de comportamento racional. Tabela 1. Abordagens conceituais sobre Inteligência Artificial Como seres humanos Racionalmente Pe ns an do “Um esforço novo e interessante para fazer os computadores pensarem (…) máquinas com mentes, no sentido total e literal” (Haugeland, 1985). “A 'automatização' de atividades que associamos ao pensamento humano, atividades como a tomada de decisões, a resolução de problemas, o aprendizado…” (Bellman, 1978). “Inteligência Artificial é o estudo das faculdades mentais através do uso de modelos computacionais” (Charniak e McDermott, 1985). “É o estudo das computações que tornam possível perceber, raciocinar e agir” (Winston, 1992). “Uma máquina é inteligente se ela é capaz de solucionar uma classe de problemas que requerem inteligência para serem solucionados por seres humanos” (McCarthy e Hayes, 1987). Ag in do “É o estudo de como fazer os computadores realizarem tarefas em que, no momento, as pessoas são melhores” (Rich & Night, 1990). “A arte de criar máquinas que executam funções que exigem inteligência quando executadas por pessoas” (Kurzweil, 1990). “Inteligência Artificial é a parte da ciência da computação que compreende o projeto de sistemas computacionais que exibam características associadas, quando presentes no comportamento humano, à inteligência” (Barr & Feigenbaum, 1981). 6INTELIGÊNCIA ARTIFICIAL Para que os métodos de Inteligência Artificial possam ser utilizados para resolver um determinado problema, é impor- tante considerar: • a necessidade de que a solução para o problema em questão requeira a incorporação de conhecimento especializado sobre o domínio da aplicação; • qual o tipo de conhecimento envolvido e quais as principais ideias a serem consideradas; • a identificação das fontes do conhecimento a serem utilizadas e, como essas fontes podem ser acessadas; • qual a melhor forma de representar o conhecimento e como realizar o processo de aquisição e representação deste co- nhecimento. Em geral, problemas cuja soluções demandem uma sequên- cia de passos rígidos e bem definidos não são adequados para serem resolvidos com recursos de IA. Nestes casos deve-se pensar na possibilidade de codificação da solução, utilizando alguma técnica tradicional e alguma linguagem de programação orientada a objetos ou mesmo estruturada. Dado-Informação-Conhecimento Quais são os aspectos conceituais relacionados? Dado: » isolado; » independente do contexto; » fatos (símbolo, texto, figura). » Armazenados em sistemas de processamento de dados: • databases; • arquivos (imagens, texto). Informação: » dado combinado; » dado em contexto; » dado estruturado, (exemplo: por tópico); » catálogo (diretórios). Conhecimento: » individual (humano); » informação baseada em interpretação, cognição, experiência. 7INTELIGÊNCIA ARTIFICIAL Dado É um conjunto de fatos distintos e objetivos, relativos aos eventos (Davenport e Prusak, 1998). Uma sequênciade letras e números, figuras, palavras sem contexto (Wiig, 1993). Valores obtidos de sensores (Siemieniuch et al., 1999). Resumindo, um conjunto de elementos brutos, sem significado, desvinculado da realidade, de interpretação e contexto. Informação É um elemento cuja existência independe de atividades interpretativas, de entidades subjetivas (Dretske, 1981). São dados com significado, relevância e propósito (Drucker, 1999) ou contextualizados para fornecer uma solução em situações de decisão. Também se definem como dados aos quais foram atribuídos um contexto (Wiig,1993; Siemieniuch er al.,1999). Conhecimento O conhecimento inclui, mas não está limitado, às descri- ções, hipóteses, conceitos, teorias, princípios e procedimentos que são úteis ou verdadeiros. O conhecimento distingue-se da mera informação porque está associado a uma intencionalida- de. Consiste em verdades e crenças, perspectivas e conceitos, julgamentos e expectativas, metodologias e know-how. O co- nhecimento é acumulado, organizado, integrado e armazenado para aplicações específicas (Wiig, 1993). Sabedoria Se estendermos a noção contextual do próprio conheci- mento, atinge-se um estado da mente humana caracterizada por uma profunda compreensão e insight. A “sabedoria” é, frequentemente, mas não necessariamente, acompanhada por um extensivo conhecimento formal. 8INTELIGÊNCIA ARTIFICIAL Dado Informação Conhecimento Sabedoria Aprendizagem de situações históricas para previsão de catástrofes ou soluções. Usado conforme o contexto: • especulador no mercado futuro de frutas; • município atingido por uma cheia; • companhia de distribuição de energia elétrica; • operadores de agências de viagem. Uma tempestade (fora de época) atingiu o estado de Pernambuco. 100 ml de água Tabela 2. Pirâmide da hierarquia de representação 9INTELIGÊNCIA ARTIFICIAL Representação do conhecimento Computadores conhecem apenas a linguagem binária. A comunicação com os usuários é constantemente traduzida por compiladores. Como um artefato com vocabulários e linguagem tão reduzidos pode compreender o funcionamento do mundo? Para que uma entidade “artificial” consiga determinar as consequências de um ato pelo pensamento ao invés de sua realização, é preciso substituir o objeto ou fenômeno real por uma representação adequada. Portanto, a Representação de Conhecimento (RC) nada mais é do que uma aplicação da disciplina de Linguagens Formais para expressar de forma eficiente os conhecimentos de especialistas para serem acessados por usuários de um sis- tema inteligente. É um conjunto de combinações sintáticas e semânticas que nos possibilitam descrever uma determinada aplicação. A representação sintática define os símbolos que po- dem ser usados na representação do conhecimento e as maneiras como estes símbolos podem ser conseguidos. A representação semântica, por outro lado, determina qual significado está incorporado naqueles símbolos representados pela sintaxe. Qualquer que seja a forma de representação do conheci- mento, esta deve dispor de algum mecanismo computacional que possa processar o conhecimento representado. Quais são os principais mecanismos de representação do conhecimento para máquinas artificiais? • Estados e busca heurística. • Lógica. • Regras de produção. • Frames e scripts. • Redes semânticas. • Computação evolutiva. • Redes neurais artificiais. 10INTELIGÊNCIA ARTIFICIAL Estados e busca heurística A representação por estados de busca constrói estrutura de grafos onde o conhecimento específico do problema está na escolha do próximo nó a ser expandido. Uma função de avaliação estima o custo do caminho do nó atual até o objetivo (conhecida como heurística). A partir da estrutura construída, algoritmos percorrem o grafo usando várias técnicas de cami- nhamento, exemplificado na Figura 1. Figura 1: Exemplo de árvore de busca simples QUAL É O MELHOR PERCURSO ITU --> UBA I C S S S U 130km 80km 180km 180km 150km 230km 160km 100km 90km 100km Lógica A lógica matemática é usada para representar o conhe- cimento através de sentenças. Estas sentenças seguem regras sintáticas e semânticas específicas a cada corpo de dedução. Uma lógica define o significado destas sentenças. A se- mântica determina a “verdade” de cada sentença (lembram de Platão?) relativo a um mundo possível. Por exemplo, a semân- tica para a aritmética especifica que a sentença “x + y = 4” é verdadeira no mundo em que x=2 e y=2, mas é falsa em outro mundo, onde x=1 e y=1 (Russel & Norvig, 2004). Assim, cada sentença deve ser verdadeira ou falsa em cada mundo possível. Existem vários tipos de lógicas utilizadas para realizar deduções automáticas. Na lógica de predicados de primeira ordem, as proposições são formadas por predicados, argumen- tos, quantificadores e variáveis. A lógica de primeira ordem é de grande importância para a representação do conhecimento 11INTELIGÊNCIA ARTIFICIAL e tem sido o instrumento mais utilizado para a formalização do conhecimento em IA. Assim, o conhecimento é expresso na forma de sentenças que são provadas na forma de teoremas. Por exemplo, para provar o teorema “herbívoro(zebra)”, a partir das premissas: • animal(zebra); • vegetal(grama); • come (zebra, grama); Basta criar uma Regra de Inferência semântica que a teste em algum mundo possível (dados pelos três fatos acima): • xy[animal(x) AND come (x, y) AND vegetal(y) herbív Na lógica, a manipulação de símbolos representando as entidades, relações, eventos de domínio de aplicação deve ser um processo de construção plausível (sound) de novas sentenças a partir de outras sentenças, conforme esquema na Figura 2 (Russel & Norvig, 2004). Figura 2: Exemplo da tradução entre entidades no mundo real com sua representação simbólica 12INTELIGÊNCIA ARTIFICIAL Regras de produção A tomada de decisão humana pode também ser moldada por meio de regras de condição do tipo SE-ENTÃO. As regras expressam relacionamentos lógicos e equivalentes de definições para simular o raciocínio humano. Um exemplo simples pode ser ilustrado pela afirmativa: • “SE está chovendo ENTÃO carregue uma sombrinha”. Portanto, como comentado anteriormente, regras de pro- dução são estruturas do seguinte tipo: • SE <condições> ENTÃO <conclusões> FAÇA <ações> Onde: SE é uma lista de condições a serem satisfeitas (an- tecedente); ENTÃO é uma lista de conclusões; e FAÇA são as ações a serem executadas. Conclusões e ações são chamadas de consequentes. Em um processo de inferência, cada uma das condições da “lista de condições” deve ser verificada. Caso todas sejam satisfeitas, as conclusões serão consideradas verdadeiras e as ações serão executadas. Exemplo da análise de restritivos em instituições bancárias: SE tipo-restritivo = Ação de busca E pessoa analisada = Jurídica E quantidade de ocorrências < 2 ENTÃO Análise Restritivo = Não Relevante 13INTELIGÊNCIA ARTIFICIAL Frames e scripts O modelo de frames e scripts foi introduzido em 1975 na representação do conhecimento por Marvin Minsk (Russel & Norvig, 2004). Um frame é um agrupamento de conhecimentos relevan- tes a uma coisa, um indivíduo, uma situação ou um conceito (Minsky, 1975). Os frames integram conhecimento declarativo sobre objetos, eventos e conhecimento procedimental sobre como recuperar informações ou calcular valores. Um frame possui um nome que identifica o conceito por ele definido e consiste de um conjunto de atributos, chamados slots. Cada slot possui um nome que o identifica e um conjunto de atributos que apresentam propriedades que dizem respeito ao tipo de valores e às restrições de número que podem ser associadas a cada atributo. Essas propriedades são chamadas facetas. Um exemplo de representação está ilustrado na Figura 3. Figura 3: Exemplo de representação usando Frames (Luger,2013) 14INTELIGÊNCIA ARTIFICIAL Redes semânticas As Redessemânticas representam o conhecimento através de modelos formulados como grafos: • os nodos representam objetos (conceitos, ou situações); • os arcos representam relações binárias entre objetos. Originalmente, os nodos representam substantivos, adjeti- vos, pronomes e nomes próprios. Os arcos representam verbos transitivos e preposições. Indivíduos podem ser representados com nodos anônimos e indicando a inclusão destes indivíduos em sua respectiva classe. Permitem hierarquias de hereditariedade, através da transitividade da relação “é_um” (is_a). A Figura 4 exibe a modelagem da memória humana, segundo (Quillian, 1968). Figura 4: Modelagem da memória humana, segundo (Quillian, 1968). Concept-1 Concept-2 Concept-3 Concept-4 Concept-4 15INTELIGÊNCIA ARTIFICIAL Exemplo de representação para três diferentes definições da palavra “Planta”: • Estrutura viva que não é um animal, geralmente possui folhas e alimenta-se de água, terra ou ar. • Aparato usado para qualquer processo na indústria. • Colocar (uma semente, uma planta, etc.) na terra – Verbo “Plantar”. Representação gráfica: 16INTELIGÊNCIA ARTIFICIAL As redes semânticas se originam de estruturas Objeto-A- tributo-Valor que determinam os valores de certos atributos de um objeto: Por exemplo: representação de um carro da marca Fiat de cor verde: Algumas extensões possíveis para as redes semânticas são as: Objeto Atributo Valor possui has é is Carro Marca Cor Fiat Verde possui é é possui a. Relações de classificação: relações “é_um” (is_a). b. Relações de pertinência: relações “é_parte_de” (is_part). 17INTELIGÊNCIA ARTIFICIAL Combinando as estruturas Objeto-Atributo-Valor com as relações de classificação e pertinência, as redes semânticas modelam relações que podem representar o conhecimento do mundo. A Figura ilustra um extrato de conceito para alguns personagens conhecidos de desenho animado. Computação Evolutiva A computação evolutiva é um método probabilístico de busca para resolução de problemas (otimização), inspirada na teoria da evolução. A representação do conhecimento é feita através de conjuntos atributo-valor e o raciocínio é indutivo, durante uma fase de treinamento, dedutivo ou abdutivo durante a fase de aplicação, utilização. No paradigma evolutivo, a aquisição do conhecimento é feita através de aprendizagem e é baseada na Natureza, onde seres mais adaptados ao ambiente sobrevivem e suas caracte- rísticas genéticas são herdadas. A formalização básica é que o indivíduo representa a solução de um problema e o sistema faz evoluir um conjunto de indivíduos mais adaptados através de funções de cruzamento; e mutação através de sucessivas gerações. 18INTELIGÊNCIA ARTIFICIAL Síntese Neste primeiro contato com a área de Inteligência artificial, resumiu-se algumas técnicas prin- cipais de representação do conhecimento. Baseado nos conceitos apresentados aqui e nas premissas iniciais de que uma máquina é inteligente se ela é capaz de solucionar uma classe de problemas que requerem inteligência para serem solucionados por seres humanos, esta unidade focou na forma como uma representação do mundo deve ser definida para que um artefato artificial consiga perceber os elementos de resolução de um problema complexo. Ao mesmo tempo, algumas áreas principais foram apresentadas, as quais serão aprofundadas nos próximos encontros, sem abranger todos os temas da Inteligência artificial. 19INTELIGÊNCIA ARTIFICIAL Execícios • Baseado no conteúdo acima, construa exemplos de dado-informação-conhecimento mais próximos do seu cotidiano. • Diferencie atributos e elementos em cada exemplo dos enunciados que você criou, que possam caracterizar o conhecimento, diferenciando-o de dado ou informação. • Pesquise a definição clássica de conhecimento de Platão. Esta definição de Platão pode ser formalizada como proposições na concepção de Aristóteles? Descubra... 20INTELIGÊNCIA ARTIFICIAL RESOLUÇÃO DE PROBLEMAS Resolver problemas é a habilidade básica de um ser inteligente. Veremos como encontrar uma sequência de ações que atinja um objetivo, quando nenhuma ação isolada é capaz de fazê-lo. 21INTELIGÊNCIA ARTIFICIAL “Para poder sobreviver, um organismo necessita ou blin- dar-se (como uma árvore ou um marisco) e ‘esperar pelo me- lhor’, ou então desenvolver métodos para escapar de possíveis danos, indo para vizinhanças melhores. Se você escolher esta última opção, você se confrontará com o problema primordial que todo agente precisa continuamente resolver: e agora, o que devo fazer?” (Dennett, 1991). De um modo informal, problemas estão relacionados à resolução de tarefas humanas, tais como: • aquisição de informações (sentidos); • processamento de informações (raciocínio); e, • ações no meio exterior (capacidade de agir). Mais formalmente, um problema constitui-se em uma coleção de informações (conhecimento, regras, objetivos) que serão usadas para decidir o que fazer (solução). Apenas alguns exemplos ilustrativos de problemas típicos são: Toy Problems: Jogos de tabuleiros: • problema das n rainhas, • Damas, Xadrez, Go, Gamão, etc. Jogos combinatórios: • n-puzzle ou Taquin; • Criptoaritmética, Palavras cruzadas; • Canibais e missionários. Problemas reais: Cálculo de rotas: • rotas em redes de computadores; • sistemas de planejamento de viagens; 22INTELIGÊNCIA ARTIFICIAL • planejamento de rotas de aviões; • caixeiro viajante; • jogos de computadores (rotas dos personagens). Alocação (Scheduling): • Salas de aula; • máquinas industriais (job shop). Projeto de VLSI: • Cell layout; • Channel routing. Navegação de Robôs Sequência de montagem. São características da definição de problemas: • Decomponível: pode ser dividido em subproblemas. • Passos podem ser desfeitos ou ignorados: deve-se avaliar o custo de voltar atrás. • Universo do problema é imprevisível: pode-se fazer uso da probabilidade. • Solução absoluta ou relativa: existem problemas com solu- ções ótimas. • A base de conhecimento é consistente internamente: modelo da realidade confere com o objeto ou é uma aproximação, ou se apenas restringe a busca. • Grande volume de conhecimento. • Interage com o usuário. 23INTELIGÊNCIA ARTIFICIAL A atividade de resolução de problemas consiste em decidir o que fazer, encontrando sequências de ações que levem a um objetivo (estado) desejado. Podemos planejar a resolução de qualquer problema seguindo as seguintes etapas: • Formular o problema. • Analisar o problema. • Identificar o conhecimento necessário. • Escolher a técnica de resolução mais adequada. Formulação do problema O primeiro passo para solucionar um problema é criar uma descrição formal manipulável para o problema. Esta descrição deve conter: • definição de um espaço de estados possíveis; • especificação dos estados iniciais; • especificação de um conjunto de estados que sejam aceitáveis como soluções (estados objetivos); • especificação do conjunto de ações disponíveis (regras ou operadores). Mais formalmente em IA, um problema é definido em termos de: • um espaço de estados possíveis, incluindo: ◊ um estado inicial; ◊ um (ou mais) estado finais = objetivo. » Exemplo: dirigir de Porto Alegre a Caxias do Sul. » Estado inicial: estar em Porto Alegre. » Estado final: estar em Caxias do Sul. » Espaço de estados: todas as cidades (x,y) da região. 24INTELIGÊNCIA ARTIFICIAL ◊ A descrição de um conjunto de ações disponíveis ao agente de resolução. Por exemplo, move(x,y), in(z), etc. ◊ Descrição do que cada ação faz, ou seja, um modelo de transição de estados, que permita passar de um estado a outro. » Exemplo: {in(x), move(x,y) = in(y)}, considerando que existe um caminho válido entre x e y. ◊ Um teste objetivo para se determinar se o estado atual pertence ao conjunto de estados finais. ◊ Uma função de utilidade, ou função de custo de caminho, que indique a qualidade do resultado. Geralmente a solução de um problema é representadopelo cami- nho que parte do estado inicial até um dos estados finais (objetivos). Vamos a um exemplo mais completo, formulando o pro- blema do Jogo de Xadrez: • Espaço de estados: uma matriz 8x8 (numerados 1-8 e a-h) onde cada posição possui um símbolo representando uma peça. • Operadores: regras de movimentação do xadrez, por exemplo, 1.d4 d5 2. c4 c6 3. cxd5 cxd5 4. Cc3 Cc6 5. Cf3 Cf6; etc. • Estado inicial: posição oficial de abertura do xadrez: • Estado final: qualquer estado onde o rei adversário está sendo atacado e o adversário não possui movimentos válidos. • Teste objetivo: um estado pertencente ao conjunto de estados finais, a partir dos operadores: 1-0, 0-1 ou ½-½. • Custo do caminho: quantidade de posições examinadas, (Shannon, 1949): • cerca de 35 movimentos legais (fator de ramificação); • em média, cada jogador poderá realizar 40 movimentos; • exame da árvore completa: ~3580 posições. 25INTELIGÊNCIA ARTIFICIAL Técnicas de resolução Em geral, o espaço de solução de um problema ou o espaço de estados é computacionalmente representado por meio de um grafo, onde cada vértice corresponde a um estado e as arestas indicam transições entre dois estados. A busca pela solução de um problema compreende a navegação pelos vértices do grafo de estados associados, a fim de encontrar o(s) vértice(s) cujo(s) estado(s) corresponde(m) a solução do problema. Por exemplo, a Figura 6 ilustra exemplos de grafos de busca para o problema da viagem. Figura 6: Exemplo grafo para o problema da viagem P P S N F C 1 2 8 7 9 3 4 6 5 26INTELIGÊNCIA ARTIFICIAL As principais técnicas de resolução deste tipo de problema podem ser enumeradas como: • Busca: método de resolução de um problema sem abordagem direta, mas com uma estrutura disponível. • Utilização do conhecimento: método de resolução de problemas complexos explorando a estrutura dos objetos envolvidos. • Abstração: método que separa características e variações importantes de outras irrelevantes no processo de resolução. O modo como as regras a serem aplicadas são selecionadas é crítico para a rapidez da resolução e para a possibilidade de encontrar alguma solução para o problema, portanto, uma estratégia de busca deve, sobretudo: • Causar movimento: movimentar o processo de resolução dentro do espaço de estados. • Ser sistemática: explorar o espaço de estados de modo que evite repetir caminhos já percorridos e/ou desnecessários. • Tratar o problema da possível explosão combinatória na exploração. As estratégias de resolução se adequam ao tipo de pro- blema, definido em função do conhecimento do sistema, que tradicionalmente estão subdivididos em: • Problemas de estado único (single-state problems). • Problemas de múltiplos estados (multiple-state problems). • Problemas de contingência (contingence problems). • Problemas exploratórios (exploratory problems). 27INTELIGÊNCIA ARTIFICIAL Problemas de estado único Este tipo de problema é caracterizado por ter um mundo observável (pelo menos o estado inicial), determinístico, estático e discreto. O conhecimento associado ao problema indica que o agente sempre sabe em que estado ele está (mundo totalmente acessível), conhece o efeito de cada uma de suas ações e sabe se localizar depois de uma sequência qualquer de ações. Cada ação leva a um único estado possível do espaço de estados definidos na formulação original do problema. Vamos a um exemplo para o projeto de um robô aspirador de pó. Informalmente este problema é descrito através de um ambiente simples composto por duas salas A e B, onde um robô aspirador de pó precisa perceber se as salas estão limpas ou sujas e tem por objetivo manter as duas salas limpas. O robô também precisa se locomover entre as duas salas e executar a operação de aspiração como ilustrado na Figura 7. Figura 7: Mundo simples do robô aspirador Problemas de múltiplos estados As características deste tipo de problema possuem um mundo parcialmente observável (estado inicial não observável), determinís- tico, estático e discreto. Neste caso, o agente não tem conheci- mento total do ambiente, não sabe seu estado inicial (percepção deficiente), mas sabe o efeito de suas ações. Ou, de outra forma, pode não conhecer o efeito das ações (execução deficiente), mas conhece seu estado inicial. Aqui podemos fazer um paralelo com 28INTELIGÊNCIA ARTIFICIAL a famosa lei de Murphy: o robô pode correr o risco de aspirar poeira existente e pode jogar poeira quando o quarto já estiver limpo. Em todo caso, a principal questão envolvendo a resolução deste tipo de problema é garantir que o agente consiga raciocinar sobre os conjuntos de estados aos quais ele pode chegar pelas ações. A técnica utilizada ainda é a busca no grafo de estados. Problemas de contingência Nos problemas do tipo contingência, o mundo é parcial- mente observável (estado inicial não observável), não-deter- minístico e dinâmico. Neste caso, o agente não conhece o ambiente inteiro ou não sabe o efeito das ações, por exemplo, o nosso robô enxerga apenas o quarto onde está. Não há uma sequência prévia de ações que garanta a solução do problema e, portanto, é necessário intercalar busca e execução em uma técnica tradicional de Planejamento. Neste contexto é neces- sário construir uma árvore de ações, onde cada ramo lida com uma possível contingência. Problemas exploratórios Nos problemas exploratórios, além das características dos problemas de contingência, os estados e as ações do ambiente são desconhecidos. O agente deve atuar e descobri-los. Ele não possui conhecimento dos possíveis estados e não possui conhe- cimento sobre o efeito de suas ações, por exemplo, um robô perdido em uma cidade desconhecida, sem mapa. Neste caso é necessário explorar o ambiente, descobrindo gradualmente o resultado das possíveis ações e os estados existentes. Se o agente “sobreviver”, terá aprendido um mapa do ambiente, que poderá ser reutilizado em problemas subsequentes, portanto, a única técnica possível de resolução destes problemas é através da aprendizagem. 29INTELIGÊNCIA ARTIFICIAL Vamos voltar a formulação de problema para nos fixarmos melhor na importância da formulação. Teremos como exemplo, o jogo das n Rainhas (n-queens), considerando um total de 8 rainhas no nosso tabuleiro. O objetivo deste problema é dispor 8 rainhas no tabuleiro de forma que nenhuma delas possa se “atacar” mutuamente. Ou seja, não pode haver mais de uma rainha em uma mesma linha, coluna ou diagonal. Neste caso, somente o custo da busca conta, pois não existe custo de caminho. Neste caso existem diferentes esta- dos e operadores possíveis onde a escolha pode ter consequências boas ou ruins na complexidade da busca ou no tamanho do espaço de estados. Vamos considerar alguns exemplos de formulações possíveis e suas características: • Formulação A: • estados: qualquer disposição com n (n ≤ 8) rainhas; • estado inicial: nenhuma rainha no tabuleiro; • operadores: adicionar uma rainha a qualquer quadrado livre. Nes- te caso tem-se 648 possibilidades, cuja execução irá até o final para testarmos se dará certo. • Formulação B: • estados: disposição com n (n ≤ 8) rainhas, uma por coluna nas n colunas mais à esquerda, sem ataque mútuo (teste gradual); • operadores: adicionar uma rainha na coluna vazia mais à esquerda em que não possa ser atacada. Assim teremos apenas 2057 possibilidades, mas poderemos chegar a um ponto em que não haja ações possíveis; • Formulação C: • estados: disposição com 8 rainhas, uma em cada coluna; • operadores: mover uma rainha atacada para outra casa, na mesma coluna. Esta busca de estados completa precisa de 8x7 sucessores para cada estado. 30INTELIGÊNCIA ARTIFICIAL Tipos de estratégia de resolução de problemas Os principais tipos de estratégias aplicadas na resolução de problemas são: • Busca não-informada ou “cega”. • Busca em amplitude. • Busca com custo uniforme. • Busca em profundidade.• Busca em profundidade limitada. • Busca em profundidade iterativa. • Busca bi-direcional. • Busca informada ou pela melhor escolha (Best-First). • Busca “gulosa” (Greedy). • Busca A*. • Busca com limite de espaço. • Busca IDA (A* interativo). • Subida de encosta (HillClimbing). Existem quatro métricas para avaliação das estratégias de resolução de problemas: • Completude: a estratégia sempre encontra uma solução quando existe alguma? • Custo do tempo: quanto tempo será gasto para encontrar uma solução? • Custo de espaço: quanta memória é necessária para realizar a busca? • Qualidade (optimality) da solução: a estratégia encontra a melhor solução quando existem diferentes soluções? Menor custo de caminho? 31INTELIGÊNCIA ARTIFICIAL Busca em amplitude Na busca em largura, amplitude ou Breadth-first, o grafo da solução é construído em níveis. Cada nó, a partir do nó raiz, é expandido para todos os sucessores do nó raiz e depois os sucessores desses nós, e assim por diante. Em geral, todos os nós, em dada profundidade no grafo de busca, serão expandidos antes que todos os nós no nível seguinte sejam expandidos. Em termos estruturais, os nós do grafo podem guardar mais informação do que apenas o estado, por exemplo: o estado correspondente, o seu nó pai, o operador aplicado para gerar o nó (a partir do pai), a profundidade do nó, o custo do nó (desde a raiz) e os nós sucessores, como exemplificado na Figura 8. Figura 8: Busca em amplitude com a marcação do nó expandido a cada nível O exemplo do algoritmo da Busca em largura retorna uma solução ou falha. Os métodos usados neste algoritmo são: • MAKE-QUEUE (estado inicial): coloca o estado inicial na fila. • REMOVE-FIRST (nodos): remove os primeiros nodos da fila. • GOAL-TEST (nodo): testa se o nodo atual é nodo final. • EXPAND (nodo): retorna uma lista de nodos que representam os estados, resultando da aplicação dos operadores ao nodo atual. • ADD-QUEUE (nodos, novos-nodos): coloca estes nodos na fila de busca. 32INTELIGÊNCIA ARTIFICIAL Um exemplo de resolução usando o algoritmo Breadth-First é exemplificado na execução da Figura 9. Considerando que o estado inicial é A e um dos estados finais é K, a sequência de execuções sobre a árvore é ilustrada pela sequência numérica em vermelho na Figura 9, onde o caminho resultante do estado inicial até o objetivo é {A,B,C,D,E,F,G,H,I,J,K}. Figura 9: Exemplo de árvore de busca usando o algoritmo Breadth-First Em relação as quatro métricas de avaliação de algoritmos de busca apresentadas anteriormente, a busca em amplitude fica assim avaliada: • Completude: é completa. • Qualidade: ótima, se os operadores sempre têm o mesmo custo. • Custo do Tempo: O(bd) nodos explorados, onde • b = fator de ramificação • d = profundidade do estado final (objetivo) • O(bd) = 1 + b + b2 + b3 + .... + bd • Custo do espaço: O(bd) nodos armazenados, ou seja, todos os estados a serem expandidos devem permanecer na me- mória e o resultado é bom quando a profundidade da árvore de busca é pequena. O(x) é a notação assintótica, que significa “complexidade exponencial”, ou seja, o algoritmo leva um tempo exponencial em função do comprimento da entrada (x) para encontrar uma solução. 33INTELIGÊNCIA ARTIFICIAL Exemplo de complexidade, considerando que b = 10, à 1000 nodos por segundo e 100 bytes por nodo: (b = 10, 1000 nodos por segundo, 100 bytes por nodo) Profundidade Nodos Tempo Memória 0 1 1ms 100B 2 111 0,1s 11KB 4 11.111 11s 1MB 6 106 18min 111MB 8 108 31hs 11GB 12 1012 35 anos 111TB 14 1014 3500 anos 11.111TB Busca em amplitude com custo uniforme A estratégia de busca uniforme continua expandindo os sucessores, mas ao invés de pegar o primeiro nó expandido, será escolhido o nó que possui o menor custo (g(n)), onde a função g(n) é uma representação do custo do caminho. O exemplo do algoritmo da Busca em largura com custo uniforme, a seguir, retorna uma solução ou falha. Notem que a diferença na expansão dos sucessores é a fun- ção SORT(...), que ordena a prioridade dos nodos com menor 34INTELIGÊNCIA ARTIFICIAL custo. Neste caso é preciso agregar informação adicional ao problema, por exemplo, o custo do caminho pode ser a distância entre cidades, a quantidade de números fora de posição em um quebra-cabeças, etc. Um exemplo de resolução usando o algoritmo Breadth-First com Custo Uniforme é exemplificado na execução da Figura 9. Considerando que o estado inicial é A e um dos estados finais é K, a sequência de execuções sobre a árvore é ilustrada pela sequência numérica em vermelho na Figura 9, onde o caminho resultante do estado inicial até o objetivo é {A,D,C,B,L,K}. Figura 10: Exemplo de árvore de busca usando o algoritmo Breadth-First com custo uniforme. Busca em profundidade Na busca em profundidade ou Depth-first, o grafo da solução é construído em profundidade, onde cada nó, a partir do nó raiz, é expandido sempre o filho mais à esquerda até a profundidade máxima. O exemplo do algoritmo da Busca em profundidade, a seguir, retorna uma solução ou falha. Nesta busca, apenas os nodos da borda (próximos a raiz) do grafo comportam-se como uma fila FIFO (First-In, First- 35INTELIGÊNCIA ARTIFICIAL -Out), executados pela função ADD-START-QUEUE (nodos, novos-nodos). Um exemplo de resolução usando o algoritmo Depth-First é exemplificado na execução da Figura10. Considerando que o estado inicial é A e um dos estados finais é K, a sequência de execuções sobre a árvore é ilustrada pela sequência numérica em vermelho na Figura10, onde o caminho resultante do estado inicial até o objetivo é {A,B,E,F,G,C,H,I,J,D,K}. Figura 11: Exemplo de árvore de busca usando o algoritmo Depth-First. O algoritmo de busca em profundidade sempre expande os nós mais profundos na borda atual da árvore de busca. À medida que os nós são expandidos, eles são marcados como visitados, não fazendo mais parte da estrutura que guarda a borda das subárvores. Um exemplo de progresso gradual é ilustrado na Figura12. Figura 12: Progresso da busca em profundidade, com nós inexplorados em cinza claro 36INTELIGÊNCIA ARTIFICIAL Busca informada ou heurística Pode-se melhorar a performance da busca através de uma função h(n) que representa uma avaliação do custo para atingir o estado final, para cada nodo n do espaço de busca. A função h(n) é chamada função heurística ou informada, pois é dependente do problema, já que utiliza informação adicio- nal para melhorar a busca, podendo representar, por exemplo, a minimização do custo para se atingir um objetivo ou a estimativa do menor caminho de um estado n até um estado objetivo. Tipos de busca heurística: • Busca pela melhor escolha (Best-First) • Busca gulosa (Greedy) • Busca A* • Busca com limite de espaço • Busca IDA (A* interativo) • Subida de encosta (Hill Climbing) Busca gulosa de melhor escolha A busca gulosa (Greedy) procura expandir sempre o nodo mais próximo do objetivo, caracterizando uma escolha de melhor local. Esta busca usa a função de avaliação h(n) como sendo a estimativa do custo do nodo atual ao objetivo. No exemplo da Figura 13, o objetivo é partir da cidade de Arad e chegar até a cidade de Bucareste na Romênia e a heurística h(n) usada é a distância em linha reta até o objetivo. Figura 13: Exemplo de grafo de possibilidades contendo uma estimativa da distância em linha reta de todas as cidades até Bucharest 37INTELIGÊNCIA ARTIFICIAL O algoritmo expande primeiro o nó, que aparentemente é o mais próximo do objetivo, de acordo com h(n). A Figura14 ilustra um resultado possível usando h(n). Figura 14: Etapas da busca gulosa para Bucareste. Os nós são rotulados com a distância em linha reta até o destino (h) Uma análise preliminar do resultado da busca gulosa de- monstra que: • Completude: não, pois pode ficar em loop, a menos que o espaço de estados seja finito e exista um teste de estados repetidos. • Qualidade (ótimo): não. • Custodo tempo: Os(bd) nós explorados, onde b = fator de ramificação e d = profundidade do estado final (objetivo). • Custo do espaço: Os(bd) nós armazenados. 38INTELIGÊNCIA ARTIFICIAL Busca A* A busca A* (A Estrela), procura conciliar as vantagens da busca em amplitude e profundidade, avaliando os nós através da combinação do custo para alcançar o nó (g(n)) e do custo para ir do nó até o objetivo (h(n)), ou seja f(n) = g(n) + h(n). Figura 15: Etapas da busca usando A*, onde os nós são rotulados com f(n) = g(n) + h(n) A Figura15 ilustra o exemplo do caminho de busca para o exemplo anterior. Se tomarmos agora a distância real per- corrida entre cada trecho, h(n), perceberemos que a estratégia A* produz o seguinte caminho de solução: Arad -> Sibiu -> Rimnici Vilcea -> Pitesti -> Bucharest, resultando em um custo total de (140+80+97+101 = 418). Enquanto que a estra- tégia Gulosa, da Figura14, gera o caminho solução: Arad -> Sibiu -> Fagaras -> Bucharest, resultando em um custo total de (140+151+178 = 469), embora tenha percorrido menos cidades. Ou seja, a estratégia A* encontra uma solução ainda melhor que a estratégia Gulosa. A principal diferença dos algoritmos de busca cega para os algoritmos de busca informada é a expansão do próximo nó a ser analisado. Um algoritmo genérico para buscas informadas, a seguir, retorna uma solução ou falha. 39INTELIGÊNCIA ARTIFICIAL Onde o método GET-BEST-NODE (nodos) implementa a função f(n) = g(n) + h(n) para o algoritmo A*, e a função f(n) = h(n) para o algoritmo Guloso. A análise do resultado do algoritmo A* demonstra que: • Completude: sim, pode ficar em loop; a menos que o espaço de estados seja finito e exista um teste de estados repetidos. • Qualidade (ótimo): sim, se f(n) é admissível. • Custo do Tempo: os(bd) nós explorados, onde b = fator de ramificação e d = profundidade do estado final (objetivo). • Custo do Espaço: os (bd) nós armazenados. Admissibilidade de uma função heurística Uma heurística é admissível se, para cada nodo, o valor retornado por esta heurística nunca ultrapasse o custo real do melhor caminho deste nodo até o objetivo. Dado que h(n) é estimativa de custo de n até a solução, g(n) é custo real de n até a solução, então se h(n) ≤ g(n), então h é admissível e, portanto, o algoritmo será ótimo, ou seja, sempre encontra o caminho mais curto até a solução. 40INTELIGÊNCIA ARTIFICIAL Busca competitiva O que existe em comum entre negociações internacionais, decisões estratégicas de executivos de empresas concorrentes, uma partida de xadrez e as estratégias de busca vistas até agora? Quando mais de um ator participa de uma resolução de problemas, geralmente surgem conflitos em ambientes com- petitivos, dando origem a problemas de busca competitiva ou jogos, como vimos no início deste capítulo. No contexto de problemas de busca competitiva, alguns jogos possuem características que podem ser formuladas como competições abstratas, por exemplo: • representados por estados e regras claramente definidos; • programas para alguns jogos podem ser derivados de mé- todos de busca, onde alguns precisam da incorporação de conhecimento e informações adicionais Definições preliminares Um Jogo é um modelo teórico de conf litos de interesse (decisões possíveis, resultados possíveis) entre duas ou mais pessoas que têm motivações conflitantes. Um Jogador é um participante ativo e racional em um jogo, cujas ações afetam os demais. Movimentos são decisões disponíveis aos jogadores (simultaneamente ou não): são seguidos de uma ação, resultan- do em um ganho (outcome, payoff, utility), podendo ser um evento probabilístico. Nas interações competitivas, as escolhas são alternativas particulares selecionadas por jogador e uma jogada é uma se- quência destas escolhas. Estratégias são descrições das decisões a tomar em todas as situações possíveis e o resultado destas jogadas resulta em valor ou pagamento de uma ação (Payoff / Utility / Ganho) ou ainda uma expressão de preferência. 41INTELIGÊNCIA ARTIFICIAL Taxonomia de jogos 1. Segundo o payoff: a. Jogos de soma zero: soma dos payoffs dos participantes é zero (Nim, Pôquer, Xadrez, etc.). b. Jogos de soma não zero: resultados dos payoffs zero (dilema do prisioneiro, etc.). 2. Segundo a informação: a. Jogos com informação perfeita: a cada jogada, todos os jogadores têm conhecimento das jogadas que já ocorreram ( Jogo da velha, Nim, Xadrez, Go, etc.). b. Jogos com informação imperfeita: conhecimento é parcial (Pôquer). 3. Duração: jogos infinitamente longos, aplicados por mate- máticos teóricos. 4. Simultaneidade: a. Jogos simultâneos cujos movimentos são paralelos e des- conhecidos pelos oponentes. b. Jogos sequenciais, com movimentos intercalados. 5. Simetria: a. Jogos simétricos: onde os payoffs para uma dada estratégia dependem de outras estratégias empregadas. b. Jogos assimétricos: não existe um conjunto idêntico de estratégias para ambos os jogadores. 42INTELIGÊNCIA ARTIFICIAL Formulação de problemas competitivos Geralmente, quando um jogo é formulado em termos de estratégias de busca, ocorre um ambiente onde os agentes são considerados hostis (competitivos) e a representação de jogos como busca torna-se: • relativamente fácil; • com operadores bem definidos; • os oponentes introduzem incertezas; • com resolução complexa (por exemplo, no xadrez, fator médio de ramificação 35 e árvore com 35100 nodos); • limitado em tempo e espaço. Tradicionalmente, a definição formal de um jogo requer a representação de um estado inicial (de um tabuleiro, das posições das peças e do iniciador do jogo). É preciso descrever os operadores, como as ações definem os movimentos permiti- dos. E, definir um teste final para determinar quando o jogo termina, o cálculo do resultado (vitória, empate ou derrota), o cálculo da função de utilidade (payoff) e um valor numérico para cada resultado do jogo. Segundo Russel & Norvig (2013), um jogo pode ser de- finido formalmente como uma espécie de problema de busca com os seguintes componentes: • S0: o estado inicial, designando como o jogo é inicialmente criado. • JOGADORES(s): define qual jogador deve se mover em um estado. • AÇÕES(s): retornam o conjunto de movimentos válidos em um estado. • RESULTADO (s, a): o modelo de transição que define o resultado de um movimento. 43INTELIGÊNCIA ARTIFICIAL • TESTE DE TÉRMINO(s): retorna verdadeiro quando o jogo termina, onde os estados são chamados estados ter- minais. • UTILIDADE (s, p): uma função de utilidade ou objetivo que define o valor numérico para um jogo que termina no estado terminal s por um jogador p. Por exemplo, no xadrez, o resultado é uma vitória, uma derrota ou um empate, com valores +1, 0 ou ½. a. Desta forma, o estado inicial S0, a função AÇÕES(s) e a função RESULTADO (s, a) definem a árvore de jogo, onde os nós são estados do jogo e as bordas são movimentos. Considerando que os jogadores são nomeados como MAX e MIN. A Figura 16 ilustra parte de uma árvore de jogo para o Jogo da Velha. A partir do estado inicial, MAX tem nove movimentos possíveis. O jogo se alterna entre a colocação de um X por MAX e a colocação de um O por MIN até que os nós folhas (ou estados terminais) sejam alcançados. O número em cada nó de folha indica o valor de utilidade do estado terminal, do ponto de vista de MAX. Neste caso, a estratégia básica é MAX tentando maximizar seu ganho e MIN tentando minimizar os efeitos das jogadas de MAX. Figura 16: Exemplo de árvore de busca (parcial) para o Jogo da velha 44INTELIGÊNCIA ARTIFICIAL Para o problema do Jogo da velha, a árvore tem o tamanho de aproximadamen- te 9! = 362.880 nós terminais. Portanto, trivial de implementar, mas o Xadrez, por exemplo, já apresenta mais de 1040 nós. Portanto, não é uma busca trivial e nem ótima do ponto de vista de completude. Portanto, a visualização em árvore deste tipo de problema é apenas teórica. Na Figura 17 seráilustrada uma parte da árvore de escolhas para MAX (representado por ) e o outro jogador, MIN (representado por ). Os nós ter- minais mostram os valores de utilidade para MAX. A seta vermelha indica o melhor movimento de MAX na raiz, através da ação A1, porque leva a um estado com o mais alto valor minimax. Figura 17: Exemplo de uma árvore parcial de jogo de duas jogadas O que é este tal de “minimax”? A partir da árvore de jogo, uma es- tratégia ótima para a escolha das ações é determinada pelo valor minimax de cada nó. O valor minimax de um nó é a utilidade que MAX conhece de se en- contrar no estado correspondente, supon- do-se que ambos os jogadores tenham desempenho ótimo desde esse estado até o fim do jogo. O valor minimax de um estado terminal é simplesmente sua utilidade. MAX sempre terá a tendên- cia de se mover para um estado de valor máximo, enquanto MIN preferirá um estado de valor mínimo, ou seja, dado que minimax é VALOR-MINIMAX(n): O algoritmo MinMax-VALOR, ilustrado abaixo, calcula a decisão mi- nimax a partir do estado atual (“estado”). De forma recursiva, o algoritmo percorre todo o caminho descendente até as folhas da árvore e, depois, os valores minimax são propagados de volta pela árvore, à medida que a recursão retorna. 45INTELIGÊNCIA ARTIFICIAL No exemplo da Figura17, o algoritmo MinMax-VALOR, primeiro percorre todo o caminho desde o nó raiz até o nó terminal mais à esquerda, no terceiro nível de profundidade da árvore. Retorna com a função UTILIDADE (estado) sobre eles para descobrir que seus valores são 3, 12 e 8, respectivamente. Em seguida, calcula o mínimo desses valores, 3, e o devolve como valor propagado de volta para o nó B. Um processo se- melhante fornece os valores propagados de volta de 2 para C e 2 para D. Por fim, tomamos o valor máximo entre 3, 2 e 2 para obter o valor propagado de volta igual a 3 para o nó raiz. O algoritmo minimax explora completamente árvore de jogo em profundidade. A complexidade de tempo e espaço do algoritmo é O(bm), para uma profundidade máxima de m e b movimentos válidos, caso todos os sucessores sejam gerados de uma vez. A complexidade de espaço será O(m) quando as ações forem geradas, uma de cada vez. Em jogos reais, o custo de tempo é totalmente impraticável, pois a busca é exponencial em relação ao número de movimentos. Uma estratégia importante é a possibilidade de calcular a decisão minimax correta sem examinar todos os nós na árvore de jogo. Esta estratégia se chama Poda Alfa-Beta. A poda Alfa-Beta é um processo de eliminar ramificações da árvore sem examiná-las, descartando os que não contenham bons movimentos. Aplica-se a ambos os jogadores e α (Alfa) denota a melhor escolha para MAX, enquanto β (Beta) denota a melhor escolha para MIN. A partir da Figura 18, o princípio da Poda Alfa-Beta define que: 46INTELIGÊNCIA ARTIFICIAL • se o valor α representa o melhor valor encontrado para MAX (ou MIN), e se ѵ é pior do que β, MAX/MIN já achou uma jogada boa e pode evitar a ramificação para v. Figura 18: Exemplo de princípio da poda alfa-beta Um algoritmo para a Poda Alfa-Beta é ilustrado a seguir: 47INTELIGÊNCIA ARTIFICIAL Síntese Este capítulo introduziu métodos de resolução de problemas através de processos de busca, definindo es- tratégias que um agente pode usar para selecionar ações em ambientes determinísticos, observáveis, estáticos e completamente conhecidos. A identificação de um objetivo e a formulação de um problema são etapas crítica na resolução de problemas. A formulação através da definição de um estado inicial, um conjunto de ações, um modelo de transição, a função de teste de objetivo e as métricas de custo são indispensáveis para um agente planejar a resolução. Algoritmos genéricos de busca consideram todos os caminhos possíveis em estratégias de buscas em árvores, enquanto que, se considerarmos a busca em grafos, podemos evitar a construção de caminhos redundantes. Analisar os algoritmos em termos de sua completude, otimização e complexidade em tempo e espaço é uma importante etapa da determinação da performance do algoritmo e na definição da qualidade das soluções encontradas. Os Toy Problems aqui apresentados e suas estratégias de solução constituem experimentos e esforço de pesquisa de aplicação em problemas no mundo real. Determinar voos ótimos de linhas aéreas, aplicação do pro- blema do caixeiro-viajante, entre outros, constituem aplicação direta de uma estratégia combinatória-padrão em Computação. Aproximações do problema do caixeiro-viajante são utilizadas em desenho de layouts de circuitos VLSI (Very-Large-Scale Integration) e em problemas de navegação e montagem de robôs. 48INTELIGÊNCIA ARTIFICIAL Exercícios Formulação de problemas Procure construir a formulação dos pro- blemas (espaço de estados, estados inicial e finais, teste objetivo, operadores e custo do caminho) abaixo, ilustrando com um grafo parcial de busca: Robô aspirador: como exercício, pro- cure definir uma formulação adequada para o problema do robô aspirador, construindo o espaço de estados possíveis, os estados inicial e final, as ações do robô (regras ou operadores), o teste de término e o custo do caminho. Jogo de 8-números: também conhecido como n-puzzle, consiste em um tabuleiro den×ncasas, contendo n*n-1números ini- cialmente desordenados arranjados aleato- riamente em cada casa do tabuleiro. Tome como exemplo um tabuleiro de 3×3 casas, distribuídos a seguir: Início: O objetivo é alcançar uma configura- ção com os números ordenados através de movimentos que só podem ser feitos para a casa que está sempre vazia: Final: Problema dos vasilhames com água: existem 2 vasilhames, 1 de 4 litros e outro de 3 litros, sem medidas. Uma torneira pode ser utilizada para enchê-los. O objetivo é colocar exatamente 2 litros de água no va- silhame de 4 litros. Problema dos canibais e missionários: três canibais e três missionários estão via- jando juntos e chegam à margem de um rio. Eles desejam atravessar para a outra margem e desta forma, continuar a viagem. O único meio de transporte disponível é um barco que comporta no máximo duas pessoas. Há uma outra dificuldade: em nenhum momen- to o número de canibais pode ser superior ao número de missionários, pois desta forma, os missionários estariam em grande perigo de vida. Como administrar a travessia? 4 5 8 1 6 7 2 3 1 2 3 4 5 6 7 8 49INTELIGÊNCIA ARTIFICIAL Estratégia busca não-informada ou cega 1. Escreva os algoritmos para busca em profundidade limitada e busca em profundidade iterativa, sabendo que: • Na busca com profundidade limitada, a busca não ultrapassa um valor limite de profundidade. A solução deve encon- trar-se dentro desse limite. Esse tipo de busca não tem uma solução ótima. • Na busca em profundidade iterativa, tenta-se primeiro uma busca em profundidade com limite de profundidade 0; se não existe uma solução, repete-se o procedimento com pro- fundidades 1, 2, ..., n até alcançar uma solução. 2. Baseado na análise da busca em amplitude, faça a análise das buscas em profundidade, profundidade limitada e pro- fundidade iterativa (sem os exemplos de complexidade). Busca competitiva 1. Construir a árvore minimax com os payoffs indicados nos nodos terminais para o Jogo dos 5 palitos: • Objetivo do jogo: de um conjunto de 5 palitos, pegar 1 ou 2 palitos e não ser o último a jogar. • Exemplo de Cenário 1: • Jogador 1: retira 2 palitos • Jogador 2: retira 2 palitos • Jogador 1: retira o último (perde). • Exemplo de Cenário 2: • Jogador 1: retira 1 palito. • Jogador 2: retira 2 palitos. • Jogador 1: retira 1 palito. • Jogador 2: retira o último (perde). 2. Construa o caminho dos nós da árvore na Figura 17, usan- do a Poda Alfa-Beta, indicando os caminhos que serão descartados. 50INTELIGÊNCIA ARTIFICIAL SISTEMAS ESPECIALISTAS Existem problemas cujo domínio está apenas na cabeça das pessoas, não formalizado.Neste caso, é preciso resolver problemas com a ajuda de um especialista e a simulação de sua inteligência. 51INTELIGÊNCIA ARTIFICIAL Sistemas especialistas armazenam e processam conheci- mento adquirido a partir da interação com especialistas em uma área de conhecimento. Inicialmente, constituem apoio à decisão, usando conhecimentos sobre áreas específicas, de acordo com comportamento humano diante destas situações. Geralmente, os sistemas especialistas usam métodos inferenciais na resolução de problemas complexos, a partir da experiência humana. Antes de mais nada, é preciso que o sistema incorpore algum conhecimento humano para poder tomar decisões, responden- do questões através de um processo de tomada de decisão ou, simplesmente, dividindo esse processo por meio de interações com o especialista. Basicamente, como qualquer abordagem de IA, um sistema especialista simula o comportamento humano. Um especialista se baseia em fatos estabelecidos para formular hipóteses a fim de tomar uma decisão sobre um determinado assunto. Para isto, busca em sua memória um conhecimento previamente armaze- nado, no período de sua formação ou no decorrer de sua vida profissional, sobre esses fatos e hipóteses. Finalmente, usa sua experiência sobre os fatos e hipóteses para emitir uma decisão. Sistemas especialistas podem ser diretamente aplicados a vários tipos de tarefas de resolução de problemas: • Tarefas de diagnóstico: processo de encontrar falhas em um sistema ou doenças em seres vivos. Exemplo: MYCIN diagnóstico de infecção sanguínea (Shortlife, 1973). • Tarefas de interpretação: análise de dados para determinar seu significado. Exemplo: PROSPECTOR (Duda et al., 1977) interpretação de dados geológicos como evidência para depósitos minerais. • Tarefas de monitoramento: interpretação contínua de sinais em um sistema com objetivo de diagnosticar ou dar um alarme. Exemplo: NAVEX monitoramento de dados de radar para estimar velocidade e posição do Space Shuttle (Marsh, 1984). 52INTELIGÊNCIA ARTIFICIAL • Tarefas de projeto (design): produção de especificações de sistemas que satisfaçam a requerimentos particulares. Exem- plo: R1/XCON configuração de sistemas VAX baseada nas necessidades do cliente (McDermott, 1980). • Tarefas de planejamento: produção de uma sequência de ações para atingir um objetivo específico. Exemplo: MOL- GEN planejamento de processos químicos para análise e síntese de DNA (Stefik, 1981). • Tarefas de predição: previsão de eventos futuros usando um modelo baseado em dados do passado e do presente. Exemplo: PLANT, previsão dos danos esperados quando determinada praga atacava o milho (Boulanger, 1983). Alguns exemplos de sistemas especialistas históricos: 1965: DENDRAL (Stanford): Inferência sobre estruturas químicas. MACSYMA (MIT): Análise de equações simbólicas diferenciais. HERSAY (Carnegie-Mellon): Interpretação de conjuntos fonéticos em linguagem natural. 1972: MYCIN (Stanford): Diagnóstico de doenças sanguíneas. PROSPECTOR (Stanford): Exploração e identificação de minérios. 1980: R1/XCON (Carnegie-Mellon): Configuração de computadores DEC. Um rápido exemplo de uma aplicação do MYCIN (Da- vis et al., 1977) é um modelo para diagnosticar meningite e outras infecções bacterianas, e prescrever tratamento: • Representação de conhecimento baseada em regras probabilísticas (em torno de 500). • Acima de 90% de acerto. • Introduziu explicação e boa interface com usuário. • Exemplo de regra: 53INTELIGÊNCIA ARTIFICIAL Arquitetura de um sistema especialista Existem várias estruturas e arquiteturas possíveis em que se pode organizar um sistema especialista. Geralmente, os principais elementos constituintes de um sistema especialista genérico são os exemplificados na Figura 19. Figura 19: Arquitetura geral de um sistema especialista básico O Usuário é o elemento responsável pela verificação e validação do comportamento do sistema. Pode ser o especia- lista que adiciona conhecimento ou modifica o conhecimento armazenado no sistema. Realiza as interações para obter res- postas do sistema ou desenvolver especialidade relacionada ao domínio, extraindo conhecimento organizado. A Base de Conhecimento (BC) constitui o repositório das primitivas de conhecimento: fatos, regras e heurísticas. O projeto deste dispositivo inf luencia o projeto e mecanismo de inferência, o processo de atualização do conhecimento e o me- canismo de atualização. Para seu desenvolvimento, utilizam-se técnicas de representação do conhecimento, tais como: regras de produção, redes semânticas, frames, scripts, etc. O processo de construção de uma base de conhecimento específico ao domínio é tarefa de um especialista conhecido como Engenheiro do Conhecimento. 54INTELIGÊNCIA ARTIFICIAL AQUISIÇÃO NÍVEL DE CONHECIMENTO NÍVEL LÓGICO NÍVEL DE IMPLEMENTAÇÃO FORMULAÇÃO IMPLEMENTAÇÃO REFINAMENTO BC O processo de aquisição do conhecimento pressupõe um levantamento de requisitos de conhecimento, isto é, extrair, estruturar e organizar o conhecimento de uma ou mais fontes. É a atividade inicial do processo de engenharia de conhecimen- to, e indispensável para que as informações essenciais sejam coletadas e o conhecimento chave fique disponível para ser organizado, representado, implementado e validado através de um sistema. Geralmente, aplicam-se técnicas de pesquisa quali- tativas: entrevistas, questionários, narrativas, técnicas manuais, semiautomáticas ou automáticas, como algoritmos de extração de conteúdo de documentos, mineração de dados, raciocínio baseado em casos, aprendizado de máquina, entre outras. Nos sistemas especialistas, o aprendizado ocorre com a in- corporação de novas regras nas bases de conhecimento. A cada processamento da base de conhecimento, o sistema especialista assume como verdade o conhecimento ali formalizado. Isto é pos- sível em virtude da estrutura modular da base de conhecimento, permitindo a adição ou deleção de novos elementos sem alterar a lógica global do sistema. Na etapa de formulação e implementação, o engenheiro precisa formalizar na Base de Conhecimento, podendo ser representado, por exemplo, através de regras de produção. Um conjunto de regras de produção pode ser mapeado em árvores de decisão, que são representações mais simples do conhecimento e, um meio efi- ciente de construir classificadores que predizem classes baseadas nos valores de atributos de um conjunto de dados. Tecnicamente, árvores de decisão são grafos acíclicos que consistem de nodos que representam os atributos de arcos, provenientes destes nodos e que recebem os valores possíveis para estes atributos, e de no- dos-folha, que representam as diferentes classes de um problema. 55INTELIGÊNCIA ARTIFICIAL O Motor de Inferência é o componente do SE que aplica um conjunto de regras lógicas sobre a BC para deduzir informações novas, fornecendo elementos para a aprendizagem e explanação do problema. A capacidade do motor de inferência é baseada em um inter- pretador capaz de percorrer a BC e buscar fatos que, deduzidos por regras de inferência lógicas, consegue inferir novo conhecimento. Duas estratégias de raciocínio são comumente usadas: • Forward chaining: encadeamento progressivo que inicia pelas condições e vai em direção aos objetivos. • Backward chaining: encadeamento regressivo que inicia pelos objetivos e vai em direção às condições. Estas regras são armazenadas na base de conhecimento no formato SE/ENTÃO, usando a seguinte gramática simplificada: O motor de inferência pode processar estas regras usando encadeamento regressivo, se começar com a solução, e verifi- car tal solução fazendo perguntas ao usuário para verificar o resultado. As perguntas feitas ao usuário são apenas para obter informações que não estão na base de conhecimento. O encadeamento progressivo acontece no questionamen- to ao usuário por toda a informação necessária. Em seguida, esta informação é usada com diferentesregras para ver se ela se ajusta a quaisquer dos problemas previamente descritos. Se ajustar, ela repassa a possível solução ao usuário. Sendo um mecanismo genérico de causa e efeito (SE- -ENTÃO), o motor de inferência pode ser reutilizado em vários contextos. Os demais componentes variam em função da aplicação. O motor de inferência é o módulo do sistema responsável pelo processo de inferência que é aplicado sobre o conhecimento disponível na base de conhecimento em função dos fatos informados via interface ou obtidos da base de dados. SE <Condição 1> <Condição 2> ENTÃO <Conclusão 1> <Conclusão 2> 56INTELIGÊNCIA ARTIFICIAL Modo de raciocínio Em um sistema especialista baseado em regras, o conhe- cimento do domínio é todo representado em relações de con- sequência por regras de produção no formato SE-ENTÃO agrupados em um conjunto “Regras (MR)”. Os dados são representados por um conjunto de fatos sobre a situação cor- rente “Fatos (MF)”. A máquina de inferência compara cada regra a partir dos fatos armazenados na base de conhecimento, através de um mecanismo de “Pattern Matching”. Quando a parte da condição “SE” combina com algum fato na base de conhecimento, a regra é disparada e a ação na parte “ENTÃO” é executada. A combinação de regras com os fatos determina uma cadeia de inferência ou modo de raciocínio que pode alterar a base de conhecimento, descobrindo fatos novos, conforme o f luxo desta Figura: Regras (MR) Fatos (MF) Conjunto de Conflitos (CC) Pattern Matching Resolução de conflitos Disparo da(s) regra(s) Regra(s) escolhida(s) Alterações em MF (MR) Eventualmente, um conjunto de fatos pode disparar a mesma regra, ou um fato pode fazer parte de várias regras na parte de condição, neste caso, um Conjunto de Conflitos (CC) é gerado. Quando isto ocorre, um mecanismo de resolução de conflitos deve ser acionado a fim de desambiguar as regras e definir uma geração determinística de fatos. 57INTELIGÊNCIA ARTIFICIAL Vamos a um exemplo prático. Su- ponha que seja necessário construir um sistema especialista para oferta de em- prego especializado: • Variáveis: • Descoberta: o candidato fez alguma descoberta? • Experiência: quantos anos de ex- periência tem o candidato? • Média: qual a nota média do can- didato em seu curso superior? • Posição: que posição deve ser ofe- recida ao candidato? • Qualifica: o candidato se qualifica para uma posição? Após esta etapa de aquisição do co- nhecimento, as variáveis que conciliarão a base de fatos, podem ser assim formuladas: Variáveis de entrada com respectivos valores: Descoberta: Sim / Não. Diploma: Sim / Não. Experiência (em anos): um número. Média (nota média do histórico): um número. Variáveis de saída com valores possíveis: Posição: Nenhuma / Pesquisa / Eng. De Serviço / Eng. De Produto. Qualifica: Sim / Não. Seja o conjunto de regras assim assi- nalado, formando a Memória de Regras (MR): R1: SE (Diploma = Não) ENTÃO (Posição <-- Nenhuma). R2: SE (Diploma = Sim) ENTÃO (Qualifica <-- Sim). R3: SE (Diploma = Sim) E (Descoberta = Sim) ENTÃO (Posição <-- Pesquisa). R4: SE (Qualifica = Sim) E (Média <= 7,0) E (Experiência >= 2) ENTÃO (Posição <-- Eng. De Serviço). R5: SE (Qualifica = Sim) E (Média < 7,0) E (Experiência > 2) ENTÃO (Posição <-- Não). R6: SE (Qualifica = Sim) E (Média > 7,0) ENTÃO (Posição <-- Eng. de Produto). O conjunto de fatos iniciais, forman- do a Memória de Fatos (MF) é assim inicializado: F0: (Diploma = Sim). F1: (Experiência = 1,5). F2: (Média = 8,0). F3: (Descoberta = Não). O modo de inferência usando Fo- rward-Chaining, apresenta o seguinte algoritmo: 58INTELIGÊNCIA ARTIFICIAL A execução completa do algoritmo, até que nenhuma regra seja mais disparada, constrói as três épocas abaixo: O modo de inferência usando Backward-Chaining, apre- senta o seguinte algoritmo: Neste caso, a cadeia de inferência será: Fatos iniciais (M0): F0: (Diploma = Sim). F1: (Experiência = 1,5). F2: (Média = 8,0). F3: (Descoberta = Não). Inferência 1: Dispara R2. F4: (Qualifica = Sim). Fatos iniciais (M1): F0: (Diploma = Sim). F1: (Experiência = 1,5). F2: (Média = 8,0). F3: (Descoberta = Não). F4: (Qualifica = Sim). Inferência 2: Dispara R6. F5: (Posição = Eng. de Produto). Fatos iniciais (M2): F0: (Diploma = Sim). F1: (Experiência = 1,5). F2: (Média = 8,0). F3: (Descoberta = Não). F4: (Qualifica = Sim). F5: (Posição=Eng.de Produto). Não dispara mais regras. 59INTELIGÊNCIA ARTIFICIAL Tratamento de incerteza O tratamento da incerteza lida com o raciocínio inexato e pode ser feito através da utilização de valores intermediários entre os valores verdadeiro e falso. A forma clássica de imple- mentação é feita pela quantificação do grau ou fator de certeza do conhecimento, conforme alguma escala convencionada pelo especialista. Um exemplo de escala para o grau de incerteza do conhe- cimento utilizado no sistema MYCIN (Davis et al., 1977) é apresentado na Tabela: Fator de Certeza Significado 100 Definitivamente certo 80 Quase certo 60 Provável 30 Há evidências 20 Ignorado 0 Ignorado -20 Ignorado -40 Há evidências contra -60 Provavelmente não -80 Quase certo que não -100 Definitivamente não Os Fatores de Certeza (FC), usados para tratamento de incerteza, foram originalmente definidos como a diferença entre a crença e a descrença, onde a partir de uma hipótese (H) dada a evidência (E), envolve o cálculo das funções: • MC[H, E]: grau de aumento da crença na hipótese H, se E for ob- servada. • MD[H, E]: grau de aumento da descrença na hipótese H, se E for observada. Ambas as medidas MC e MD serão definidas em função de: • p(H): probabilidade a priori de H; • p(H|E): probabilidade a posterior de H ou probabilidade condicional, dada a evidência E. Logo, o fator de crença FC na hipótese H dada a evidência E é calculado por: • FC [H, E] = MC[H, E] – MD[H, E] 60INTELIGÊNCIA ARTIFICIAL A partir desta abordagem é possível combinar crença e descrença em uma medida de utilidade, por exemplo, se um paciente tem cer- tos sintomas os quais sugerem diversas doenças possíveis, a doença com um alto FC poderia ser a primeira a ser investigada pelos testes ordenados. O FC representa uma rede de crenças em uma hipótese sobre alguma evidência, onde um FC positivo significa que a evidência suporta a hipótese desde que MC > MD. Um FC=1 significa que a evidência definitivamente prova a hipótese enquanto um FC=0 pode significar: • que não existe evidência ou ela é irrelevante (MC=MD=0); • a crença é cancelada pela descrença, pois as duas são igualmente fortes ou fracas (MC=MD≠0). Em contrapartida, um FC negativo significa que a evidência favo- rece a negação da hipótese, desde que MC < MD, ou seja, existem mais razões para a descrença em uma hipótese do que para a crença nela. Sistema de explanação O sistema de explanação é usado quando um usuário precisa de uma explicação sobre a cadeia de inferência realizada de SE, exibindo “por que” e “como” o sistema chegou a determinada conclusão, rumo à solução do problema analisado. O processo é caracterizado por uma busca inversa, percorrendo as trilhas utilizadas e mar- cadas durante a sessão de consulta, apresentando todos os argumentos que o levaram à solução apresentada. O processo de explanação também pode ser utili- zado como instrumento de treinamento do usuário, já que apresenta conceitos teóricos e aplicações práticas, reforçando a tese da importância das interfaces na apli- cação de sistemas especialistas. Para fornecer explanações, um SE necessita utilizar “metaconhecimento”, conhecimento sobre o seu próprio 61INTELIGÊNCIA ARTIFICIAL conhecimento e, “introspecção”, observação sobre o seu próprio modo de operação. Muitas vezes estas explicações são feitas listando as regras que estão sendo utilizadas. O objetivo da explanação é apresentar o comportamento do SE através de questões como: • Por que uma certa pergunta foi feita pelo SE? • Como a conclusãofoi alcançada? • Por que alguma alternativa foi rejeitada? • Qual é o plano para alcançar a solução? Por exemplo, para responder à pergunta “por que é necessário saber o preço?”, o sistema de explanação navega pela árvore da ca- deia de inferência buscando as informações contidas no conjunto de regras. Assim, uma explanação pode ser a apresentação da própria regra que disparou alguma condição: REGRA #5 SE preço = importante E pagamento = prestação ENTÃO pagamento mensal é determinado Ferramentas de sistemas especialistas Atualmente, a própria IA se confunde com Sistemas especialistas, por este ser apenas uma técnica de aplica- ção, muitas ferramentas foram criadas especificamente para modelar sistemas especialistas, tal como foi abor- dado neste capítulo. O quadro ilustrará alguns exemplos de ferramentas, sistemas e abordagens que podem ser usados em aplicações de sistemas especialistas: 62INTELIGÊNCIA ARTIFICIAL Ferramenta Descrição Acesso BABYLON Permite desenvolver frames, regras de produção, lógica (PROLOG) e restrições. Requer o Common Lisp instalado. https://www.cs.cmu.edu/afs/cs/project/ai-repository/ ai/areas/expert/systems/babylon/0.html CLIPS (C Language Integrated Production System) Baseado em forward-chaining, escrito em C. Desenvolvido pela NASA. Plataformas: DOS, Windows, VMS, Mac e UNIX. http://www.clipsrules.net/Documentation.html DYNACLIPS (DYNAamic CLIPS Utilities) Conjunto de ferramentas constituído por blackboard, troca de conhecimento dinâmico e agentes que podem ser linkados com CLIPS. https://www.cs.cmu.edu/afs/cs/project/ai-repository/ ai/areas/expert/systems/clips/dyna/0.html FuzzyCLIPS CLIPS com conceitos nebulosos (fuzzy) e raciocínio. https://www.cs.cmu.edu/afs/cs/project/ai-repository/ ai/areas/expert/systems/clips/fzclips/0.html Jess the Rule Engine for Java Ambiente para máquina de regras declarativas em Java. https://herzberg.ca.sandia.gov/jess/ Expert SINTA Representação do conhecimento baseado em regras de produção e fatores de confiança. Motor de inferência compartilhado: construção automática de telas e menus, tratamento de incerteza e utilização de explicações sensíveis ao contexto. http://www.lia.ufc.br/~bezerra/exsinta/ PIKE - Python knowledge engine Através de regras de forward/backward chaining através de código python. http://pyke.sourceforge.net EZ-Xpert 3.0 Sistema baseado em regras que apresentam rápido desenvolvimento, grande velocidade e precisão, implementado sem um mecanismo de inferência. http://www.ez-xpert.com/index.html LPA (Logic Programming Associates) Plataforma para desenvolvimento de Sistemas especialistas. http://www.lpa.co.uk/pro_exp.htm IBM Watson Conjunto de ferramentas de IA, entre elas, sistemas baseados em regras. www.ibm.com/watson/br-pt https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/babylon/0.html https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/babylon/0.html http://www.clipsrules.net/Documentation.html https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/dyna/0.html https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/dyna/0.html https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/fzclips/0.html https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/expert/systems/clips/fzclips/0.html https://herzberg.ca.sandia.gov/jess/ http://www.lia.ufc.br/~bezerra/exsinta/ http://pyke.sourceforge.net/ http://www.ez-xpert.com/index.html http://www.lpa.co.uk/pro_exp.htm http://www.ibm.com/watson/br-pt 63INTELIGÊNCIA ARTIFICIAL Síntese Neste capítulo abordamos detalhes dos vários temas pertencentes ao estudo de Sistemas multiagentes, principalmente aliando questões conceituais com aplicações práticas e introdução a algoritmos básicos de comportamento de sistemas de agentes. Estudos mais recentes integram comportamentos cognitivos com representação de objetos inativos do ambiente, artefatos simbólicos de atuação do agente e repre- sentação de questões normativas para comportamento social. A área de simulação atrai bastante atenção para a simulação de modelos matemáticos através de com- portamentos reativos e deliberativos de múltiplas entidades interagentes. As questões aqui abordadas são base para aplicações, envolvendo tomadas de decisão, planejamento autônomo, elaboração de metas, avaliação de atividades co- ordenadas e inteligência distribuída. 64INTELIGÊNCIA ARTIFICIAL Exercícios Problema 1: Diagnóstico de falha de automóveis O usuário expõe o problema, dizendo que “tentou ligar o carro hoje e o motor não funcionou”! • Procure modelar o problema utilizando regras de produção a partir da seguinte explicação do especialista: • Quando o motor de um carro não arranca, minha primeira suspeita é de que o carro esteja sem gasolina. Porém, se há cheiro de gasolina quando se tenta arrancar, ou se tem a certeza que o tanque está cheio, suspeito que a gasolina pode não chegar ao carburador, logo, a mangueira pode estar bloqueada. Se até aqui tudo está bem, tente ligar os faróis para testar a bateria ou algum problema elétrico. Problema 2: Diagnóstico médico Três diagnósticos distintos são identificados através dos seguintes conjuntos de sintomas e problemas associados. • Modele o problema de forma que o conjunto de regras possa inferir as recomendações segundo as evidências. Como existem evidências compartilhadas, acrescente fatores de certeza para inferir múltiplas recomendações por ordem de certeza. Gripe • espirros • febre • dores no corpo • coriza • cansaço Recomendação: vitamina C, repouso Recomendação: antibiótico, repouso Recomendação: antibiótico, xarope, repouso Amidalite • dor ao engolir • febre • amídalas inchadas e avermelhadas Bronquite • tosse seca • febre • cansaço • amidalite 65INTELIGÊNCIA ARTIFICIAL Problema 3: Diagnóstico financeiro Um banco está disponibilizando aos seus clientes um empréstimo de R$20.000,00 para compra de au- tomóveis. Os clientes que solicitam o empréstimo são avaliados pela instituição, verificando se tem ou não direito ao benefício. • Apresente a modelagem dos fatos e das regras de produção para inferência da avaliação dos clientes. • Escolha uma das ferramentas de desenvolvimento de sistemas especialistas deste capítulo e procure implementar o módulo de avaliação do problema financeiro. Características essenciais de clientes habilitados • Residência = Porto Alegre • Renda acima de R$ 1500,00 • Outras características de clientes habilitados • Emprego com carteira assinada • Estado civil = casado, divorciado • Casa própria • Carro quitado • Idade superior a 25 anos 66INTELIGÊNCIA ARTIFICIAL ALGORITMOS GENÉTICOS É possível encontrar soluções cada vez melhores a partir da evolução das gerações anteriores, baseando-se nos processos naturais de evolução. Computação evolutiva determina a sobrevivência dos melhores candidatos, construindo uma população de soluções ótimas. 67INTELIGÊNCIA ARTIFICIAL Algoritmos genéticos representam um tipo de estratégia de busca de soluções em que os estados sucessores são gerados pela combinação de dois estados, ao invés da geração ocorrer tradicionalmente apenas sobre um único estado. As estratégias de busca vistas até agora exploravam sistema- ticamente espaços de busca, mantendo-se um ou mais caminhos na memória, registrando as alternativas exploradas em cada ponto do caminho. A solução encontrada é o caminho completo até o estado objetivo. Nem sempre a solução necessária é este caminho, problemas de otimização baseados em n-queens, por exemplo, tais como projeto de circuitos integrados, leiaute de instalações industriais, escalonamento de jornadas de trabalho, programação automática, otimização de rede de telecomunica- ções, roteamento de veículos, gerenciamento de carteiras, entre outros, buscam uma configuração final otimizada das rainhas (ou recursos) e não a ordem em que elas são posicionadas.
Compartilhar