Doctoral Thesis: Risk-Bounded Scheduling of Temporal Plans

Andrew Wang

Abstract:

When plans have deadlines and/or require temporal coordination among activities, we must decide when to schedule and dispatch those activities. Unfortunately, real-world activities are often subject to exogenous or environmental factors that affect their durations. We can partially mitigate this by employing dynamic scheduling policies, which respond to duration outcomes throughout execution. (In contrast, static policies do not have access to this information, so they effectively make all their decisions offline.) However, if the underlying models of activity duration don’t distinguish between outcomes’ likelihoods, then trying to handle all outcomes leads to ultra-conservative schedules or even scheduling infeasibility.

To widen the solution space, I observe that by modeling activities’ durations with probability distributions, we can construct scheduling policies with bounded risk of failure. Namely, I express bounded risk via a chance constraint, which imposes a maximum allowable likelihood of violating a plan’s temporal requirements. Thus, we reduce conservatism by accepting quantifiable risk, and this opens up a spectrum of solutions. Producing dynamic scheduling policies for chance-constrained plans, then, is the goal of my thesis.

Accessing these policies can be difficult, because the nonlinearity of temporal distributions makes it expensive to evaluate chance constraints directly. My strategy to address this is twofold: First, I reformulate the chance-constrained problem as a risk allocation, which strategically distributes the risk bound over the activities’ durations. This allows us to map the probabilistic model of uncertainty back into an interval-bounded formulation, and thus leverage existing scheduling algorithms that are efficient.

However, this only works if the mapping produces a plan that can be feasibly scheduled. So second, I present a conflict-directed hybrid architecture for finding a successful mapping. The approach is hybrid in that it iterates between using a nonlinear solver to generate candidate risk allocations, and running efficient scheduling algorithms to identify conflicts. The risk allocations produce plans for the algorithms to check, and the conflicts further inform the solver when generating subsequent risk allocations.

This hybrid design aims to relieve the solver of having to process the entire network of temporal constraints. Instead, the hope is that only a limited number of rounds are needed to conclude whether a chance-constrained policy exists. Due to a fundamental relationship between conflicts for static versus dynamic policies, I first instantiate the architecture for static policies as a two-layer construction. Then using the same principles, I augment it with a third layer for handling dynamic policies.

To evaluate my approach, I construct simulated plans based on lunar construction and public transit scenarios. These exemplify complexity in the real world when coordinating parallel threads of execution. I demonstrate that chance-constrained plans are more likely than their non-probabilistic counterparts to admit scheduling policies. But the trade-off lies in the expense of computing chance-constrained policies, due to the inherent nonlinearity of risk allocation. Nonetheless, the hybrid architecture provides an order-of-magnitude speedup over pure nonlinear programming.

Details

• Date: Wednesday, June 29
• Time: 3:15 pm
• Category: Thesis Defense
• Location: 32-G449 (Patil/Kiva)

Additional Location Details:

Thesis Supervisor: Prof. Brian Williams