Inconsistencies between different information sources may arise because of statements that are inaccurate, albeit not completely false. In such scenarios, the most natural way to restore consistency is often to interpret assertions in a more flexible way, i.e. to enlarge (or relax) their meaning. As this process inherently requires extra-logical information about the meaning of atoms, extensions of classical merging operators are needed. In this paper, we introduce syntactic merging operators, based on possibilistic logic, which employ background knowledge about the similarity of atomic propositions to appropriately relax propositional statements.

We present a fast local search algorithm that finds an improved solution (if there is any) in the k-exchange neighborhood of the given solutionto an instance of Weighted Feedback Arc Set in Tournaments. More precisely,given an arc weighted tournament T on n vertices and a feedback arc set F (a set of arcs whose deletion from T turns it into a directed acyclic graph), our algorithm decides in time O(2 o ( k ) n log n) if there is a feedback arc set of smaller weight and that differs from F in at most k arcs. To our knowledge this is the first algorithm searching the k -exchange neighborhood of an NP-complete problem that runs in (parameterized) subexponential time. Using this local search algorithm for Weighted Feedback Arc Set in Tournaments, we obtain subexponential time algorithms for a local search variant of Kemeny Ranking — a problem in social choice theory and of One-Sided Cross Minimization — a problem in graph drawing.

In several application areas for Planning, in particular helping with the creation of new processes in Business Process Management (BPM), a major obstacle lies in the modeling. Obtaining a suitable model to plan with is often prohibitively complicated and/or costly. Our core observation in this work is that, for software-architectural purposes, SAP is already using a model that is essentially a variant of PDDL. That model describes the behavior of Business Objects, in terms of status variables and how they are affected by system transactions. We show herein that one can leverage the model to obtain (a) a promising BPM planning application which incurs hardly any modeling costs, and (b) an interesting planning benchmark. We design a suitable planning formalism and an adaptation of FF, and we perform large-scale experiments. Our prototype is part of a research extension to the SAP NetWeaver platform.

People constantly apply acquired knowledge to new learning tasks, but machines almost never do. Research on transfer learning attempts to address this dissimilarity. Working within this area, we report on a procedure that learns and transfers constraints in the context of inductive process modeling, which we review. After discussing the role of constraints in model induction, we describe the learning method, MISC, and introduce our metrics for assessing the cost and benefit of transferred knowledge. The reported results suggest that cross-domain transfer is beneficial in the scenarios that we investigated, lending further evidence that this strategy is a broadly effective means for increasing the efficiency of learning systems. We conclude by discussing the aspects of inductive process modeling that encourage effective transfer, by reviewing related strategies, and by describing future research plans for constraint induction and transfer learning.

Developing a robust, flexible, closed-loop walking algorithm for a humanoid robot is a challenging task due to the complex dynamics of the general biped walk. Common analytical approaches to biped walk use simplified models of the physical reality. Such approaches are partially successful as they lead to failures of the robot walk in terms of unavoidable falls. Instead of further refining the analytical models, in this work we investigate the use of human corrective demonstrations, as we realize that a human can visually detect when the robot may be falling. We contribute a two-phase biped walk learning approach, which we experiment on the Aldebaran NAO humanoid robot. In the first phase, the robot walks following an analytical simplified walk algorithm, which is used as a black box, and we identify and save a walk cycle as joint motion commands. We then show how the robot can repeatedly and successfully play back the recorded motion cycle, even if in open-loop. In the second phase, we create a closed-loop walk by modifying the recorded walk cycle to respond to sensory data. The algorithm learns joint movement corrections to the open-loop walk based on the corrective feedback provided by a human, and on the sensory data, while walking autonomously. In our experimental results, we show that the learned closed-loop walking policy outperforms a hand-tuned closed-loop policy and the open-loop playback walk, in terms of the distance traveled by the robot without falling.

People tracking is a key technology for autonomous systems, intelligent cars and social robots operating in populated environments. What makes the task difficult is that the appearance of humans in range data can change drastically as a function of body pose, distance to the sensor, self-occlusion and occlusion by other objects. In this paper we propose a novel approach to pedestrian detection in 3D range data based on supervised learning techniques to create a bank of classifiers for different height levels of the human body. In particular, our approach applies AdaBoost to train a strong classifier from geometrical and statistical features of groups of neighboring points at the same height. In a second step, the AdaBoost classifiers mutually enforce their evidence across different heights by voting into a continuous space. Pedestrians are finally found efficiently by mean-shift search for local maxima in the voting space. Experimental results carried out with 3D laser range data illustrate the robustness and efficiency of our approach even in cluttered urban environments. The learned people detector reaches a classification rate up to 96% from a single 3D scan.

This paper summarizes our line of research about the introduction of function symbols (functions) in Answer Set Programming (ASP) – a powerful language for knowledge representation and reasoning. The undecidability of reasoning on ASP with functions, implied that functions were subject to severe restrictions or disallowed at all, drastically limiting ASP applicability. We overcame most of the technical difficulties preventing this introduction, and we singled out a highly expressive class of programs with functions (FG-programs), allowing the (possibly recursive) use of function terms in the full ASP language with disjunction and negation. Reasoning on FG-programs is decidable, and they can express any computable function (causing membership in this class to be semi-decidable). We singled out also FD-programs, a subset of FG-programs which are effectively recognizable, while keeping the computability of reasoning. We implemented all results into the DLV system, thus obtaining an ASP system allowing to encode any computable function in a rich and fully declarative KRR language, ensuring termination on every FG program. Finally, we singled out the class of DFRP programs, where decidability of reasoning is guaranteed and Prolog-like functions are allowed.

This paper describes a system called SITAC based on our proposed approach to discover concepts (called SITACs) in text archives that are identical semantically but alter their names over time. Our approach integrates natural language processing, association rule mining and contextual similarity to discover SITACs in order to answer historical queries over text corpora.

Correcting recognition errors is often necessary in a speech interface. These errors not only reduce users' overall entry rate, but can also lead to frustration. While making fewer recognition errors is undoubtedly helpful, facilities for supporting user-guided correction are also critical. We explore how to better support user corrections using Parakeet — a continuous speech recognition system for mobile touch-screen devices. Parakeet's interface is designed for easy error correction on a handheld device. Users correct errors by selecting alternative words from a word confusion network and by typing on a predictive software keyboard. Our interface design was guided by computational experiments and used a variety of information sources to aid the correction process. In user studies, participants were able to write text effectively despite sometimes high initial recognition error rates. Using Parakeet as an example, we discuss principles we found were important for building an effective speech correction interface.

We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost. We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.