In this paper we propose a new algorithm for solving general two-player turn-taking games that performs symbolic search utilizing binary decision diagrams (BDDs). It consists of two stages: First, it determines all breadth-first search (BFS) layers using forward search and omitting duplicate detection, next, the solving process operates in backward direction only within these BFS layers thereby partitioning all BDDs according to the layers the states reside in. We provide experimental results for selected games and compare to a previous approach. This comparison shows that in most cases the new algorithm outperforms the existing one in terms of runtime and used memory so that it can solve games that could not be solved before with a general approach.
One of the most essential parts of any recommender system is personalization how acceptable the recommendations are from the user's perspective. However, in many real-world applications, there are multiple objectives often from multiple stakeholders that need to be incorporated into the recommendation generation. In this work, we define the problem of multi-stakeholder recommendation and we focus on finding algorithms for a special case where the recommender system itself is also a stakeholder. We also define different types of system-level objectives and find algorithmic solutions for each of them such that similar problems can be solved by the same class of algorithms. Finally, we will explore the idea of incremental incorporation of system-level objectives into recommender systems to tackle the existing problems with the optimization techniques which only look for optimizing the individual users' lists rather than looking at the whole picture of system performance over time. With autonomous robots being exposed to unstructured environments, they inevitably run across cases in which they stand unable to overcome their limitations, such as removing objects in their path, or location uncertainty. These limitations can be overcome when robots obtain help from humans. We are investigating how robots can effectively interact and request help from human. We test a scenario where the robot needs a door to be opened by a human, so the robot could complete its other tasks. The robot is too short to reach the door handle himself. In the polite request, the robot may say "Can you open the door please?", while in the indirect request, the robot may say "I cannot open the door and it is blocking my way". In the friendly way, the robot asks with less formal tones like "You seem taller than me. Would you open the door for me?". The robot can point its hand to the door that it needs opened. Later humans were interviewed as to why they did or did not take the robot seriously. The polite interaction manner was significantly more efficient. We show how to factor the situational awareness effects (whether participants realize the nature of the experiment) in the analysis. The proposed evaluation procedure allows identifying promising mechanisms for such human-robot interactions.
This paper proposes a highly efficient exact dynamic programming algorithm for computing all the conditionals generated from consonant belief functions. The time and space complexities of this novel algorithm are linear for computing all the conditional beliefs, and hence it significantly outperforms the exponential time and space complexity requirements of the brute force approach and the currently available conditional computation strategies. We provide a thorough analysis and experimental validation of the utility, efficiency, and implementation of the proposed algorithm for carrying out the Fagin-Halpern conditional. A new computational library is developed and harnessed in the simulations.
Laaziz, Safia (Université des Sciences et Technologie Houari Boumediene) | Zeboudj, Younes (Université des Sciences et Technologie Houari Boumediene) | Benferhat, Salem (Université des Sciences et Technologie Houari Boumediene) | Haned, Faiza (Université des Sciences et Technologie Houari Boumediene)
Belief revision consists in modifying an epistemic state in the light of a new information. In this paper, we focus on the so-called multiple iterated belief revision process called C-revision. Epistemic states are represented in terms of Ordinal Conditional Functions OCF and penalty knowledge bases. The input is a set of consistent weighted formulas. We show that C-revision, defined at a semantic level using OCF, has a very natural counterpart in penalty logic.
Forgetting as a knowledge management operation has received much less attention than operations like inference, or revision. It was mainly in the area of logic programming that techniques and axiomatic properties have been studied systematically. However, at least from a cognitive view, forgetting plays an important role in restructuring and reorganizing a human's mind, and it is closely related to notions like relevance and independence which are crucial to knowledge representation and reasoning. In this paper, we propose axiomatic properties of (intentional) forgetting for general epistemic frameworks which are inspired by those for logic programming, and we evaluate various forgetting operations which have been proposed recently by Beierle et al. according to them. The general aim of this paper is to advance formal studies of (intentional) forgetting operators while capturing the many facets of forgetting in a unifying framework in which different forgetting operators can be contrasted and distinguished by means of formal properties.
The lifted dynamic junction tree algorithm (LDJT) efficiently answers filtering and prediction queries for probabilistic relational temporal models by building and then reusing a first-order cluster representation of a knowledge base for multiple queries and time steps. Specifically, this paper contributes (i) a relational forward backward algorithm with LDJT, (ii) smoothing for hindsight queries, and (iii) different approaches to instantiate a first-order cluster representation during a backward pass. Further, our relational forward backward algorithm makes hindsight queries with huge lags feasible. LDJT answers multiple temporal queries faster than the static lifted junction tree algorithm on an unrolled model, which performs smoothing during message passing.
Reasoning in the context of a conditional knowledge base containing rules of the form ’If A then usually B’ can be defined in terms of preference relations on possible worlds. These preference relations can be modeled by ranking functions that assign a degree of disbelief to each possible world. In general, there are multiple ranking functions that accept a given knowledge base. Several nonmonotonic inference relations have been proposed using c-representations, a subset of all ranking functions. These inference relations take subsets of all c-representations based on various notions of minimality into account, and they operate in different inference modes, i.e., skeptical, weakly skeptical, or credulous. For nonmonotonic inference relations, weaker versions of monotonicity like rational monotony (RM) and weak rational monotony (WRM) have been developed. In this paper, we investigate which of the inference relations induced by sets of minimal c-representations satisfy rational monotony or weak rational monotony.
We focus on the problem of modeling deterministic equations over continuous variables in discrete Bayesian networks. This is typically achieved by a discretisation of both input and output variables and a degenerate quantification of the corresponding conditional probability tables. This approach, based on classical probabilities, cannot properly model the information loss induced by the discretisation. We show that a reliable modeling of such epistemic uncertainty can be instead achieved by credal sets, i.e., convex sets of probability mass functions. This transforms the original Bayesian network in a credal network, possibly returning interval-valued inferences, that are robust with respect to the information loss induced by the discretisation. Algorithmic strategies for an optimal choice of the discretisation bins are also discussed.