| Summary: | Resistance to adoption of autonomous systems in comes in part from the perceived unreliability of the systems. The concerns can be addressed by deploying decision making algorithms that operate in the presence of uncertainty.
The default approach is to optimise expected utility given probabilistic descriptions of uncertainty. However, such approaches become problematic when the cost of failure is difficult to define, for example when imposing constraints on remote science missions. Without well-defined costs of failure, it is difficult to balance the risks of failure against the rewards of success. This motivates an alternative approach, in which we define what it means to fail, and look for plans with the highest reward while limiting the probability of failure.
The alternative approach thus explicitly imposes a set of constraints required for success, and provide upper-bounds on the probability of violating such constraints. A chance-constrained mixed logical-linear program (CC-MLLP) is a natural formulation, allowing for the specification of linear and logical constraints, with probabilistic continuous variables. The formalism can be used to describe problems ranging from automonous underwater vehicle path planning, to network routing under uncertainty.
My thesis addresses shortcomings in current approaches to CC-MLLP. In particular, I focus on the problem of computation speed for solving CC-MLLPs, and the problem of accurate uncertainty representation.
While naive encodings of CC-MLLPs can be solved with generalised solvers, the solution time may be unreasonable. In this thesis, I study architectures to speed up solutions by partitioning CC-MLLPs into the discrete and continuous portions.
In order to provide faster solutions, I investigate methods for speeding up the solutions to the continuous chance-constrained linear programs. Further, by exploiting the new solution methods, I develop techniques for guiding the discrete decision making portion of the problem. The resulting algorithm achieves 10 times speed up over prior approaches on autonomous path planning benchmarks.
Lastly, current chance-constrained approaches require distributional descriptions of uncertainty. In this thesis, I consider the problem of deriving uncertainty bounds from data, which cover a required proportion of outcomes with a quantifiable amount of confidence. In particular, I provide bounds for real world scenarios which feature a finite number of executions. This is demonstrated on MBTA Red Line subway schedules.
|
|---|