OPTIMISATION TECHNIQUES

OPTIMISATION TECHNIQUES

_
iten
Codice
86733
ANNO ACCADEMICO
2020/2021
CFU
5 cfu al 1° anno di 10635 ROBOTICS ENGINEERING (LM-32) GENOVA
SETTORE SCIENTIFICO DISCIPLINARE
MAT/09
LINGUA
Inglese
SEDE
GENOVA (ROBOTICS ENGINEERING )
periodo
1° Semestre
materiale didattico

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.

Modalità 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

Ricevimento: Su appuntamento.

Commissione d'esame

MARCELLO SANGUINETI (Presidente)

FEDERICA BRIATA

MASSIMO PAOLUCCI

DANILO MACCIO'

MAURO GAGGERO

LEZIONI

Modalità didattiche

Lezioni frontali ed esercitazioni

INIZIO LEZIONI

21 settembre 2020.

ESAMI

Modalità d'esame

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