^August September – 2009 ^October

We evolve heuristics to aid search algorithms. The main method applied is Genetic Programming (GP), a sub-class of evolutionary algorithms, in which the individuals undergoing artificial evolution are (simple, yet large) LISP programs. In the domain of games, where search spaces are enormous, and the number of possible heuristics is even larger, the advantages of GP come to the fore, as an alternative to manually fine-tuning static evaluation functions. First, this method is demonstrated in the domain of Chess - both for endgames and the Mate-in-N problem. We further analyze the performance of evolved players and show that they demonstrate some emergent features. Second, we move to single-player games (puzzles) and show that a slightly-modified version of this methodology (using a form of policies), produces strong players for the 6x6 and 8x8 Rush-Hour puzzle, a PSPACE-Complete problem (for the nxn case). Some broader conclusions are drawn for the interplay between search and knowledge.

UML is now widely accepted as the standard modeling language for software construction. The Class Diagram is its core view, having well formed semantics and providing the backbone for any modeling effort. Class diagrams are widely used for purposes such as software specification, database and ontology engineering, meta-modeling, and model transformation. The central role played by class diagrams emphasizes the need for strengthening UML modeling tools with features such as recognition of erroneous models and the detection of errors’ sources.

Correctness of UML class diagrams refers to the capability of a diagram to denote a finite but not empty reality. This is a natural, unquestionable requirement. Nevertheless, incorrect diagrams are often designed, due to interaction of contradicting constraints and limitations of current tools. In this talk, I will discuss correctness problems in class diagrams, the methods we have develop for tackling them, and the latest results. I will also suggest directions for future work in this field.

Agents operating in the real world need to handle both uncertainty and resource constraints. Typical problems in this framework are rational observation control (ROC) and optimal allocation of computation tasks during reasoning and search (also known as meta-reasoning). In both tasks, a crucial issue is value of information, a quantity hard to compute in general, and thus usually estimated using severe assumptions, such as myopic look-ahead, independence of information sources and separability of reward function.

Recently, a dynamic programming approach, which bypasses the myopic assumption, was introduced. An efficient method, based on this approach, constructs an optimal observation plan for a chain-shaped dependency model with exact measurements and additive reward function.

In this work we consider several extensions for the above method, that allow inexact and multiple measurements, various reward functions and more general dependency models. We developed a unifying approach to a wide class of ROC problems. To this end we extended the concept of a conditional performance profile, and developed an efficient technique for compiling a composite system beyond the input monotonicity assumption. The resulting framework can be applied to many real-world domains, such as medical diagnostics, setup optimization, mobile robot navigation and game-tree search.