CODICE 86733 ANNO ACCADEMICO 2019/2020 CFU 5 cfu anno 1 ROBOTICS ENGINEERING 10635 (LM-32) - GENOVA SETTORE SCIENTIFICO DISCIPLINARE MAT/09 LINGUA Inglese SEDE GENOVA PERIODO 1° Semestre MATERIALE DIDATTICO AULAWEB PRESENTAZIONE Il Corso presenta modelli e metodi di ottimizzazione utilizzabili per la soluzione di problemi decisionali, con particolare enfasi su modelli e problemi che originano nel campo della Robotica. Si articola nei temi fondamentali della modellazione di problemi, dello studio della trattabilità computazionale e della risoluzione tramite algoritmi implementabili su un calcolatore. La materia viene presentata nei suoi aspetti metodologici, teorici ed applicativi. OBIETTIVI E CONTENUTI OBIETTIVI FORMATIVI The lecture presents different theoretical and computational aspects of a wide range of optimization methods for solving a variety of problems in engineering and robotics. OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO Agli studenti verrà insegnato a: interpretare e modellare un processo decisionale nei termini di un problema di ottimizzazione, individuando cioè le variabili decisionali, la funzione di costo da minimizzare (o la cifra di merito da massimizzare) e i vincoli; inquadrare il problema nella gamma dei problemi considerati “canonici” (lineari/non lineari, discreti/continui, deterministici/stocastici, statici/dinamici, ecc.); realizzare il "matching" tra l’algoritmo risolutivo (da scegliere tra quelli esistenti o da progettare) e un adeguato supporto software di elaborazione. PREREQUISITI Algebra lineare. Calcolo vettoriale e matriciale. Fondamenti di Analisi Matematica e di Geometria. MODALITA' DIDATTICHE Lezioni frontali ed esercitazioni PROGRAMMA/CONTENUTO Introduzione al Corso. L’ottimizzazione e la ricerca operativa per la robotica Modelli di ottimizzazione: continua/discreta, linear/non-lineare, deterministica/stocastica, a obiettivo singolo/multiobiettivo, ecc. Funzione obiettivo, vincoli e variabili decisionali. Dalla formulazione matematica alle metodologie di risoluzione, fino agli algoritmi implementabili su un supporto di calcolo. Il ruolo della Ricerca Operativa nella Robotica e nell’Ingegneria del Controllo. Programmazione lineare a variabili reali (PL) Esempio introduttivo: un problema di PL nella Robotica. Formalizzazione dei problemi di PL e altri esempi di interesse nelle applicazioni. Geometria della PL. Poliedro dei vincoli e sue proprietà. Esempio introduttivo di risoluzione grafica. Approccio algebrico per la soluzione di problemi di PL. Forma standard di un PL e riduzione a forma standard. Variabili di slack e di surplus. Matrici di base e soluzioni di base. Teorema fondamentale della programmazione lineare. Algoritmo del simplesso, sua inizializzazione e sua implementazione sul tableau. Programmazione matematica lineare a variabili intere (PLI) Esempio introduttivo: un problema di PLI nella Robotica. Formalizzazione dei problemi di PL e altri esempi di interesse nelle applicazioni. Rilassamento di un PLI. Algoritmo del branch and bound. Programmazione non lineare (PNL) non vincolata Esempio introduttivo: un problema di PNL nella Robotica. Formalizzazione dei problemi di PNL e altri esempi di interesse nelle applicazioni. PNL non-vincolata: condizioni necessarie e condizioni sufficienti di ottimalità; direzione di discesa e passo di discesa; algoritmi del gradiente e di Newton-Raphson; velocità di convergenza. PNL vincolata: cenni all’approccio Lagrangiano; metodo delle funzioni di penalità; metodo delle funzioni barriera. Ottimizzazione su grafi Esempio introduttivo: un problema di ottimizzazione su grafi nella Robotica. Formalizzazione dei problemi su grafi e altri esempi di interesse nelle applicazioni. Rappresentazione dei grafi. Il problema dell’albero ricoprente di costo minimo (SST: “Shortest Spanning Tree”). Algoritmi di Kruskal e didi Prim-Dijkstra per la risoluzione del problema SST. Il problema del percorso minimo (SP: “Shortest Path”). Algoritmi di Dijkstra, Bellman-Ford e Floyd-Wharshall per la risoluzione del problema SP. Ottimizzazione a stadi e programmazione dinamica Esempio introduttivo: un problema di ottimizzazione a stadi nella Robotica. Formalizzazione dei problemi di ottimizzazione a stadi e altri esempi di interesse nelle applicazioni. Fase backward e fase forward. Principio di ottimalità. Le equazioni di Bellman nel contesto deterministico. Estensione al contesto stocastico. La “maledizione della dimensionalità”. Dai componenti alla visione d’insieme: modelli, metodologie e tecniche di Ricerca Operativa per l’ottimizzazione di sistemi robotici Scelta di un modello di Ricerca Operativa per l’ottimizzazione di un sistema robotico. Tecniche e metodologie per la fase 1: pianificazione di un sistema robotico. Tecniche e metodologie per la fase 2: design di un sistema robotico. Tecniche e metodologie per la fase 3: operatività di un sistema robotico. Applicativi software per l’ottimizzazione Principali software per la risoluzione al calcolatore di problemi di PL, PLI e PNL. Introduzione a Excel, Lingo e Matlab per l’ottimizzazione. Esempi di utilizzo dei software. TESTI/BIBLIOGRAFIA Dispense preparate dal Docente e disponibili in formato elettronico. DOCENTI E COMMISSIONI MARCELLO SANGUINETI Ricevimento: Su appuntamento Commissione d'esame MARCELLO SANGUINETI (Presidente) RENATO UGO RAFFAELE ZACCARIA (Presidente) MAURO GAGGERO DANILO MACCIO' MASSIMO PAOLUCCI LEZIONI INIZIO LEZIONI 23 settembre 2019 Orari delle lezioni L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy ESAMI MODALITA' D'ESAME Scritto Calendario appelli Data appello Orario Luogo Tipologia Note 06/02/2020 09:00 GENOVA Scritto 09/06/2020 09:00 GENOVA Scritto 30/06/2020 09:00 GENOVA Scritto 10/09/2020 09:00 GENOVA Scritto