ABSTRACT. Some ten years ago, when I left Xerox PARC to work for a search startup, I hadn’t realized how much the work I had done till then was not mine and could not be continued, for licensing reasons. For almost nine years at PARC I worked on a project to create logic from language, the Bridge project, using a collection of technologies developed by a strong collection of researchers, through at least two decades, under the leadership of Bobrow and Kaplan. I decided that I needed to redo my part of this work, using only open source tools, as I was not ready to give up on the idea of logic from language. I gave a talk at SRI, explaining my reasons and plans, published in ENTCS as ”Bridges from Language to Logic: Concepts, Contexts and Ontologies”, LSFA2010. This talk recalls and unifies some of the research that came up from this project and that is scattered in applications. We focus on a methodology for producing specific domain knowledge from text that we hope to improve, but that is already producing promising initial results, based on Universal Dependencies

ABSTRACT. Three connections between Dynamic Programming (DP) and Constraint Programming (CP) have previously been explored in the literature: DP-based global constraints, DP-like memoisation during tree search to avoid recomputing results, and subsumption of both by bucket elimination. In this paper we propose a new connection: many discrete DP algorithms can be directly modelled and solved as a constraint satisfaction problem (CSP) without backtracking. This has applications including the design of monolithic CP models for bilevel optimisation. We show that constraint filtering can occur between leader and follower variables in such models, and demonstrate the method on network interdiction.

ABSTRACT. Although being quite inexpressive, the description logic (DL) FL0, which provides only conjunction, value restriction and the top concept as concept constructors, has an intractable subsumption problem in the presence of terminologies (TBoxes): subsumption reasoning w.r.t. acyclic FL0 TBoxes is coNP-complete, and becomes even ExpTime-complete in case general TBoxes are used. In the present paper, we use automata working on infinite trees to solve both standard and non-standard inferences in FL0 w.r.t. general TBoxes. First, we give an alternative proof of the ExpTime upper bound for subsumption in FL0 w.r.t. general TBoxes based on the use of looping tree automata. Second, we employ parity tree automata to tackle non-standard inference problems such as computing the least common subsumer and the difference of FL0 concepts w.r.t. general TBoxes.

ABSTRACT. We introduce the Historical Gradient Boosting Machine with the objective of improving the convergence speed of gradient boosting. Our approach is analyzed from the perspective of numerical optimization in function space and considers gradients in previous steps, which have rarely been appreciated by traditional methods. To better exploit the guiding effect of historical gradient information, we incorporate both the accumulated previous gradients and the current gradient into the computation of descent direction in the function space. By fitting to the descent direction given by our algorithm, the weak learner could enjoy the advantages of historical gradients that mitigate the greediness of the steepest descent direction. Experimental results show that our approach improves the convergence speed of gradient boosting without significant decrease in accuracy.

ABSTRACT. Service robots are becoming more and more capable but at the same time they are opaque to their users. Once a robot starts executing a task it is hard to tell what it is doing or why. To make robots more transparent to their users we propose to expand the capabilities of robots to not only execute tasks but also answer questions about their experience.

During execution, our CoBot robots record log files. We propose to use these files as a recording of the robot experience. Log files record the experience of the robot in term of its internals. To process information from the logs we define Log Primitives Operations (LPOs) that the robot can autonomously perform. Each LPO is defined in term of an operation and a set of filters. We frame the problem of understanding questions about robot past experiences, as grounding input sentences to LPOs. To do so, we introduce a probabilistic model to ground sentences to these primitives. We evaluate our approach on a corpus of 133 sentences showing that our method is able to learn the meaning of users' questions.

Finally we introduce the concept of checkable answers to have the robot provide answers that better explain the computation performed to achieve the result reported.

ABSTRACT. The Winograd Schema Challenge (WSC) ---the task of resolving pronouns in certain forms of sentences where shallow parsing techniques seem not to be directly applicable --- has been proposed as an alternative to the Turing Test. According to Levesque, having access to a large corpus of text would likely not help much in the WSC. Among a number of attempts to tackle this challenge, one particular approach has demonstrated the plau- sibility of using commonsense knowledge automatically acquired from raw text in English Wikipedia. Here, we present the results of a large-scale experiment that shows how the performance of that particular automated approach varies with the availability of training material. We compare the results of this experiment with two studies: one from the literature that inves- tigates how adult fluent speakers tackle the WSC, and one that we design and undertake to investigate how teenager non-fluent speakers tackle the WSC. We find that the perfor- mance of the automated approach correlates positively with the performance of humans, suggesting that the performance of the particular automated approach could be used as a metric of hardness for WSC instances.

ABSTRACT. Advances in state-of-the-art techniques including convolutional neural networks (CNNs) have led to improved perception in autonomous robots. However, these new techniques make the robot's decision-making process obscure even for the experts. Our goal is to automatically generate natural language explanations for robot's state and decision-making algorithms in order to help people understand how they made their decisions. Generating natural language explanations is particularly challenging for perception and other high-dimension classification tasks because 1) we lack a mapping from features to language and 2) there are a large number of features which could be explained. We present a novel approach to generating explanations that first find important features that most affect the classification output and then utilize a secondary detector to label (i.e., generate natural language groundings) only those features. We demonstrate our explanation algorithm's ability to explain our service robot's building floor identification classifier.

ABSTRACT. Software vulnerabilities in organizational computer networks can be leveraged by an attacker to gain access to sensitive information. As fixing all vulnerabilities requires much effort, it is critical to rank the possible fixes by their importance. Centrality measures over logical attack graphs, or over the network connectivity graph, often provide a scalable method for finding the most critical vulnerabilities.

In this paper we suggest an analysis of the planning graph, originating in classical planning, as an alternative for the logical attack graph, to improve the ranking produced by centrality measures. The planning graph also allows us to enumerate the set of possible attack plans, and hence, directly count the number of attacks that use a given vulnerability. We evaluate a set of centrality-based ranking measures over the logical attack graph and the planning graph, showing that metrics computed over the planning graph reduce more rapidly the set of shortest attack plans.

ABSTRACT. We assume that service robots will have spare time in between scheduled user requests, which they could use to perform additional unrequested services in order to learn a model of users' preferences and receive rewards. However, a mobile service robot is constrained by the need to travel through the environment to reach users in order to perform services for them, as well as the need to carry out scheduled user requests. We assume service robots operate in structured environments comprised of hallways and floors, resulting in scenarios where an office can be conveniently added to the robot's plan at a low cost, which affects the robot's ability to plan and learn.

We present two algorithms, Planning Thompson Sampling and Planning UCB1, which are based on existing algorithms used in multi-armed bandit problems, but are modified to plan ahead considering the time and location constraints of the problem. We compare them to existing versions of Thompson Sampling and UCB1 in two environments representative of the types of structures a robot will encounter in an office building. We find that our planning algorithms outperform the original naive versions in terms of both reward received and the effectiveness of the model learned in a simulation. The difference in performance is partially due to the fact that the original algorithms frequently miss opportunities to perform services at a low cost for convenient offices along their path, while our planning algorithms do not.

ABSTRACT. Search and optimization problems are a major arena for the practical application of Artificial Intelligence. However, when supply chain optimization and scheduling is tackled, techniques based on linear or non-linear programming are often used in preference to Evolutionary Computation such as Genetic Algorithms (GAs). It is important to analyse whether GA are suitable for continuous realworld supply chain scheduling tasks which needs adaption regularly? We analysed a practical situation of iron ore train networks which is indeed one of significant economic importance. In addition, iron ore train networks have some interesting and distinctive characteristics so analysing this situation is an important step toward understanding the performance of GA in real-world supply chain scheduling. We compared the performance of GA with Nonlinear programming heuristics and existing industry’s scheduling approaches. The main result is that our comparison of techniques here produce an example in which GAs perform well and is a cost effective approach.