Apontamentos_IA_Recurso PDF

Índice O que é a Inteligência Artificial (IA)?........................................................................................... 3 Teste de Turing.............................................................................................................................. 3 Critica ao test...

Índice O que é a Inteligência Artificial (IA)?........................................................................................... 3 Teste de Turing.............................................................................................................................. 3 Critica ao teste de Turing.............................................................................................................. 3 Espaço de Estados......................................................................................................................... 4 Representação de Estado............................................................................................................. 4 Solução.......................................................................................................................................... 4 Estratégias de exploração de árvores.......................................................................................... 5 Breath-First (Largura Primeiro).................................................................................................... 5 Custo Uniforme............................................................................................................................. 6 Depth-First (Profundidade primeiro)........................................................................................... 6 Grafos em vez de árvores............................................................................................................. 7 Uso de Funções de avaliação........................................................................................................ 8 Procura ordenada..................................................................................................................... 8 Algoritmo A*................................................................................................................................. 9 Algoritmo de procura ótimo......................................................................................................... 9 Admissibilidade............................................................................................................................ 9 Informação Heurística................................................................................................................ 10 Consistência................................................................................................................................ 10 Exercícios sobre o A*.................................................................................................................. 11 Medidas de desempenho........................................................................................................... 14 IDA* (Iterative Deepening A*).................................................................................................... 14 Desempenho........................................................................................................................... 15 RBFS – Recursive Best-First Search............................................................................................. 15 SMA* - Simplified Memory Bounded A*................................................................................... 16 Comparação de algoritmos.................................................................................................... 16 Tipos de Jogos: Sequenciais vs. Simultâneos............................................................................. 17 Representação formal de jogos.................................................................................................. 17 Simétricos vs. Assimétricos........................................................................................................ 17 Soma Zero vs. Soma Não-Zero................................................................................................... 17 Cooperativos ou não................................................................................................................... 17 Equilíbrio de Nash....................................................................................................................... 18 Tipos de Jogos Combinatórios.................................................................................................... 18 Heurísticas e funções de avaliação............................................................................................ 18 Terminologia............................................................................................................................... 18 Cortes Alfa-Beta.......................................................................................................................... 19 Regras de Corte........................................................................................................................... 19 Fail-soft vs. Fail-hard................................................................................................................... 19 Exemplo Alfa-Beta Fail-Soft........................................................................................................ 20 Programação Dinâmica e Memorização.................................................................................... 20 SSS*............................................................................................................................................. 20 SCOUT......................................................................................................................................... 21 PVS/NegaScout Principal Variation Search................................................................................ 21 MTD(f)......................................................................................................................................... 22 Best node search (BNS).............................................................................................................. 22 Exemplo do Best node search (BNS).......................................................................................... 23 Exemplo do Alfa-Beta................................................................................................................. 23 Exercícios sobre a matéria.......................................................................................................... 24 O que é a Inteligência Artificial (IA)? Aspetos a considerar: Capacidade de resolver problemas Capacidade de usar o conhecimento – raciocínio Capacidade de Aprender Não há uma definição globalmente aceite. Elaine Rich: “Estudo de como fazer os computadores realizarem tarefas em que de momento as pessoas são melhores.” A certa altura as pessoas eram melhores que as máquinas a fazer operações aritméticas Teste de Turing Método: 2 canais de comunicação idênticos e independentes 1 pessoa e 1 máquina Se não for possível distinguir a pessoa da máquina ao fim de um período de interação razoável então a máquina é considerada inteligente Critica ao teste de Turing Atualmente a IA está mais interessada em fazer máquinas que ajudem as pessoas a resolver problemas, de forma colaborativa, tirando o melhor partido das capacidades das máquinas (memória e rapidez de cálculo) e das capacidades das pessoas (criatividade, capacidade de tratar exceções) do que em fazer máquinas que imitem seres humanos. Espaço de Estados Uma forma simples de resolver problemas que não se podem resolver com fórmulas ou algoritmos, consiste em explorar o espaço de possibilidades tentando vários caminhos possíveis até encontrar a solução. Neste caso um problema terá de ser equacionado em termos de: Estados Operadores (de transição de estados) Terá ainda de ser definido o estado final (poderá ser com uma função de teste); Representação é composta por: Grafo: O Espaço de Estados pode ser representado por um grafo dirigido acíclico. Nó: Cada nó do grafo representa um estado do problema, com alguma informação adicional (pointer para o nó que o gerou; etc.) Arco: Cada arco do grafo representa uma transição de estado ao longo do processo de resolução do problema. Representação de Estado Um estado no problema do caixeiro-viajante pode ser representado como um conjunto de 2 elementos: {C, V} C = Conjunto de cidades a visitar. V = Conjunto das cidades já visitadas. O estado final é um estado em que C = Ø O estado inicial é o estado em que C contém todas as cidades e V = Ø. Solução A solução é obtida aplicando operadores às descrições dos estados até que surja a descrição do estado final. Estratégias de exploração de árvores Conceitos: Nó inicial Sucessores de um nó: nós que são gerados por aplicação de um dos operadores legais. Expansão de um nó: geração de todos os sucessores. Ponteiros para o nó pai: Permite obter de imediato a solução a partir do estado final. Lista de (nós) abertos: lista com os nós que ainda não foram expandidos. Lista de (nós) fechados: lista com os nós que já foram expandidos. Breath-First (Largura Primeiro) 1. Nó inicial => ABERTOS 2. Se ABERTOS vazia falha. 3. Remove o primeiro nó de ABERTOS (n) e coloca-o em FECHADOS 4. Expande o nó n. Colocar os sucessores no fim de ABERTOS, colocando os ponteiros para n. 5. Se algum dos sucessores é um nó objetivo sai, e dá a solução. Caso contrário vai para 2. Assume-se que o nó inicial não é um nó objetivo. O BF encontra sempre a solução que corresponde ao caminho mais curto. Se não houver solução o método termina com falha se o grafo for finito ou não termina se o grafo for infinito. Custo Uniforme Se interessar minimizar o custo em vez da distância, e se os custos associados aos arcos forem diferentes de arco para arco, então é necessário usar uma variante do BF designada “método do custo uniforme” que garante a minimização do custo. 1. Nó inicial(s) => ABERTOS. Faz g(s)=0. 2. Se ABERTOS vazia falha. 3. Remove o nó de ABERTOS (n) com menor custo (g) e coloca-o em FECHADOS 4. Se n for um nó objetivo termina e dá a solução. 5. Expande o nó n. Colocar os sucessores em ABERTOS, colocando os ponteiros para n e calculando o g de cada um dos sucessores. 6. Vai para 2. Depth-First (Profundidade primeiro) Convenciona-se que a profundidade do nó raiz é zero. A profundidade de um nó é 1 + a profundidade do antecessor. É definido um nível de profundidade máximo a partir do qual os “nós” não são expandidos 1. Nó inicial => ABERTOS 2. Se ABERTOS vazia falha. 3. Remove o primeiro nó de ABERTOS (n) e coloca-o em FECHADOS 4. Se a profundidade de n é maior que d vai para 2. 5. Expande o nó n. Colocar os sucessores no início de ABERTOS, colocando os ponteiros para n. 6. Se algum dos sucessores é um nó objetivo sai, e dá a solução. Caso contrário vai para 2. quando são gerados sucessores que já estão em ABERTOS ou FECHADOS pode ser necessário recalcular a profundidade dos nós correspondentes. Grafos em vez de árvores Os métodos anteriores presumem que o espaço de estados tem uma estrutura do tipo árvore. Se o espaço de estados for um grafo é preciso modificar os algoritmos: Breath-First: reconhecer se um estado sucessor já está em ABERTOS ou em FECHADOS e nesse caso não colocar o nó correspondente em ABERTOS. Custo uniforme: Se o sucessor (nsuc) está em ABERTOS nsuc não é adicionado se g(nsuc)>g(na) caso contrário nsuc substitui na. Se o sucessor está em FECHADOS ignora-se nsuc. Depth-First: Se está em abertos um nó com o mesmo estado, isso quer dizer que esse nó tem um custo g menor ou igual ao do nó gerado agora. Abandona o nó gerado. Se está em fechados e tem um custo maior ou igual: Elimina o nó antigo e coloca o nó gerado em abertos e coloca pointers nos sucessores do nó antigo para o nó gerado. Caso contrário: Abandona o nó gerado. Uso de Funções de avaliação Considera-se que é possível definir uma função de avaliação do interesse dos nós f(n). Por convenção a lista de nós ABERTOS é ordenada por ordem crescente de f(n), em que f(n) é o valor da função de avaliação aplicada ao nó n. Um algoritmo que use a convenção anterior para fazer procura em espaço de estados cuja estrutura seja do tipo grafo acíclico, consiste na sequência de passos: Procura ordenada 1. Nó inicial(s) => ABERTOS. Faz f(s)=0. 2. Se ABERTOS vazia falha. 3. Remove o nó de ABERTOS (n) com menor custo (f) e coloca-o em FECHADOS 4. Expande o nó n. Calcula o f de cada um dos sucessores. 5. Colocar os sucessores que ainda não existem em ABERTOS nem FECHADOS na lista de ABERTOS, por ordem de f colocando os ponteiros para n. 6. Se algum sucessor for um nó objetivo termina e dá a solução. 7. Associa aos sucessores já em ABERTOS ou FECHADOS o menor dos valores de f (existente ou agora calculado). Coloca em ABERTOS os sucessores que estavam em FECHADOS cujos valores de f baixaram. Redireciona para n os ponteiros de todos os nós cujos valores de f baixaram. 8. Vai para 2. Algoritmo A* O algoritmo anterior não especifica o tipo de função de avaliação. Se esta consistir em f(n)=g(n)+h(n) em que g(n) é o custo do nó n e h(n) é o seu valor heurístico, designa-se essa família de algoritmos por A. Se se modificar o algoritmo de procura ordenada por forma a que o teste de estado objetivo seja feito sobre o nó n que é selecionado depois de colocar todos os sucessores em ABERTOS, tem-se o algoritmo A*. Algoritmo de procura ótimo A função de avaliação f’(n)=g(n)+h’(n) dá uma estimativa do custo total do caminho de custo mínimo que passa por n. Nota: O algoritmo de custo uniforme encontra a solução ótima (de menor custo). h’(n)≡0 => o algoritmo A* coincide com o do custo uniforme, e encontra a solução ótima. Pode demonstrar-se que se h’ for um limite inferior de h, o algoritmo A* continua a encontrar a solução ótima. Ver pp. 60 e seguintes Nils Nilsson. Admissibilidade Um algoritmo diz-se admissível se, para qualquer grafo, descobre sempre o caminho ótimo para o objetivo, desde que esse caminho exista. Se h’ é um limite inferior de h então o algoritmo A* é admissível. A admissibilidade implica que: ▪ Quando o A* expande um nó n já encontrou um caminho ótimo para n. ▪ Quando o A* expande um nó n a função de avaliação f’ não é maior que o custo real f. Informação Heurística Usar h’(n)≡0 reflete a ausência total de conhecimento acerca do domínio de aplicação pelo que embora o algoritmo seja admissível é pouco prático. Um algoritmo A é mais informado do que um algoritmo B se hA > hB para todos os estados exceto o objetivo. Exemplo: 8-puzzle com h=W em que W é o número de peças erradas. Este algoritmo é mais informado do que o do custo uniforme (h’=0). Consistência Pode demonstrar-se que se a heurística for consistente o A* nunca expande mais nós do que um algoritmo A com informação heurística menor ou igual. Consistente  h’(m) – h’(n) ≤ h(m) – h(n), ou seja: a estimativa do custo do caminho entre dois nós é um limiar inferior (ou igual) do custo real. Esta característica é normalmente verificada desde que a heurística não mude ao longo do processo de procura. Exemplo: h=W é consistente. Exercícios sobre o A* Medidas de desempenho IDA* (Iterative Deepening A*) Os requisitos de memória dos métodos não informados aumentam exponencialmente com a profundidade do estado objetivo no espaço de procura. A utilização de heurísticas não evita este problema, apesar de reduzir o fator de ramificação. IDA* surge em 1985 (Korf) Pode ser objeto de implementação paralela (Powley, Ferguson e Korf 1993; O IDA* garante a descoberta da solução ótima, desde que se use uma heurística admissível. Aplica-se uma série de vezes o método de procura em profundidade, com limiares de profundidade variáveis, mas em que o limite (“cost cutt-off”) é dado em termos do f. Na primeira pesquisa o limiar L é dado por f’(n0) = g(n0) + h’(n0) = h’(n0), em que n0 é o nó inicial. O custo do caminho ótimo pode ser igual ao limiar, mas não maior dado que a heurística tem de ser admissível, i.e., h(n0) >= h’(n0) Só se expandem nós com f’(n) NAO H2 = max(h0 -1, 0) -> SIM 16- Será que o SMA* pode gerar o mesmo nó várias vezes? R: Pode, porque a ideia base deste algoritmo é a de que quando é necessário gerar um sucessor, mas não há memória disponível é preciso abrir espaço, “esquecendo” um dos nós anteriormente gerados, habitualmente o que contem o f’ mais elevado e é incapaz de resolver o tipo de problemas em que é necessário gerar repetidamente as mesmas subárvores ao oscilar entre caminhos candidatos. 17- Será que o RBFS* pode gerar o mesmo nó várias vezes? R: Sim, o RBFS pode gerar o mesmo nó várias vezes isto porque o RBFS é um algoritmo de procura limitada que utiliza uma abordagem recursiva para explorar. O RBFS mantem um limite de procura baseado em f(n), semelhante ao IDA*, mas ao contrário do IDA* que realiza várias procuras em profundidade e descarta o estado da procura anterior, o RBFS utiliza a recursividade para voltar atras e revistar nós anteriores. 18- Quais os algoritmos de procura em que é possível que o mesmo nó seja apagado e voltado a gerar mais tarde ? R: a. SMA* R: b. RBFS c. A* d. Custo Uniforme R: e. IDA* 19- A modelação de problemas usando espaço de estados exige a definição dos seguintes aspetos: R: a. Estado inicial b. Lista de Abertos R: c. Lista de Operadores de Transição R: d. Estado Objetivo e. Penetrância 20- Quais os elementos de programação que são diretamente dependentes do domínio de aplicação? Marque todas as opções que se aplicam. R: a. Heurística R: b. Custo de um nó R: c. Função de determinação de estado final R: d. Operadores de transição R: d. Estado do problema. 21- Considere a implementação do algoritmo A* / IDA* / SMA* em LISP para resolver um problema por procura em espaço de estados. Quais os tipos abstratos de dados que considera necessário implementar para cada um? Marque todas as opções que se aplicam. A* → Nó e Lista de Fechados IDA* → Custo e Lista de Abertos SMA* → Nó do grafo 22- A garantia de obtenção da solução ótima depende de: a. Custo entre cada nó N e o nó inicial R: b. Admissibilidade da heurística usada, quando se usam algoritmos informados c. Lista de operadores 23- A garantia de obtenção da solução ótima quando se usa o algoritmo A* depende de: ? a. Fator de ramificação do problema R: b. Valor da heurística usada, para cada nó N, quando se usam algoritmos informados c. Profundidade a que se encontra o nó final 24- Comparando a eficiência de dois algoritmos de procura, qual é incondicionalmente melhor? R: a. O que tem penetrância maior b. O que tem um fator de ramificação média maior c. O que encontra o nó final num nível de profundidade menor R: d. O que gera menos nós admitindo que ambos encontram a solução no mesmo nível de profundidade 25- O que são tabelas de transposição? Indique uma possível forma de implementação em LISP. R: Tabelas de transposição servem como que uma cache onde se pode guardar os estados para que na geração de um estado já existente se consulte a hashtable evitando a geração de alguns estados consequentes que possam já ter sido gerados previamente. 26- Comente a afirmação “Não há nada de tão prático como uma boa teoria” (Ludwig Boltzmann) R: Uma boa teoria deve ser válida, deve ser um modelo semanticamente consistente. Uma boa teoria deverá ter poder descritivo e prescritivo e por isso ajudar a compreender a realidade e a resolver problemas. 27- O MINIMAX ou Alfa Beta pode aplicar-se a que tipos de jogos? Assinale todas as respostas corretas: a) Cooperativos b) Simultâneos R: c) De soma nula R: d) Sequenciais 28- Qual é a relação matemática que explica a razão de ser da utilização do algoritmo NEGAMAX em termos da sua relação com o MINIMAX? R: max(a,b) = -min(-a,-b) 29- Qual a razão pela qual o algoritmo ALFA-BETA é considerado melhor do que o MINIMAX? Assinale todas as respostas que se aplicam: a. O ALFA-BETA percorre o grafo em profundidade primeiro e o MINIMAX em largura primeiro. R: b. O ALFA-BETA realiza cortes no grafo, não explorando certas subárvores. c. O MINIMAX tem sempre de explorar mais níveis do que o ALFA-BETA. d. O ALFA-BETA explora mais nós do que o MINIMAX no mesmo intervalo. 30- Explique o que é o alfa e o beta, usados no algoritmo ALFA-BETA e como se usam durante o processamento de uma árvore de jogo. R: Seja a o valor da melhor escolha encontrada até ao momento, ao longo do ramo corrente, para MAX. Seja ß o valor da melhor escolha encontrada até ao momento, ao longo do ramo corrente, para MIN. O ALFA-BETA utiliza estes valores para efetuar cortes nas subárvores geradas. 31- Como se relacionam os algoritmos ALFABETA e MINIMAX? Assinale todas as respostas corretas: a) O ALFABETA percorre o grafo em largura primeiro e o MINIMAX em profundidade primeiro. b) O MINIMAX explora todos os nós da árvore e o ALFABETA não. R: c) O ALFABETA realiza cortes no grafo quando o valor da função de avaliação é menor que zero. d) O ALFABETA explora mais nós do que o MINIMAX no mesmo intervalo de tempo. 32- Um sistema pericial realiza um raciocínio não probabilístico, logicamente válido, em que faz um diagnóstico com base numa série de observações, usa valores lógicos no intervalo [0, 1], está a aplicar o quê? Marque todas as respostas corretas. R: a. Dedução b. Encadeamento para trás R: c. Encadeamento para a frente – através de uma série de observações d. Indução e. Lógica Booleana →{} R: f. Lógica Fuzzy →[] 33- Diga quais os tipos de inferência que não podem garantir a validade dos resultados. R: a) Abdução R: b) Indução c) Dedução 34- Quais os componentes da arquitetura de um sistema pericial que são de natureza declarativa? Indique todos os que se apliquem. R: a) Base de Conhecimento b) Motor de Inferência c) Módulo de Explicação 35- Porque é que um sistema pericial precisa de um módulo de explicação? R: a) Porque pode dar respostas erradas b) Porque representa um modelo da realidade c) Porque tem interesse didático 36- Desenhe o esquema de blocos da arquitetura de um Sistema Pericial e indique as características dos principais módulos, caracterizando os em especial quanto à sua dependência do domínio e à natureza do conhecimento que contêm. Base de Conhecimento: Natureza essencialmente declarativa, Dependente do domínio. Máquina de Inferência: Natureza essencialmente procedimental, Independente do domínio. 37- Considere a seguinte regra: (?y tem ?x anos) (?y é Europeu) (?z é Americano) (?z tem ?x anos) => (?y e ?z gostam das mesmas séries) O diagrama RETE desta regra tem: a) 3 nós alfa e 4 nós beta b) 4 nós alfa e 4 nós beta R: c) 4 nós alfa e 3 nós beta d) 3 nós alfa e 3 nós beta 38- Desenhe a árvore de decisão mínima e as regras de produção resultantes da interpretação da árvore de decisão obtida 39- A utilização de heurísticas no processo de resolução de problemas de espaço de estados reduz o número de nós expandidos por unidade de tempo. a) Sim b) Não 40- O algoritmo MINIMAX propaga valores dos nós folha para o nó raiz? a) Sim b) Não 41- A função que determina o valor dos nós de um grafo de jogo a que se aplica o MINIMAX sem cortes tem uma natureza heurística. a) Sim b) Não 42- O algoritmo MINIMAX sem cortes que gera uma árvore de jogo com 10 níveis e um fator de ramificação de 2 exige a aplicação da função de avaliação mais de mil vezes. a) Sim b) Não 43- No ALFABETA, o valor do nó raiz do grafo de jogo é sempre o mesmo quais quiser que sejam os cortes alfa e beta aplicados. a) Sim b) Não 44- Um jogo de soma nula (ou soma zero) é aquele em que o valor da função ALFABETA para o nó inicial é zero. a) Sim b) Não 45- O algoritmo ALFABETA pode incorrer numa explosão combinatória? a) sim b) não c) depende do nível máximo de profundidade permitido 46- O Algoritmo ALFABETA pode dar valores, para alguns dos nós do grafo de jogo, diferentes dos obtidos pelo algoritmo NegaMax. a) Sim b) Não 47- Um sistema pericial pode dar respostas erradas? a) Sim b) Não 48- A base de conhecimento é um declarativo de arquitetura de um sistema pericial. a) Sim b) Não 49- O mecanismo de explicação existe porque o sistema pericial pode dar resultados errados. a) Sim b) Não 50- As regras de um sistema pericial estão inseridas no motor de inferência e os factos estão na base de conhecimento. a) Sim b) Não -> (Ambos são parte da base do conhecimento) 51- O motor de inferência é dependente do domínio de aplicação. a) Sim b) Não 52- A existência de uma boa teoria do domínio de aplicação aconselha a utilização de sistemas periciais. a) Sim b) Não 53- O raciocínio efetuado na máquina de inferência dos sistemas periciais baseados em sistemas de produção e lógica de primeira ordem é de natureza dedutiva. a) Sim b) Não 54- Considere o puzzle-de-8, com as posições inicial e final indicadas de seguida. Use como heurística a distância de Manhattan (somatório das distâncias das peças à posição correta). Apresente o grafo gerado pelo A* indicando os valores de f, g e h para todos os nós gerados e indique a fórmula e calcule o valor da penetrância para este problema. R: 55- Considere o puzzle-de-8, com as posições inicial e final indicadas de seguida. Use como heurística a distância de Manhattan (somatório das distâncias das peças à posição correta). Apresente o grafo gerado pelo A* indicando os valores de f, g e h para todos os nós gerados e indique a fórmula e calcule o valor da penetrância para este problema. R: 56- Considere o puzzle-de-8, com as posições inicial e final indicadas de seguida. Use como heurística a distância de Manhattan (somatório das distâncias das peças à posição correta). Apresente o grafo gerado pelo A* indicando os valores de f, g e h para todos os nós gerados e indique a fórmula e calcule o valor da penetrância para este problema. R: 57- Considere a seguinte posição do jogo do galo. Determine a melhor jogada a realizar pelo jogador X, usando para isso: a) o algoritmo MINIMAX. 58- Resolver o Alfa-Beta para o seguinte exercício: 59- Resolver o Alfa-Beta para o seguinte exercício: 60- O Jogo do NIM é um jogo de 2 adversários em que existem várias pilhas de objetos e cada jogador pode tirar qualquer número de objetos de qualquer uma das pilhas. O jogador que tira o último objeto perde. a) Use o alfabeta para determinar a melhor jogada no jogo (1 2 1). b) Use o alfabeta para determinar a melhor jogada no jogo (1 2 2). 61- Considere o problema do quadrado mágico 3x3 em que se querem distribuir os números de 1 a 9 num quadrado de forma que a soma da linhas, colunas e diagonais resulte sempre no mesmo valor. Exemplo: 816 357 492 Defina o espaço de estados do problema, os operadores e uma função de avaliação de solução. 62- Considere o problema das torres de Hanói em que se pretende passar n discos de tamanhos distintos empilhados de uma posição para outra, existindo uma posição intermédia. Só se pode mover um disco de cada vez e não se pode colocar um disco maior sobre um mais pequeno. Defina o espaço de estados do problema, os operadores e uma função de avaliação de solução. 63- Considere o problema dos Missionários e os Canibais. Quer-se passar de um lado para o outro do rio, três missionários e três canibais. Existe um só barco com lotação máxima de duas pessoas. Os missionários nunca podem estar em inferioridade numérica.