Inteligência Artificial

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.

suposições do mundo simplificado

Planejamento clássico opera sob suposições que simplificam drasticamente o problema. O mundo é assumido como totalmente observável: conhecemos todas as informações relevantes. O ambiente é determinístico: cada ação tem um único resultado previsível e garantido. O tempo é discreto: ações ocorrem em etapas sequenciais sem concorrência. Além disso, os objetivos são estáticos, não mudam durante o planejamento. Por exemplo, no mundo dos blocos, sabemos posição de cada bloco a todo momento. Essas suposições permitem que planejadores clássicos usem algoritmos eficientes e completos. Elas definem o paradigma fundamental do planejamento em IA.

representação com STRIPS

STRIPS (Stanford Research Institute Problem Solver) é a representação clássica para planejamento. Ela descreve estados como conjuntos de predicados atômicos que são verdadeiros no momento. Ações são definidas por três componentes: pré-condições, efeitos positivos e efeitos negativos. Por exemplo, ação “pegar(bloco)” requer “mão_vazia” e “bloco_livre” como pré-condições. Seus efeitos: adiciona “segurando(bloco)” e remove “bloco_livre” e “mão_vazia”. Um plano é uma sequência de ações que transforma o estado inicial no objetivo. Essa representação simples e expressiva tornou-se padrão na área.

exemplo prático com strips

Considere um problema simples com dois blocos A e B sobre a mesa. Estado inicial: “sobre_mesa(A)”, “sobre_mesa(B)”, “mão_vazia”. Objetivo: “sobre(A,B)” (bloco A sobre bloco B). Ação “pegar(bloco)” exige “sobre_mesa(bloco)” e “mão_vazia”. Seus efeitos: “segurando(bloco)” e negação de “sobre_mesa(bloco)” e “mão_vazia”. Ação “colocar(bloco, alvo)” exige “segurando(bloco)” e “livre(alvo)”. Seus efeitos: “sobre(bloco, alvo)”, “mão_vazia” e negação de “segurando(bloco)” e “livre(alvo)”. O plano: pegar(A), colocar(A,B). Esse exemplo mostra como ações transformam predicados sistematicamente.

algoritmos de planejamento clássico

Planejadores clássicos utilizam busca no espaço de estados ou no espaço de planos. Busca no espaço de estados explora diferentes estados aplicando ações sucessivamente. Busca no espaço de planos trabalha com planos parciais, refinando-os até completude. O algoritmo STRIPS original utilizava busca com encadeamento para trás a partir do objetivo. Planejadores modernos como FF (Fast-Forward) usam heurísticas derivadas de problemas relaxados. A heurística remove pré-condições negativas, criando um problema mais fácil de resolver. Essa abordagem permite encontrar planos eficientes mesmo em problemas complexos.

limitações e legado

O planejamento clássico enfrenta limitações quando aplicado a problemas do mundo real. A suposição de observabilidade total falha em ambientes com sensores limitados. O determinismo não captura ações que podem falhar ou ter resultados variáveis. O mundo real é concorrente e contínuo, não discreto e sequencial. Apesar disso, o planejamento clássico estabeleceu fundamentos teóricos sólidos. Extensões como planejamento probabilístico e planejamento com observabilidade parcial abordam essas limitações. Para iniciantes, o planejamento clássico oferece a base conceitual para entender planejamento automatizado. Ele revela como problemas complexos podem ser resolvidos com ações estruturadas e raciocínio lógico.