
Solomon Eyal Shimony 
My research focuses on structured probabilistic reasoning and its derivatives, in patricular decisionmaking under uncertainty. Within these fields, the structure of the distributions and utility functions, represented as a graphical model (such as a Bayes network representing the distributions, or a CP network representing the preference structure) is crucial. Much of my research is aimed at exploiting such structure, towards effective schemes for reasoning over these models, both in theory and in practice.
In earlier works, we defined ``irrelevancebased independence'', a dependency structure that has since become known as ``contextspecific independence''. Typically defined on top of a graphical probability model such as a Bayes network, this refined version allows specifying that variables are independent given specific instantiations of other random variables, rather than given all possible such instantiations as is standard for Bayes networks. This refined model is more complicated, but allows for many more cases where independence can be stated, and thus this notion allows for a more compact representation of specific types of multivariate distributions, such as the wellknown noisy or. That in turn enables improving performance of reasoning algorithms in networks that exhibit such structure. As a result, this notion is exploited in the community for efficient probabilistic reasoning.
Numerous AI applications use some form of weights or heuristics, in order to convey uncertainty or incompleteness, such as in abductive reasoning for natural language interpretation. It is crucial to attach a probabilistic semantics to these weights if possible, as that makes the treatment of these weights more disciplined, by exposing hidden assumptions, as well as frequently allowing improved heuristics. Papers using this methodology include a probabilistic semantics for weighted abduction, where the costs of assumed literals behave like negative logarithm of the probability that the event specified by the literal occurs. The semantics in this case highlights the independence assumption underlying the weighted abduction scheme. Another case is probabilitybased heuristics for constraint satisfaction problems, where an estimate for the number of solutions under different independence assumptions can be beneficially used as a valueordering search heuristic. Finally, the observation that kappacalculus is a valid semantics for degrees of evidence also helps understand assumptions implicit in the degrees of evidence model.
For the more standard utility function representation, solving various classes of partially observable markov decision processes (POMDP) is an important computationally intractable problem. Techniques relying on metareasoning aspects of flexible computation have shown to be applicable, for example in reasoning over what ``backup'' actions to perform in beliefpoint based algorithms. Using problem structure, i.e. the way the value functions and the distributions are defined in terms of the variables composing the states of the POMDP, is another way to go. Special cases of POMDP, such as the observation subset selection problem, when the dependency model has the right structure, such as a chain, or a tree, can be solved in polynomial time. In fact, this research finds immediate application in such problems encountered by our industrial partners in the IMG4 consortium.
Decision making under uncertainty for robots, both real and simulated, is an important application area, and requires understanding both in spatial issues and structured probability models. We pioneered the research on uncertain data models and models for uncertain spatial data that are recently becoming popular. Increased research community interest in AI in games has renewed examination of such issues, and an abstaction that we are currently examining is the path planning under uncertainty problem known as the Canadian traveller problem (CTP) and its variants. In this problem, a weighted graph is given, but some of its edges may be blocked. The actual state of an edge becomes known to the agent only upon reaching an incident vertex. This problem and its variants with remote sensing, which is also a sort of POMDP, is a large unexplored territory in my research plan for the next several years.
Yet another application of decisionmaking under uncertainty is that of metareasoning. Here we try to optimize computational actions performed to reach certain computational goals. One wellknown but underexplored domain is rational metareasoning for search, initially introduced circa 1990. In recent work we applied this methodology to selecting heuristics to deploy during CSP search. Another ongoing direction is finding what to sample in MonteCarlo tree search.
Building 37 (Alon HiTech Building) Room 216 Office hours: Tuesday 1416
Department of Computer Science BenGurion University of the Negev P.O. Box 653 84105 BeerSheva Israel Tel: (+9728) 6477857 FAX: (+9728) 6472909