Grafos e Planejamento em IA: Conceitos Essenciais

Grafos

1) Defina Grafo

Um grafo pode ser definido como um conjunto de vértices e um conjunto de arestas.

2) Defina Rede Semântica

Conjunto de grafos e arestas.

3) Descreva as características de Árvore Semântica

• Cada nó possui um pai/predecessor, exceto o nó raiz.
• Cada nó possui um ou mais filhos/sucessores, exceto os nós folha.
• Tipicamente orientado.

4) Qual a diferença entre a busca em largura e profundidade?

• Profundidade: Segue cada caminho até a maior profundidade antes de partir para o próximo caminho.
• Largura: Percorre cada nível da árvore.

5) Descreva as propriedades (complexidade, completude, admissibilidade e irrevogabilidade) dos métodos de busca em grafos.

• Complexidade:
  • Temporal: Tempo (processamento) para chegar a um estado objetivo.
  • Espacial: Espaço (memória/disco) que o método utiliza.
  • Por exemplo: Busca em Profundidade é eficiente com relação ao uso de espaço, mas pode não ser eficiente em tempo. Uma solução mais rápida pode não ser a melhor.
• Completude:
  • Garantia de que o método vai achar um estado objetivo se houver algum.
  • Um método que não é completo pode acabar relatando que não há solução.
  • Pode não ser necessária ou possível em todos os casos.
• Admissibilidade:
  • Garantia de que é a melhor solução (solução ótima).
  • Encontra o menor caminho até a solução.
  • Um método pode não ser eficiente, mas pode garantir a melhor solução.
• Irrevogabilidade:
  • Métodos que examinam apenas um caminho até o final.
  • Frequentemente encontram soluções sub-ótimas.

6) Descreva como são os métodos de busca informados e não informados.

• Métodos de busca não informados (cegos): Método que não possui nenhuma informação adicional sobre o problema para escolher o caminho/direção a seguir.
• Métodos de busca informados: Utilizam conhecimento específico do problema (heurística) além da própria definição.

Planejamento

1) Defina método de planejamento em Sistema Inteligente de Informação (IA).

Métodos de planejamento são usados para resolver problemas nos quais uma sequência de ações deve ser seguida para atingir um objetivo.

Um planejador (ou agente de planejamento) começa em um estado inicial e tem um objetivo específico a atingir.

Para atingir o objetivo, o planejador desenvolve um plano e o executa.

Exemplos: Robôs.

2) Descreva as características das técnicas de busca utilizadas em planejamento.

• Para desenvolver um plano, o planejador pode criar uma árvore de busca.
• Começar em um estado.
• Indicar a ação que o leva a cada estado.
• Um plano adequado é encontrado quando um estado objetivo é encontrado.

3) Cite 2 problemas encontrados na etapa de planejamento.

• Agente pode “pular” ações irrelevantes.

  Exemplo: Objetivo: ter um livro “X” cujo código possui 10 dígitos.

  Busca deveria examinar a árvore até descobrir um estado objetivo (ação) de Compra com sucesso.

  Agente de planejamento poderia ter uma descrição explícita do objetivo e comprar somente o código informado.

• Encontrar uma boa função heurística.

  Exemplo: Objetivo: Comprar quatro livros diferentes.

  Na árvore de busca, os estados objetivo são inúmeros.

  Se o planejador possuir uma conjunção de sub-objetivos (comprar A, B, C e D), pode-se usar uma heurística: comprar um por vez e ir reduzindo o custo da solução à medida que objetivos sejam satisfeitos.

4) Explique a diferença entre busca para frente e para trás no espaço de estados.

• Busca para frente no espaço de estados: Executam-se ações partindo do estado inicial até chegar ao objetivo.
• Busca para trás no espaço de estados: Avalia-se as ações executadas partindo do objetivo (considera apenas ações relevantes).

5) Descreva como é feito o planejamento de ordem parcial.

Abordagem que tenta resolver sub-objetivos por meio de sub-planos.

Combinando os subplanos, o objetivo final também deve ser atingido.