Algoritmo para Planeador por
ordem parcial
l
Algoritmo POP (partial-order planner)
Começa com um plano mínimo; em cada iteração, expande o plano garantindo
a condição c de um passo Snec.
function POP(inicial, objectivo, operadores) returns plano
plano <- MAKE-MINIMAL-PLAN(inicial, objectivo)
loop do
if SOLUTION(plano) then return plano
Snec, c <- SELECT-SUBGOAL(plano)
CHOOSE-OPERATOR(plano, operadores, Snec, c)
RESOLVE-THREATS(plano)
end
Raciocínio e Resolução de Problemas
© Amílcar Cardoso, DEI-FCTUC, 1996
1. Planeamento - 70
Algoritmo para Planeador por
ordem parcial
function SELECT-SUBGOAL(plano) returns Snec, c
escolhe passo Snec de STEPS(plano)
com pré-condição c ainda não garantida
Raciocínio e Resolução de Problemas
© Amílcar Cardoso, DEI-FCTUC, 1996
1. Planeamento - 71
Algoritmo para Planeador por
ordem parcial
O operador pode ser escolhido entre o conjunto de operadores disponíveis,
incluindo os que constituem já passos do plano
procedure CHOOSE-OPERATOR(plano, operadores, Snec, c)
choose passo Sadd de operadores ou de STEPS(plano)
com c na ADDLIST
if não existe tal passo then fail
c
→ Snec a LINKS(plano)
adiciona Sadd 
adiciona Sadd < Snec a ORDERINGS(plano)
if Sadd é um passo retirado de operadores
then adiciona Sadd a STEPS(plano)
adiciona Start < Sadd < Finish a ORDERINGS(plano)
Raciocínio e Resolução de Problemas
© Amílcar Cardoso, DEI-FCTUC, 1996
1. Planeamento - 72
Algoritmo para Planeador por
ordem parcial
Se algum passo ameaçar alguma ligação causal, efectuar propoção ou
despromoção
procedure RESOLVE-THREADS(plano)
c
for each Sthr que ameace Si → Sf em LINKS(plano) do
choose entre
Promoção: adicionar Sthr < Si a ORDERINGS(plano)
Despromoção: adicionar Si < Sthr a ORDERINGS(plano)
if not CONSISTENT(plano) then fail
end
Raciocínio e Resolução de Problemas
© Amílcar Cardoso, DEI-FCTUC, 1996
1. Planeamento - 73
Ponto da Situação
l
POP consegue resolver com poucos estados de procura o
que requeriria uma procura pesada se trabalhássemos num
espaço de estados
l
Mínimo comprometimento:
o só procura nos pontos de intersecção entre sub-planos
l
Ligações causais:
o permitem reconhecer prematuramente planos
condenados ao fracasso
Raciocínio e Resolução de Problemas
© Amílcar Cardoso, DEI-FCTUC, 1996
1. Planeamento - 73-A
Ponteiros para a frente...
l
Extensões para admitir
o operadores parcialmente instanciados
o efeitos condicionais
o quantificação universal
o ...
l
Planeamento hierárquico
l
Planeamento condicional
Raciocínio e Resolução de Problemas
© Amílcar Cardoso, DEI-FCTUC, 1996
1. Planeamento - 73-B