Optimal Approximation of Random Variables for Estimating the Probability of Meeting a Plan Deadline

Title: Optimal Approximation of Random Variables for Estimating the Probability of Meeting a Plan Deadline
Speaker: Liat Cohen, Department of Computer Science, Ben-Gurion University of the Negev
Date: 8/1/2019
Time: 12:00 – 13:00
Place: Building #3A, lower conference room, floor 2 (floor 1 in the elevator), Ariel University, Ariel

Abstract:
In planning algorithms and in other domains, there is often a need to run long computations that involve summations, maximizations and other operations on random variables, and to store intermediate results. In this paper, as a main motivating example, we elaborate on the case of estimating probabilities of meeting deadlines in hierarchical plans. A source of computational complexity, often neglected in the analysis of such algorithms, is that the support of the variables needed as intermediate results may grow exponentially along the computation. Therefore, to avoid exponential memory and time complexities, we need to trim these variables. This is similar, in a sense, to rounding intermediate results in numerical computations. Of course, to maintain the quality of algorithms, the trimming procedure should be efficient and it must maintain accuracy as much as possible. In this paper, we propose an optimal trimming algorithm with polynomial time and memory complexities for the purpose of estimating probabilities of deadlines in plans. More specifically, we show that our algorithm, given the needed size of the representation of the variable, provides the best possible approximation, where approximation accuracy is considered with a measure that fits the goal of estimating deadline meeting probabilities.

Short bio:
Liat Cohen is a Ph.D. student in the Department of Computer Science at Ben-Gurion University of the Negev. Her advisors are Dr. Gera Weiss from Ben-Gurion University and Dr. Tal Grinshpoun from Ariel University. Liat's main topic of research is decision making under uncertainty, and more specifically, compression of random variables. In addition, Liat is interested in planning, scheduling, and transportation problems.