Aula Prática 1 – Procura em Espaços de Estados

Matéria das aulas T3 (procura cega) e T4 (procura informada). O exercício 1 é resolvido no quadro; os restantes são para trabalho autónomo, individualmente ou em grupos de dois. Os exercícios que ficarem por resolver na aula devem ser resolvidos em casa.

Convenções

Toda a terminologia é a do AIMA, 4.ª edição (capítulo 3) e a dos slides T3 e T4.

• Os sucessores de um estado são gerados por ordem alfabética.
• Desempates na fila de prioridade: sai primeiro o nó que foi gerado há mais tempo.
• A fila FIFO escreve-se com a frente (o próximo a sair) à esquerda; a pilha LIFO escreve-se com o topo (o próximo a sair) à direita. Na pilha, os sucessores são empilhados por ordem inversa, para que o primeiro por ordem alfabética seja o primeiro a sair.
• Quando um nó é recolocado na fronteira — porque apareceu um caminho mais barato para o seu estado —, o nó anterior para esse estado sai da fronteira, e nas tabelas escreve-se apenas o nó novo.
• Na procura de profundidade limitada, o nó inicial está à profundidade 0 e os nós à profundidade ℓ não são expandidos — é a condição DEPTH(node) ≥ ℓ da listagem dos slides. Com o limite ℓ exploram-se, portanto, caminhos de no máximo ℓ acções.
• Nos grafos, os arcos são dirigidos; o número junto ao arco é o ACTION-COST; o valor de h está junto ao nome do estado. O estado inicial está a verde e os objectivos têm contorno vermelho.

Exercício 1 – Dois algoritmos no mesmo grafo

Figura 1 — Estado inicial S, objectivo G.

(a) Aplique a procura em largura primeiro, preenchendo passo a passo uma tabela com quatro colunas: #, nó retirado, fronteira (FIFO) depois e atingidos depois. Indique o caminho devolvido e o seu custo.

(b) Aplique o A*. Mesma tabela, escrevendo cada nó da fronteira na forma X(g+h=f) e ordenando a fronteira por f. Caminho e custo.

(c) No passo em que se expande B, o estado D já estava em atingidos. O que faz a BEST-FIRST-SEARCH, e porquê? Que linhas do pseudocódigo são responsáveis?

(d) A procura em largura devolveu o caminho com menos acções; o A* devolveu o de menor custo. Porque é que não são o mesmo caminho? O que teria de acontecer aos custos para que fossem sempre o mesmo?

(e) Verifique que h é admissível. É consistente?

Exercício 2 – Custo uniforme e sôfrega no mesmo grafo

Ainda sobre o grafo da Figura 1.

(a) Aplique a procura de custo uniforme, com a tabela do exercício 1 (escreva X(g)). Caminho e custo.

(b) Aplique a procura sôfrega, escrevendo X(h). Caminho e custo.

(c) Complete:

Algoritmo	Nós expandidos	Caminho devolvido	Custo	Óptimo em custo?
Largura primeiro
Custo uniforme
Sôfrega
A*

(d) A sôfrega expande menos nós do que o A*. Porque é que isso não faz dela o melhor algoritmo?

(e) Na procura de custo uniforme, G entra em atingidos com g = 22 e, mais tarde, com g = 20. Se o teste de objectivo fosse feito ao gerar — como na procura em largura — que caminho teria sido devolvido? Relacione com o slide «Porque é que o teste tem de ser ao retirar».

Exercício 3 – Formular um problema de procura

Um drone de entregas opera sobre uma cidade representada por uma grelha de N × M células. O drone parte do depósito, numa célula fixa e conhecida.

Há P pacotes. Cada pacote i está numa célula de recolha fixa e conhecida e tem uma célula de entrega, também fixa e conhecida. Todas estas células são distintas entre si e distintas do depósito. O drone transporta no máximo um pacote de cada vez.

Acções: mover para uma das células adjacentes na horizontal ou na vertical (custo 1); recolher o pacote da célula onde está, se não levar nenhum (custo 1); entregar o pacote que leva, se estiver na célula de entrega desse pacote (custo 1); recarregar, só no depósito (custo 5).

O drone tem uma bateria com E unidades de carga, que começa cheia. Cada mover gasta uma unidade; recolher e entregar não gastam; recarregar repõe a bateria em E. Com a bateria a zero o drone não se pode mover. O objectivo é ter os P pacotes entregues.

(a) Formalize o problema indicando os seis componentes do AIMA: espaço de estados, estado inicial, estados objectivo (IS-GOAL), acções (ACTIONS), modelo de transição (RESULT) e custo das acções (ACTION-COST).

(b) Qual é o tamanho do espaço de estados, em função de N, M, P e E? Justifique a contagem.

(c) Qual é o factor de ramificação máximo a partir de um estado qualquer? Justifique.

(d) Suponha agora que o drone pode transportar até dois pacotes ao mesmo tempo. Qual passa a ser o tamanho do espaço de estados?

(e) Apresente uma heurística admissível não trivial e justifique a admissibilidade. Sugestão: pense num problema relaxado.

(f) Considere h₂(n) = (número de pacotes ainda não entregues). É admissível? É consistente? Domina a heurística da alínea (e), ou é dominada por ela?

Exercício 4 – Procura cega

Figura 2 — Estado inicial S, objectivo G. O grafo é acíclico.

Para cada um dos algoritmos seguintes, preencha a tabela passo a passo (nó retirado, fronteira depois, atingidos depois) e indique o caminho devolvido, o seu custo e a lista de nós expandidos.

(a) Procura em largura primeiro.

(b) Procura em profundidade primeiro (tipo-árvore, pilha LIFO, com IS-CYCLE). Nesta não há tabela de atingidos.

(c) Procura de custo uniforme.

(d) A procura em largura expandiu muito menos estados do que a de custo uniforme e devolveu um caminho muito pior. Explique as duas coisas ao mesmo tempo.

(e) O grafo é acíclico, e por isso a procura em profundidade tipo-árvore termina mesmo sem o teste IS-CYCLE. Se existisse também o arco H → A com custo 1, o que aconteceria à procura em profundidade sem IS-CYCLE? E com IS-CYCLE?

Exercício 5 – Profundidade limitada e aprofundamento progressivo

Ainda sobre o grafo da Figura 2.

(a) Aplique a procura de profundidade limitada com ℓ = 1 e com ℓ = 2. Para cada limite indique os nós retirados da fronteira, pela ordem, e o resultado (failure, cutoff ou um nó solução).

(b) Aplique o aprofundamento progressivo. A que limite ℓ encontra solução? Qual é o caminho e o custo?

(c) Some os nós expandidos em todas as iterações do aprofundamento progressivo e compare com os da procura em largura primeiro sobre o mesmo grafo. Comente.

(d) Com ℓ = 3, o estado H é retirado da fronteira duas vezes. Porquê? O que é que o evitaria, e a que preço?

(e) A procura em largura precisa de O(b^d) de memória e o aprofundamento progressivo de O(bd). Com b = 10 e d = 8, e supondo 1 kbyte por nó, quanta memória é isso em cada caso?

Exercício 6 – Procura informada

Ainda sobre o grafo da Figura 2.

(a) Aplique a procura sôfrega. Tabela, caminho, custo, nós expandidos.

(b) Aplique o A*. Tabela com X(g+h=f), caminho, custo, nós expandidos.

(c) O A* e a procura de custo uniforme devolveram o mesmo caminho, mas o A* expandiu metade dos estados. Explique com a ideia dos contornos do slide «Contornos de procura».

(d) Quais são os nós que o A* nunca expande? Diga, para cada um, qual é o valor de f que o impede, e relacione com o critério «o A* nunca expande nós com f(n) > C*».

(e) Neste grafo o A* não substituiu nenhuma entrada em atingidos. Diga porquê: repare em que estados é que chega mais do que um caminho e verifique se ambos os caminhos chegaram sequer a ser gerados.

Exercício 7 – Comparar os algoritmos

Complete a tabela para o grafo da Figura 2 (use os resultados dos exercícios 4 a 6):

Algoritmo	Nós expandidos	Caminho	Custo	Óptimo?	Memória
Largura primeiro
Profundidade primeiro (tipo-árvore)
Aprofundamento progressivo
Custo uniforme
Sôfrega
A*

E responda:

(a) Três algoritmos expandiram apenas três estados, e devolveram caminhos de custo 19, 19 e 11. Que conclusão se tira daqui sobre «expandir poucos nós»?

(b) A procura em largura e o aprofundamento progressivo devolveram o mesmo caminho. Isso é coincidência? Em que condições é que o aprofundamento progressivo devolve sempre o mesmo caminho que a procura em largura?

(c) A procura em profundidade devolveu um caminho melhor do que a de largura. Isso contraria alguma garantia dada nas aulas?

(d) Dos seis, quais são completos neste grafo e quais seriam completos num espaço de estados infinito?

Exercício 8 – Admissibilidade, consistência e dominância

Ainda sobre o grafo da Figura 2.

(a) Calcule h*(n) — o custo do caminho óptimo de n até G — para A, C, D e E, e verifique que h é admissível nesses estados.

(b) Verifique a consistência de h nos arcos S → C, A → F, C → E e F → H. Em quais deles é que a desigualdade fica justa (com igualdade)?

(c) Substitua h(C) = 4 por um valor x, mantendo tudo o resto.

• (i) Para que valores de x é que h continua admissível?
• (ii) Para que valores de x é que h continua consistente?
• (iii) Há valores de x que a tornem admissível mas não consistente? Quais?

(d) Repita a alínea (c) para h(B) = 8, substituído por y. Os dois intervalos coincidem. Explique porquê, olhando para os arcos que entram e saem de B.

(e) Sejam h₁ e h₂ duas heurísticas admissíveis. Mostre que h(n) = max{h₁(n), h₂(n)} é admissível. Se ambas forem consistentes, h é consistente?

(f) E o mínimo? Se h₁ for consistente e h₂ admissível, min{h₁, h₂} é necessariamente admissível? E consistente?

(g) Diz-se que h₂ domina h₁ se h₂(n) ≥ h₁(n) para todo o n, sendo ambas admissíveis. Porque é que dominar é ser melhor? Qual é o preço a pagar?

Exercício 9 – As duas linhas que repõem um nó na fronteira

Um colega diz que as duas últimas linhas do corpo do if da BEST-FIRST-SEARCH são redundantes e apagou-as, ficando com isto:

function A*(problem) returns a solution node or failure
    node ← NODE(STATE = problem.INITIAL)
    frontier ← a priority queue ordered by g + h, with node as an element
    reached ← a lookup table, with one entry with key
              problem.INITIAL and value node
    while not IS-EMPTY(frontier) do
        node ← POP(frontier)
        if problem.IS-GOAL(node.STATE) then return node
        for each child in EXPAND(problem, node) do
            s ← child.STATE
            if s is not in reached then   ⟵ sem comparar PATH-COST
                reached[s] ← child
                add child to frontier
    return failure

(a) Execute este algoritmo sobre o grafo da Figura 1. Que caminho devolve, e com que custo? Compare com o A* do livro.

(b) Identifique o passo exacto em que o caminho óptimo é perdido, e diga porquê.

(c) Construa uma instância com no máximo 5 estados e uma heurística admissível em que este algoritmo devolve um caminho sub-óptimo. Desenhe o grafo e indique h.

(d) [difícil] Consegue construir uma instância em que a heurística seja, além de admissível, também consistente, e em que o algoritmo continue a devolver um caminho sub-óptimo?

Se sim, há um erro no raciocínio que levou o colega a apagar as duas linhas:

«Os slides dizem que, com h consistente, nenhum estado já expandido volta a ser atingido por um caminho melhor. Então a condição child.PATH-COST < reached[s].PATH-COST nunca se verifica, e posso apagá-la.»

Identifique a premissa, que é verdadeira, e a conclusão, que é falsa, e diga porque é que a segunda não se segue da primeira.

(e) Este algoritmo não é a procura tipo-árvore. Aplique ao mesmo grafo o A* tipo-árvore — sem tabela atingidos nenhuma — e diga que caminho devolve. Como é possível que guardar atingidos, e nunca o actualizar, seja pior do que não guardar nada?

(f) [difícil] A demonstração de optimalidade do A* dada na aula usa apenas a admissibilidade de h, e não fala de atingidos em lado nenhum. Identifique o passo da demonstração que deixa de ser válido neste algoritmo, e diga porque é que esse passo continua válido na procura tipo-árvore.

Exercício 10 – IDA* e RBFS

Ainda sobre o grafo da Figura 2.

(a) Aplique o IDA*. Para cada iteração indique o f-limite, os nós expandidos e os estados cortados (com o f que os cortou). Quantas iterações são precisas?

(b) Quantas vezes é que S e C são expandidos ao longo de toda a execução? Porque é que isso não é catastrófico?

(c) Aplique o RBFS. Identifique a primeira mudança de ideias: qual é o nó que a provoca, qual era o seu f e qual passa a ser. Explique de onde vem o novo valor (backed-up value).

(d) Compare a memória usada pelo A*, pelo IDA* e pelo RBFS neste grafo. E o número de expansões.

Exercício 11 – Complexidade, b* e afirmações

(a) Num espaço de estados com factor de ramificação b = 4 e solução mais rasa à profundidade d = 6: quantos nós gera a procura em largura primeiro? E o aprofundamento progressivo? Calcule o rácio e explique porque é que não é catastrófico.

(b) O A* encontrou uma solução à profundidade d = 5 tendo gerado 52 nós. Qual é o factor de ramificação efectivo b*? O que é que um b* próximo de 1 significa?

(c) Para cada afirmação, indique se é verdadeira (V) ou falsa (F). Justifique em uma linha as que forem falsas.

• i. Uma heurística consistente h satisfaz sempre h(n) ≤ h*(n).
• ii. Uma heurística admissível h satisfaz sempre h(n) ≤ c(n, a, n′) + h(n′).
• iii. A procura sôfrega com h(n) = 0 para todo o n é equivalente ao A* com h(n) = 0.
• iv. Somar uma constante positiva a todos os custos das acções não muda o caminho devolvido pela procura de custo uniforme.
• v. Se h for admissível mas inconsistente, o A* tipo-árvore continua a devolver uma solução óptima.
• vi. Para qualquer h admissível, o conjunto de nós expandidos pelo A* tipo-árvore é sempre um subconjunto dos expandidos pela procura de custo uniforme tipo-árvore.
• vii. O aprofundamento progressivo junta a memória da procura em profundidade à completude da procura em largura.
• viii. A procura em profundidade primeiro em grafos (com tabela de atingidos) nunca fica presa num ciclo num espaço de estados finito.
• ix. O A* ponderado com W = 1 é o A*, e com W → ∞ tende para a procura sôfrega.
• x. Num espaço de estados finito sem solução, o A* com h admissível expande todos os estados alcançáveis a partir do estado inicial.