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.
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
Agli studenti verrà insegnato a:
Algebra lineare. Calcolo vettoriale e matriciale. Fondamenti di Analisi Matematica e di Geometria.
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.
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)
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.
Dispense preparate dal Docente e disponibili in formato elettronico.
Ricevimento: Su appuntamento
MARCELLO SANGUINETI (Presidente)
MAURO GAGGERO
MASSIMO PAOLUCCI (Presidente Supplente)
DANILO MACCIO' (Supplente)
ELENA TANFANI (Supplente)
https://easyacademy.unige.it/portalestudenti/index.php?view=easycourse&_lang=it&include=corso
Scritto.
Esercizi e domande sui principali concetti esposti e sulle applicazioni illustrate durante il Corso.
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.
