********************************** ********** IA - Matéria ********** ********************************** Data : 17/03/2005 a 18/04/2005 Versão : 04/07/2007 Professor: Fabrício Jailson Barth Autor : Leandro Salvador ( leandrosalvador.com.br ) * Bibliografia - Artificial Intelligence - A Modern Approach - Stuart Russell & Peter Norvig - Prentice Hall - 1995 * Objetivos - desenvolver sistemas inteligentes - são sistemas que solucionam problemas comlexos de maneira otimizada - entender a concepção de inteligência * Temas (Capítulos do livro-texto) - 1 e 2 - Introdução, Agente, Ambiente - 3 - Busca em espaços de estados - 4 - Buscas Heurísticas - 3 e 4 - Implementações (Busca) - 6 e 7 - Representação de conhecimento - 8 e 9 - Aquisição de conhecimento - 10 - Árvores de decisão - 18 - Aprendizado de máquina - 18 - Indução de regras - Implementações / Seminários * Divisão da Disciplina - busca - representação de conhecimento e inteligência - aprendizado de máquina * Agente - diagrama v----- percebe / sensores ------. ( Agente / Raciocina ) ( Ambiente ) `----- age / analizadores ------^ - agente autônomo --> conhecimento codificado + conhecimento aprendido * Propriedades de Ambiente - acessível --> o agente percebe todo o ambiente - determinístico --> toda a ação possui um efeito bem determinado - episódico --> pode ser dividido em instantes de tempo - estático --> enquanto o agente raciocina o ambiente não muda - discreto --> o número de ações e variáveis é conhecimento - autônomo --> conhecimento inserido pelo programador + conhecimento aprendido * Definições de Estruturas de Dados - árvore --> composta de nodos (vértices) e arestas (caminhos) - arestas --> têm sentido único - nodo-raiz --> é um nodo-pai, ou um estado inicial - nodos-filhos --> só têm um pai - folhas --> nodos que não têm filhos - exemplo (jogo de xadrez) - nodo-raiz --> estado inicial do jogo - folhas --> todas as possibilidades de cheque-mate - diagramas ( ) --> nodo-pai / \ / \ --> arestas / \ ( ) ( ) --> nodos-filhos / \ / \ / \ / \ --> arestas ( ) ( ) ( ) ( ) --> folhas - exemplo (8-puzzle) |2|3|6| |5|4|1| |8|7| | v-----^ ^-----v |2|3|6| |2|3|6| |5|4| | |5|4|1| |8|7|1| |8| |7| - exemplo (grafo) ,--->(B)--->(C)---, / ^ v (A)-----|---------->(D) \ | ^ `--->(E)----------´ A = São Paulo B = Curitiba C = Blumenau D = Porto Alegre E = Mancha - grafos também possuem nodos e arestas - existem dois tipos de grafos - unidirecional --> as arestas só possuem um sentido (acima) - bidirecional --> as arestas possuem dois sentidos sempre ,--->(B)<-->(C)<--, v ^ v (A)<----|---------->(D) ^ v ^ `--->(E)<---------´ * Resolução de Problemas Baseado em Busca em um Espaço de Estados - forma de representação do estado - identificar quais elementos são relevantes - identificação das ações (ex: no jogo dos 8 números para o espaço andar) - pré-condições - up : E 1 elemento em cima dele - down : E 1 elemento em baixo dele - right : E 1 elemento na direita dele - left : E 1 elemento na esquerda dele - OBS: E na verdade é E ao contrário, que significa "para todo e qualquer" - efeito - up : o elemento que estava em cima do branco fica no lugar do branco - down : o elemento que estava em baixo do branco fica no lugar do branco - right : o elemento que estava na direita do branco fica no lugar do branco - left : o elemento que estava na esquerda do branco fica no lugar do branco - canibais x missionários | | | | | | | | | | | | | | `-----------´|`-----------´ esquerda | direita barco - 1 = esquerda - 0 = direita - M = missionário - C = canibal |C|C|C|M|M|M|1| | | | | | | --> estado inicial | | | | | | |0|C|C|C|M|M|M| --> estado final ação : "Canibal (C) movendo pra direita (-->)" requisito: "1 Canibal do Lado Esquerdo (CLE) e barco (R[6]) do lado esquerdo (R[6] = 1) implica : "+ 1 Canibal do Lado Direito, - 1 Canibal do Lado Esquerdo" C --> : @ 1CLE ^ R[6] = 1 : +1CLD -1CLE C <-- : @ 1CLD ^ R[6] = 0 : -1CLD +1CLE M --> : @ 1MLE ^ R[6] = 1 : +1MLD -1MLE M <-- : CC --> : CC <-- : MM --> : MM <-- : CM --> : CM <-- : - OBS: @ = E invertido = para todo e qualquer Regra Geral: # L NºC <= NºM em qualquer lado o número de canibais deve ser menor ou igual que o número de missionários - OBS: # = A invertido = ??? * Algoritmos de Busca - existem 2 categorias - não-informados - informados - não-informados - têm como características ser repetitivos e seguirem um padrão - não utilizam nenhuma informação adicional do ambiente - tipos - profundidade - percorre um caminho até encontrar uma folha - então retorna até o último nó mais recente - e escolhe um outro caminho - largura - percorre todos os níveis executando todas as possibilidades - desce gradativamente pela árvore, nível por nível, todos os filhos - profundidade limitado - semelhante ao em profundidade - porém existe um limite de filhos que podem ser abertos em profundidade - profundidade iterativo - semelhante ao em profundidade limitado - porém o nível de profundidade vai começa em 1 e vai sendo alterado conforme a solução não vai sendo encontrada - tabela comparativa | Profundidade | Largura | P. Limitado | P. Iterativo | completo | não | sim | sim (se nível ideal) | sim | ótimo | não | sim | não | sim | processamento | rápido | lento | rápido | rápido | memória | pouca | alta | baixa | baixo | tempo | | | | | * Agente Orientado a Meta - o projetista não determina um mapeamento entre percepções e ações, mas determina que objetivo o agente deve alcançar - é necessário que o próprio agente continue um plano de ação que atinja seu objetivo (como se o próprio agente construísse seu programa) - exemplos - agente aspirador de pó - agente motorista de taxi - sonda espacial - o que é busca - o mundo do agente tem um conjunto de estados possíveis (muitas vezes este conjunto é infinito) - existem transições entre os estados do mundo, formando um grafo - são utilizados algoritmos para encontrar um caminho, neste grafo - partindo do estado inicial (atual) - até o estado final (objetivo) - exemplo do aspirador de pó - um robô aspirador de pó deve limpar uma casa com duas posições - as operações que ele sabe executar são - sugar - ir para a posição da esquerda - ir para a posição da direita - como o aspirador pode montar um plano para limpar a casa se inicialmente ele está na posição direita e as duas posições têm sujeira? - quais os estados possíveis no mundo do aspirador e as transições? - estados possíveis 1 [AS|S ] 2 [ S|SA] 3 [AS| ] 4 [ |SA] 5 [A |S ] 6 [ S| A] 7 [A | ] 8 [ | A] - A = Aspirador - S = Sujeira - espaço de busca (ver gráfico no livro) - por que estados? - as informações do mundo real são absurdamente complexas - é praticamente impossível modelá-las todas - no exemplo do aspirador, o mundo dele tem várias outras informações - cor do tapete - dia ou noite - material com que o aspirador é feito - quantidade de energia disponível - a notação de estado é utilizada para abstrair esses detalhes e considerar somente o que é relevante para a solução do problema - o mesmo acontece com as operações modeladas * Estratégias da Poda da Árvore de Busca - um nodo não gera um sucessor - igual a seu pai - igual a um de seus ascendentes - que já exista na árvore de busca - detalhes de implementação - verificar se um estado já está na árvore pode levar muito tempo - imagine uma árvore com milhares de estados do jogo de xadrez - cada novo estado deve ser comparado com outros milhares de estados - ter uma tabela hash (que tem tempo ótimo de consulta) - algoritmo de busca em profundidade (pilha) - crie duas pilhas: abertos e fechados - inicialize a pilha abertos = nó raiz - enquanto abertos <> vazio faça - (ver algoritmo no livro) ----------//----------