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

INIZIO LEZIONI

https://corsi.unige.it/10635/p/studenti-orario

Orari delle lezioni

L'orario di questo insegnamento è consultabile all'indirizzo: Portale 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