Springer Science and Business Media LLC

We investigate the topological structure of configuration spaces of kinematic scenes, i.e., mechanisms consisting of rigid, independently movable objects in a 2- or 3-dimensional environment. We demonstrate the practical importance of the considered questions by giving a motivation from the viewpoint of qualitative reasoning. Especially, we investigate topological invariants of the configuration space as a means for characterizing and classifying mechanisms. This paper focuses on the topological invariants homeomorphy, homotopy equivalence and fundamental group. We describe a procedure for computing a finite representation of the fundamental group of a given kinematic scene, and investigate its possible structure and complexity for simple classes of scenes. We show that for any finitely represented group one can construct a kinematic scene in the plane such that the fundamental group of its configuration space is isomorphic to the given group. This construction shows the undecidability of a variety of problems concerning the topological structure of configuration spaces, and reveals that the considered invariants in their general form do not provide an algorithmic method for characterizing or classifying arbitrary mechanisms.

The focus of this paper is on action domain descriptions whose meaning can be represented by transition diagrams. We introduce several semantic measures to compare such action descriptions, based on preferences over possible states of the world and preferences over some given conditions (observations, assertions, etc.) about the domain, as well as the probabilities of possible transitions. This preference information is used to assemble a weight which is assigned to an action description. As applications of this approach, we study updating action descriptions and identifying elaboration tolerant action descriptions, with respect to some given conditions. With a semantic approach based on preferences, not only, for some problems, we get more plausible solutions, but also, for some problems without any solutions due to too strong conditions, we can identify which conditions to relax to obtain a solution. We further study computational issues, and give a characterization of the computational complexity of computing the semantic measures.

We propose the usage of two power indices from cooperative game theory and public choice theory for ranking attributes of closed sets, namely intents of formal concepts (or closed itemsets). The introduced indices are related to extensional concept stability and are also based on counting of generators, especially of those that contain a selected attribute. The introduction of such indices is motivated by the so-called interpretable machine learning, which supposes that we do not only have the class membership decision of a trained model for a particular object, but also a set of attributes (in the form of JSM-hypotheses or other patterns) along with individual importance of their single attributes (or more complex constituent elements). We characterise computation of the Shapley and Banzhaf-Penrose values of a formal concept in terms of minimal generators and their order filters, provide the reader with their properties important for computation purposes, prove related #P-completeness results, and show experimental results with model and real datasets. We also show how this approach can be applied in both supervised (classification) and unsupervised (pattern mining) settings.

This paper describes a new formalism for inheritance systems, based on the formal semantics of set expressions. Using the formalism, it is possible to define new semantic classes by arbitrary set expressions operating on previously defined classes. Thus generalizing bothIS-A links andIS-NOT-A links and adding the set intersection operation. We present an efficient algorithm which follows these definitions to deduce the properties implied by the inheritance network, i.e., the properties of the classes containing a given element. The application which motivated the development of the formalism, namely semantic disambiguation of natural language, is also described.

There are exactly three regular planar grids, which are formed by tiling the 2-dimensional Euclidean space with regular triangles, squares, and hexagons. The topology of the square grid is well-understood, but it cannot be said of the remaining two regular sampling schemes. This work deals with the topological properties of digital binary pictures sampled on the triangular grid. Some characterizations of simple pixels and sufficient conditions for topology preserving operators are reported. These results provide the theoretical background to various topological algorithms including thinning, shrinking, generating discrete Voronoi diagrams, and contour smoothing on the triangular grid.

Electric Vehicles (EVs) are the future of transportation, but due to their battery and charging technology they cannot yet directly replace traditional vehicles. Nonetheless, EVs are a great option for city-logistics, due to the small distances and their zero local emissions. In this paper, a novel variant of the Electric Vehicle Routing Problem (EVRP), called Close-Open EVRP (COEVRP), is presented. It considers ending EV trips at Charging Stations, as opposed to other EVRP variants that only allow for en-route charging. This new variant follows a traditional routing scheme, allowing EVs to recharge only at the end of their route. The objective is to minimize energy consumption, as well as the number of vehicles. The energy consumption function takes into account the weight of the transported items. A mathematical formulation for the problem is presented and small instances were solved using a commercial solver. To solve larger instances, a hybrid metaheuristic combining Simulated Annealing and Variable Neighborhood Search algorithm was employed and thoroughly tested.

A multi-armed bandit episode consists of n trials, each allowing selection of one of K arms, resulting in payoff from a distribution over [0,1] associated with that arm. We assume contextual side information is available at the start of the episode. This context enables an arm predictor to identify possible favorable arms, but predictions may be imperfect so that they need to be combined with further exploration during the episode. Our setting is an alternative to classical multi-armed bandits which provide no contextual side information, and is also an alternative to contextual bandits which provide new context each individual trial. Multi-armed bandits with episode context can arise naturally, for example in computer Go where context is used to bias move decisions made by a multi-armed bandit algorithm. The UCB1 algorithm for multi-armed bandits achieves worst-case regret bounded by $O\left(\sqrt{Kn\log(n)}\right)$ . We seek to improve this using episode context, particularly in the case where K is large. Using a predictor that places weight M i  > 0 on arm i with weights summing to 1, we present the PUCB algorithm which achieves regret $O\left(\frac{1}{M_{\ast}}\sqrt{n\log(n)}\right)$ where M  ∗  is the weight on the optimal arm. We illustrate the behavior of PUCB with small simulation experiments, present extensions that provide additional capabilities for PUCB, and describe methods for obtaining suitable predictors for use with PUCB.

SAT Competition 2002 held in March–May 2002 in conjunction with SAT 2002 (the Fifth International Symposium on the Theory and Applications of Satisfiability Testing). About 30 solvers and 2300 benchmarks took part in the competition, which required more than 2 CPU years to complete the evaluation. In this report, we give the results of the competition, try to interpret them, and give suggestions for future competitions.

There has been a long-lasting misunderstanding in the literature of artificial intelligence and uncertainty modeling, regarding the role of fuzzy set theory and many-valued logics. The recurring question is that of the mathematical and pragmatic meaningfulness of a compositional calculus and the validity of the excluded middle law. This confusion pervades the early developments of probabilistic logic, despite early warnings of some philosophers of probability. This paper tries to clarify this situation. It emphasizes three main points. First, it suggests that the root of the controversies lies in the unfortunate confusion between degrees of belief and what logicians call “degrees of truth”. The latter are usually compositional, while the former cannot be so. This claim is first illustrated by laying bare the non-compositional belief representation embedded in the standard propositional calculus. It turns out to be an all-or-nothing version of possibility theory. This framework is then extended to discuss the case of fuzzy logic versus graded possibility theory. Next, it is demonstrated that any belief representation where compositionality is taken for granted is bound to at worst collapse to a Boolean truth assignment and at best to a poorly expressive tool. Lastly, some claims pertaining to an alleged compositionality of possibility theory are refuted, thus clarifying a pervasive confusion between possibility theory axioms and fuzzy set basic connectives.