^April May – 2010 ^June

Decision making is the ability to decide on the best alternative among a set of candidates based on their value. In many real-world domains the value depends on events that occur dynamically, so that the decision is based on dynamically changing uncertain information. When there is a cost to waiting for more information, the question is when to make the decision. Do you stop and make the best decision you can, given the information you have so far, or do you wait until more information arrives so you can make a better decision? We propose a model that characterizes the influence of dynamic information on the utility of the decision. Based on this model, we present an optimal algorithm that guarantees the best time to stop. Unfortunately, its complexity is exponential in the number of candidates. We present an alternative framework in which the different candidates are solved separately. We formally analyze the alternative framework, and show how it leads to a range of specific heuristic algorithms. We evaluate the optimal and the simplest heuristic algorithms through experiments, and show that the heuristic algorithm is much faster than the optimal algorithm, and the utility of the winner it finds is close to the optimum.

The celebrated Johnson-Lindenstrauss lemma says that every n points in Euclidean space can be represented with O(log n) dimensions with only a minor distortion of pairwise distances. It has been conjectured that a such-improved dimension reduction representation is achievable for many interesting data sets, by bounding the target dimension in terms of the intrinsic dimensions of the data (for example, by replacing the log n term with the doubling dimension). This question appears to be quite challenging, requiring new (nonlinear) embedding techniques. We make progress towards resolving this question by presenting two dimension reduction theorems with similar flavor to the conjecture. For some intended applications, these results can serve as an alternative to the conjectured embedding. [Joint work with Robert Krauthgamer.]

Admissible heuristics are a key tool for optimizing heuristic-search planning procedures such as A* or IDA*. Most typically, such a heuristic for domain-independent planning is defined as the (optimal) cost of achieving the goals in an over-approximating abstraction of the planning problem in hand. Such an abstraction is obtained by relaxing certain constraints in the specification of the real problem, and the desire is to obtain a provably poly-time solvable, yet informative abstract problem. The main questions are thus:

1. What constraints should we relax to obtain such an effective over-approximating abstraction? 2. How should we combine information provided by multiple such abstractions?

In this talk we consider both these questions, and present some recent formal and empirical results that help answering these questions (sometimes even to optimality). Specifically,

- Considering Q1, we introduce a generalization of explicit abstractions (such as pattern databases (PDB) and merge-and-shrink) to what we call implicit absractions. The basic idea is in abstracting the problem in hand into provably tractable fragments of optimal planning, alleviating by that the constraint of PDBs to use projections of only low dimensionality. We then introduce concrete instance of this framework called fork-decomposition, and show both formally and empirically that the admissible heuristics induced by the latter abstractions provide state-of-the-art worst-case informativeness guarantees on several standard domains.

- Considering Q2, we describe a procedure that takes a classical planning task, a forward-search state, and a set of abstraction-based admissible heuristics, and derives an optimal additive composition of these heuristics with respect to the given state. Most importantly, we show that this procedure is polynomial-time for arbitrary sets of all known to us abstraction-based heuristics such as PDBs, constrained PDBs, merge-and-shrink abstractions, fork-decomposition implicit abstractions, and implicit abstractions based on tractable constraint optimization.

The talk is based on a joint work with Michael Katz (Technion).