Salta al contenuto principale della pagina

OPTIMISATION TECHNIQUES

CODICE 86733
ANNO ACCADEMICO 2021/2022
CFU
  • 5 cfu al 1° anno di 10635 ROBOTICS ENGINEERING (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

    Commissione d'esame

    MARCELLO SANGUINETI (Presidente)

    MAURO GAGGERO

    DANILO MACCIO'

    MASSIMO PAOLUCCI (Presidente Supplente)

    LEZIONI

    Orari delle lezioni

    L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.

    ESAMI

    MODALITA' D'ESAME

    Scritto, se sarà possibile fare esami in presenza. Altrimenti, il docente deciderà se l'esame su Teams sarà orale o scritto.

    Calendario appelli

    Data Ora Luogo Tipologia Note
    11/01/2022 08:00 GENOVA Scritto
    03/02/2022 08:00 GENOVA Scritto
    30/05/2022 09:00 GENOVA Scritto
    28/06/2022 08:00 GENOVA Scritto
    14/09/2022 08:00 GENOVA Scritto