Author name cluster

Gera Weiss

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

AIJ Journal 2024 Journal Article

Efficient optimal Kolmogorov approximation of random variables

Liat Cohen
Tal Grinshpoun
Gera Weiss

Discrete random variables are essential ingredients in various artificial intelligence problems. These include the estimation of the probability of missing the deadline in a series-parallel schedule and the assignment of suppliers to tasks in a project in a manner that maximizes the probability of meeting the overall project deadline. The solving of such problems involves repetitive operations, such as summation, over random variables. However, these computations are NP-hard. Therefore, we explore techniques and methods for approximating random variables with a given support size and minimal Kolmogorov distance. We examine both the general problem of approximating a random variable and a one-sided version in which over-approximation is allowed but not under-approximation. We propose several algorithms and evaluate their performance through computational complexity analysis and empirical evaluation. All the presented algorithms are optimal in the sense that given an input random variable and a requested support size, they return a new approximated random variable with the requested support size and minimal Kolmogorov distance from the input random variable. Our approximation algorithms offer useful estimations of probabilities in situations where exact computations are not feasible due to NP-hardness complexity.

Details DOI

CSL Conference 2023 Conference Paper

A Normalized Edit Distance on Infinite Words

Dana Fisman
Joshua Grogin
Gera Weiss

We introduce ω^ ̅-NED, an edit distance between infinite words, that is a natural extension of NED, the normalized edit distance between finite words. We show it is a metric on (equivalence classes of) infinite words. We provide a polynomial time algorithm to compute the distance between two ultimately periodic words, and a polynomial time algorithm to compute the distance between two regular ω-languages given by non-deterministic Büchi automata.

Details

AAAI Conference 2019 Conference Paper

Efficient Optimal Approximation of Discrete Random Variables for Estimation of Probabilities of Missing Deadlines

Liat Cohen
Gera Weiss

We present an efficient algorithm that, given a discrete random variable X and a number m, computes a random variable whose support is of size at most m and whose Kolmogorov distance from X is minimal. We present some variants of the algorithm, analyse their correctness and computational complexity, and present a detailed empirical evaluation that shows how they performs in practice. The main application that we examine, which is our motivation for this work, is estimation of the probability of missing deadlines in series-parallel schedules. Since exact computation of these probabilities is NP-hard, we propose to use the algorithms described in this paper to obtain an approximation.

PDF Details

AIJ Journal 2019 Journal Article

Estimating the probability of meeting a deadline in schedules and plans

Liat Cohen
Solomon Eyal Shimony
Gera Weiss

Given a plan (or schedule) with uncertain task times, we propose a deterministic polynomial (time and memory) algorithm for estimating the probability that it meets a deadline, or, equivalently, that its makespan is less than a given duration. Approximation is needed as it is known that this problem is NP-hard even for sequential plans (sum of random variables). In addition, we show two new complexity results: (1) Counting the number of events that do not cross the deadline is #P-hard; (2) Computing the expected makespan of a hierarchical plan is NP-hard. For the proposed approximation algorithm, we establish formal approximation bounds and show that the time and memory complexities grow polynomially with the required accuracy, the number of nodes in the plan, and with the size of the support of the random variables that represent the durations of the primitive tasks. We examine these approximation bounds empirically and demonstrate, using task networks taken from the literature, how our scheme outperforms sampling techniques and exact computation in terms of accuracy and run-time. As the empirical data shows much better error bounds than guaranteed, we also suggest a method for tightening the bounds in some cases.

Details DOI

AAAI Conference 2019 Conference Paper

Labor Division with Movable Walls: Composing Executable Specifications with Machine Learning and Search (Blue Sky Idea)

David Harel
Assaf Marron
Ariel Rosenfeld
Moshe Vardi
Gera Weiss

Artificial intelligence (AI) techniques, including, e. g. , machine learning, multi-agent collaboration, planning, and heuristic search, are emerging as ever-stronger tools for solving hard problems in real-world applications. Executable specification techniques (ES), including, e. g. , Statecharts and scenario-based programming, is a promising development approach, offering intuitiveness, ease of enhancement, compositionality, and amenability to formal analysis. We propose an approach for integrating AI and ES techniques in developing complex intelligent systems, which can greatly simplify agile/spiral development and maintenance processes. The approach calls for automated detection of whether certain goals and sub-goals are met; a clear division between sub-goals solved with AI and those solved with ES; compositional and incremental addition of AI-based or ES-based components, each focusing on a particular gap between a current capability and a well-stated goal; and, iterative refinement of sub-goals solved with AI into smaller sub-sub-goals where some are solved with ES, and some with AI. We describe the principles of the approach and its advantages, as well as key challenges and suggestions for how to tackle them.

PDF Details

AAAI Conference 2018 Conference Paper

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

Liat Cohen
Tal Grinshpoun
Gera Weiss

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 efﬁcient 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 speciﬁcally, 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 ﬁts the goal of estimating deadline meeting probabilities.

PDF Details

IJCAI Conference 2015 Conference Paper

Estimating the Probability of Meeting a Deadline in Hierarchical Plans

Liat Cohen
Solomon Eyal Shimony
Gera Weiss

Given a hierarchical plan (or schedule) with uncertain task times, we may need to determine the probability that a given plan will satisfy a given deadline. This problem is shown to be NPhard for series-parallel hierarchies. We provide a polynomial-time approximation algorithm for it. Computing the expected makespan of an hierarchical plan is also shown to be NP-hard. We examine the approximation bounds empirically and demonstrate where our scheme is superior to sampling and to exact computation.

PDF Details