FenixEdu™

Disciplina

Procura e Planeamento

Área

Área Científica de Inteligência Artificial > Tecnologia de Inteligência Artificial

Activa nos planos curriculares

MEIC-A 2021 > MEIC-A 2021 > 2º Ciclo > Area Principal > Agrupamentos > Inteligência Artificial > Procura e Planeamento

MEIC-T 2018 > MEIC-T 2018 > 2º Ciclo > Agrupamentos > Sistemas Inteligentes > Procura e Planeamento

MEIC-T 2021 > MEIC-T 2021 > 2º Ciclo > Área Principal > Agrupamentos > Inteligência Artificial > Procura e Planeamento

MEIC-T 2015 > MEIC-T 2015 > 2º Ciclo > Agrupamentos > Sistemas Inteligentes > Procura e Planeamento

MEIC-A 2015 > MEIC-A 2015 > 2º Ciclo > Agrupamentos > Sistemas Inteligentes > Procura e Planeamento

MEIC-T 2006 > MEIC-T 2006 > 2º Ciclo > Áreas de Especialização Complementares > Sistemas Inteligentes > Procura e Planeamento

MEIC-A 2006 > MEIC-A 2006 > 2º Ciclo > Área de Especialização Principal > Sistemas Inteligentes > Procura e Planeamento

Nível

A nota final da disciplina é composta por uma componente teórica e por uma componente prática. A componente teórica é composta por um exame (60% da nota final). A componente prática é composta por um projecto de programação (35% da nota final) feito em grupo (trabalho de equipa) e um trabalho de casa (5% da nota final) feito individualmente. A nota de cada componente tem que ser igual ou superior a 9,5 valores. Pode ser solicitada um exame oral pelo corpo docente em casos excepcionais ou pelo aluno quando tenha uma nota igual ou superior a 16 valores. A nota do exame oral será a nota final da disciplina.

Tipo

Não Estruturante

Regime

Semestral

Carga Horária

1º Semestre

Aula Teórica (T): 3.0 h/semana

Aula de Laboratório (PL): 1.5 h/semana

Trabalho Autónomo: 147.0 h/semestre

Créditos ECTS:

Objectivos

• Aprofundar os temas da procura de soluções para problemas complexos e do planeamento de acções. • Reconhecer os diferentes tipos de problemas a resolver. • Dominar as principais metodologias e estratégias de procura. • Perceber que metodologia e estratégia aplicar para cada tipo de problema. • Ser capaz de resolver problemas razoavelmente complexos. • Compreender a especificidade do problema do planeamento de acções e porque necessita de uma abordagem mais potente. • Estudar os fundamentos e abordagens do planeamento de acções e ser capaz de resolver problemas simples de planeamento.

Programa

PARTE 1 – PROCURA 4. HEURÍSTICAS E REPRESENTAÇÃO DE PROBLEMAS a. Tipos de Problemas b. Espaço de Estados face a Redução de Problemas c. Heurísticas d. Formulação Construtiva face a Formulação Reparativa e. Satisfação, Optimização e Semi-Optimização f. Geração-e-Teste face a Divisão-e-Poda g. Procura Sistemática face a Procura Local 5. ESTRATÉGIAS BÁSICAS DE PROCURA HEURÍSTICA a. Procura Local (Trepar-a-Colina) b. Procura Sistemática Cega (Estratégias LIFO e FIFO e Procura em Grafos AND/OR) c. Procura Sistemática Informada (Procura Melhor-Primeiro, BF, GBF e GBF*) d. Estratégias Melhor-Primeiro Especializadas (Z*, A*, AO e AO*) e. Estratégias Híbridas 6. ESTRATÉGIAS AVANÇADAS DE PROCURA HEURÍSTICA a. Estratégias de Memoria Limitada i) Estratégias Minimalistas (IDS Uni- e Bi-direccional, IDA*, RBF e IBS) ii) Estratégias Maximalistas (SMA*) b. Estratégias de Tempo Limitado i) Estratégias Quase-Óptimas (A* com pesos estáticos e com pesos dinâmicos, A*-epsilon) ii) Estratégias Avançadas de Procura Local – Meta-Heurísticas (Versões melhoradas do Trepar-a-Colina, Têmpera Simulada, Procura Local em Banda Determinística e Estocástica, Algoritmos Genéticos) iii) Estratégias de Procura Parcial Não-Sistemáticas • Sondagem Iterativa (1-samp, ISS, i-samp, r-samp) • Retrocesso Limitado e Multi-Sondagem (BBS) • Profundidade-Primeiro com Recomeços (RDFS) • Largura Incremental Estocástica (SIB) iv) Estratégias de Discrepância Limitada (LDS, ILDS e DDS) 7. PROBLEMAS DE SATISFAÇÃO DE RESTRIÇÕES a. Formalização i) Grafos de restrições ii) Formulação incremental e de estado-completo iii) Tipos de PSRs iv) Restrições unárias, binárias e globais v) Restrições absolutas e de preferência b. Procura de Retrocesso i) Ordenação de variáveis e valores ii) Propagação de restrições iii) Forward checking: Antecipação iv) Restrições especiais v) Retrocesso inteligente c. Procura Local para PSRs d. Estrutura de Problemas 8. PROCURA COM OUTRAS FONTES DE CONHECIMENTO a. Sub-Objectivos i) Independentes ii) Sequenciáveis iii) Insequenciáveis iv) Sequenciáveis-por-Bloco b. Macro-Operadores i) Sub-Objectivos Insequenciáveis ii) Espaços de Estados Arbitrários com um único Estado Objectivo iii) Espaços de Estados Arbitrários c. Abstracção i) Modelo de Subconjunto e de Região ii) Nível Singular de Abstracção iii) Níveis Múltiplos de Abstracção PARTE 2 – PLANEAMENTO 1. PLANEAMENTO CLÁSSICO a. Da Resolução de Problemas ao Planeamento b. Planeamento em Cálculo Situacional c. O Problema do Planeamento i. Linguagem de problemas de planeamento ii. Representação de estados, objectivos e acções iii. Pré-condições e Efeitos iv. Expressividade e extensões d. Planear com procura num espaço de estados i. Planeamento de Ordem-Total ii. Procura Progressiva e Regressiva iii. Heurísticas e. Planear com procura num espaço de planos i. Planeamento de Ordem-Parcial ii. Princípio do Compromisso Mínimo iii. Linearizações iv. Componentes de um Plano de Ordem-Parcial v. Planeamento com variáveis desligadas f. Grafos de Planeamento i. Grafos de planeamento para estimativa heurística ii. Algoritmo GRAPHPLAN iii. Terminação do GRAPHPLAN 2. PLANEAMENTO E ACÇÃO NO MUNDO REAL a. Tempo, Cronogramas e Recursos i. Representar restrições temporais e de recursos ii. Resolver problemas de calendarização b. Planeamento Hierárquico i. Acções de alto-nível ii. Procurar soluções primitivas iii. Procurar soluções abstractas c. Planeamento e Acção em Domínios Não-Determinísticos i. Planeamento sem sensores ii. Planeamento com contingências iii. Planeamento em Tempo-Real d. Planeamento Multi-Agente i. Planeamento com acções múltiplas simultâneas ii. Cooperação e Coordenação