Apostila

Prévia do material em texto

<p>I. Introdução a IA</p><p>Slides IA-1-introducao.pdf</p><p>II. Agentes Inteligentes</p><p>1. Definição: Um agente é tudo o que pode ser considerado capaz de perceber seu ambiente por meio</p><p>de sensores e de agir sobre esse ambiente por intermédio de atuadores.</p><p>2. Exemplos de Agentes</p><p>• Agente humano</p><p>– Sensores: olhos, orelhas e outros órgãos</p><p>– Atuadores: mãos, pernas, boca e outras partes do corpo</p><p>• Agente robótico</p><p>– Sensores: câmaras e detetores de infravermelhos</p><p>– Atuadores: motores</p><p>3. Conceitos</p><p>• Percepção: conjunto de entradas perceptivas do agente em qualquer momento dado.</p><p>• Sequência de percepções: história de tudo o que o agente já percebeu. A escolha de uma ação</p><p>pode depender da sequência de percepções observadas até o momento.</p><p>• Função agente: descreve o comportamento do agente. Mapeia a sequencia de percepções para</p><p>ações. Essa função é uma descrição matemática abstrata.</p><p>• Programa de agente: implementa a função agente. É uma implementação concreta relacionada</p><p>à arquitetura do agente.</p><p>Exemplo: O mundo do Aspirador</p><p>Percepções: Agente percebe:</p><p>• em que quadrado está,</p><p>• se existe sujeira no quadrado.</p><p>Função do agente: Se o quadrado atual estiver sujo, então aspirar; caso contrário mover-se para o</p><p>outro quadrado</p><p>Programa de agente:</p><p>função AgenteAspirador ([posição, estado]) devolve ação</p><p>Se estado = Sujo então devolve Aspirar</p><p>Senão se posição = A então devolve Direita</p><p>Senão se posição = B então devolve Esquerda</p><p>4. Medida de desempenho</p><p>Critério objectivo que mede o sucesso do comportamento do agente.</p><p>Exemplo: medida de desempenho do agente aspirador pode ser a sujidade aspirada, tempo</p><p>utilizado, eletricidade consumida, ruído gerado, etc.</p><p>5. Racionalidade</p><p>Um agente racional é aquele que faz tudo certo. A ação certa é aquela que fará o agente obter</p><p>maior sucesso. Para isso precisaremos de algum método para medir o sucesso: Medida de</p><p>desempenho.</p><p>O que é racional em qualquer instante depende de 4 fatores:</p><p>•Medida de desempenho,</p><p>•Conhecimento anterior</p><p>•Ações que o agente pode executar</p><p>•Sequencia de percepções</p><p>Definição de Agente Racional</p><p>Para cada sequência de percepções possível, um agente racional deve selecionar uma ação que se</p><p>espera venha a maximizar sua medida de desempenho, dada a informação disponibilizada pela</p><p>sequência de percepções e eventualmente pelo conhecimento que o agente possui.</p><p>5.1. Onisciência:</p><p>É a capacidade de saber tudo infinitamente. Um agente onisciente sabe o resultado real de suas</p><p>ações e pode agir de acordo com ele; porém, a onisciência é impossível na realidade pois não é</p><p>possível saber todo a priori.</p><p>Exemplo:</p><p>Você esta caminhando na avenida paulista e de repente vê um velho amigo do outro lado da rua.</p><p>Não existe nenhum tráfego perto e você não tem nenhum outro compromisso, sendo racional,</p><p>você atravessa a rua. Enquanto isso, a 10 000 metros de altura a porta do compartimento de</p><p>carga se solta de um avião e antes de chegar ao outro lado da rua, você é atingido.</p><p>Conclusão: não foi irracional atravessar a rua, mas é impossível a onisciência na vida real</p><p>Logo:</p><p>Racionalidade ≠ omnisciência: Percepções nas quais se baseou um agente racional podem não</p><p>disponibilizar conhecimento que é importante na realidade.</p><p>Racionalidade ≠ clarividência: Resultado de uma ação pode não estar de acordo com o</p><p>esperado.</p><p>Logo, racionalidade ≠ sucesso.</p><p>5.2. Aprendizagem</p><p>Um agente racional deve aprender tanto quanto possível do que ele percebe. A configuração</p><p>inicial do agente poderia refletir algum conhecimento anterior do ambiente mas, à medida que o</p><p>agente ganha experiência, isso pode ser modificado e ampliado.</p><p>5.3. Autonomia</p><p>Um agente é autônomo se o seu conhecimento for determinado apenas pela sua experiência</p><p>(com capacidade de aprender e adaptar-se). Agentes podem tomar ações para obter informações</p><p>úteis.</p><p>Um agente racional deve ser autônomo. Ele deve aprender o que puder para compensar um</p><p>conhecimento prévio parcial ou incorreto.</p><p>6. Ambiente de Tarefas</p><p>Ambientes de tarefas são essencialmente os “problemas” para os quais os agentes racionais são as</p><p>“soluções”.</p><p>6.1. Especificação do ambiente de tarefas</p><p>Para especificar um ambiente de tarefas, precisamos especificar 4 itens. Essa descrição dos 4</p><p>itens chama-se PEAS.</p><p>PEAS (Performance, Environment, Actuators, Sensors): desempenho, ambiente, atuadores,</p><p>sensores.</p><p>A primeira tarefa quando se projeta um agente deve ser especificar o</p><p>ambiente de tarefa de forma tão completa quanto possível.</p><p>Exemplo: PEAS: agente taxista</p><p>Desempenho</p><p>– Segurança, destino, lucros, legalidade, conforto</p><p>Ambiente</p><p>– Clientes, estradas, trânsito, transeuntes, tempo</p><p>Atuadores</p><p>– Volante, acelerador, travão, buzina, pisca</p><p>Sensores</p><p>– GPS, conta km, velocímetro, nível do depósito, temperatura do óleo</p><p>Exemplo: PEAS: Agente sistema de diagnóstico médico</p><p>Medida de Desempenho</p><p>– Saúde do paciente, custos</p><p>Ambiente</p><p>– Paciente, hospital, funcionários</p><p>Atuadores</p><p>– Monitor: exibe diagnósticos, tratamentos</p><p>Sensores</p><p>– Teclado: sintomas, respostas do paciente.</p><p>6.2. Tipos de ambientes de tarefa</p><p>• Completamente observável vs. Parcialmente observável</p><p>• Determinístico vs. Estocástico</p><p>• Episódico vs. Sequencial</p><p>• Estático vs. dinâmico</p><p>• Discreto vs. contínuo</p><p>• Agente único vs. Multi-agente</p><p>7. Tipos de agentes</p><p>• Agentes reativos simples</p><p>É o tipo mais simples de agente. Selecionam ações com base na percepção atual, ignorando o</p><p>restante do histórico de percepções.</p><p>Função AgenteReativoSimples (percepção) devolve ação</p><p>Variaveis estáticas: regras (conjunto de regras condição-ação)</p><p>estado ← InterpretarEntrada(percepção)</p><p>regra ← RegraCorrespondente(estado,regras)</p><p>ação ← AcãoDaRegra[regra]</p><p>retornar ação</p><p>• Agentes reativos baseados em modelos</p><p>Mantêm um estado interno para aspectos que não pode ver agora. Este estado interno está</p><p>baseado no histórico de percepções e permite refletir sobre aspectos atuais não conhecidos.</p><p>Para atualizar essas informações internas precisa-se:</p><p>- como o mundo evolui independentemente do agente</p><p>- como as ações do agente afetam o mundo</p><p>O agente baseado em modelo é aquele que usa esse modelo do mundo.</p><p>Assim a figura a seguir mostra como a percepção atual é combinada com o estado interno antigo</p><p>para gerar a descrição atualizada do estado atual.</p><p>Função AgenteReflexosBaseadoEmModelos (percepção) devolve acção</p><p>Variáveis estáticas: estado (descrição do estado do mundo)</p><p>regras (conjo de regras condição-acção)</p><p>ação (a acção mais recente)</p><p>estado ← ActualizarEstado(estado,ação,percepção)</p><p>regra ← RegraCorrespondente(estado,regras)</p><p>acção ←AçãoDaRegra[regra]</p><p>devolve acção</p><p>• Agentes baseados em objetivos</p><p>Conhecer o estado atual do ambiente nem sempre é suficiente para decidir o que fazer. Assim</p><p>como temos o estado do mundo atual, precisamos informação sobre objetivos para decidir</p><p>situações que queremos alcançar (objetivos). Assim, um agente tem um (ou mais) objectivo(s)</p><p>As vezes, uma única ação satisfaz um objetivo. Outras vezes, precisa-se considerar longas</p><p>sequencias de ações até encontrar um meio de atingir o objetivo. Busca e planejamento são</p><p>subcampos da IA dedicados a encontrar sequencias de ações que alcançam os objetivos do</p><p>agente.</p><p>A tomada de decisões sobre que ações adotar é mais complexa pois envolve considerações a</p><p>futuro.</p><p>Além de ter as mesmas caraterísticas de um agente reativo simples, incrementa considerações</p><p>sobre o futuro, a fim de alcançar os objetivos.</p><p>Exemplo: O agente taxista tem como objectivo chegar a um destino. Chegando a um</p><p>cruzamento, o agente decide avançar, virar à direita ou virar à esquerda em função do objetivo.</p><p>• Agentes baseados em utilidade</p><p>Para ter um comportamento de alta qualidade, precisam-se mais que objetivos. Existem varias</p><p>maneiras de chegar a um objetivo, mas a utilidade permite escolher aquela forma que dará</p><p>maior utilidade ao agente (medindo o grau de felicidade).</p><p>A função de utilidade permite estabelecer preferências entre sequências</p><p>de estados que</p><p>permitem atingir os mesmos objetivos</p><p>Exemplo: Um agente taxista pretende chegar a um destino. A função de utilidade permite</p><p>distinguir as diferentes formas de chegar ao destino, em função do tempo, da despesa, da</p><p>segurança. Escolhe-se então aquela forma de chegar ao destino que incremente a utilidade.</p><p>• Agentes com aprendizagem</p><p>Correspondem à ideia de máquina inteligente caracterizada por Turing (1950)</p><p>O agente pode atuar num mundo inicialmente desconhecido.</p><p>• Elemento de aprendizagem: Torna o agente mais eficiente ao longo do tempo, – Usa</p><p>feedback da crítica que avalia atuação do agente de acordo com o desempenho espectável</p><p>• Elemento de desempenho: Responsável por selecionar as ações do agente</p><p>• Elemento de geração de problemas: Sugere ações que podem trazer informação útil</p><p>III. BUSCA em Espaço de Estados</p><p>1. Agentes de resolução de problemas</p><p>É um tipo de agente baseado em objetivos. Estes agentes decidem o que fazer encontrando</p><p>sequências de ações que levam a estados desejáveis.</p><p>Os agentes inteligentes devem maximizar a sua medida de desempenho. Isso às vezes é</p><p>simplificado se o agente pode adotar um objetivo e desejar satisfazê-lo.</p><p>Exemplo:</p><p>Temos um agente na cidade de Arad na Romênia de férias.</p><p>Medida de desempenho:</p><p>• melhorar língua romena</p><p>• ver paisagens</p><p>• apreciar vida noturna</p><p>• melhorar bronzeado</p><p>• etc.</p><p>Este é um problema de decisão Complexo pois envolve muitos compromissos e a leitura cuidadosa</p><p>de guias de viagem.</p><p>Agora suponha que o agente tem uma passagem não-reembolsável saindo de Bucareste(capital da</p><p>Romênia) com destino Brasil para amanhã.</p><p>Objetivo: Chegar a Bucareste a tempo para o vôo.</p><p>As ações que impedem a chegada a tempo a Bucareste podem ser rejeitadas e o problema fica</p><p>bastante simplificado quando estabelecemos o objetivo.</p><p>2. Conceitos</p><p>Formulação de objetivos</p><p>Os objetivos ajudam a organizar o comportamento do agente</p><p>A formulação de objetivos é o primeiro passo para a resolução de problemas e está baseada na</p><p>situação atual e na medida de desempenho.</p><p>Objetivo: Conjunto de estados do mundo (estados em que o objetivo é satisfeito).</p><p>Tarefa do agente: descobrir que sequência de ações o levará a um estado objetivo.</p><p>Formulação de problemas: processo de decidir que ações e estados devem ser considerados,</p><p>dado um objetivo.</p><p>3. Busca</p><p>Um agente com várias opções imediatas de valor desconhecido pode decidir o que fazer</p><p>examinando primeiro diferentes sequências de ações possíveis que levam a estados de valor</p><p>conhecido, e depois escolhendo a melhor sequência. A procura dessa sequencia é uma BUSCA.</p><p>Um algoritmo de busca:</p><p>• recebe um problema como entrada e</p><p>• retorna um solução sob a forma de uma sequencia de ações.</p><p>4. Fases para resolver um problema</p><p>• Formulação : processo de decidir que ações e estados devem ser considerados, dado um objetivo</p><p>(o veremos mais a detalhe na seção a seguir).</p><p>• Busca : Podemos usar uma algoritmo de busca com as ações e estados definidos na formulação</p><p>do problema e obteremos uma sequencia de ações recomendadas.</p><p>• Execução : Processo de fazer as ações devolvidas pelo algoritmo de busca.</p><p>Estas fases são ilustradas na Figura a seguir.</p><p>5. Formulação de problemas</p><p>Um problema é definido por quatro itens descritos a seguir.</p><p>Os exemplos estão baseados no problema do agente da Romênia que quer ir a Bucareste.</p><p>• Estado inicial . Estado em que o agente começa.</p><p>Ex: Em(Arad), pois o agente encontra-se inicialmente em Arad.</p><p>• Função sucessor : A função sucessor é a formulação mais comum para descrever as ações</p><p>possíveis que estão disponíveis para o agente.</p><p>Dado um estado particular x, Sucessor(x) retorna um conjunto de pares ordenados</p><p><ação,sucessor> em que cada ação é uma das ações válidas no estado x e cada sucessor é um</p><p>estado que pode ser alcançado a partir do estado x aplicando-se a ação.</p><p>Exemplo: Sucessor(Arad)->{<Ir(Sibiu), Em(Sibiu)>,}</p><p>• Teste de objetivo : Determina se um dado estado é um estado objetivo</p><p>Exemplo: {Em(Bucareste)}</p><p>• Custo de caminho ou Função de custo : Reflete medida de desempenho. Custo numérico de</p><p>cada caminho. Ex: cumprimento do caminho em km.</p><p>Custo de passo: Custo para ir do estado x ao estado y.</p><p>6. Espaço de estados</p><p>Conjunto de todos os estados acessíveis a partir do estado inicial.</p><p>Definido implicitamente pelo estado inicial e a função sucessor.</p><p>Grafo (representação de estados)</p><p>O espaço de estados pode ser representado em forma de grafo onde:</p><p>• Nós : estados</p><p>• Arcos : ações</p><p>Exemplo: O mapa da Romênia mostrado na Figura a seguir pode ser interpretado como um</p><p>grafo do espaço de estados. Os estados (nós do grafo) representam o fato de estar em uma</p><p>cidade e as ações (arcos) representam duas ações (cada arco é bidirecional) pois existe a</p><p>possibilidade de dirigir para cada sentido.</p><p>Um caminho no espaço de estados é uma sequência de estados conectados por uma sequência</p><p>de ações. Exemplo: Um caminho desde Neamt até Iasi tem uma sequencia de ações: Ir(Iasi),</p><p>Ir(Vaslui).</p><p>7. Árvore de busca</p><p>Além de formular os problemas, precisamos resolve-los. Isso é feito por meio de uma busca em</p><p>todo o espaço de estados.</p><p>Para isso podemos utilizar uma árvore de busca explícita, gerada pelo estado inicial e pela</p><p>função sucessor que também servem para definir o espaço de estados (por isso também pode-se</p><p>gerar a árvore de busca analisando o grafo do espaço de estados).</p><p>As 3 Figuras a seguir mostram algumas das expansões da árvore de busca para encontrar uma</p><p>rota de Arad até Bucareste. A raiz da árvore de busca é um nó de busca correspondente ao</p><p>estado inicial, Em(Arad). Depois após verificar queesse não é um estado objetivo, podemos</p><p>expandir o estado atual. Para realizar a expansão devemos aplicar a função sucessor ao estado</p><p>atual, gerando assim um novo conjunto de estados. Neste caso, ao expandirmos Em (Arad),</p><p>alcançamos um novo conjunto de estados: Em(Sibiu), Em(Timisoara), Em(Zerind). Após isso</p><p>seguimos expandindo cada um dos novos estados alcançados seguindo uma opção e deixando as</p><p>outras reservadas, no caso que a primeira escolha não leve a uma solução. A escolha de qual</p><p>estado expandir é determinada pela estratégia de busca.</p><p>(a) O estado inicial Arad</p><p>(b) Depois de expandir Arad</p><p>(c) Depois de expandir Sibiu</p><p>IV. Busca em Largura</p><p>1. Conceito</p><p>O nó raiz é expandido, em seguida todos os nós sucessores são expandidos, então todos próximos nós</p><p>sucessores são expandidos, e assim em diante.</p><p>2. Algoritmo</p><p>3. Exemplo</p><p>O exemplo a seguir mostra um diagrama passo a passo do desenvolvimento do algoritmo</p>