Geometric Conditions for Lossless Convexification in Linear Optimal Control with Discrete-Valued Inputs

Titolo

Condizioni Geometriche per la Convessificazione Senza Perdita nel Controllo Ottimo Lineare con Input a Valori Discreti

1. Il Problema

Il controllo ottimo di sistemi fisici che utilizzano attuatori a valori discreti (es. sistemi on-off o con livelli di magnitudine finiti) è intrinsecamente complesso. Questi problemi portano a Programmi a Numeri Interi Misti (MIP), che sono computazionalmente intrattabili per applicazioni in tempo reale e critiche per la sicurezza a causa della loro natura non convessa e della crescita esponenziale del tempo di calcolo rispetto al numero di variabili decisionali.

Metodi esistenti come le tecniche di apprendimento automatico (per il "warm-start" degli solver MIP) o i metodi di omotopia offrono accelerazioni o approssimazioni, ma non garantiscono formalmente l'ottimalità o la convergenza. L'obiettivo di questo lavoro è risolvere il problema del controllo ottimo per sistemi lineari con input discreti trasformandolo in un problema convesso risolvibile in modo efficiente, mantenendo la garanzia di ottimalità (convessificazione senza perdita).

2. Metodologia

Gli autori propongono un quadro teorico che estende i risultati esistenti sulla convessificazione senza perdita. La metodologia si articola nei seguenti passaggi chiave:

• Formulazione del Problema: Il problema originale è formulato in forma di Lagrange, con una funzione di costo che minimizza l'energia di controllo (norma $L_1$), tipica per il risparmio di carburante nei veicoli spaziali. L'insieme degli input $U$ è un insieme finito e disconnesso.
• Trasformazione Epigrafica: Per applicare la convessificazione, il problema in forma di Lagrange viene convertito in un problema in forma di Mayer. Viene introdotta una variabile di stato aggiuntiva ($x_c$) che integra la funzione di costo nel tempo, trasformando il funzionale di costo in un costo terminale.
• Rilassamento Convesso: L'insieme degli input discreti $U$ viene rilassato nel suo inviluppo convesso ($\text{conv}(U)$). Viene definito un insieme aumentato $\tilde{U}_e$ che combina l'inviluppo convesso degli input e l'epigrafo della funzione di costo.
• Condizioni Geometriche e Normalità:
  • Viene introdotta l'ipotesi (A1): i vertici dell'insieme aumentato rilassato $\tilde{U}_e$ devono coincidere con i punti originali dell'insieme discreto $U$.
  • Viene dimostrato che la normalità forte del sistema originale $(A, B)$ rispetto a $\text{conv}(U)$ implica la normalità forte del sistema aumentato $(\hat{A}, \hat{B})$ rispetto a $\tilde{U}_e$.
• Teorema Principale: Sotto le condizioni di normalità forte e la validità dell'ipotesi geometrica (A1), la soluzione del problema rilassato (convesso) cade esattamente sui vertici dell'insieme rilassato. Di conseguenza, la soluzione del problema convesso è identica alla soluzione del problema originale non convesso a valori interi, rendendo la convessificazione "senza perdita".

3. Contributi Chiave

1. Estensione alla Forma di Lagrange: Il lavoro estende le tecniche di convessificazione senza perdita, precedentemente limitate alla forma di Mayer, ai problemi in forma di Lagrange (come il controllo a consumo minimo di carburante), dimostrando che la proprietà di normalità del sistema viene preservata durante la trasformazione epigrafica.
2. Condizioni Geometriche Sufficienti: Identifica condizioni geometriche precise sull'insieme degli input e sulla funzione di costo (in particolare la natura poli-edrale convessa) che garantiscono che il rilassamento convesso restituisca una soluzione discreta.
3. Eliminazione dell'Ottimizzazione MIP: Dimostra che è possibile risolvere problemi di controllo ottimo con input discreti utilizzando esclusivamente solver per programmi convessi (CP), evitando la complessità computazionale dei MIP.

4. Risultati Numerici

I risultati sono stati validati attraverso simulazioni numeriche su un caso di studio di rendezvous orbitale per un satellite in orbita terrestre bassa (LEO) con attuatori a gas freddo (thruster discreti).

• Validazione della Discretezza: Le simulazioni mostrano che la soluzione ottenuta dal problema convesso rilassato produce traiettorie di controllo che aderiscono perfettamente all'insieme discreto originale $U = \{-u_{max}, 0, u_{max}\}^3$. La distanza media dalla soluzione discreta è risultata trascurabile ($\bar{d}(u) \approx 0.002$).
• Performance in Tempo Reale:
  • Sono state eseguite simulazioni Monte Carlo con 1000 condizioni iniziali diverse.
  • Il tempo di calcolo medio è stato di 0.083 secondi (mediana 0.069 s), ben al di sotto del requisito di aggiornamento di 1 secondo stabilito dalle linee guida NASA (progetto SPLICE) per il controllo di veicoli spaziali.
  • L'aumento della risoluzione della griglia temporale migliora la precisione della discretizzazione, ma mantiene i tempi di calcolo entro limiti accettabili per applicazioni in tempo reale.

5. Significato e Implicazioni

Questo lavoro è significativo per l'ingegneria aerospaziale e il controllo robotico perché:

• Abilita la generazione di traiettorie ottimali in termini di carburante per veicoli spaziali con attuatori discreti in tempo reale, superando i limiti degli attuali algoritmi basati su funzioni di costo quadratiche che non minimizzano direttamente il consumo di propellente.
• Fornisce garanzie formali di ottimalità e convergenza, a differenza dei metodi euristici o basati su apprendimento automatico.
• Dimostra la fattibilità pratica di implementare strategie di controllo avanzate su hardware con risorse limitate (es. computer di bordo di piccoli satelliti), aprendo la strada a missioni autonome più complesse e sicure.

In conclusione, il documento stabilisce un ponte teorico e pratico tra la teoria del controllo ottimo non convesso e l'implementazione in tempo reale, dimostrando che, sotto specifiche condizioni geometriche, i problemi complessi a numeri interi possono essere risolti efficientemente come problemi convessi senza sacrificare la qualità della soluzione.