Solucionador Geral de Problemas (GPS)

O solucionador geral de problemas (GPS – General Problem Solver) é considerado por muitos como o primeiro software útil gerado pela Inteligência Artificial, criado por Simon, Shaw e Newell em 1959. Alguns autores também consideram essa data como a época clássica da IA (entre 1956 e 1970), na qual o objetivo era “simular a mente humana” por meio de solucionadores gerais de problemas e lógica. A ideia básica do GPS era resolver vários tipos de problemas utilizando o mesmo mecanismo de raciocínio. Desta forma, teríamos um algoritmo genérico que poderia ser aplicado em várias áreas do conhecimento, como se fosse uma máquina universal para solucionar problemas! Alguns exemplos  de aplicações que foram resolvidas com ele são: provas de teoremas matemáticos, problemas de geometria e até o jogo de xadrez.

Segundo os autores, a construção e a investigação desse programa teve o objetivo de entender o processamento de informações envolvido no intelecto humano e também suas habilidades criativas. Ao contrário do que muitos pensam, o propósito de sua criação não foi para relacioná-lo com o comportamento humano, mas para descrever suas principais características e analisar suas capacidades como um mecanismo para solução de problemas. No link abaixo você pode baixar o artigo original de 1958!

A estrutura de um problema que usa o GPS envolve basicamente ações e pré-condições, e o código abaixo é parte de um exemplo desenvolvido na linguagem Lisp que mostra o problema de levar o filho ao colégio. Não vou abordar o Lisp neste artigo, mas somente a estrutura básica do algoritmo para que você tenha um entendimento melhor de como ele funciona 🙂

acao ‘1-levar-filho-ao-colegio
  precondicoes ‘(filho-esta-em-casa carro-esta-em-bom-funcionamento)
  add-lista ‘(filho-no-colegio)
  del-lista ‘(filho-esta-em-casa)

acao ‘2-efetuar-a-instalacao-da-bateria-na-oficina
  precondicoes ‘(carro-necessita-de-nova-bateria oficina-instala-nova-bateria oficina-recebe-o-dinheiro-do-servico)
  add-lista ‘(carro-esta-em-bom-funcionamento)

acao ‘3-informar-problema-ao-mecanico
  precondicoes ‘(em-comunicacao-com-a-oficina)
  add-lista ‘(oficina-instala-nova-bateria)

acao ‘4-telefonar-para-a-oficina
  precondicoes ‘(conhece-o-numero-telefone-de-uma-oficina)
  add-lista ‘(em-comunicacao-com-a-oficina)

acao ‘5-procurar-numero-de-telefone-de-uma-oficina
  precondicoes ‘(possui-lista-telefonica)
  add-lista ‘(conhece-o-numero-telefone-de-uma-oficina)

acao ‘6-passar-dinheiro-para-o-caixa-da-oficina
  precondicoes ‘(possui-dinheiro)
  add-lista ‘(oficina-recebe-o-dinheiro-do-servico)
  del-lista ‘(possui-dinheiro)

Note que existem seis ações e cada uma possui uma lista de pré-condições e logo abaixo as ações que serão executadas. Por exemplo, para poder executar a primeira ação “levar-filho-ao-colegio” é necessário que as pré-condições sejam cumpridas, ou seja: “filho-esta-em-casa” e “carro-esta-em-bom-funcionamento”. Caso essas pré-condições não sejam satisfeitas, o GPS não conseguirá seguir em frente! Supondo-se que esta ação seja executada, o resultado será adicionar na lista que o filho está no colégio (“filho-no-colegio”) e retirar da lista que o filho está em casa (“filho-esta-em-casa”).

Vamos analisar a segunda ação, que é “efetuar-a-instalacao-da-bateria-na-oficina”. Para poder executá-la, é necessário que o carro necessite de nova bateria (“carro-necessita-de-nova-bateria”), que a oficina a instale (“oficina-instala-nova-bateria”) e também que a oficina receba o dinheiro do serviço (“oficina-recebe-o-dinheiro-do-servico”). Como resultado, adiciona-se na lista que o carro está em bom funcionamento (“carro-esta-em-bom-funcionamento”). Desta forma, a mesma lógica segue para todas as outras ações, ou seja, suas pré-condições precisam ser satisfeitas para que as ações possam ser efetivamente executadas.

Observe que após a satisfação das pré-condições são utilizados os comandos “add-lista” e “del-lista”, que adiciona e remove as variáveis da lista, respectivamente. Essa é a forma que foi feita a implementação do GPS no Lisp, por meio de listas para gerenciar quais pré-requisitos já foram ou não resolvidos. Neste código, as partes que apresentam os caracteres “ ‘( “ – aspas simples seguida de abre parênteses – são listas.

Após as ações terem sido definidas é possível rodar o GPS para que ele encontre qual é a solução para este problema de levar o filho ao colégio! Porém, precisamos ainda passar alguns parâmetros para que ele possa iniciar a busca, conforme mostrado abaixo.

estado_inicial ‘(filho-esta-em-casa
                             carro-necessita-de-nova-bateria
                             possui-dinheiro
                             possui-lista-telefonica)

estado_final ‘(filho-no-colegio)

Note que os parâmetros passados são uma lista de estados iniciais e uma lista com o estado final. O primeiro diz respeito a como “encontra-se o mundo” no momento atual  enquanto que o segundo é onde desejamos chegar. Neste exemplo, temos que o filho está em casa, o carro necessita de nova bateria, o pai possui dinheiro e também possui uma lista telefônica. Como o objetivo é levar o filho no colégio, quando o GPS for executado irá procurar uma ação que adicione na lista o objetivo, ou seja: add-lista ‘(filho-no-colegio). Neste caso o algoritmo de busca tentará executar a ação 1, porém, para que ela seja executada é preciso satisfazer as suas duas pré-condições (“filho-esta-em-casa” e “carro-esta-em-bom-funcionamento”). Podemos notar que a primeira pré-condição (“filho-esta-em-casa”) está presente em nosso estado inicial, porém, a segunda (“carro-esta-em-bom-funcionamento”) não consta na lista. Dessa forma, o algoritmo procurará por uma outra ação que adicione na lista esse pré-requisito, ou seja, a ação 2. Com isso, o fluxo do programa vai da ação 1 até a ação 2 e verificará quais são suas pré-condições, que são: “carro-necessita-de-nova-bateria”, “oficina-instala-nova-bateria” e “oficina-recebe-o-dinheiro-do-servico”. A única dessas pre-condições que está na lista do estado inicial é a “carro-necessita-de-nova-bateria”, enquanto que as outras não foram definidas. Por esse motivo, o algoritmo iterará recursivamente e buscará novas ações que adicionem na lista essas duas variáveis que não estão no estado inicial, até que ele encontre a solução ou então não consiga resolver o problema. Abaixo é mostrada a ordem de execução das regras do GPS tendo como entrada o estado inicial e final mostrados anteriormente, nas quais podemos notar que para levar o filho no colégio primeiro precisamos procurar o número de telefone de uma oficina, executar todas as ações subsequentes para que então consigamos resolver o problema original.

executando procurar-numero-de-telefone-de-uma-oficina
executando telefonar-para-a-oficina
executando informar-problema-ao-mecanico
executando passar-dinheiro-para-o-caixa-da-oficina
executando efetuar-a-instalacao-da-bateria-na-oficina
executando levar-filho-ao-colegio
resolvido

É importante ressaltar que o GPS retorna uma sequência de ações, ou seja, dado o estado inicial, você precisa executar várias ações até que consiga chegar no seu objetivo. Vamos supor que você tenha a meta de terminar um curso de graduação, poderia passar o estado final “Graduação completa” e o GPS indicaria cada um dos passos necessários até chegar até lá, como fazer a matrícula, comparecer às aulas, fazer os trabalhos, tirar boas notas nas provas, pagar a mensalidade, dentre vários outros. É claro que todas essas ações precisam ser previamente programadas assim como mostrado no exemplo acima, pois o GPS é um algoritmo que faz as inferências nos dados para buscar a solução. Outra questão é que após a base de ações/regras estar definida, podemos parametrizar o estado inicial e final com qualquer “variável” que existe na base, não estando limitado à somente “levar o filho ao colégio”.

Veja abaixo um vídeo clássico da área que mostra um pombo tentando comer uma banana, que pode servir de exemplo do passo a passo para fazer as ações até chegar em seu objetivo!

No link abaixo você pode baixar o arquivo do problema do pombo e da banana, em um formato semelhante ao exemplo de levar o filho ao colégio.

Para finalizar, é importante deixar claro que o GPS é chamado de solucionador geral de problemas devido às suas características recursivas para buscar a solução. Muitos confundem e acabam comentando que esse exemplo acima não é algo genérico, pois trata-se de um problema específico de levar o filho ao colégio. Isso é verdade, porém, a ideia desta técnica de IA é utilizar essa estrutura de regras e busca para que qualquer pessoa pessoa programar suas próprias ações de acordo com os problemas que querem resolver.

E caso você queira saber mais sobre o GPS, eu gravei dois vídeos que mostram passo a passo o mecanismo de raciocínio e como esse sistema consegue tomar as decisões. Veja abaixo!

Espero que você tenha aprendido um pouco mais sobre essa importante parte da história da Inteligência Artificial. Até o próximo artigo! 🙂