Algoritmos de Busca para Inteligência Artificial
Este texto é parte da disciplina de Fundamentos de Inteligência Artificial do Programa de Pós-Graduação em Computação da Universidade Federal de Pelotas e não foi feito para fazer muito sentido fora deste contexto.
Algoritmos de busca são a base de muitas sub-áreas da Inteligência Artificial, desde raciocínio lógico até aprendizado de máquina. De forma sucinta, um algoritmo de busca enumera possíveis soluções para um problema seguindo alguma sistemática que permita (e as vezes garanta) que uma solução desejada seja encontrada.
Considere como você soluciona um problema do tipo Sudoku abaixo, onde deve-se preencher os espaços vazios com números entre 1 e 4 de forma que todas colunas, todas linhas e todos quadrados delimitados internos possuam todos números.
Para cada posição, você provavelmente testou diferentes números verificando se o número testado (a solução candidata) satisfaz as condições do jogo. Ao chegar no número correto, você parou. Ou seja, você buscou por uma solução enumerando possíveis soluções candidatas. Podemos nos perguntar o quão eficiente é o método que você utilizou. Certamente você não testou múltiplas vezes o mesmo número. Talvez você tenha olhado os números que já existem na coluna e/ou linha que tentava preencher, de forma a não repetir números que já estavam ali. Talvez inspirado pelo assunto anterior da disciplina tenha aplicado lógica ao problema para pelo menos eliminar soluções incorretas.
Você concorda que quanto menos tentativas forem feitas para solucionar o problema, o que é correlacionado com a rapidez com que se soluciona o problema, mais "inteligente" é o método?
Se considerarmos que solucionar Sudoku é uma atividade que exige inteligência, e que é primariamente solucionado por humanos (ainda que para fins de entretenimento), então construir um algoritmo que solucione Sudoku se encaixa em nossa definição de IA. E, então, devemos nos perguntar como criar este algoritmo e o quão eficiente (ou, "inteligente") ele é.
Ao longo da história da computação, múltiplos algoritmos foram propostos para abordar problemas como este, sendo referenciados como "algoritmos de busca" em geral, levando ao método de IA denominado "solução de problemas por meio de busca". Algoritmos de busca aparecem em diversas formas e são desenvolvidos para abordar particularidades do problema, ou da classe de problemas, que se tenta solucionar. O Sudoku é um tipo de problema onde o número de estados (soluções candidatas) é finito, há exatamente uma solução possível, é determinístico e totalmente observável.
Podemos solucionar a instância de Sudoku lá de cima com uma técnica conhecida como Busca Exaustiva Sem Informação. Na sua forma mais simples, basta preenchermos todos os espaços vazios com quaisquer números e verificar se chegamos à solução, apenas tomando algum cuidado para não ficar gerando o mesmo estado múltiplas vezes. São 8 espaços vazios, 4 números possíveis em cada um, o que dá 8⁴ =4096 possibilidades. Um computador passa por todas em micro-segundos.
Porém, mesmo problemas bem-comportados como o Sudoku podem ser desafiadores, simplesmente devido a enorme quantidade de estados. É o problema da explosão do espaço de estados e é bem evidente quando tentamos solucionar um Sudoku mais realista, como o abaixo.
Com a mesma técnica força-bruta delineada dois parágrafos acima, quantos estados existem para serem testados? Considerando que um computador leva 10 nano-segundos para passar por cada estado, qual o tempo esperado para encontrar uma solução? Como isso se compara com uma pessoa com experiência nesse tipo de jogo? Faça as contas. E o tempo nem é o maior problema aqui — para garantir que não geramos estados repetidos, precisaríamos armazenar os que já geramos na memória. Não há memória que chegue.
Esta explosão do espaço de estados é um dos maiores problemas da IA (e da Computação como um todo) e afeta virtualmente todas suas metodologias — é o maior limitador para implementar programas lógicos extensos, por exemplo.
Este é um bom momento para ler o Capítulo 6 da nossa referência até a seção 6.2 (inclusive), que trata da busca exaustiva sem informação e métodos para torná-la um pouco melhor.
É evidente que força-bruta pura não é muito inteligente e técnicas melhores são necessárias. Um passo adicional é Busca Exaustiva com Informação ou Busca Heurística. Uma heurística é uma função aproximada para algo. No contexto de buscas, é uma função que retorna, para um dado estado, o custo aproximado de chegar deste estado até uma solução. Enquanto para uma busca sem informação todos os estados são iguais e não importa a ordem com que o algoritmo os avalia, a heurística permite priorizar estados "promissores", grandemente reduzindo o número de estados necessários a serem avaliados.
Esta função é externa ao problema e deve ser provida de alguma forma. Pode-se utilizar conhecimento de um especialista sobre o problema ou aplicar técnicas para encontrar heurísticas úteis. Por exemplo, no Sudoku uma heurística é iniciar o preenchimento pelo quadrado que possui o maior número de números já preenchidos. Note que isso não faz parte das regras do jogo, é uma regra induzida pela experiência.
Neste momento, leia a Seção 6.3 do Capítulo 6 da referência. Deixaremos a 6.4 em diante para a próxima semana.
Para pensar: o algoritmo é inteligente se a heurística é fornecida por uma inteligência externa (i.e. uma pessoa)? Este é um dos argumentos usado por Kasparov para questionar se ele realmente perdeu para uma IA ou apenas para um grupo de especialistas intermediado por computador. Discuta no fórum.
Ainda que não exista uma resposta satisfatória para essa pergunta, é importante observar que a abordagem utilizando algoritmos de busca é qualitativamente diferente de criar um algoritmo que soluciona uma instância do problema apenas. Por exemplo, é simples criar um algoritmo que soluciona uma única instância do Sudoku — o programador só precisa solucionar o jogo (talvez com ajuda de um especialista) e colocar os valores da solução no programa. Mas dada uma nova instância do jogo, este programa falhará, enquanto a técnica de IA fornecerá solução para qualquer instância solucionável, inclusive aquelas nunca vistas antes pelo criador do algoritmo. É verdade que o criador potencialmente teve que pensar em heurísticas, mas isso não é a mesma coisa que solucionar o problema. Pode-se argumentar que é um trabalho cooperativo que utiliza o melhor dos computadores e o melhor dos seres humanos. Isso é o tema do chamado Paradoxo de Moravec, que discutiremos mais adiante na disciplina.
