Mixed-Integer Programming

• Detto anche: MIP, MILP, MIQP, MICP
• Categoria: Planning & manipulation › Trajectory optimisation
• Tag: optimization, integer-programming, motion-planning, task-allocation, hybrid-systems

Ottimizzazione in cui alcune variabili devono assumere valori interi, spesso 0 o 1, permettendo a un unico problema di combinare scelte discrete e grandezze continue.

Definizione

Programmazione intera mista (mixed-integer programming, MIP) è l'ottimizzazione su un insieme di variabili continue e di variabili vincolate a valori interi, il più delle volte variabili binarie che assumono il valore 0 o 1. Le variabili binarie codificano decisioni discrete: quale regione attraversa un percorso, quale piede appoggia per primo, se un contatto è attivo, quale robot si occupa di quale compito. Le variabili continue rappresentano il resto, come posizioni, velocità e forze. Le classi comuni prendono il nome dalla forma del problema rimanente: programmi lineari interi misti (MILP), programmi quadratici interi misti (MIQP) e, più in generale, programmi convessi interi misti (MICP).

Questi problemi sono NP-difficili in generale, ma i solver moderni gestiscono bene molte istanze pratiche. Usano il branch and bound: risolvere il rilassamento continuo eliminando i requisiti di interezza, scegliere una variabile risultata frazionaria, dividere in due sottoproblemi che la forzano verso il basso o verso l'alto, e potare qualsiasi ramo il cui rilassamento sia già peggiore della migliore soluzione intera trovata. I piani di taglio stringono il rilassamento lungo il percorso. Solver commerciali come Gurobi e CPLEX e open source come SCIP, HiGHS e CBC implementano questi metodi.

Il modo in cui un problema è scritto conta quanto il solver usato. Le condizioni logiche sono spesso codificate con vincoli big-M, che attivano o disattivano un vincolo con una variabile binaria e una costante grande; una costante troppo grande indebolisce il rilassamento e causa problemi numerici. Le formulazioni con rilassamenti stretti si risolvono molto più in fretta, ed è uno dei motivi per cui approcci strutturati come i grafi di insiemi convessi sono progettati in modo che il loro rilassamento sia vicino al problema reale.

Perché è importante

Molti problemi di pianificazione robotica sono in parte discreti: passare a sinistra o a destra di un ostacolo, scegliere una sequenza di contatti, assegnare compiti. La programmazione intera mista gestisce queste scelte in modo esatto all'interno di un'unica ottimizzazione, spesso con un limite su quanto la risposta disti dall'ottimo, invece di affidarsi a euristiche fatte a mano o al campionamento.

Applicazioni principali

• Pianificazione degli appoggi e delle sequenze di contatto per robot con zampe
• Pianificazione di traiettorie attraverso regioni convesse per droni e manipolatori
• Assegnazione e schedulazione dei compiti per flotte di robot
• Controllo predittivo basato su modello ibrido con modi discreti
• Pianificazione dei compiti e pianificazione del movimento con scelte discrete delle azioni

In pratica

Un team che pianifica gli appoggi di un umanoide su pietre di guado rappresenta la superficie calpestabile di ogni pietra come un poligono convesso. Per ciascuno dei passi successivi aggiunge variabili binarie che selezionano su quale poligono appoggia il piede, con vincoli attivi solo per il poligono scelto, più variabili continue per le posizioni del piede e limiti sulla lunghezza del passo e sulla rotazione. Il costo premia l'avanzamento verso l'obiettivo e penalizza i passi scomodi. Un solver intero misto restituisce una sequenza di passi, di solito entro un limite di tempo fissato per la ripianificazione, insieme al gap tra la migliore soluzione trovata e il miglior limite. Se i tempi di soluzione sono troppo lunghi, il team riduce il numero di passi pianificati alla volta, stringe i valori di big-M o fa un warm start dal piano precedente.

Idee sbagliate comuni

• I programmi interi misti sono sempre troppo lenti per la robotica — problemi piccoli e ben formulati si possono risolvere abbastanza in fretta per la ripianificazione online
• Arrotondare il rilassamento continuo dà la soluzione intera ottima — l'arrotondamento può essere non ammissibile o lontano dall'ottimo, a meno che il rilassamento non sia stretto
• Qualsiasi valore grande di M va bene nei vincoli big-M — valori eccessivamente grandi indeboliscono il rilassamento e causano difficoltà numeriche
• Un solver che si ferma al limite di tempo ha fallito — di solito restituisce la migliore soluzione trovata fino a quel momento e un gap di ottimalità che dice quanto è buona

Chi dovrebbe saperlo

• Ingegneri di pianificazione del movimento e degli appoggi
• Sviluppatori di schedulazione di flotte e allocazione dei compiti
• Ricercatori di controllo basato sull'ottimizzazione
• Studenti di robotica che studiano l'ottimizzazione

Tecnologie correlate

• Branch and Bound
• Gurobi
• SCIP
• HiGHS
• Programmazione lineare (Linear Programming)
• Ottimizzazione convessa (Convex Optimization)

Termini correlati

• Graph of Convex Sets
• Task and Motion Planning
• Model Predictive Control
• Motion Planning
• Trajectory Planning
• Multi-Agent Path Finding

Progetti correlati

• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
• GTSAM: Factor-graph optimization library powering many modern SLAM backends
• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• PyPose: PyTorch library for differentiable robotics with deep learning and Lie group optimization

Video

• Mixed Integer Linear Programming (MILP) Tutorial: APMonitor.com