Cap. 11: PLANNING

• Uma vez tendo estabelecido um conjunto de estados e construído um modelo completo e correto, precisamos traçar um plano de ação de forma que o agente possa seguir as ações e atingir os objetivos.

• Algoritmo básico:

From Problem Solving to Planning

• diferenças: representações de ações, estados, objetivos e planos.

• exemplo simples: comprar 1 l de leite, uma dúzia de maçãs e uma lanterna.

• problem solving:

– estado inicial: agente está em casa, mas sem todas as coisas necessárias.

– operadores: tudo que o agente pode fazer para obter os objetos.

– opcional: heurística (ex, número de coisas ainda não compradas).

[figure]

From Problem Solving to Planning

• três idéias principais: transparência de ações e estados, liberdade para adicionar ações ao plano de ações a qualquer momento (sem ser incremental), e independência das partes.

• Planning utilizando cálculo de situações:

– estado inicial: Em(Casa, S_{0}) ∧ ¬T em(Leite, S_{0}) ∧ ¬T em(Macas, S_{0}) ∧ ¬T em(Lanterna)

– estado final: ∃sEm(Casa, s) ∧ T em(Leite, s) ∧ T em(Macas, s) ∧ T em(Lanterna, s)

– operadores: ex, axioma do estado sucessor para comprar leite: ∀a, sT em(Leite, Result(a, s)) ⇔ ((a = Compra(Leite) ∧ Em(Supermercado, s)∨T em(Leite, s)∧a ≠ Largou(Leite)))

[figure]

From Problem Solving to Planning

• Em “planning” representamos sequências de ações, não somente ações únicas. Em cálculo de situações representamos Result:

– ∀sResult′([], s) = s

– ∀a, p, sResult′([a | p], s) = Result′(p, Result(a, s))

• Uma solução para o problema das compras é um plano p que qdo aplicado ao estado inicial S_{0} produz a solução:

– Em(Casa, Result′(p, S_{0})) ∧ T em(Leite, Result′(p, S_{0})) ∧ T em(Macas, Result′(p, S_{0}))∧T em(Lanterna, Result′(p, S_{0})

• ASK daria uma solução do tipo:

p = [V a(Supermercado), Compre(Leite), Compre(Macas), V a(CasaEV ideo), Compre(Lanterna), V a(Casa)]

From Problem Solving to Planning

• soluções teóricas nem sempre são eficientes se usarmos regras de inferência não guiadas.

• para soluções práticas:

– Restringir a linguagem de definição do problema.

– Utilizar algoritmos de “planning” particulares (planner para cada problema, invés de algoritmos gerais para provas de teoremas).

Representações básicas para Planning

• Maioria dos “planners” utilizados descreve estados e operadores em STRIPS ou extensões (linguagem baseada em cálculo de situações).

• Estados: representados por conjunções de literais “ground” (completamente instanciados), sem funções (predicados aplicados a símbolos constantes). Ex: Em(Casa) ∧ ¬T em(Leite) ∧ ¬T em(Macas) ∧ ¬T em(Lanterna) ∧ …

• Descrição do estado não precisa ser completa.

• Maior parte dos “planners” assume que se nada é dito sobre um literal, ele é falso (negação por falha em programação lógica).

[figure]

Representações básicas para Planning

• Objetivos: tb representados por conjunções de literais. Ex: Em(Casa) ∧ T em(Leite) ∧ T em(Macas) ∧ T em(Lanterna).

• Podem conter variáveis. Ex, estar numa loja que venda leite: Em(x) ∧ V ende(x, Leite).

• Como em provadores automáticos de teoremas, assume-se que todas as variáveis do objetivo estão quantificadas existencialmente.

• Diferenças entre objetivos num “planner” e num provador de teoremas: objetivo do “planner” pergunta por uma sequência de ações que permitam validar o objetivo se este for executado. Objetivo no provador de teoremas é diretamente provado verdadeiro.

Representações básicas para Planning

• Representação de ações: operadores STRIPS consistem de três componentes:

– Descrição da ação: para o “planner” serve apenas como um nome para a ação.

– Precondição: conjunção de átomos (literais positivos) que devem ser verdadeiras antes do operador ser aplicado.

– Efeito (ou poscondição): conjunção de literais (positivos ou negativos) que descrevem como a situação é modificada quando o operador é aplicado.

Representações básicas para Planning

• Ex: Op(ACAO : V a(la), P RECON : Em(aqui) ∧ Caminho(aqui, la), EF EIT O : Em(la) ∧ ¬Em(aqui)

Representações básicas para Planning

• Um operador pode conter variáveis: esquema de operador.

• Corresponde a uma família de ações.

• Somente operadores completamente instanciados podem ser executados.

• Linguagem de descrição de precondições e efeitos bastante restrita. Pode ser menos restrita.

Representações básicas para Planning

• Operador é dito aplicável num estado s, se há alguma forma de instanciar variáveis do operador tal que a precondição seja verdadeira para esta instância. No estado resultante, todos os literais positivos da poscondição também devem ser verdadeiros, exceto os negados.

• Ex: situação inicial, Em(casa), Caminho(Casa, Supermercado) …, ação Va(Supermercado) é aplicável, e a situação resultante contém ¬Em(Casa), Em(Supermercado), Caminho(Casa, Supermercado) …

[figure]

Espaço de Situações e Espaço de Planos

• Dada uma definição do problema na linguagem STRIPS, algoritmos de busca podem ser utilizados para resolver o problema de “planning” do estado inicial para o objetivo.

• Chamados geradores de planos sobre o espaço de situações, e progressivos.

• Problema com esta abordagem: fator de ramificação!

• Alternativa: gerador de planos regressivo, vai do objetivo para o estado inicial de forma a cortar o espaço de busca.

• Algoritmo original utilizado por STRIPS era de um gerador de planos sobre o espaço de situações regressivo, mas era incompleto, pois não sabia lidar com o fato de gerar uma conjunção.

• Ineficiente produzir algoritmo completo utilizando esta abordagem de geração de planos por situações.

Espaço de Situações e Espaço de Planos • Alternativa: busca pelo espaço de planos.

• Começamos com um plano simples, incompleto: plano parcial.

• Aplicamos os operadores (de plano) e geramos outros planos até chegar a um que nos leve à solução.

• Possíveis operadores de plano: adicionar um novo passo ao plano, imposição de ordem aos passos do plano, instanciação de uma variável etc.

• Solução é o plano final. Caminho para chegar a este plano é irrelevante (eficiência...)

[figure]

Representações para Planos

• Operações sobre planos:

– Operadores de refinamento: adiciona restrições a um plano parcial. Elimina alguns planos do conjunto possível de planos.

– Operadores de modificação: qualquer outro operador que

não seja de refinamento.

• Ex: Plano para calçar um par de sapatos.

• Objetivo:

ColocadoSapatoP eDireito ∧ ColocadoSapatoP eEsquerdo.

• Estado inicial: não necessário.

[figure]

Representações para Planos

• Operadores:

– Op(ACAO : ColocarSapatoP eDireito, P RECOND : ColocadaMeiaP eDireito, EF EIT O : ColocadoSapatoP eDireito)

– Op(ACAO : ColocarMeiaP eDireito, EF EIT O : ColocadaMeiaP eDireito)

– Op(ACAO : ColocarSapatoP eEsquerdo, P RECOND : ColocadaMeiaP eEsquerdo, EF EIT O : ColocadoSapatoP eEsquerdo)

– Op(ACAO : ColocarMeiaP eEsquerdo, EF EIT O : ColocadaMeiaP eEsquerdo)

[figure]

Representações para Planos

• Plano parcial deve ter dois passos: ColocarSapatoPeDireito, ColocarSapatoPeEsquerdo. Quem vem primeiro?

• Menos “comprometedor”: somente escolher planos com informações relevantes no momento. Deixar outras escolhas para serem feitas mais tarde.

• Plano de ordem parcial: alguns passos do plano são ordenados, outros não.

• Plano de ordem total: todos os passos são ordenados.

• Linearização de planos: geração de um plano de ordem total após adição de restrições ao plano anterior.

• Restrições no valor das variáveis a serem instanciadas.

[figure]

Representações para Planos

• Um plano é formalmente definido como uma estrutura de dados contendo os seguintes 4 componentes:

– conjunto de passos. Cada passo é um dos operadores do problema.

– conjunto de restrições de ordenação dos passos.

– conjunto de instâncias de variáveis para cada passo.

– conjunto de ligações causais. Ex: S_{i} ⟶^{c} S_{j}, com c sendo precondição de S_{j}.

• Plano inicial descreve o problema ainda não resolvido. Consiste de dois passos: início e fim com relação de precedência Inicio ≺ Fim.

[figure]

Representações para Planos

• Passo Início não tem precondições e o efeito é adicionar todas as proposições verdadeiras ao estado inicial.

• Passo Fim tem o objetivo como precondição, e nenhum efeito.

• Ex:

Plan(STEPS:{ S_{1}: Op(ACAO:Inicio),

S_{2}: Op(ACAO: Fim,

PRECOND: ColocadoSapatoP eDireito∧

ColocadoSapatoP eEsquerdo)},

ORDERINGS: { S_{1} ≺ S_{2} }, BINDINGS: {}, LINKS: {})