Many problems in AI, including planning, logical reasoning and probabilistic inference, have been shown to reduce to (weighted) constraint satisfaction. While there are a number of approaches for solving such problems, the recent gains in efficiency of the satisfiability approach have made SAT solvers a popular choice. Modern propositional SAT solvers are efficient for a wide variety of problems. However, particularly in the case of spatial reasoning, conversion to propositional SAT can sometimes result in a large number of variables and/or clauses. Moreover, spatial reasoning problems can often be more efficiently solved if the agent is able to exploit the geometric nature of space to make better choices during search and backtracking. The result of these two drawbacks — larger problem sizes and inefficient search — is that even simple spatial constraint problems are often intractable in the SAT approach. In this paper we propose a spatial reasoning system that provides significant performance improvements in constraint satisfaction problems involving spatial predicates. The key to our approach is to integrate a diagrammatic representation with a DPLL-based backtracking algorithm that is specialized for spatial reasoning. The resulting integrated system can be applied to larger and more complex problems than current approaches and can be adopted to improve performance in a variety of problems ranging from planning to probabilistic inference

We consider the task of assigning experts from a portfolio of specialists in order to solve a set of tasks. We apply a Bayesian model which combines collaborative filtering with a feature-based description of tasks and experts to yield a general framework for managing a portfolio of experts. The model learns an embedding of tasks and problems into a latent space in which affinity is measured by the inner product. The model can be trained incrementally and can track non-stationary data, tracking potentially changing expert and task characteristics. The approach allows us to use a principled decision theoretic framework for expert selection, allowing the user to choose a utility function that best suits their objectives. The model component for taking into account the performance feedback data is pluggable, allowing flexibility. We apply the model to manage a portfolio of algorithms to solve hard combinatorial problems. This is a well studied area and we demonstrate a large improvement on the state of the art in one domain (constraint solving) and in a second domain (combinatorial auctions) created a portfolio that performed significantly better than any single algorithm.

In this paper, we study the knowledge compilation task for propositional epistemic logic S5. We first extend many of the queries and transformations considered in the classical knowledge compilation map to S5. We then show that the notion of disjunctive normal form (DNF) can be profitably extended to the epistemic case; we prove that the DNF fragment of S5, when appropriately defined, satisfies essentially the same queries and transformations as its classical counterpart.

In the form of topic discussions, users interact with each other to share knowledge and exchange information in online forums. Modeling the evolution of topic discussion reveals how information propagates on Internet and can thus help understand sociological phenomena and improve the performance of applications such as recommendation systems. In this paper, we argue that a user’s participation in topic discussions is motivated by either her friends or her own preferences. Inspired by the theory of information flow, we propose dynamic topic discussion models by mining influential relationships between users and individual preferences. Reply relations of users are exploited to construct the fundamental influential social network. The property of discussed topics and time lapse factor are also considered in our modeling. Furthermore, we propose a novel measure called ParticipationRank to rank users according to how important they are in the social network and to what extent they prefer to participate in the discussion of a certain topic. The experiments show our model can simulate the evolution of topic discussions well and predict the tendency of user’s participation accurately.

On the surface, bidirectional search (BDS) is an attractive idea with the potential for significant asymptotic reductions in search effort. However, the results in practice often fall far short of expectations. We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Searc (SFBDS). Unlike traditional BDS which keeps two frontiers, SFBDS uses a single frontier. Each node in the tree can be seen as an independent task of finding the shortest path between the current start and current goal. At a particular node we can decide to search from start to goal or from goal to start, choosing the direction with the highest potential for minimizing the total work done. Theoretical results give insights as to when this approach will work and experimental data validates the algorithm for a broad range of domains.

We propose a framework where humans and computers can collaborate seamlessly to solve problems. We do so by developing and applying a network model, namely Memenets, where human knowledge and reasoning are combined with machine computation to achieve problem-solving. The development of a Memenet is done in three steps: first, we simulate a machine-only network, as previous results have shown that memenets are efficient problem-solvers. Then, we perform an experiment with human agents organized in a online network. This allows us to investigate human behavior while solving problems in a social network and to postulate principles of agent communication in Memenets. These postulates describe an initial theory of how human-computer interaction functions inside social networks. In the third stage, postulates of step two allow one to combine human and machine computation to propose an integrated Memenet-based problem-solving computing model.

We study the computational complexity of the counting version of the Possible-Winner problem for elections. In the Possible-Winner problem we are given a profile of voters, each with a partial preference order, and ask if there are linear extensions of the votes such that a designated candidate wins. We also analyze a special case of Possible-Winner, the Manipulation problem. We provide polynomial-time algorithms for counting manipulations in a class of scoring protocols and in several other voting rules. We show #P-hardness of the counting variant of Possible-Winner for plurality and veto and give a simple yet general and practically useful randomized algorithm for a variant of Possible-Winner for all voting rules for which a winner can be computed in polynomial time.

Traditional clustering methods deal with a single clustering task on a single data set. However, in some newly emerging applications, multiple similar clustering tasks are involved simultaneously. In this case, we not only desire a partition for each task, but also want to discover the relationship among clusters of different tasks. It's also expected that the learnt relationship among tasks can improve performance of each single task. In this paper, we propose a general framework for this problem and further suggest a specific approach. In our approach, we alternatively update clusters and learn relationship between clusters of different tasks, and the two phases boost each other. Our approach is based on the general Bregman divergence, hence it's suitable for a large family of assumptions on data distributions and divergences. Empirical results on several benchmark data sets validate the approach.

Recent advancements in model-based reinforcement learning have shown that the dynamics of many structured domains (e.g. DBNs) can be learned with tractable sample complexity, despite their exponentially large state spaces. Unfortunately, these algorithms all require access to a planner that computes a near optimal policy, and while many traditional MDP algorithms make this guarantee, their computation time grows with the number of states. We show how to replace these over-matched planners with a class of sample-based planners — whose computation time is independent of the number of states — without sacrificing the sample-efficiency guarantees of the overall learning algorithms. To do so, we define sufficient criteria for a sample-based planner to be used in such a learning system and analyze two popular sample-based approaches from the literature. We also introduce our own sample-based planner, which combines the strategies from these algorithms and still meets the criteria for integration into our learning system. In doing so, we define the first complete RL solution for compactly represented (exponentially sized) state spaces with efficiently learnable dynamics that is both sample efficient and whose computation time does not grow rapidly with the number of states.

Software developers increasingly rely on information from the Web, such as documents or code examples on Application Programming Interfaces (APIs), to facilitate their development processes. However, API documents often do not include enough information for developers to fully understand the API usages, while searching for good code examples requires non-trivial efforts. To address this problem, we propose a novel code search engine, combining the strength of browsing documents and searching for code examples, by returning documents embedded with high-quality code example summaries mined from the Web. Our evaluation results show that our approach provides code examples with high precision and boosts programmer productivity.