Continuando a série de traduções dos artigos do Ola Bini, traduzirei a seguir este artigo. Posso demorar um pouco, mas pretendo traduzir todos os artigos da série.

O Resolvedor de problemas gerais, Parte 1

Para uma das primeiras tentativas de se criar um sistema de resolução de problemas foi dado o grandioso nome de Resolvedor de Problemas Gerais (General Problem Solver). Foi desenvolvido em 1957 por Alan Newell e Herbert Simon. Quando o RPG foi inicialmente apresentado, este causou bastante agitação na comunidade de IA. Porém o RPG não sobreviveu a suas expectativas, mesmo assim é bastante importante do ponto de vista histórico. A implementação orginal do GPS foi escrita em IPL e tem algumas diferenças sutis em relação ao programa desenvolvido no livro PAIP. Eu seguirei a versão do PAIP enquanto estiver desenvolvendo a versão em Ruby. Se você tem algum interesse na versão original, sugiro que primeiro encontre um livro sobre IPL (que, de maneira alguma, é uma linguagem divertida).

O RPG implementa uma versão de algo chamado análise de meios e fins. O tipo de pensamento abordado por essa análise é de bastante senso comum. Resumidamente, você tem alguns objetivos, você então deve descobrir quais condições necessitam ser verdadeiras para que você atinja um determinado objetivo. Se estas condições não são verdadeiras, você terá que descobrir como atinji-las, e assim por diante.

A maneira que escreveremos a primeira versão do GPS possui algumas propriedades interessantes. As principais são o estado inicial, os objetivos e as operaçõs disponíveis. Por enquanto representarei os estados e objetivos como símbolos. Uma operação precisa ser um pouco mais complicada. Em primeiro lugar, ela possui um nome para que você possa rastreá-la. Ela possui pré-condições que detalham o que precisa ser verdadeiro para que essa operação possa ocorrer. E ela possui uma lista de adições e uma lista de remoções. A lista de adições nos diz quais condições são verdadeiras após a execução da operação e a lista de remoções detalha o que já não é mais verdadeiro.

Então vamos dar uma olhada na primeira versão da implementação. Eu fiz algumas mudanças se comparado ao código Lisp de Norvig. A mais óbvia é que não estou usando variáveis globais. Ao invés delas, opto por colocar tudo em uma classe chamada GPS (este código pode ser encontrado em lib/ch04/gps.rb ).

class GPS
  Op = Struct.new(:action, :preconds, :add_list, :del_list)

  def initialize(state, ops)
    @state = state
    @ops = ops
  end

  # Interface prinicipal do Resolvedor de Problemas Gerais: 
  # atinge todos os objetivos (goals)
  # usando as operações definidas
  def solve(*goals)
    goals.all? do |goal|
      achieve goal
    end
  end

  # Um objetivo é atingido se ele já foi 
  # atingido ou se há uma operação 
  # apropriada que seja aplicável a ele
  def achieve(goal)
    @state.include?(goal) ||
      (@ops.find_all do |op|
         appropriate?(goal, op)
       end.any? do |op|
         apply(op)
       end)
  end

  # Uma operação é apropriada para um 
  # objetivo se ela está na lista de adições
  def appropriate?(goal, op)
    op.add_list.include?(goal)
  end

  # Imprime uma mensagem e atualiza o estado
  # caso a operação seja aplicável
  def apply(op)
    if op.preconds.all? { |cond| achieve(cond) }
      puts "Executing #{op.action}"
      @state -= op.del_list
      @state += op.add_list
      return true
    end
    false
  end
end

Existem alguns componentes neste código, portanto vamos olhar peça por peça. Em primeiro lugar, criamos uma classe chamada GPS. Dentro dela, imediatamente definimos uma estrutura (Struct) chamada Op. Existe uma simetria entre a operação do Lisp defstruct e a chamada Struct.new do Ruby que muito me aprecia. Neste caso ela é perfeita já que nós não queremos que Op tenha nenhum comportamento neste momento. A Op consiste em uma ação, nas pré-condições, na lista de adições e na lista de remoções.

O método initialize recebe o estado atual e as operações disponíveis (ops). O estado atual é um array de estados e ops é um array de ops.

A peça central neste código é na verdade o método solve (resolver). Este método corresponde a função GPS no código original. A principal diferença é que a função GPS recebe o estado, os objetivos e as ops como parâmetros, enquanto nós colocamos estes dentro do objeto usando o método initialize.

Então o que significa para nós resolver os objetivos? Basicamente nós tentamos atingir todos objetivos. Se pudermos atingir todos objetivos nós conseguimos resolvê-los, caso contrário não conseguimos. O código Lisp de Norvig lida com isso um pouco diferente, retornando o símbolo ‘resolvido’ caso ele funcione. Ao invés disso, eu resolvi apenas retornar um booleano. Isso significa que nosso uso do método solve pode ser um pouco mais verboso.

O método achieve (alcançar) tenta fazer duas coisas diferentes. Em primeiro lugar ele checa para saber se o estado atual já inclui o objetivo. Neste caso estamos bem. Caso contrário primeiro precisaremos encontrar todas as operações que são apropriadas para esse objetivo e então checar se alguma destas operações pode ser aplicada. Antes de olhar para os métodos appropriate? e apply, é interessante notar que eu decidi usar o any? (algum) aqui, enquanto Norvig usa a função chamada some (alguns). Estas duas operaçãos são na verdade um pouquinho diferentes, mas por enquanto essa diferença não é importante. A diferença é que enquanto o any? sempre retornára verdadeiro ou falso, o some retornará o valor não-nulo gerado pelo método test. O Ruby não parecer ter nada parecido com isso (Enumerable#detect/find retorna o valor original, não o valor gerado pelo bloco). Como você verá no próximo artigo (parte 2) eu terei que implementar o some nesse ponto.

O que é o método appropriate? (apropriado) então? Em primeiro lugar, é um método que provavelmente deve pertencer a classe Op no lugar da classe GPS. No momento ele apenas checa se a lista de adições das operações inclui o objetivo - o que significa que tal operação pode ser usada para se alcançar o objetivo.

Finalmente temos o método apply (aplicar, chamado de apply-op no código de Norvig). O Apply é o local onde os elementos recursivos do algoritmo entram em jogo. Basicamente, para que uma operação seja aplicada, todas as pré-condições desta operação precisam ser compridas. Usamos all? para tentar atinger todas a pré-condições e se le é bem sucedido imprimimos quais ações foram executadas, modificamos o estado removendo a lista de remoção e adicionado a lista de adição e, finalmente, retornamos true.

E é realmente isso o que há no resolvedor de problemas gerais. É claro que deveríamos testá-lo e ver, certo? O domínio comum de uso do GPS era o de guiar até a enfermaria e nós vamos usar algo similar a isso para testar esta implementação.

A primeira coisa que precisamos é ter algumas operações definidas para este domínio. Você também pode encontrar esse código em (http://github.com/olabini/paipr/tree/master/lib/ch04/gps.rb?raw=true)[lib/ch04/gps.rb]:

SCHOOL_OPS = [ Op.new(:drivesonto_school, [:sonat_home, :carworks], [:son_at_school], [:son_at_home]), Op.new(:shopinstallsbattery, [:carneedsbattery, :shopknowsproblem, :shophasmoney], [:car_works], []), Op.new(:tellshopproblem, [:incommunicationwith_shop], [:shopknowsproblem], []), Op.new(:telephone_shop, [:knowphonenumber], [:incommunicationwith_shop], []), Op.new(:look_up_number, [:havephonebook], [:knowphonenumber], []), Op.new(:giveshopmoney, [:have_money], [:shophasmoney], [:have_money]) ]

Como você pode ver, este domínio dá uma dica sobre o que pode entrar em jogo nos objetivos do domínio. Então, vamos começar dando uma olhada nos problemas em questão. O primeiro problema está em [lib/ch04/problem1.rb]():

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_money,
               :have_phone_book],
              GPS::SCHOOL_OPS)
if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

O estado atual diz que o filho está em casa, o carro precisa de uma bateria e que nós temos dinheiro e uma lista telefônica. O objetivo a se alcançar é levar o filho até a escola. Se executarmos este código ele gera a seguinte saída:

Executing look_up_number
Executing telephone_shop
Executing tell_shop_problem
Executing give_shop_money
Executing shop_installs_battery
Executing drive_son_to_school
Solved

Bem, isso parece ter funcionado corretamente, certo? E no caso em que não temos nenhuma lista telefônica? (lib/ch04/problem2.rb):

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_money],
              GPS::SCHOOL_OPS)

if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

Isso gera:

<filter:code lang='ruby'>
Not solved

como esperávamos. E se pegarmos um exemplo bem simples em que o carro já funciona (lib/ch04/problem3.rb):

require 'gps'

gps = GPS.new([:son_at_home,
               :car_works],
              GPS::SCHOOL_OPS)

if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

Obtemos:

Executing drive_son_to_school
Solved

Legal. Parece bom. Então quais são os problemas com a abordagem atual? Em primeirlo lugar, ela não resolve alguns problemas bem fáceis. A representação é em geral incorreta para atividades contínuas. Norvig chama esse problema de “correndo ao redor do quarteirão”. É fácil definir um objetivo de dirigir de casa para a escola, mas é um pouco mais complicado representar uma corrida ao redor do quarteirão. Existem modos de fazê-lo, claro, mas o operador GPS não os tornam necessariamente naturais como poderiam ser.

Outro problema mais sério é o problema do objetivo do irmão derrotado. No lib/ch04/problem4.rb a versão do GPS lida com tudo corretamente:

require 'gps'

gps = GPS.new([:son_at_home,
               :have_money,
               :car_works],
              GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

Mas se criarmos um problema como este (lib/ch04/problem5.rb):

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_phone_book,
               :have_money],
              GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

Isto será incorretamente reportado como resolvido - já que o GPS resolve primeiro o problema de termos dinheiro, então resolve o problema de termos o filho na escola. O modo de lidarmos com esse problema é substuirmos cada instância que atinge cada chamada com uma chamada para um novo método chamado achieveall (alcança tudo). Isso envolve os métodos solve e apply. você pode ver este código em lib/ch04/gpsno_clobber.rb:

require 'gps'

class Array
  def subset_of?(other)
    (self - other) == []
  end
end

class GPS
  def solve(*goals)
    achieve_all goals
  end

  def apply(op)
    if achieve_all(op.preconds)
      puts "Executing #{op.action}"
      @state -= op.del_list
      @state += op.add_list
      return true
    end
    false
  end

  def achieve_all(goals)
    goals.all? do |goal|
      achieve goal
    end && goals.subset_of?(@state)
  end
end

Aqui eu apenas decidi abrir a classe GPS para prover esta nova funcionalidade. Outra opção seria criar uma subclasse, mas já que isso substancialmente não altera a funcionalidade, decici apenas fazer deste modo. Existem algumas coisas acontecendo neste código. Primeiro decidi adicionar um operador a classe Array, que se espelha na função susetp do Common Lisp. Array.subsetof? retorna verdadeiro se o array atual é um subconjunto do array de argumentos, então [].subsetof?([1]) == true, enquanto [1].subsetof?([]) == false. O método solve é atualizado para apenas chamar o achieveall, e apply também chama achievaall. A definição do método achieveall primeiro tem certeza de que podemos atingir todos objetivos e então tem certeza de que todos outros objetivos a se atingir ainda estão no estado atual.

Se você executar lib/ch04/problem6.rb:

require 'gps_no_clobber'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_phone_book,
               :have_money],
              GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

Verá que ele executa algumas ações mas então retorna um não resolvido, já que não é possível atingir ambos objetivos.

Outro problema com esta implementação é baseado na intercalação entre planejamento e execução. Norvig chama isso de “o problema de saltar antes de olhar”. Você pode ver um exemplo deste problema na última execução - isto é, vemos que fizemos várias coisas, mas então percebemos que não podemos resolver o problema. No final da execução nos já consertamos o carro dando o dinheiro a oficina. Isso pode não ter sido muito bom. Já que nós temos apenas uma variável de estado, e isto já foi alterado, não há como voltarmos atrás.

Há um problema final, com subobjetivos recursivos. Isto é, esta versão do GPS não é tão boa em lidar com um caso em que o objetivo depende de outro objetivo que depende do primeiro. O arquivo lib/ch04/problem7.rb exemplifica isso:

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_money],
              GPS::SCHOOL_OPS +
              [
               GPS::Op.new(:ask_phone_number,
                           [:in_communication_with_shop],
                           [:know_phone_number],
                           [])
              ])

if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

Nós removemos o estado :havephonebook do estado inicial e adicionamos uma nova operação para pedir pelo número de telefone. Esta operação requer que você entre em contato com a oficina e, já que você precisa do número de telefone para isso, isso resultará num SystemStackError (erro de pilha do sistema) no Ruby.

Uma última perturbação com a implementação atual é que ela apenas diz verdadeiro ou falso. A única informação que recebemos é a saída impressa na tela.

Tudo isso são coisas que a versão final do GPS irá lidar mais corretamente - pelo menos em alguns casos. Este artigo já está sufcientemente longo, então o GPS2 terá que esperar para o próximo!