Optimisation and computational optimal control via local pursuit

Abstract

This thesis develops a family of algorithms for solving a class of non-autonomous optimal control problems in which the running cost and the set of admissible states vary with time. Such problems arise when physical systems operate in non-stationary dynamic environments which contain moving, deforming obstacles and whose geometry changes over time. When sensor noise is present in such settings, no ‘off-the-shelf’ method is available; in the noise-free case, the only known approach presumes complete knowledge of the environment’s future evolution. We introduce methods grounded in the idea of local pursuit, inspired by behaviors observed in biological systems such as ants foraging. We adopt a multi-agent formulation in which agents iteratively solve a sequence of optimisation problems by ‘pursuing’ one another, relying exclusively on local information and without imposing restrictive structural assumptions on their dynamics, constraints, or cost functions. This approach results in three algorithms, all of which generate control inputs that produce a trajectory guaranteed to be locally optimal, while respecting state and input constraints. The algorithms form a progression of increasing generality in terms of the environments they can be applied in. We first extend prior local pursuit approaches from static environments to noise-free non-stationary ones, preserving convergence guarantees and matching the quality of the ‘full-knowledge’ benchmark approach at substantially lower computational cost. Subsequently, we account for noise in both agent and obstacle observations, where convergence guarantees are retained under mild problem-specific conditions. Finally, we restore convergence guarantees where those conditions are violated, at a tractable computational cost. The performance of all three algorithms is demonstrated in extensive numerical simulations.

Η παρούσα διατριβή αναπτύσσει μια οικογένεια αλγορίθμων για την επίλυση μιας κλάσης μη αυτόνομων προβλημάτων βέλτιστου ελέγχου, στα οποία το τρέχον κόστος και το σύνολο των αποδεκτών καταστάσεων μεταβάλλονται με τον χρόνο. Τέτοια προβλήματα ανακύπτουν όταν φυσικά συστήματα λειτουργούν σε μη στάσιμα δυναμικά περιβάλλοντα, τα οποία περιέχουν κινούμενα και παραμορφούμενα εμπόδια και των οποίων η γεωμετρία μεταβάλλεται με την πάροδο του χρόνου. Όταν σε τέτοιες συνθήκες υπάρχει θόρυβος αισθητήρων, δεν διατίθεται καμία «έτοιμη» μέθοδος· στην περίπτωση χωρίς θόρυβο, η μόνη γνωστή προσέγγιση προϋποθέτει πλήρη γνώση της μελλοντικής εξέλιξης του περιβάλλοντος. Εισάγουμε μεθόδους που βασίζονται στην ιδέα της τοπικής καταδίωξης (local pursuit), εμπνευσμένες από συμπεριφορές που παρατηρούνται σε βιολογικά συστήματα, όπως τα μυρμήγκια κατά την αναζήτηση τροφής. Υιοθετούμε μια πολυπρακτορική διατύπωση, στην οποία οι πράκτορες επιλύουν επαναληπτικά μια ακολουθία προβλημάτων βελτιστοποίησης «καταδιώκοντας» ο ένας τον άλλον, βασιζόμενοι αποκλειστικά σε τοπική πληροφορία και χωρίς να επιβάλλονται περιοριστικές δομικές υποθέσεις για τη δυναμική, τους περιορισμούς ή τις συναρτήσεις κόστους τους. Η προσέγγιση αυτή οδηγεί σε τρεις αλγορίθμους, οι οποίοι παράγουν όλοι εισόδους ελέγχου που δίνουν τροχιά εγγυημένα τοπικά βέλτιστη, τηρώντας παράλληλα τους περιορισμούς κατάστασης και εισόδου. Οι αλγόριθμοι συνιστούν μια διαδοχή αυξανόμενης γενικότητας ως προς τα περιβάλλοντα στα οποία μπορούν να εφαρμοστούν. Αρχικά, επεκτείνουμε προγενέστερες προσεγγίσεις τοπικής καταδίωξης από στατικά περιβάλλοντα σε μη στάσιμα περιβάλλοντα χωρίς θόρυβο, διατηρώντας τις εγγυήσεις σύγκλισης και επιτυγχάνοντας ποιότητα αντίστοιχη με εκείνη της προσέγγισης αναφοράς «πλήρους γνώσης», με σημαντικά χαμηλότερο υπολογιστικό κόστος. Στη συνέχεια, λαμβάνουμε υπόψη τον θόρυβο στις παρατηρήσεις τόσο των πρακτόρων όσο και των εμποδίων, όπου οι εγγυήσεις σύγκλισης διατηρούνται υπό ήπιες συνθήκες που εξαρτώνται από το εκάστοτε πρόβλημα. Τέλος, αποκαθιστούμε τις εγγυήσεις σύγκλισης στις περιπτώσεις όπου οι συνθήκες αυτές παραβιάζονται, με διαχειρίσιμο υπολογιστικό κόστος. Η επίδοση και των τριών αλγορίθμων επιδεικνύεται μέσω εκτενών αριθμητικών προσομοιώσεων.