Professor
Head of Department
רמ"ח
| Building | Floor | Room | Category | Telephone |
|---|
| בנין מערכות מידע וסייבר - 96 | 2 | 221
| Phone | +972-74-7795113
|
- B.Sc: 1991-1993 Hebrew University, Jerusalem – Computer Science and Mathematics. With distinction.
- M.Sc: 1994-1995 Hebrew University, University – Computer Science
- Advisor’s Name: Prof. Jeff Rosenchein
- Thesis title: “Searching for an Alternative Plan”
- Ph.D: 1998-2002 Bar-Ilan University – Computer Science,
- Advisor’s Name: Prof. Sarit Kraus.
- The work was carried out with a considerable amount of help
- and advice from Prof. Richard E. Korf from UCLA.
- Dissertation title: " Improving Search Techniques and Using them in Different Environments .”
- My main research area is heuristic search . I am also interested in mobile agents in unknown physical environments.
- Heuristic Search and Pattern Databases
- Heuristic search is a fundamental field of research in Artificial Intelligence where any or an optimal path between two states in large state spaces should be found. Since the state spaces are exponentially large, we use heuristic evaluation functions in order to guide the search towards the goal and to prune regions of the search space where solutions cannot be found. To guarantee finding the optimal solution, we require that the heuristics should be “admissible” – that is, the heuristic always return a value which is less than or equal to the exact optimal solution. Much of my research is on developing enhanced search algorithms and generating more accurate heuristic functions.
- In particular, I am interested in pattern-databases (PDBs) which are a recent breakthrough that have made a revolution in calculating accurate admissible heuristic functions. Many state-of-the-art problem solvers are based on this new idea. Pattern databases are large tables that store solutions to "patterns" or subproblems and are usually stored in main memory. These solutions are then used as heuristics that guide the search. With heuristics defined by pattern databases we are able to solve problems thousands of times faster than with previous heuristics. A basic question in this field is how to handle and combine multiple heuristics that arise from different pattern databases. The obvious way to combine them without loosing admissibility (and in fact, to combine multiple heuristics of any kind) is to take their maximum [J:5 C:16]. Nevertheless, we have shown that in some circumstances PDBs can be added without losing admissibility [J:1,8,12]. How to store PDBs might be domain dependent and can benefit from different data structures. Many of my works dealt with applying PDBs to different domains such as the vertex-cover problem [J:8], the graph partitioning problem [J:7] and about general data structures for PDB [C:1,3,13]. Another direction taken is to compress the PDBs into smaller amount of memory without losing much of the information [J:3 C:17]. Another direction that I explored concerned new and efficient search algorithms for various domains and environments [J:10,11 C:4,5,6,8,16].
- Another recent direction of my research considers duality and inconsistency in search spaces. This project was funded by ISF [grant #1]. Traditionally it was thought that consistency is a desirable attribute for heuristics but we have show the contrary. Inconsistent heuristics provide many benefits and might reduce the search effort [C:2,7,11]. In addition, we explored the duality concept which is a logical symmetry that provides alternatives heuristic lookups as well as new search algorithm. [J:2 C:10].
- Currently and in the near future the following directions are researched. One of my goals is to show the applicability of PDBs and the theories developed for them can be applied to realistic real-world problems such as optimization problems CSP, path planning in roadmaps etc. Also, I plan to focus on the question of how to perform a search where the shortest paths between pairs of states from a set of start states to a set of goal states should be found. How can we perform one search to solve all these problems?
- Agents in physical environments
- Another field that I am interested in is the field of mobile agents in unknown physical environments . Here, each agent needs to decide where to go next based on its partial knowledge of the environment and on the problem to be solved. In a multi-agent systems, agents need to communicate and share knowledge. What is the best communication model for physical environment? How different communication models and constraint influence the behavior of the entire group of agents?
- My first work in this topic is the Physical A* (PHA*) algorithm and its multi agent version MAPHA* [J:9 C:20]. These algorithms are designed to help one or more mobile agents/robots to activate A* on physical environments. The objective is to minimize the traveling effort of the agents. Other works in this direction are [J: 4,13,17 C: 10,12,19]. I also explored a new model of communication in multi agent systems which we call large pheromones [funded by grant #2]. With pheromones, data items are places on the environment for future usage by other agents. Large pheromones do not limit the amount of data in each of the pheromones. As a test case we implemented a version of MAPHA* with this paradigm [J:6 C: 14,15]. New directions and findings in this area will be presented in [J:16,17].
- Currently and in the near future I would like to combine these directions into one general question. How to solve classic graph problems in physical graphs? Classic algorithms in computer science are aimed to minimize the CPU time and memory requirements. Such algorithms assume that the entire graph is known and stored in main memory. However, in unknown physical graph where traveling agents need to move there are other possible cost functions such as the travel effort, sensing effort, time elapsed, energy consumption etc. In many cases we would like to solve a problem on such graphs (e.g., navigation, shortest path, finding a specific pattern etc.) but the cost function is not just the computation effort but also includes all of some of the above costs. The main question to be addressed is how to apply classic graph algorithms for physical graphs with these costs functions. The direction taken in PHA* of two phase algorithm might be more general and can be applied to other problems and other costs functions.