Optimal approximation of random variables for estimating the probability of meeting a plan deadline

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

4 ציטוטים ‏(Scopus)

תקציר

In planning algorithms and in other domains, there is often a need to run long computations that involve summations, max-imizations 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.

שפה מקוריתאנגלית
כותר פרסום המארח32nd AAAI Conference on Artificial Intelligence, AAAI 2018
עמודים6327-6334
מספר עמודים8
מסת"ב (אלקטרוני)9781577358008
סטטוס פרסוםפורסם - 2018
אירוע32nd AAAI Conference on Artificial Intelligence, AAAI 2018 - New Orleans, ארצות הברית
משך הזמן: 2 פבר׳ 20187 פבר׳ 2018

סדרות פרסומים

שם32nd AAAI Conference on Artificial Intelligence, AAAI 2018

כנס

כנס32nd AAAI Conference on Artificial Intelligence, AAAI 2018
מדינה/אזורארצות הברית
עירNew Orleans
תקופה2/02/187/02/18

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Optimal approximation of random variables for estimating the probability of meeting a plan deadline'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי