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.

Le lezioni sono organizzate in i) metodologia e ii) "case-study" provenienti da applicazioni "real-world". Esercizi addizionali e utilizzo di strumenti software sono presentati durante ore di esercitazione. 

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

The Course presents methodological and computational aspects of optimization methods for the solution of a variety of problems, with particular attention to models and tasks arising in Robotics Engineering. Algorithms and software tools are illustrated. The lectures are structured according to the basic topics of problem modelling, its tractability, its solution by means of algorithms that can be implemented on computers, and related software tools. Several case-studies from Robotics are considered and solved by means of the described algorithms and available software

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.

Si consigliano gli studenti lavoratori e gli studenti con certificazione di DSA, di disabilità o di altri bisogni educativi speciali di contattare il docente all’inizio del corso per concordare modalità didattiche e d’esame che, nel rispetto degli obiettivi dell’insegnamento, tengano conto delle modalità di apprendimento individuali.
 

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.

Programmazione lineare a variabili reali (PL)

Formalizzazione dei problemi di PL ed esempi applicativi.

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.

Case-study: un problema di PL nella Robotica.

Programmazione matematica lineare a variabili intere (PLI)

Formalizzazione dei problemi di PL ed esempi applicativi.

Rilassamento di un PLI.

Algoritmo del branch and bound.

Case-study: un problema di PLI nella Robotica.

Programmazione non lineare (PNL) non vincolata

Formalizzazione dei problemi di PNL ed esempi applicativi

PNL non-vincolata:

             condizioni necessarie e condizioni sufficienti di ottimalità;

             direzione di discesa, passo di discesa, velocità di convergenza;

             algoritmi di Nelder-Mead, del gradiente e di Newton-Raphson;

PNL vincolata:

             metodo delle funzioni di penalità;

             metodo delle funzioni barriera.

Case-study: un problema di PNL nella Robotica.

Ottimizzazione su grafi

Formalizzazione dei problemi su grafi ed esempi applicativi.

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 e di Bellman-Ford per la risoluzione del problema SP.

Case-study: un problema di ottimizzazione su grafi nella Robotica.

Ottimizzazione a stadi e programmazione dinamica 

Formalizzazione dei problemi di ottimizzazione a stadi ed esempi applicativi.

Fase backward e fase forward.

Principio di ottimalità. Le equazioni di Bellman nel contesto deterministico.

Cenni all'estensione al contesto stocastico.

La “maledizione della dimensionalità”.

Case-study: un problema di ottimizzazione a stadi nella Robotica.

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.

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

ELENA TANFANI

MASSIMO PAOLUCCI (Presidente Supplente)

LEZIONI

INIZIO LEZIONI

https://easyacademy.unige.it/portalestudenti/index.php?view=easycourse&_lang=it&include=corso

Orari delle lezioni

L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy

ESAMI

MODALITA' D'ESAME

Scritto.

Esercizi e domande sui principali concetti esposti e sulle applicazioni illustrate durante il Corso.

MODALITA' DI ACCERTAMENTO

Comprensione dei concetti esposti durante il Corso.

Capacità di:

- interpretare e modellare un processo decisionale nei termini di un problema di ottimizzazione, con particolare riguardo a processi decisionali nella Robotica;

- inquadrare il problema nella gamma dei problemi considerati “canonici” (lineari/non lineari, discreti/continui, deterministici/stocastici, statici/dinamici, ecc.);

- scegliere e/o sviluppare un algoritmo risolutivo che implementi un'opportuna tecnica di ottimizzazione, con particolare riferimento a problemi che si presentano in campo robotico.

Calendario appelli