A conflict-directed approach to chance-constrained mixed logical linear programming & nbsp;

Resistance to the adoption of autonomous systems comes in part from the perceived unreliability of the systems. The concerns can be addressed by deploying decision making algorithms that defines what it means to fail, and look for plans with the highest reward while limiting the probability of failure. This chance-constrained approach thus explicitly imposes a set of constraints that must be satisfied for success, and provides 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 autonomous underwater vehicle path planning, to network routing under uncertainty. While naive encodings of CC-MLLPs can be solved with generalised solvers, the solution time may be unreasonable. In this work, we study architectures to speed up solutions by partitioning CC-MLLPs into the discrete and continuous portions. In order to provide faster solutions, we investigate methods for speeding up the solutions to the continuous chance constrained linear programs. Further, by exploiting the new solution methods, we 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.& COPY; 2023 Published by Elsevier B.V.

Automated summary

Resistance to the adoption of autonomous systems is addressed by deploying decision making algorithms to define failure and find plans with the highest reward while limiting the probability of failure. This can be achieved using a chance-constrained mixed logical-linear program (CC-MLLP) formulation, which allows for the specification of linear and logical constraints with probabilistic continuous variables. By partitioning CC-MLLPs into discrete and continuous portions and developing faster solution methods for the continuous chance constrained linear programs, the resulting algorithm achieves a 10 times speed up over prior approaches on autonomous path planning benchmarks.