STRIPS

o pioneiro do planejamento automatizado

STRIPS (Stanford Research Institute Problem Solver) foi o primeiro sistema de planejamento automatizado da história. Desenvolvido por Richard Fikes e Nils Nilsson no final dos anos 1960, ele estabeleceu paradigmas. Primeiramente, o sistema introduziu a representação de problemas como estados, ações e objetivos. Diferente de abordagens anteriores, STRIPS separou conhecimento do domínio do mecanismo de planejamento. Além disso, ele demonstrou que robôs poderiam planejar sequências de ações para alcançar objetivos. O sistema foi utilizado no robô Shakey, o primeiro robô móvel com raciocínio autônomo. Consequentemente, STRIPS se tornou a base para inúmeras linguagens e sistemas posteriores.

representação de ações em strips

Em STRIPS, cada ação possui três componentes fundamentais que definem seu comportamento. A lista de pré-condições especifica o que deve ser verdade antes da ação executar. Por outro lado, a lista de adição (add-list) descreve os predicados que se tornam verdade após a ação. Além disso, a lista de remoção (delete-list) descreve os predicados que deixam de ser verdade após a ação. Por exemplo, a ação “pegar(bloco)” exige “mão_vazia” e “bloco_livre” como pré-condições. Seus efeitos: adiciona “segurando(bloco)” e remove “mão_vazia” e “bloco_livre”. Dessa forma, essa estrutura captura como ações transformam o estado do mundo de forma determinística.

exemplo prático de domínio

Considere um domínio simples de transporte de pacotes com ações bem definidas. Ação “carregar(pacote, local)” requer “em(local)” e “pacote_em(pacote, local)” como pré-condições. Seus efeitos: adiciona “carregando(pacote)” e remove “pacote_em(pacote, local)”. Além disso, ação “descarregar(pacote, local)” requer “carregando(pacote)” e “em(local)” como pré-condições. Seus efeitos: adiciona “pacote_em(pacote, local)” e remove “carregando(pacote)”. Ação “mover(de, para)” requer “em(de)” e exclui “em(para)” já verdadeiro. Seus efeitos: adiciona “em(para)” e remove “em(de)”. Portanto, essas ações permitem planejar rotas completas de entrega.

algoritmo de planejamento strips

O algoritmo STRIPS utiliza busca no espaço de estados com encadeamento para trás. Primeiramente, ele começa com o objetivo e busca ações cujos efeitos satisfaçam partes do objetivo. Para cada ação candidata, o algoritmo verifica se suas pré-condições são satisfeitas no estado atual. Se alguma pré-condição não for satisfeita, ela se torna um subobjetivo a ser resolvido recursivamente. O algoritmo constrói um plano parcial e depois o executa na ordem inversa. Consequentemente, esse processo de regressão simplifica o problema de planejamento consideravelmente. Assim, STRIPS demonstrou que planejamento poderia ser feito de forma eficiente com essa abordagem.

legado e influência duradoura

O STRIPS deixou um legado que transcende sua implementação original como sistema. Primeiramente, sua representação de ações inspirou linguagens como PDDL, hoje padrão na área. Além disso, o conceito de pré-condições e efeitos se tornou universal em planejamento automatizado. A separação entre domínio e problema permitiu reutilização de conhecimento. Dessa forma, o algoritmo de regressão influenciou gerações de planejadores subsequentes. Atualmente, a família de linguagens baseadas em STRIPS continua sendo utilizada. Para iniciantes, estudar STRIPS é compreender as origens do planejamento automatizado em IA. Por fim, ele mostra como representação adequada de ações permite resolução estruturada de problemas complexos.