Ebook: STAIRS 2016

These are the proceedings of the 8th European Starting AI Researcher Symposium (STAIRS), held as a satellite event of the 22th European Conference on Artificial Intelligence (ECAI) in The Hague, Netherlands, on 29th and 30th of August 2016. STAIRS is aimed at young researchers in Europe and elsewhere, particularly PhD students. It provides not only an opportunity to submit and present work at an international event with a broad scientific scope and a peer review process, but also the chance to discuss, receive constructive feedback and explore research interests and career opportunities.

The Call for Papers solicited submissions from all areas of AI, ranging from foundations to applications. Topics included applications of AI; autonomous agents and multiagent systems; case-based reasoning; cognitive modelling and cognitive architectures; computational creativity; constraints, satisfiability, and search; information retrieval and natural language processing; knowledge representation, reasoning, and logic; machine learning and data mining; model based reasoning; natural language processing; planning and scheduling; robotics, perception, vision and sensing; social intelligence and socio-cognitive systems; uncertainty in AI; web and knowledge-based information systems and multidisciplinary topics. In short, the scope of STAIRS is the same as that of the major international conferences in AI. What sets STAIRS apart is that the principal author of every submitted paper must be a young researcher who either does not yet hold a PhD or who has obtained their PhD less than one year before the paper submission deadline.

We received a total of 39 submissions, from Europe and beyond. All of them were carefully reviewed by the STAIRS Programme Committee, consisting of leading European researchers who together cover the depth and breadth of the AI field. We are very grateful for the great service provided by these colleagues, as well as by the additional reviewers assisting them in their task. In the end, 11 papers were accepted for oral presentation at the symposium, and a further 10 for presentation during a poster session. These 21 accepted papers are included in this volume. Part I contains the long papers that will be presented orally at the symposium; Part II contains both long and short papers that will be presented in poster sessions.

The body of submitted papers covers the field of AI well, with social intelligence and socio-cognitive systems, machine learning and data mining, autonomous agents and multiagent systems, being the areas attracting the largest numbers of submissions. Among the papers collected here there is a good balance between foundational issues and AI applications. The problems they tackle range widely from classical AI themes such as planning and scheduling, and natural language processing, to questions related to decision theory and games, as well to other, newly emerging areas.

The STAIRS programme will be enriched by several keynote talks. At the time of writing the confirmed speakers are Virginia Dignum, Professor in the Faculty of Technology, Policy and Management at the Delft University of Technology, Frank van Harmelen, Professor in Knowledge Representation and Reasoning at the Free University Amsterdam, Ramon López de Mántaras, Research Professor and Director of the Research Centre for Artificial Intelligence, IIIA, of the Spanish Council for Scientific Research, Barcelona, and Stefan Woltran, Professor for Formal Foundations of Artificial Intelligence at the Vienna University of Technology. We are very grateful to all of them for accepting our invitation. We are looking forward to an exciting two days in The Hague, and we hope that readers of this volume will find it as valuable as we have in providing a clear picture of current developments in our field.

July 2016

H. Sofia Pinto

David Pearce

Enabling robotic systems to collaborate with humans is a challenging task, on different levels of abstraction. Such systems need to understand the context under which they operate, by perceiving, planning and reasoning to team up with a human. The robotic system should also have perspective taking capabilities in order to efficiently collaborate with the human. In this work an integrated cognitive architecture for human robot collaboration, that aims to develop perspective taking capabilities using human preferences, is proposed. This is achieved by developing a ‘mental model’ that takes human preferences, the knowledge of the task (including the objects), and the capabilities of the human and the robot. This mental model forms the basis of the cognitive architecture, to perceive, reason and plan in the human-robot collaborative scenario. The robotic platform guided by the cognitive architecture, performs ‘picking’, ‘showing’, ‘placing’ and ‘handover’ actions on real world objects (of interest in the assembly process) in coordination with the human. The goal is to answer the ‘how’ (how a manipulation action should be carried out by the robot in a dynamically changing environment) and the ‘where’ (where the manipulation action should take place) of the assembly process considering/given varying human preferences. We show that the proposed cognitive architecture is capable of answering these questions through various experiments and evaluation.

This paper addresses vectorial form of Markov Decision Processes (MDPs) to solve MDPs with unknown rewards. Our method to find optimal strategies is based on reducing the computation to the determination of two separate polytopes. The first one is the set of admissible vector-valued functions and the second is the set of admissible weight vectors. Unknown weight vectors are discovered according to an agent with a set of preferences. Contrary to most existing algorithms for reward-uncertain MDPs, our approach does not require interactions with user during optimal policies generation. Instead, we use a variant of approximate value iteration on vectorial value MDPs based on classifying advantages, that allows us to approximate the set of non-dominated policies regardless of user preferences. Since any agent's optimal policy comes from this set, we propose an algorithm for discovering in this set an approximated optimal policy according to user priorities while narrowing interactively the weight polytope.

Opponent modeling consists in modeling the strategy or preferences of an agent thanks to the data it provides. In the context of automated negotiation and with machine learning, it can result in an advantage so overwhelming that it may restrain some casual agents to be part of the bargaining process. We qualify as “curious” an agent driven by the desire of negotiating in order to collect information and improve its opponent model. However, neither curiosity-based rationality nor curiosity-robust protocol have been studied in automatic negotiation. In this paper, we rely on mechanism design to propose three extensions of the standard bargaining protocol that limit information leak. Those extensions are supported by an enhanced rationality model, that considers the exchanged information. Also, they are theoretically analyzed and experimentally evaluated.

Simulating emotions within a group of agents has been shown to support co-operation in the prisoner's dilemma game. Most work on simulating these emotions has focused on environments where the agents do not move, that is, they are static and their neighbours are fixed. However, it has also been shown in other work that when an agent is given the ability to move, then the type of the environment affects how co-operation evolves in the group of agents. In this paper, we investigate the combination of these two ideas in an experimental study that explores the effects on co-operation when autonomous agents that can show emotions are given the ability to move within structured environments. We observe that once mobility is introduced, different strategies become successful. Successful strategies respond quickly to defection, while not immediately reciprocating co-operation, regardless of the environment type. The further an agent travels, the higher its average payoff in a small world environment. The slower an agent is to copy another agent by imitating its strategy, the higher its increase in average payoff.

Usually, clustering algorithms consider that document collections are static and are processed as a whole. However, in contexts where data is constantly being produced (e.g. the Web), systems that receive and process documents incrementally are becoming more and more important. We propose OHDOCLUS, an online and hierarchical algorithm for document clustering. OHDOCLUS creates a tree of clusters where documents are classified as soon as they are received. It is based on COBWEB and CLASSIT, two well-known data clustering algorithms that create hierarchies of probabilistic concepts and were seldom applied to text data. An experimental evaluation was conducted with categorized corpora, and the preliminary results confirm the validity of the proposed method.

Single-peakedness is one of the most important and well-known domain restrictions on preferences. The computational study of single-peaked electorates has largely been restricted to elections with tie-free votes, and recent work that studies the computational complexity of manipulative attacks for single-peaked elections for votes with ties has been restricted to nonstandard models of single-peaked preferences for top orders. We study the computational complexity of manipulation for votes with ties for the standard model of single-peaked preferences and for single-plateaued preferences. We show that these models avoid the anomalous complexity behavior exhibited by the other models. We also state a surprising result on the relation between the societal axis and the complexity of manipulation for single-peaked preferences.

Levesque has argued that the problem of resolving difficult pronouns in a carefully chosen set of twin sentences, which he refers to as the Winograd Schema Challenge (WSC), could serve as a conceptually and practically appealing alternative to the well-known Turing Test. As he said, probably anything that answers correctly a series of these questions is thinking in the full-bodied sense we usually reserve for people. In this paper we examine the task of resolving cases of definite pronouns. Specifically, we examine those for which traditional linguistic constraints on co-reference as well as commonly-used resolution heuristics are not useful, or the procedure they follow is very similar to a statistical approach, without invoking common logic like humans do.

State-of-the-art belief space planning (BSP) approaches assume data association to be solved or given. Some of the current authors have recently proposed a relaxation of this assumption, resulting in a more general framework of belief space planning where data association is incorporated within the belief (DA-BSP). Unfortunately, this can quickly become intractable under non-myopic planning. In this work, we seek to harness recent approaches in formal methods (specifically, linear temporal logic in the context of planning under uncertainty), to obtain formal-DA-BSP, an approach that incorporates high-level domain knowledge, to obtain more tractable planning. Thanks to generalised form of specification, the framework can also incorporate other complexities including explicit collision probability and determining planning horizon. The initial concepts are shown in an abstracted example of a robot janitor lost in one of the two floors.

Path-disruption games are a class of cooperative games in which agents try to block any path from an intruder's source vertex to a target vertex. We study algorithmic properties and characterizations of the least core and the cost of stability for these games.

This work presents a knowledge acquisition platform and a certain game developed on that platform for endowing machines with common sense, by following a hybrid approach that combines crowdsourcing techniques, knowledge engineering, and automated reasoning. Short narratives are presented to players, who are asked to combine fragments of text into rules that would correctly answer a given question, to evaluate the appropriateness of gathered rules, and to resolve conflicts between them by assigning priorities. The text fragments that are used are a priori translated by a knowledge engineer into a machine-readable predicate form. Players are rewarded based not only on their inter-agreement (as in most games with a purpose) but also based on the objective ability of the rules to answer questions correctly, as determined by an underlying reasoning engine. Beyond discussing the knowledge acquisition platform and the game design, we analyze the common sense that has been gathered during the deployment of the game over a five-month period and we use the acquired knowledge to answer questions on unknown stories.

In order to enhance the behavior of autonomous service robots, we are exploring multiple paradigms for their planning and execution strategy (the way of interleaving the planning, selection and execution of actions). In this paper we focus on continuous proactive planning with multiple hypotheses in order to continuously generate multiple solution-plans from which an action can be selected when appropriate. To illustrate the concepts, we develop how it could be used for autonomous navigation in dynamic environments, and analyze the tests we realized with several instantiations. We also discuss several aspects and concerns about the proposed strategy, and how integrating more semantic information could enhance the capabilities of service robots for real-world applications.

Anomaly detection is an important problem with many applications in industry. This paper introduces a new methodology for detecting anomalies in a real laser heating surface process recorded with a high-speed thermal camera (1000 fps, 32×32 pixels). The system is trained with non-anomalous data only (32 videos with 21500 frames). The proposed method is built upon kernel density estimation and is capable of detecting anomalies in time-series data. The classification should be completed in-process, that is, within the cycle time of the workpiece.

This paper proposes a new repair operator to be used inside algorithms based on the concept of Search by Column Generation (SearchCol). This concept has revealed to be suitable to address problems represented by models that decompose the problem into several subproblems and in which a global solution can be obtained by combining solutions of the subproblems. SearchCol starts by solving the linear relaxation of the integer programming decomposition model using column generation. Metaheuristics are then used to search for the best global integer solution by combining subproblems' solutions. The new repair operator intents to fix the invalid solutions but ends up has a generator of new subproblems' solutions and allows to change the search space as the metaheuristic explores the search space. The success of the repair operator is verified in a SearchCol based evolutionary algorithm to solve a Bus Driver Rostering Problem.

This paper presents a method for using topic distributions generated from topic models as features for performing sentiment analysis on documents. This will be tested in the social media domain, specifically Twitter. The proposed approach allows for the mapping from word space to topic space which allows for less features to be needed and also reduces computational complexity. Multiple machine learning algorithms will be used to test the topic model generated features and a number of different versions of test corpus will be used, including unigrams, bigrams, part-of-speech tagging and adjectives only. The method proposed will also be compared to other notable topic-sentiment methods such as the aspect-sentiment unification model and the joint sentiment/topic model. The results show that using topic distributions can improve the accuracy of classification algorithms, however, the performance can be dependent on the algorithm used and the initial features used. Additionally, we show that using only topics as features outperforms the hybrid topic-sentiment models.

The wide spread of low-cost personal devices equipped with GPS sensors has paved the way towards the creation of customized services based on user mobility habits and able to track and assist users in everyday activities, according to their current location.

In this paper we propose a new approach to extraction and comparison of mobility models, by means of the structure inferred from positioning data. More specifically, we suggest to use concepts and methods borrowed from Algorithmic Learning Theory (ALT) and we formulate mobility models extraction in term of Grammatical Inference (GI), an inductive process able to select the best grammar consistent with the samples and to provide multi-scale generative models. Moreover, we propose a similarity measure by adapting a state-of-the-art metric originally conceived for automata.

A thorough experimental assessment was conducted on the publicly available dataset provided by the Geolife project. Results show how a structural model and similarity metric can provide a better insight on data despite its complexity.

Many real-world problems are encoded into SAT instances and efficiently solved by CDCL (Conflict-Driven Clause Learning) SAT solvers. However, some scenarios require distributed problem solving approaches. Privacy is often the main reason. This motivates the need to solve distributed SAT problems We analyze how this problem can be tacked in an efficient way, and present ABTSAT, a new version of the ABT (Asynchronous Backtracking) algorithm adapted to solve distributed SAT instances. It combines ABT execution with calls to CDCL SAT solvers and clause learning. ABTSAT is sound and complete, properties inherited from ABT, and solves local problems efficiently by using CDCL SAT solvers.

Many efficient path planners have been invented for finding paths while avoiding obstacles in a dynamic environment. However, most global path planning methods focus on problems where the knowledge of the environment is deterministic or that the states of the environment are stationary over time. This paper aims to introduce a path planning method to avoid obstacles which have a probabilistic moving pattern. Such approach can find its wide use in planning applications for unmanned aerial vehicles (UAVs), which not only have to avoid no-fly zones delimited by the airspace, but also zones of hazardous weather conditions such as turbulences and clouds, which move over time. First a spatiotemporal state space is defined to provide a formal representation of the time-varying search problem. The benefit of a spatiotemporal state space for the path planning of a vehicle moving in a time-varying vector field is also highlighted. Then a linear probabilistic movement model based on Gaussian distribution is proposed to estimate the probability of a state being occupied by obstacles. This probability is subsequently used to compute the travel cost in a discrete shortest path search. Finally, a fast subset path planning/ replanning method is introduced. The planning method consists of performing the search on a selected subset of the state-space to reduce computation runtime. By adapting the subset of the state space, the efficiency of the search can be greatly increased and hence a fast global replanning is possible. An efficient replanning is necessary since the UAV cannot remain stationary while waiting for a new path planned.

This work aims at creating a user recommender system that recommends relevant people to follow for twitter users. We propose to use a novel topic modeling method Biterm Topic Model (BTM) to profile users into vectors of bag of words. We then propose an algorithm that uses both social network relationship information and the user-generated content modeled through BTM to recommend twitter followees. A preliminary evaluation is carried out on the implementation of this technique that shows BTM performs well in making valid recommendations to twitter users. We also found that considering both user generated content and social relationships for recommending followees helped improve the results.

In computer and robotic vision point clouds from depth sensors have to be processed to form higher-level concepts such as lines, planes, and objects. Bayesian methods formulate precisely prior knowledge with respect to the noise and likelihood of points given a line, plane, or object. Nonparametric methods also formulate a prior with respect to the number of those lines, planes, or objects. Recently, a nonparametric Bayesian method has been proposed to perform optimal inference simultaneously over line fitting and the number of lines. In this paper we propose a nonparametric Bayesian method for segment fitting. Segments are lines of finite length. This requires 1.) a prior for line segment lengths: the symmetric Pareto distribution, 2.) a sampling method that handles nonconjugacy: an auxiliary variable MCMC method. Results are measured according to clustering performance indicators, such as the Rand Index, the Adjusted Rand Index, and the Hubert metric. Surprisingly, the performance of segment recognition is worse than that of line recognition. The paper therefore concludes with recommendations towards improving Bayesian segment recognition in future work.

This paper describes our research-in-progress into providing content-agnostic procedural content generation for computer games via answer set programming and a formal semantic description of the design space. Existing generative approaches are often closely coupled to a particular form of content and/or game, limiting opportunities for re-use—a dungeon level generator in one game is substantially different to a sci-fi weapon generator in another. We propose an approach involving a re-usable generator system that is able to produce and refine a model of any structured content from formal desired properties produced by designers. As an intermediate step towards this system for multi-purpose content generation we present initial work on generating content within a commercial game engine, using answer set programming to generate varied and challenging combat progressions for third-person action/combat games. By using semantic models as input for a content-agnostic generation system, we hope to provide more domain-general content generation.

Author profiling and Gender Identification have gained relevance in the last few years. The goal of the research in these fields is to extract certain demographic information on the authors of texts by analyzing their writing at several levels. In our work, we address the problem of the identification of the gender (male vs. female) of the authors of opinion pieces published online. Unlike the overwhelming majority of the proposals, we argue that the use of deeper linguistic features (i.e., syntactic and discourse structure), instead of mainly lexical features leads to a higher accuracy of gender identification. Using such features with supervised machine learning, we achieve very competitive results with accuracies over 84%.