Solomon E. Shimony

AAAI Conference 2019 Conference Paper

Allocating Planning Effort When Actions Expire

• Shahaf S. Shperberg
• Andrew Coles
• Bence Cserna
• Erez Karpas
• Wheeler Ruml
• Solomon E. Shimony

Making plans that depend on external events can be tricky. For example, an agent considering a partial plan that involves taking a bus must recognize that this partial plan is only viable if completed and selected for execution in time for the agent to arrive at the bus stop. This setting raises the thorny problem of allocating the agent’s planning effort across multiple open search nodes, each of which has an expiration time and an expected completion effort in addition to the usual estimated plan cost. This paper formalizes this metareasoning problem, studies its theoretical properties, and presents several algorithms for solving it. Our theoretical results include a surprising connection to job scheduling, as well as to deliberation scheduling in time-dependent planning. Our empirical results indicate that our algorithms are effective in practice. This work advances our understanding of how heuristic search planners might address realistic problem settings.

AAAI Conference 2019 Conference Paper

Enriching Non-Parametric Bidirectional Search Algorithms

• Shahaf S. Shperberg
• Ariel Felner
• Nathan R. Sturtevant
• Solomon E. Shimony
• Avi Hayoun

NBS is a non-parametric bidirectional search algorithm proven to expand at most twice the number of node expansions required to verify the optimality of a solution. We introduce new variants of NBS that are aimed at finding all optimal solutions. We then introduce an algorithmic framework that includes NBS as a special case. Finally, we introduce DVCBS, a new algorithm in this framework that aims to further reduce the number of expansions. Unlike NBS, DVCBS does not have any worst-case bound guarantees, but in practice it outperforms NBS in verifying the optimality of solutions.

IJCAI Conference 2009 Conference Paper

• Sivan Albagli
• Rachel Ben-Eliyahu-Zohary
• Solomon E. Shimony

iMatch is a probabilistic scheme for ontology matching based on Markov networks, which has several advantages over other probabilistic schemes. First, it uses undirected networks, which better supports the non-causal nature of the dependencies. Second, it handles the high computational complexity by doing approximate reasoning, rather then by ad-hoc pruning. Third, the probabilities that it uses are learned from matched data. Finally, iMatch naturally supports interactive semiautomatic matches. Experiments using the standard benchmark tests that compare our approach with the most promising existing systems show that iMatch is one of the top performers.

IJCAI Conference 2007 Conference Paper

• Guy Shani
• Ronen I. Brafman
• Solomon E. Shimony

Recent scaling up of POMDP solvers towards realistic applications is largely due to point-based methods which quickly converge to an approximate solution for medium-sized problems. Of this family HSVI, which uses trial-based asynchronous value iteration, can handle the largest domains. In this paper we suggest a new algorithm, FSVI, that uses the underlying MDP to traverse the belief space towards rewards, finding sequences of useful backups, and show how it scales up better than HSVI on larger benchmarks.

AAAI Conference 2007 Conference Paper

Computing Optimal Subsets

• Maxim Binshtok
• Solomon E. Shimony

Various tasks in decision making and decision support require selecting a preferred subset of items from a given set of feasible items. Recent work in this area considered methods for specifying such preferences based on the attribute values of individual elements within the set. Of these, the approach of (Brafman et al. 2006) appears to be the most general. In this paper, we consider the problem of computing an optimal subset given such a specification. The problem is shown to be NP-hard in the general case, necessitating heuristic search methods. We consider two algorithm classes for this problem: direct set construction, and implicit enumeration as solutions to appropriate CSPs. New algorithms are presented in each class and compared empirically against previous results.

AAAI Conference 2006 Conference Paper

Preferences over Sets

• Ronen I. Brafman
• Solomon E. Shimony

Research on preference elicitation and reasoning typically focuses on preferences over single objects of interest. However, in a number of applications the “outcomes” of interest are sets of such atomic objects. For instance, when creating the program for a film festival, editing a newspaper, or putting together a team, we need to select a set of films (resp. articles, members) that is optimal with respect to quality, diversity, cohesiveness, etc. This paper describes an intuitive approach for specifying preferences over sets of objects. An algorithm for computing an optimal subset, given a set of candidate objects and a preference specification, is developed and evaluated.

AAAI Conference 1991 Conference Paper

Explanation, Irrelevance, and Statistical Independence

• Solomon E. Shimony

We evaluate current explanation schemes. These are either insufficiently general, or suffer from other serious drawbacks. We propose a domain-independent explanation system that is based on ignoring irrelevant variables in a probabilistic setting. We then prove important properties of some specific irrelevance-based schemes and discuss how to implement them.