Raz Nissim

Journal Papers

 

2014 -  “Distributed Heuristic Forward Search for Multi-agent Planning” by Raz Nissim and Ronen I. Brafman. Journal of Artificial Intelligence Research (JAIR).  (slides)

 

This paper deals with the problem of classical planning for multiple cooperative agents who have private information about their local state and capabilities they do not want to reveal. Two main approaches have recently been proposed to solve this type of problem -- one is based on reduction to distributed constraint satisfaction, and the other on partial-order planning techniques. In classical single-agent planning, constraint-based and partial-order planning techniques are currently dominated by heuristic forward search. The question arises whether it is possible to formulate a distributed heuristic forward search algorithm for privacy-preserving classical multi-agent planning. Our work provides a positive answer to this question in the form of a general approach to distributed state-space search in which each agent performs only the part of the state expansion relevant to it. The resulting algorithms are simple and efficient -- outperforming previous algorithms by orders of magnitude -- while offering similar flexibility to that of forward-search algorithms for single-agent planning. Furthermore, one particular variant of our general approach yields a distributed version of the A* algorithm that is the first cost-optimal distributed algorithm for privacy-preserving planning.

 

 

2014 - "Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces" by Malte Helmert, Patrik Haslum, Joerg Hoffmann and Raz Nissim. Journal of the ACM (JACM). 

 

Many areas of computer science require answering questions about reachability in compactly described discrete transition systems. Answering such questions effectively requires techniques able to do so without building the entire system. In particular, heuristic search uses lower-bounding (admissible) heuristic functions to prune parts of the system known to not contain an optimal solution. A prominent technique for deriving such bounds is to consider abstract transition systems that aggregate groups of states into one. The key question is how to design and represent such abstractions. The most successful answer to this question are pattern databases, which aggregate states if and only if they agree on a subset of the state variables.

Merge-and-shrink abstraction is a new paradigm that, as we show, allows to compactly represent a more general class of abstractions, strictly dominating pattern databases in theory. We identify the maximal class of transition systems, which we call factored transition systems, to which merge-and-shrink applies naturally, and we show that the well-known notion of bisimilarity can be adapted to this framework in a way that still guarantees perfect heuristic functions, while potentially reducing abstraction size exponentially. Applying these ideas to planning, one of the foundational subareas of artificial intelligence, we show that in some benchmarks this size reduction leads to the computation of perfect heuristic functions in polynomial time and that more approximate merge-and-shrink strategies yield heuristic functions competitive with the state of the art.

2010 - present

2010 - present

Conference Papers

 

2015 - "Watch-It-Next: A Contextual TV Recommendation System" by Michal Aharon, Eshcar Hillel, Amit Kagian, Ronny Lempel, Hayim Makabee, and Raz Nissim. Proceedings of ECML PKDD. (slides) 

As consumers of television are presented with a plethora of available programming, improving recommender systems in this domain is becoming increasingly important. Television sets, though, are often shared by multiple users whose tastes may greatly vary. Recommendation systems are challenged by this setting, since viewing data is typically collected and modeled per device, aggregating over its users and obscuring their individual tastes.This paper tackles the challenge of TV recommendation, specifically aiming to provide recommendations for the next program to watch following the currently watched program on the device. We present an empirical evaluation of several recommendation methods over large-scale, real-life TV viewership data. Our extensions of common state-of-the-art recommendation methods, exploiting the current watching context, demonstrate a significant improvement in recommendation quality.

 

2015 - "Serving Ads to "Yahoo Answers" Occasional Visitors" by Michal Aharon, Amit Kagian, Yohay Kaplan, Raz Nissim, Oren Somekh. Proceedings of WWW Ad targeting workshop. (slides)

 

Modern ad serving systems can benefit when allowed to accumulate user information and use it as part of the serving algorithm. However, this often does not coincide with how the web is used. Many domains will see users for only brief interactions, as users enter a domain through a search result or social media link and then leave. Having access to little or no user information and no ability to assemble a user profile over a prolonged period of use, we would still like to leverage the information we have to the best of our ability. In this paper we attempt several methods of improving ad serving for occasional users, including leveraging user information that is still available, content analysis of the page, information about the page’s content generators and historical breakdown of visits to the page. We compare and combine these methods in a framework of a collaborative filtering algorithm, test them on real data collected from Yahoo Answers, and achieve significant improvements over baseline algorithms.

 

2013 - “Cost-Optimal Planning by Self-Interested Agents” by Raz Nissim, Ronen I. Brafman. Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI). (slides)

 

As our world becomes better connected and autonomous agents no longer appear to be science fiction, a natural need arises for enabling groups of selfish agents to cooperate in generating plans for diverse tasks that none of them can perform alone in a cost-effective manner. While most work on planning for/by selfish agents revolves around finding stable solutions (e.g., Nash Equilibrium), this work combines techniques from mechanism design with a recently introduced method for distributed planning, in order to find cost optimal (and, thus, social welfare maximizing) solutions. Based on the Vickrey-Clarke-Groves mechanisms, we present both a centralized, and a privacy-preserving distributed mechanism.

 

2012 - “Tunneling and Decomposition-Based State Reduction for Optimal Planning” by Raz Nissim, Udi Apsel, Ronen I. Brafman. Proceedings of the Twentieth European Conference on Artificial Intelligence (ECAI). (slides)

 

Action pruning is one of the most basic techniques for improving a planner's performance. The challenge of preserving optimality while reducing the state space has been addressed by several methods in recent years. In this paper we describe two optimality preserving pruning methods: The first is a generalization of tunnel macros. The second, the main contribution of this paper, is a novel partition-based pruning method. The latter requires the introduction of new automated domain decomposition techniques which are of independent interest. Both methods prune the actions applicable at state s based on the last action leading to s, and both attempt to capture the intuition that, when possible, we should focus on one sub-goal at a time. As we demonstrate, neither method dominates the other, and a combination of both allows us to obtain an even stronger pruning rule. We also introduce a few modifications to A* that utilize properties shared by both methods to find an optimal plan. Our empirical evaluation compares the pruning power of the two methods and their combination, showing good coverage, reduction in running time, and reduction in the number of expansions.

 

2012 - “Multi-Agent A* for Parallel and Distributed Systems” by Raz Nissim, Ronen I. Brafman. Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS)      (Superseded by 2014 JAIR paper)

 

This paper describes a number of distributed forward search algorithms for solving multi-agent planning problems. We introduce a distributed formulation of non-optimal forward search, as well as an optimal version, MAD-A*. Our algorithms exploit the structure of multi-agent problems to not only distribute the work efficiently among different agents, but also to remove symmetries and reduce the overall workload. The algorithms ensure that private information is not shared among agents, yet computation is still efficient -- outperforming current state-of-the-art distributed planners, and in some cases even centralized search -- despite the fact that each agent has access only to partial information.

 

2011 - “Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning” by Raz Nissim, Joerg Hoffmann, Malte Helmert. Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI).

 

A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&S yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction – not distinguishing between certain groups of operators – without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a simple hybrid of two such variants is competitive with the leading heuristic LM-cut.

 

2010 - “A General, Fully Distributed Multi-Agent Planning Algorithm” by Raz Nissim, Ronen I. Brafman, Carmel Domshlak. Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS).

 

We present a fully distributed multi-agent planning algorithm. Our methodology uses distributed constraint satisfaction to coordinate between agents, and local planning to ensure the consistency of these coordination points. To solve the distributed CSP efficiently, we must modify existing methods to take advantage of the structure of the underlying planning problem. In multi-agent planning domains with limited agent interaction, our algorithm empirically shows scalability beyond state of the art centralized solvers. Our work also provides a novel, real-world setting for testing and evaluating distributed constraint satisfaction algorithms in structured domains and illustrates how existing techniques can be altered to address such structure.