Frequência de 99 - Universidade de Coimbra

UNIVERSIDADE DE COIMBRA
FACULDADE DE CIÊNCIAS E TECNOLOGIA
Departamento de Engenharia Informática
Pólo II da Universidade, Pinhal de Marrocos
3030 Coimbra, Portugal
Tel.: 790000 — Fax: 701266
PLANEAMENTO E ESCALONAMENTO
ANO LECTIVO 1998/99
Exame de Recurso, 8/6/99
Duração: 2h (+ 15m de tolerância)
1ª Questão (12 valores)
Asterix e Obelix têm que transportar um menir através de um tunel para o oferecerem a
ZáZá. Obelix pode pegar num menir e transportá-lo. Asterix pode transportar um menir
desde que antes beba poção mágica, mas para pegar nele precisa da ajuda do Obelix:
como tem braços pequenos, precisa que o Obelix pegue no menir para lho pôr às costas.
Túnel
Como o túnel é estreito e baixo, Obelix não consegue passar por ele juntamente com o
menir. Asterix, por ser mais pequeno, consegue.
a) Escreva os operadores necessários à formalização deste domínio. Utilize para tal a
sintaxe do Prodigy
1
Prova Escrita de Frequência de Planeamento e Escalonamento, 8/6/99
b) Diga, justificando, que tipo de extensões ao algoritmo POP básico deverá considerar
para que seja possível resolver problemas com os operadores apresentados.
c) Considerando os operadores da alínea a), mostre graficamente o plano parcial que um
planeador construído com base no algoritmo POP com as extensões referidas na alínea
b) gerará, considerando como estado inicial a situação descrita na figura, e como
objectivos: Asterix junto a ZáZá; Obelix junto a ZáZá; menir junto a ZáZá, pousado no
chão (ZáZá é frágil).
d) Assinale uma situação em que o POP, durante a construção do plano parcial, detecte uma
ameaça; explique de que forma o POP resolve essa ameaça.
2ª Questão (8 valores)
Considere a lógica temporal de 1ª ordem (Thomas Dean) apresentada nas aulas, com o
tempo representado por inteiros. Considere ainda que são conhecidos, para as
proposições-fluentes A, B, C e D, e para as proposições-eventos E1 e E2, as seguintes
fórmulas:
holds(1, A)
∀ t [holds(t, A) ∧ holds(t, E1) ⇒ holds(t+1, B)]
∀ t [holds(t, ¬A) ∧ holds(t, E1) ⇒ holds(t+1, D)]
∀ t [holds(t, B) ∧ holds(t, E2) ⇒ holds(t+1, C)]
Suponha que ocorre o evento E1 no tempo 2 e E2 no tempo 3.
a) Descreva qual a interpretação mais preferida nos tempos 1, 2, 3 e 4, de entre as que
resultam da aplicação da Lei da Inércia do Senso Comum.
b) Descreva qual a interpretação menos preferida nos tempos 1, 2, 3 e 4, de entre as que
resultam da aplicação da Lei da Inércia do Senso Comum.
c) Considere agora que está a armazenar informação temporal numa base de dados
recorrendo a tokens representados por fórmulas do tipo holds( α, ψ), onde α é um intervalo
e ψ uma fórmula lógica. Escreva as regras causais correspondentes ao seguinte texto:
Se ocorre E1 quando A é verdade, B passa a ser verdade; se ocorre E1
quando A é falso, D passa a ser verdade; se ocorre E2 quando B é verdade,
C passa a ser verdade
Escreva ainda o Mapa Temporal que se obtém utilizando Projecção e Persistence Clipping,
sabendo que inicialmente se conhece holds((0-1), A), holds(2, E1) e holds(3, E2).
2