Continuando esse post aqui: http://www.agaelebe.com.br/2009/3/12/traducao-paipr-o-resolvedor-de-problemas-gerais-parte-2
Macacos e bananas
Para que possamos ver o G em GPS há uma razão. Vamos ver se podemos aplicar a nova versão do GPS para um novo domínio. Este é um clássico problema de IA – macacos e bananas. A idéia básica é que há um macaco em frente a porta de uma sala, há bananas penduradas no meio da sala – longe do alcance dos macacos - e há uma cadeira próxima a porta que o macaco pode empurrar para dentro da sala e então subir nela para alcançar as bananas. A primeira coisa que precisamos fazer é definir os operadores para este domínio (lib/ch04/gps2_monkey1.rb):
require 'gps2' require 'pp' $banana_ops = [ GPS2::op(:climb_on_chair, :preconds => [:chair_at_middle_room, :at_middle_room, :on_floor], :add_list => [:at_bananas, :on_chair], :del_list => [:at_middle_room, :on_floor]), GPS2::op(:push_chair_from_door_to_middle_room, :preconds => [:chair_at_door, :at_door], :add_list => [:chair_at_middle_room, :at_middle_room], :del_list => [:chair_at_door, :at_door]), GPS2::op(:walk_from_door_to_middle_room, :preconds => [:at_door, :on_floor], :add_list => [:at_middle_room], :del_list => [:at_door]), GPS2::op(:grasp_bananas, :preconds => [:at_bananas, :empty_handed], :add_list => [:has_bananas], :del_list => [:empty_handed]), GPS2::op(:drop_ball, :preconds => [:has_ball], :add_list => [:empty_handed], :del_list => [:has_ball]), GPS2::op(:eat_bananas, :preconds => [:has_bananas], :add_list => [:empty_handed, :not_hungry], :del_list => [:has_bananas, :hungry]) ]
Nada muito estranho aqui. Então vamos usá-los e ver se o GPS funciona para eles. (lib/ch04/gps2_monkey1.rb):
gps = GPS2.new([:at_door, :on_floor, :has_ball, :hungry, :chair_at_door], $banana_ops) pp gps.solve(:not_hungry) Isto gerará a saída esperada: [[:start], [:executing, :push_chair_from_door_to_middle_room], [:executing, :climb_on_chair], [:executing, :drop_ball], [:executing, :grasp_bananas], [:executing, :eat_bananas]]
E já que não fizemos nenhuma mudança no problema GPS, a afirmação de que ele é geral apresenta alguma validade.
Busca no labirinto
Outro problema clássico de IA é a busca no labirinto. Podemos facilmente definir um labirinto como quadrados numerados onde um quadrado numerado pode levar para zero ou mais outros quadrados. Para fazer as definições realmente fáceis, vamos definir alguns métodos que tornam fácil a definição das operações para nós (lib/ch04/maze.rb):
require 'gps2' require 'pp' module Maze class << self def make_ops(pair) [make_op(pair[0], pair[1]), make_op(pair[1], pair[0])] end def make_op(here, there) GPS2::op([:move, :from, here, :to, there], :preconds => [[:at, here]], :add_list => [[:at, there]], :del_list => [[:at, here]]) end end Ops = [[1,2], [2,3], [3,4], [4,9], [9,14], [9,8], [8,7], [7,12], [12,13], [12,11], [11,6], [11,16], [16,17], [17,22], [21,22], [22,23], [23,18], [23,24], [24,19], [19,20], [20, 15], [15,10], [10,5], [20,25]].inject([]) do |sum, obj| sum + make_ops(obj) end end
Aqui nós temos primeiro makeops, que apenas faz todas as passagens de um quadrado para outro simétricas – o que significa que não teremos que definir uma passagem de 1 para 2 e a de 2 para 1. O método makeop faz uso de algumas propriedades interessantes de nosso código que estavam lá e para as quais nenhuma atenção especial foi dada. Isto é, os objetivos podem ser representados por arrays ao invés de símbolos. De fato, não importa como você representa os objetivos, contanto que você use sempre a mesma representação para o mesmo objetivo. Você pode também misturar e combinar strings, símbolos, regexps e arrays, se quiser. Neste caso, os únicos objetivos que temos são da forma [:at, 1] (em 1), mas é necessário um poder um pouco maior de representação para fazer deste jeito.
No final, um grande array de pares de números é transformado em operações usando inject e fazendo chamadas a make_ops. O resultado final é o conjunto de todas as operações que precisamos para definir esse labirinto em particular. Então, um primeiro problema para este labirinto seria provavelmente saber como sair dele. Então vamos ver isso (lib/ch04/maze_problem1.rb):
require 'blocks' require 'pp' gps = GPS2.new([[:a, :on, :table], [:b, :on, :table], [:space, :on, :a], [:space, :on, :b], [:space, :on, :table]], Blocks.make_ops([:a, :b])) pp gps.solve([:a, :on, :b], [:b, :on, :table])
Isto nos dá a saída esperada:
[[:start], [:executing, [:move, :a, :from, :table, :to, :b]]]
Vamos considerar o caso em que temos a em cima de b e queremos movê-lo de modo que b fique sobre a. Desta vez vamos habilitar o debug de saída (lib/ch04/blocks_problem2.rb):
require 'blocks' require 'pp' gps = GPS2.new([[:a, :on, :b], [:b, :on, :table], [:space, :on, :a], [:space, :on, :table]], Blocks.make_ops([:a, :b])) pp gps.solve([:b, :on, :a])
Isto também nos dá o que esperávamos:
Goal: [:b, :on, :a] Consider: [:move, :b, :from, :table, :to, :a] Goal: [:space, :on, :b] Consider: [:move, :a, :from, :b, :to, :table] Goal: [:space, :on, :a] Goal: [:space, :on, :table] Goal: [:a, :on, :b] Action: [:move, :a, :from, :b, :to, :table] Goal: [:space, :on, :a] Goal: [:b, :on, :table] Action: [:move, :b, :from, :table, :to, :a] [[:start], [:executing, [:move, :a, :from, :b, :to, :table]], [:executing, [:move, :b, :from, :table, :to, :a]]]
Uma das características mais interessantes da minha implementação comparada com a de Norvig é que ele possui alguns problemas de ordenamento que necessitam de código extra no método achieve_all. Eu não entendi porque, mas meu código não tem esse problema, então eu não mostrarei o código consertado (visto que não foi necessário consertá-lo). Um exemplo que causava os problemas para Norvig parece-se com este código aqui (lib/ch04/blocks_problem3.rb):
require 'blocks' require 'pp' gps = GPS2.new([[:a, :on, :b], [:b, :on, :c], [:c, :on, :table], [:space, :on, :a], [:space, :on, :table]], Blocks.make_ops([:a, :b, :c])) pp gps.solve([:c, :on, :b], [:b, :on, :a])
Este problema representa um mundo de blocos onde a está sobre b, b está sobre c e c está sobre a mesa, e você quer reverter a ordem deles.
Outro problema que Norvig tem e que não aparece neste código são alguns exemplos que fazem muitas operações para alcançar algo. O arquivo lib/ch04/blocks_problem4.rb é um deles:
require 'blocks' require 'pp' gps = GPS2.new([[:c, :on, :a], [:a, :on, :table], [:b, :on, :table], [:space, :on, :b], [:space, :on, :c], [:space, :on, :table]], Blocks.make_ops([:a, :b, :c])) pp gps.solve([:c, :on, :table])
Em casos em que a solução ótima precisa de uma ação, o código lisp realiza duas ações (mover c de a para b e então de b para a mesa). Isso acontece pó problemas de ordenação. Uma ordenação topológica (Topological sort) pode resolvê-los, por exemplo. Existe outro exemplo que necessita de quatro operações ao invés de duas (lib/ch04/blocks_problem5.rb):
require 'blocks' require 'pp' gps = GPS2.new([[:c, :on, :a], [:a, :on, :table], [:b, :on, :table], [:space, :on, :b], [:space, :on, :c], [:space, :on, :table]], Blocks.make_ops([:a, :b, :c])) pp gps.solve([:c, :on, :table], [:a, :on, :b])
Mas, como mencionei anteriormente, não parece que o código Ruby tem esse problema, então decidi não implementar as soluções de Norvig para eles.
Interessantemente, existem alguns problemas que não podem ser resolvidos, não importa em qual ordem você ponha os objetivos. Pegue, por exemplo, o caso em que b e a estão na mesa e c está sobre a. Você quer que c fique na mesa, b sobre c e a sobre b. A implementação atual do GPS não pode lidar com isso, não importa em que ordem você tente (lib/ch04/blocks_problem6.rb):
require 'blocks' require 'pp' gps = GPS2.new([[:c, :on, :a], [:a, :on, :table], [:b, :on, :table], [:space, :on, :c], [:space, :on, :b], [:space, :on, :table]], Blocks.make_ops([:a, :b, :c])) pp gps.solve([:a, :on, :b], [:b, :on, :c]) pp gps.solve([:b, :on, :c], [:a, :on, :b])
Isto é chamado de anomalia de Sussman, e algumas soluções serão vistas mais tarde no livro de Norvig.
Conclusão
É óbvio que esta versão do GPS é muito mais poderosa que a original. Mas também existem algumas coisas problemáticas. Embora tenhamos introduzido algumas medidas, ainda há casos em que uma solução correta não pode ser encontrada. Por exemplo, podemos olhar para o problema de pegar uma criança na escola novamente, adicionando um novo operador para pegar um táxi lá. Digamos que queremos pegar o filho na escola sem usar nenhum dinheiro e definimos isso da seguinte maneira (lib/ch04/gps2_problem7.rb):
require 'gps3' require 'pp' gps = GPS2.new([:son_at_home, :have_money, :have_works], GPS::SCHOOL_OPS + [ GPS2::op(:taxi_son_to_school, :preconds => [:son_at_home, :have_money], :add_list => [:son_at_school], :del_list => [:son_at_home, :have_money]) ]) debug :gps pp gps.solve(:son_at_school, :have_money)
Aqui algo engraçado acontece. Se você olha na saída de debug:
Goal: :son_at_school Consider: :drive_son_to_school Goal: :son_at_home Goal: :car_works Consider: :shop_installs_battery Goal: :car_needs_battery Consider: :taxi_son_to_school Goal: :son_at_home Goal: :have_money Action: :taxi_son_to_school Goal: :have_money []
Existem dois modos de resolver isso: primeiro resolver o objetivo de se ter dinheiro (have money) e então pegar o filho na escola. Neste caso, o objetivo have_money é resolvido trivialmente e então o dinheiro é gasto com o táxi. Se outra ordem for tentada então o filho é enviado de táxi para escola e então o objetivo ‘ter dinheiro’ falha. Existe uma solução válida (levar o filho até a escola) mas ela nunca é tentada.
Outro problema com esta abordagem é que o poder descritivo dela não é muito geral nem poderoso o suficiente. As condições que usamos para os operadores no GPS não são realmente abstratas o suficiente.
O GPS também assume que você sabre tudo sobre o mundo (“informação perfeita”), e esse tudo é verdadeiro ou falso. A probabilidade é hoje em dia um das melhores abordagens disponíveis para a AI e o GPS não leva em consideração a lógica fuzzy.
Finalmente, objetivos de interação, em que você tem alguns objetivos ativos ao mesmo tempo é o que a maioria das pessoas tem, mas o GPS só pode receber um objetivo por vez.
Todos esses problemas tornaram problemático continuar usando a abordagem do GPS. Outra coisa que impactou bastante foi à percepção de como problemas NP-completos afetaram resolvedores como o GPS. No final das contas, o GPS foi uma abordagem inicial interessante para resolver o problema, e ele definitivamente faz parte da herança da IA disponível nos dias de hoje.
Sorry, comments are closed for this article.