^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.

In this paper we present a new approach for interactive view-dependent rendering of large polygonal datasets, which relies on advanced features of modern graphics hardware. Our preprocessing algorithm starts by generating a simplified representation of the input mesh. It then builds a multiresolution hierarchy for the simplified model. For each face in the hierarchy, it generates and assigns a displacement map that resembles the original surface represented by that face. At runtime, the multiresolution hierarchy is used to select a coarse viewdependent level-of-detail representation, which is sent to the graphics hardware. The GPU then refines the coarse representation by replacing each face with a planar patch, which is elevated according to the assigned displacement map. Initial results show that our implementation achieves quality images at high rates.

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.]

A power assignment is an assignment of transmission power to each of the nodes of a wireless network, so that the induced communication graph has some desired properties. The cost of a power assignment is the sum of the powers. The {em energy} of a transmission path from node $u$ to node $v$ is the sum of the squares of the distances between adjacent nodes along the path. For a constant $t >1$, an energy $t$-spanner is a graph $G'$, such that for any two nodes $u$ and $v$, there exists a path from $u$ to $v$ in $G'$, whose energy is at most $t$ times the energy of a minimum-energy path from $u$ to $v$ in the complete Euclidean graph.

We study the problem of finding a power assignment, such that (i) its induced communication graph is a `good' energy spanner, and (ii) its cost is `low'. We show that for any constant $t >1$, one can find a power assignment, such that its induced communication graph is an energy $t$-spanner, and its cost is bounded by some constant times the cost of an optimal power assignment (where the sole requirement is strong connectivity of the induced communication graph).

Based on joint work with Rom Aschner, Paz Carmi and Matya Catz.

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).