Guaranteed safe autonomy: Probabilistic and game-theoretic approaches

This thesis develops randomized and game-theoretic approaches to safely regulate control systems under environmental uncertainty, providing computationally efficient alternatives to exact deterministic methods. This approach offers suboptimal solutions with high probability while significantly reducing computational complexity. The four topics under consideration are (i) minimax optimization, (ii) multi-agent coverage and reachable set characterization, (iii) controlled invariant sets under disturbances, and (iv) minimax policy iteration. All topics relate to the control of systems to provide worst case guarantees in the presence of disturbances. Minimax optimization: The thesis presents a scenario-based, risk-sensitive optimization algorithm designed to approximate minimax solutions with high confidence. The algorithm first samples the maximizing variable and then solves a sample-based risk-sensitive optimization problem. The analysis establishes the required risk-sensitivity levels and sample complexities to satisfy predefined tolerances. Through applications in zero-sum games and model predictive control, the examples highlight the impact of sampling distributions on solution accuracy. Multi-agent coverage and reachable set characterization: The thesis combines game-theoretic learning with concepts from rapidly exploring random trees (RRT) in robotics for multi-agent coverage. The approach, supported by an analysis of related diffusion dynamics, ensures asymptotic probabilistic optimal coverage while improving transient performance, particularly in large-agent settings. Leveraging a link between coverage and reachable set characterization, a modified algorithm is applied to approximate, with probabilistic guarantees, reachable sets, i.e., all states that can be reached by a dynamical system under exogenous disturbances. Controlled invariant sets under disturbances: Existing approaches to design controllers for guaranteed safe state evolution for linear systems run into computational challenges due to linear programs with an increasing large number of constraints. The thesis tackles redundant constraint elimination through monotone submodular maximization. The algorithm uses a sample-based approximation of the infeasible region to develop a greedy-inspired sampling algorithm that selects a subset of constraints to effectively represent the feasible region. The analysis provides the sample complexity for the number of points required in the primal space to ensure the selection of all essential constraints with high probability. Targeted sampling techniques, such as hit-and-run sampling, further enhance scalability in high-dimensional spaces. The application to controlled invariant sets achieves substantial reductions in computational complexity while maintaining accuracy. Minimax policy iteration: The thesis examines minimax policy iteration for minimax infinite-horizon discounted cost problems. First, it is shown that policy evaluation can be represented as linear program. A combination of using basis functions to represent a policy’s cost and utilizing scenario-based sampling reduces the complexity of the associated linear program. The analysis provides the sample complexity of determining the number of sample constraints needed to capture all supporting constraints with high probability and establishes approximation error bounds for the linear programming-based policy evaluation. The analysis focuses on the accuracy of minimax policy iteration under deterministic error bounds in both the policy evaluation and improvement steps.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Systems & Entrepreneurial Engr

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Rajab, Fat-Hy Omar

Contributors dc:contributor

• Shamma, Jeff S
• Stipanovic, Dusan M
• Dullerud, Geir E
• Etesami, Seyed

• Safe Autonomy
• Multi-agent coverage
• Reachable sets estimation
• Robust control invariant set
• Robust control
• Game-theoretic approaches
• Randomized approaches
• Scenario optimization
• Minimax optimization
• Minimax dynamic programming.

Statement dc:rights

• Copyright 2025 Fat-Hy Omar Rajab

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129205

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129205