Programa

Procura e Planeamento

Mestrado Bolonha em Engenharia Informática e de Computadores - Alameda

Mestrado Bolonha em Engenharia Informática e de Computadores - Taguspark

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