35
Inteligência Artificial Universidade da Madeira 1 Inteligência Artificial Planeamento Agenda Parte 1 Introdução Resolução de Problemas versus Planeamento Planeamento com Cálculo Situacional Linguagem STRIPS Parte 2 Mundo de Blocos Anomalia de Sussman Algoritmos de Planeamento

Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

  • Upload
    others

  • View
    23

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

1

Inteligência Artificial

Planeamento

Agenda

Parte 1Introdução

Resolução de Problemas versus PlaneamentoPlaneamento com Cálculo SituacionalLinguagem STRIPS

Parte 2Mundo de BlocosAnomalia de SussmanAlgoritmos de Planeamento

Page 2: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

2

O que é um plano?

1. Um esquema, programa ou método preparado para atingir um objectivo.

2. Uma proposta ou tentativa de um curso de acção.

3. “[Representação] de um comportamento futuro … geralmente um conjunto de acções, com restrições no tempo, para ser executado por um ou mais agentes.”

Austin Tate – MIT Encyclopaedia of the Cognitive Sciences, 1999

O que é um plano?

Um plano pode ser definido como uma sequência de acções para transformar um dado estado num estado final que cumpre um conjunto predefinido de objectivos inicialmente definidos.

Problema: obter banana, leite e um berbequim.Plano: ir ao supermercado, ir à secção de frutas, pegar nas bananas, ir à secção de leite, pegar numa caixa de leite, ir à caixa, pagar tudo, ir a uma loja de ferragens, ..., voltar para casa.

Page 3: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

3

Planeamento

O planeamento lida com aspectos de formalização, implementação e avaliação de algoritmos que permitem construir um plano.

Porque precisamos de um plano?

Já vimos métodos de busca (procura) que parecem funcionar bem, certo?

Page 4: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

4

Resolução de problemas x planeamento

Representação em RPAcções : programas que geram o estado sucessor.Estados : descrição completa.

Problemático em ambientes inacessíveis.Objectivos: função de teste e heurística.Planos: totalmente ordenados e criados incrementalmente a partir do estado inicial.

Ex.: Posições das peças de um jogo.

Exemplo do supermercado:estado inicial: em casa, sem objectos desejadosestado final: em casa com objectos desejadosoperadores: tudo o que o agente pode fazerheurística: número de objectos ainda não possuídos

Exemplo em RP

começo

Ir ao banco

Ir à escola

Ir ao supermercado

Ir dormir

Ler um livro

Sentar na cadeira

Etc...

Pagar contas

Assistir aula

Pegar dinheiro

Levantar

Ler um livro

Comprar queijo

Comprar banana

Comprar atum

Fim...

Page 5: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

5

Limitações da RP

Factor de ramificação grande.A função heurística apenas escolhe o estado mais próximo do objectivo. Não permite descartar acções à priori (≈ adivinhação).Não permite abstracção dos estados parciais.Considera acções a partir do estado inicial, uma após a outra.

Planeamento: 3 ideias principais

Representação dos estados, objectivos e acções usando lógica (descrições parciais dos estados)

Pode conectar directamente estados (sentenças) e acções (pré condições + efeitos)

Ex.: Estado: Have (Milk), Acção: Buy (milk) => Have (Milk)

Liberdade de adicionar acções ao plano quando forem necessárias

Ordem de planeamento ≠ ordem de execução

Primeiro, o que é importante : Buy (Milk)

Diminui factor de ramificação

Page 6: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

6

Planeamento: 3 ideias principais

Aproveitar a independência entre a maioria das partes do mundo (sub-goaling)

Sub plano - supermercado, sub plano - loja de ferramentas.

Não funciona para Puzzles!!!

Criação de Planos

A partir de:Uma forma de descrever um domínioUm estado inicial do mundoUm objectivoUm conjunto de acções possíveis

Encontrar:Uma sequência de acções que permita atingir o estado objectivo.

Page 7: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

7

Aplicações

RobóticaAgentes AutónomosMissões EspaciaisAmbientes Simulados (Ex.: Jogos)Gestão de Situações de Crise

Porquê que planear é difícil?

O próprio problema não está bem definido.Não existe um acordo na preferência dos objectivos a alcançar.Não se conhecem os resultados de determinadas acções.Existem restrições de tempo/recursos.Agentes externos podem interferir na determinação da solução.

Page 8: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

8

Como reduzir a incerteza?

Representar explicitamente os estados, objectivos e acções.

Permitindo centralizar a acção em determinados objectivos em detrimento de outros e fazer aplicar algoritmos específicos.

Decompor os objectivosAplicar a técnica de ‘dividir para conquistar’ na realização do plano.

O Agente Planeador

Combina o agente baseado em conhecimento com o agente “solução” de problemas (planear adiante).

≠ representação de estados, objectivos e acções≠ representação e construção da solução

Os agentes planeadores olham adiante. Os agentes planeadores são diferentes dos agentes que resolvem problemas.

Utilização de representações mais flexíveis de estados, acções, objectivos, e planos.

Page 9: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

9

O Agente Planeador

Algoritmo1. Gerar um objectivo a atingir2. Construir um plano para atingir o objectivo,

partindo do estado actual3. Executar o plano até este estar terminado4. Começar novamente com um novo

objectivo

Engenharia do conhecimento

Decidir sobre o que falar.Decidir sobre um vocabulário de condições, operadores e objectos.Codificar os operadores para o domínio.Codificar uma descrição da instância do problema.Colocar o problema para o planeador existente e obter os planos.

Page 10: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

10

Cálculo Situacional (revisão)O mundo consiste numa sequência de situações

situação N === acção ===> situação N+1Predicados que mudam com o tempo têm um argumento de situação adicional

Ao invés de Em (Agente, local) teremos (Em(Agente,[1,1],S0) ∧ Em(Agente,[1,2],S1))

Predicados que denotam que não mudam com o tempo Não necessitam de argumentos de situaçãoEx.: No mundo do Wumpus:Parede(0,1) e Parede(1,0)

Para representar as mudanças no mundo: função Resultado

Resultado (acção, situação N) = situação N+1

Resultado(Avançar,S0) = S1 Resultado(Virar(Direita),S1) = S2Resultado(Avançar,S2) = S3

S0

S1

S2

S3

Page 11: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

11

Axiomas estado - sucessorAs acções são descritas pelos seus efeitos.

Especificando-se as propriedades da situação resultante da realização da acção.Por meio dos axiomas de efeito (o que muda) e dos axiomas frames (o que não muda).

Axioma de efeito + axioma de frames = axioma estado –sucessor.

uma coisa é verdade depois ⇔[uma acção acabou de torná-la verdade∨ ela já era verdade e nenhuma acção a tornou falsa ]

Ex. ∀ a, x, s Segurando (x, Resultado (a, s)) ⇔[(a = Pegar ∧ (Presente (x, s) ∧ Portável (x)) ∨ (Segurando (x, s) ∧ (a ≠ Soltar)]

Planeando com Cálculo de Situações

Estado inicial: sentença lógicaAt (Home, S0) ∧ ¬ Have(Milk , S0) ∧ ¬ Have(Bananas , S0) ∧ ¬

Have(Drill , S0)Estado Objectivo: pergunta lógica (p/ unificação)

At(Home, S) ∧ Have(Milk , S) ∧ Have(Bananas , S) ∧ Have(Drill , S)Operadores: conjunto de axiomas de estado sucessor∀ a,s Have(Milk, Result(a, s)) ⇔

[(a = Buy(Milk) ∧ At(supermarket, s)∨ (Have(Milk, s) ∧ α ≠ Drop(Milk))]

NotaçãoResult (a, s) - uma acçãoResult’(p, s) - sequência de acções

Page 12: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

12

Planeando com Cálculo de Situações

Estado Objectivo: pergunta lógicaAt(Home,Result’(p, S0)) ∧ Have(Milk, Result’(p, S0)) ∧

Have(Bananas, Result’(p, S0)) ∧ Have(Drill, Result’(p, S0))

Solução:p = [Go(SuperMarket), Buy(Milk), Buy(Bananas),

Go(HardwareStore), Buy(Drill), Go(home)]

LimitaçõesEficiência da inferência em lógica de primeira ordemNenhuma garantia sobre a qualidade da solução

Ex.: Pode haver passos redundantes

Resolução de problemas x Planeamento com Cálculo Situacional

Resolver o Problema:(Procura Espaço de Estados)

A representação de acções, estados, objectivos, planos são representados por um programa que gera descrições completas.“Caixa preta”; sequências de acções começando do estado inicial e acabando no estado objectivo.

Planeamento:(Cálculo Situacional)

“Abre” a representação de estados, objectivos, e acções.O planeador é livre para adicionar acções ao plano onde quer que elas sejam necessárias.A maioria das partes do mundo são independentes da maioria das outras partes (Dividir para Conquistar).

Page 13: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

13

Limitações do Cálculo Situacional

Situações são pontos instantâneos no tempo.

Vocacionado para mundos onde ocorre uma acção de cada vez.

Não pode ser usado quando:As acções têm durações diferentes.Os seus efeitos dependem da duração.

Podem ser introduzidos passos irrelevantes no plano.

Limitações do Cálculo Situacional

Conclusão:Apesar de tudo, é suficiente para muitos domínios de planeamento.

Solução:Utilizar linguagem mais restritiva.Recorrer a algoritmos específicos.

Page 14: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

14

Linguagem STRIPSSTRIPS = STanford Research Institute ProblemSolver

Criado de forma a evitar os problemas do cálculo situacional.

Foi a primeira proposta de solução para um problema de planeamento integrando um sistema formal.

Apresentado por Fikes e Nilsson em 1971.

Linguagem STRIPS

Características:Mantém muita da expressividade do cálculo situacional.Esta linguagem recorre a algoritmos específicos, como tal mais eficientes.As acções são representadas de forma simplificada relativamente à representação em Lógica.

Page 15: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

15

Linguagem STRIPS

Constituição:Operadores

Descrevem as acçõesPré – condições:

Têm que verificar-se para o operador ser aplicávelDelete – List

Predicados que se tornam falsos após a execução da acção

Add – ListPredicados que se tornam verdadeiros após a execução da acção

Linguagem STRIPS

Exemplo:Forma escrita:

Nome: liga-carroPre – condição: motor_off (carro) ∧colocada(chave, carro)Delete-List: motor_off(carro)Add-List: motor_on(carro)

Graficamente:

Page 16: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

16

Linguagem STRIPS

Estados:Conjunções de literais sem variáveis

ObjectivosConjunções de literaisPodem conter variáveis (assumem-se existencialmente quantificadas)

Linguagem STRIPS

Assumpção STRIPS:Tudo o que não for retirado explicitamente por um operador mantém-se válido no estado resultante da aplicação desse operador.

Page 17: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

17

Linguagem STRIPS

Dois Quartos: R1 e R2Um Robot aspiradorPó

R1 R2

Linguagem STRIPSRepresentação do estado:

Proposições verdadeirasno estado actual

“and”Lógico

R1 R2

In(Robot, R1) ∧ Clean(R1)

R1 R2

Page 18: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

18

Linguagem STRIPS

Não existe proposições negativas, como ¬Clean(R2)Assumpção de Mundo fechado: Todas as proposições que não estão listadas no estado, são falsas nesse estado.Sem “or” conector, como In(Robot,R1) ∨ In(Robot,R2)Sem variáveis do tipo, ∃x Clean(x)

Representação do estado

In(Robot, R1) ∧ Clean(R1)

R1 R2

Linguagem STRIPS

Representação do objectivo.Exemplo: clean(R1) ∧ clean(R2)

Um objectivo é atingido num estado S se todas as proposições em G (chamado Sub objectivos) estão também em S.

Page 19: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

19

Linguagem STRIPS

Representação das acções:RIGHT

Pré-condição: In(Robot, R1)Delete-list: In(Robot, R1)Add-list: In(Robot, R2)

R1 R2 R1 R2

In(Robot, R1) ∧Clean(R1) In(Robot, R2) ∧ Clean(R1)

Right

Linguagem STRIPS

Representação das acções:RIGHT

Pré-condição: In(Robot, R1)Delete-list: In(Robot, R1)Add-list: In(Robot, R2)

Uma acção A é aplicável a um estado S se as proposições na sua pré condição estão todas em S.A aplicação de A para S é um novo estado obtido apagando as proposições existentes na lista de itens a apagar de S e adicionando estes na lista a adicionar.

Page 20: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

20

Linguagem STRIPS

Esquema de Acções:Descreve um conjunto de acções: Suck(R1) e Suck(R2)

Parâmetros que irão ser instanciados e combinados com uma pré - condição em relação a um determinado estado

Linguagem STRIPS

Esquema de Acções:Descreve um conjunto de acções: Suck(R1) e Suckr(R2)

Suck(r)Pré-condição: In(Robot, r)

Delete-list: ∅Add-list: Clean(r)

Page 21: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

21

Linguagem STRIPS

Aspirar(r)Pré-condição: In(Robot, r)

Delete-list: ∅Add-list: Clean(r)

In(Robot, R1) ∧ Clean(R1) In(Robot, R1) ∧ Clean(R1)

Suck(R1)R1 R2

r R1

R1 R2

Linguagem STRIPS

Aspirar(r)Pré-condição: In(Robot, r)

Delete-list: ∅Add-list: Clean(r)

R1 R2

In(Robot, R2) ∧ Clean(R1)

R1 R2

In(Robot, R2) ∧ Clean(R1)∧ Clean(R2)

Suck(R2)

r R2

Page 22: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

22

FIM PARTE 1

Introdução à

Inteligência Artificial

Planeamento

Page 23: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

23

Agenda

Parte 1Introdução

Resolução de Problemas vs PlaneamentoPlaneamento com Cálculo SituacionalLinguagem STRIPS

Parte 2Mundo de BlocosAnomalia de SussmanAlgoritmos de Planeamento

Mundo de BlocosDomínio:

Conjunto de blocos assentes numa superfície.

Acções:Os blocos podem ser empilhados;Podemos pegar num bloco e movê-lo para outra posição;Apenas pode ser movimentado um bloco de cada vez.

Objectivo:construir uma pilha específica de blocos.

B

C

AEstado inicial

Estado objectivo

A

B

C

Page 24: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

24

Pergunta?

Dado um plano com sub objectivos parciais, é sempre possível resolve-los numa ordem sequencial?

Anomalia de Sussman

Apresentado por Sussman em 1973:Problema:

Estado inicial:sobre(C, A) ∧ sobre(A, Mesa) ∧ sobre(B, Mesa)

Estado final:sobre(C, Mêsa) ∧ sobre(A, B) ∧ sobre(B, C)

B

C

AEstado inicial Estado objectivo

A

B

C

Page 25: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

25

Anomalia de SussmanÁrvore de Procura:

(sub objectivos: sobre(C, Mêsa) ∧ sobre(A, B) ∧ sobre(B, C) )

B

C

A

Estado inicial

B

C

A

BC A

BC

A

Anomalia de Sussman

Neste exemplo podemos ver que por vezes sub planos são incompatíveis entre si.

Page 26: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

26

Algoritmos de Planeamento

Algoritmos de procura standard (Depth-first, A*, etc.) são ineficientes devido a:

O problema do ruídoConseguir encontrar uma boa função heurísticaEstes algoritmos não podem tirar vantagem da decomposição do problema em sub problemas

Vamos abordar algoritmos mais eficientes:Procura num espaço de estadosPlaneamento de ordem parcial

Procura num espaço de estados

Procura em progressãoProcura em regressãoEx.: Init( At(C1,SFO) ∧ At(C2,JFK) ∧ At(P1,SFO) ∧ At(P2,JFK)

∧ Cargo(C1) ∧ Cargo(C2) ∧ Plane(P1) ∧ Plane(P2)∧ Airport(JFK) ∧ Airport (SFO)

Goal( At(C1,JFK) ∧ At(C2,SFO) )Action( Load(c,p,a),

PRECOND: At(c,a) ∧ At(p,a) ∧ Cargo(c) ∧ Plane(p ) ∧ Airport(a)EFFECT: ¬At(c,a) ∧ At(c,p) )

Action( Unload(c,p,a),PRECOND: In(c,p) ∧ At(p,a) ∧ Cargo(c) ∧ Plane(p ) ∧ Airport(a)EFFECT: At(c,a) ∧ ¬In(c,p) )

Action( Fly(p,from,to),PRECOND: At(p,from) ∧ Plane(p ) ∧ Airport(from) ∧ Airport(to)EFFECT: ¬At(p,from) ∧ At(p,to) ) )

Tabela: Problema de planeamento involvendo o transporte de carga entre aeroportos.

Page 27: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

27

Procura em ProgressãoA formulação de problemas de planeamento é a seguinte:1) O estado inicial da procura é o estado inicial do problema de

planeamento.

2) Cada estado será um conjunto de literais positivos.

3) O estado sucessor resultante de uma acção é gerado adicionando os literais positivos e apagando os literais negativos.

4) O teste do objectivo verifica se o estado satisfaz o objectivo do problema de planeamento.

5) O custo de cada acção é geralmente 1, este custo pode ser colocado pelos utilizadores.

Procura em ProgressãoExemplo do transporte de carga entre aeroportos:

A procura começa no estado inicial até ao objectivo

Page 28: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

28

Procura em ProgressãoConclusões:

Todas as acções são consideradas em cada estado, sendo analisadas acções irrelevantes para a resolução do problema.

Quanto mais acções, mais caminhos possíveis a percorrer e em alguns casos podemos chegar a um nível em que a resolução do problema não écomputável.

Imaginemos 10 aeroportos com 5 aviões em cada e 20 peças de carga para transportar1000 acções diferentes 1000^41 nós a percorrer

Procura em RegressãoNesta procura apenas consideramos as acções relevantes para a resolução do nosso problema.Como considerar uma acção como relevante ?

Relevante = se essa acção tiver como efeito um dos elementos da conjunção.

Ex.: Vamos usar o exemplo do transporte de carga entre aeroportos

Se o objectivo é ter 20 peças de carga num aeroporto B: At(C1,B) ∧ At(C2,B) ∧ At(C3,B) ∧ .. ∧At(C20,B) . Considerando a conjunção At(C1,B), temos de procurar uma acção que tenha esta última como efeito. Unload(C1,p,B) tem como efeito At(C1,B)

Page 29: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

29

Procura em Regressão

Como construir estados antecessores ao estado objectivo ?

1) Quaisquer efeitos positivos de A que aparecem em G são apagados

2) Cada literal que seja pré-condição de A éadicionado. Caso este literal já exista ele éignorado

3) A procura acaba quando for gerado um estado antecessor que satisfaça o estado inicial do problema de planeamento

Procura em Regressão

Exemplo:

A procura começa no estado objectivo até ao estado inicial.

Page 30: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

30

Heurísticas no planeamento num espaço de estados

Procuras em regressão e progressão são ineficientes sem uma boa função heurística.A função heurística estima a distância de um estado até um objectivo.Como calcular uma boa função heurística ?

Derivar um problema simplificado da especificação do problema a resolver.Usar a assunção de independência do sub objectivo.

Neste caso o custo de resolução de um conjunto de sub objectivos é aproximado pela soma dos custos de resolução de cada um dos sub objectivos de forma independente.

Planeamento de ordem parcialAs procuras em progressão e em regressão são formas particulares de procura totalmente ordenada.

Estes tipos de algoritmos exploram apenas sequências lineares de acções ligados directamente ao estado inicial ou ao objectivo.

Estes não podem tirar proveito de decompor um problema em vários sub problemas.

Page 31: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

31

Planeamento de ordem parcialObjectivo:

Separar os problemas em sub problemas e assim ter a vantagem de flexibilidade na ordem em que construímos o plano.

O planeador pode trabalhar em decisões ou partes importantes primeiro.

Qualquer algoritmo de planeamento que consiga colocar duas acções num plano sem especificar qual deles vem primeiro é chamado de planeador de ordem parcial.

Planeamento de ordem parcial

Ex.:

Tabela: problema de colocar um par de sapatos

Goal( RigthShoeOn ∧ LeftShoeOn ) Init() Action(RightShoe, PRECOND: RightSockOn, EFFECT:

RightShoeOn) Action(RightSock, EFFECT: RightSockOn) Action(LeftShoe, PRECOND: LeftSockOn, EFFECT: LeftShoeOn) Action(LeftSock, EFFECT: LeftSockOn)

Page 32: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

32

Planeamento de ordem parcial

Resolução:Start

LeftSock

RightSock

LeftShoe

RightShoe

Finish

Start

Finish

RightSock

LeftSock

LeftShoe

RightShoe

Start

Finish

LeftSock

RightSock

RightShoe

LeftShoe

Start

Finish

LeftSock

RightSock

LeftShoe

RightShoe

Start

Finish

RightSock

RightShoe

LeftSock

LeftShoe

Start

Finish

RightSock

LeftSock

RightShoe

LeftShoe

Start

Finish

LeftSock

LeftShoe

RightSock

RightShoe

Planos de ordem parcial Planos de ordem total

Planeamento de ordem parcialCada plano é constituído por quatro componentes:

AcçõesO plano vazio contem apenas as acções Start e Finish.Start não tem pré condições e tem como efeito todos os literais no estado inicial do problema de planeamento.Finish não tem efeitos e tem como pré condições os literais objectivo do problema de planeamento.

Restrições de ordenaçãoEstes elementos definem limitações na ordem das acções.São da forma A < B, e lê-se como “A antes de B” e significa que a acção A tem que ser executada antes da B.Qualquer ciclo como: A < B e B <A representam uma contradição por isso as regras que dão origem a ciclos não podem ser adicionadas ao plano.

Page 33: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

33

Planeamento de ordem parcialLigações causais

Uma ligação causal entre duas acções A e B num plano é escrito como:

A P BNo exemplo anterior teríamos que a ligação causal

RightSock RightSockOn RightShoe

Pré condições abertasUma pré condição está aberta se não é acessível por alguma das acções do plano. Reduzir o conjunto de pré condições abertas até atingir um conjunto vazio, sem introduzirem contradições.

Planeamento de ordem parcialExemplo dos sapatos:

Acções: {RightSock, RightShoe, LeftSock, LeftShoe, Start, Finish}

Restrições de ordenação: {RightSock < RightShoe, LeftSock < LetfShoe}

Ligações causais:RightSock RightSockOn RightShoeLeftSock LeftSockOn LeftShoeRightShoe RightShoeOn FinishLeftShoe LeftShoeOn Finish

Pré condições abertas: {}.

Page 34: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

34

Heurísticas para o planeamento de ordem parcial

Planeamento de ordem parcial vs planeamento de ordem total:

No planeamento de ordem parcial a vantagem é ser possível decompor problemas em sub problemas.Uma desvantagem é o facto de não representar os estados directamente do problema original.É difícil estimar a que distância um plano de ordem parcial estáde alcançar um objectivo.Há menos conhecimento de como computar heurísticas exactas usando o planeamento de ordem parcial do que para o planeamento de ordem total.Em ambos os casos, custo é sobrestimado quando existem acções que alcançam vários objectivos e subestimado quando existem interacções negativas entre os passos de um plano.

Heurísticas para o planeamento de ordem parcial

A heurística mais óbvia usada no planeamento de ordem parcial écontar o número de pré condições abertas distintas. A função heurística é usada para escolher que plano devemos refinar. Dada esta escolha, o algoritmo gera sucessores baseados na selecção de uma única pré condição aberta para trabalhar sobre a mesma.A heurística most-constrained-variable (de CSPs) pode ser adaptada para algoritmos de planeamento:

Seleccionar a condição aberta que pode ser satisfeita num menor número de maneiras diferentes; Casos especiais:

Se uma condição aberta não pode ser alcançada por nenhuma das acções existentes, a heurística irá seleccioná-la;Se uma condição aberta pode ser alcançada de uma única forma, então deve ser seleccionada pois pode impor limitações adicionais noutras escolhas para ainda possam ser feitas.

Page 35: Inteligência Artificial - UMacee.uma.pt/edu/iia/acetatos/iia-Planeamento -PeB.pdfInteligência Artificial Universidade da Madeira 5 Limitações da RP zFactor de ramificação grande

Inteligência Artificial Universidade da Madeira

35

Heurísticas para o planeamento de ordem parcial

Estudos mostram que o uso destes dois casos especiais dá-nos um grande aumento da velocidade:

A computação de todos os casos possíveis para satisfazer todas as condições abertas tem um elevado custo;Nem sempre a computação de todos os casos traz

grandes valias.

FIM