Ebook: STAIRS 2012

The Sixth European Starting AI Researchers' Symposium (STAIRS 2012) took place in conjunction with the 20th European Conference on Artificial Intelligence (ECAI 2012), the Seventh Conference on Prestigious Applications of Intelligent Systems (PAIS 2012) as well as the Sixth International Symposium on Rules (RuleML 2012) in Montpellier, France, 27-28 August 2012.

STAIRS is an international meeting intended to support AI researchers from all countries at the beginning of their career: PhD students or those who have held a PhD for less than one year. STAIRS offers doctoral students and young post-doctoral AI fellows a unique and valuable opportunity to gain experience in presenting their work in a supportive scientific environment, where they can obtain constructive feedback on the technical content of their work as well as advice on how to present it, and where they can also establish contacts with the broader European AI research community.

Papers selected by the program committee through a peer-review process were presented at the symposium. The topics covered a broad spectrum of subjects in the field of AI: machine learning and data mining, constraint satisfaction problems and belief propagation, logic and resoning, dialogue and multi-agent systems, and games and planning. We had 48 submissions, of which 32 were eventually accepted for inclusion in the proceedings. To ensure the quality of the reviewing process, each paper received three reviews, and each reviewer had a quota of no more than 3 papers to review. Finally, the program committee co-chairs read borderline papers and reviewers' comments to make confident decisions for all papers.

In addition to submitted papers, we were excited to have five keynotes: Alan Bundy (University of Edinburgh), Gemma C. Garriga (INRIA Lille Nord Europe), Malte Helmert (University of Basel), Andreas Krause (ETH Zurich), and Michele Sebag (Universitè Paris Sud). We thank them for their great contributions to the program and goals of STAIRS. We would also like to thank the ECAI program commitee chair Luc De Raedt and the ECAI organizing committee chair Christian Bessiere for supporting STAIRS and for creating a perfect environment for it, as well as the local organization team. Our special thanks go to the STAIRS program committee for their work in selecting papers and providing feedback to the authors. They were:

Thomas Ågotnes, Babak Ahmadi, Natasha Alechina, Josep Lluis Arcos, Kai Arras, Roman Barták, Christian Bauckhage, Maren Bennewitz, Elizabeth Black, Sylvain Bouveret, Oliver Brock, Rui Camacho, Hubie Chen, Amanda Clare, Alvaro Collet, Fabio G. Cozman, Claudia D'Amato, Eric De La Clergerie, Sarah J. Delany, Clare Dixon, Anca Dragan, Esra Erdem, Shaheen Fatima, Alan Fern, Daan Fierens, Chiara Ghidini, Guillaume Infantes, Andreas Karwath, Ian Kash, Angelika Kimmig, Udo Kruschwitz, Oliver Kutz, Tobias Lang, Wenwen Li, Francesca A. Lisi, Weiru Liu, Manuel Lopes, Matthew Molineaux, Katarzyna Musial, Sriraam Natarajan, Mathias Niepert, Eva Onaindia, Hector Palacios, Novi Quadrianto, Achim Rettinger, Matthijs Spaan, Cyrill Stachniss, Kostas Stergiou, Florent Teichteil-Königsbuch, Matthias Thimm, Rudolph Triebel, Anni-Yasmin Turhan, Menno Van Zaanen, Wamberto Vasconcelos, Stefan Woelfl, Stefan Wrobel, Rong Zhou, Inon Zuckerman

Also many thanks to the auxiliary reviewers Nicola Fanizzi, Tias Guns, Pasquale Minervini, Marco Montali, Sergio Pajares, and Domenico Redavid. The work and help of the program committee and auxiliary reviewers are essential to the success of this symposium. The reviews that we received were of general high quality and included constructive comments to help the authors improve upon their papers.

Last but not least, we would like to thank all authors who submitted their work to this symposium. Thanks!

Bonn and Berlin, June 2012

Kristian Kersting

Marc Toussaint

This paper concerns supervised classification of text. Rocchio, the method we choose for its efficiency and extensibility, is tested on three reference corpora “20NewsGroups”, “OHSUMED” and “Reuters”, using several similarity measures. Analyzing statistical results, many limitations are identified and discussed. In order to overcome these limitations, this paper presents two main solutions: first constituting Rocchio-based classifier committees, and then using semantic resources (ontologies) in order to take meaning into consideration during text classification. These two approaches can be combined in a Rocchio-based semantic classifier committee.

In a multiagent system, coalition formation is a coordination method for agents aiming to form groups of interest. In this paper, we focus on the particular context where agents are self-interested and plan their activities. We develop a new coalition formation model that uses the plans of the agents to guide the search for the coalitions and analyzes the coalition proposals already suggested by other agents in order to derive their preferences. This eases the negotiation for the coalitions. We analyse and develop the constraints that should be enforced on self-interested agents in order to form suitable coalitions which guarantee significant solution concepts. In addition, we detail in this paper our coalition formation mechanism, we experiment and evaluate it.

In computational social choice, the complexity of changing the outcome of elections via various control actions, such as adding or deleting candidates or voters, has been studied intensely. We introduce the concept of control for judgment aggregation procedures, and study the complexity of changing the outcome of such procedures via control by adding, deleting, or replacing judges.

The solution to the problem of actual causation - i.e. determining what caused an effect in a specific scenario - put forward by Halpern and Pearl recently has received a lot of attention. It forms the basis for many other approaches within the dominant tradition of counterfactual theories of causation. However, their solution runs into a number of difficulties for a certain type of examples exhibiting so-called switching causation and early preemption. We discuss these in the light of the core concept of counterfactual dependency, and offer a comparison with the recent definition of actual causation formulated in CP-logic. We argue both that for this type of examples the CP-logic definition provides better anwers, and that it does more justice to the fundamental intuitions underlying counterfactual dependency.

This paper presents an approach to identifying geographic events and processes in temporal series of topographic data. This approach is based on a novel ontological framework which encompasses coherent representations of time, space, events, processes and the geographic features which are said to participate in events and processes. The novelty of this model lies in several characteristics, which include: (i) it comprises a flexible method of representing attributed spatial-temporal data; (ii) it provides a mechanism for grounding the ontology upon the data; (iii) it takes into account how the phenomenon of temporal vagueness can affect the representation of geographic processes; (iv) its concepts are defined in a level of detail which enables reasoning.

In this paper we present an Action Language-Logic Programming based approach to solving planning and scheduling problems in hybrid domains - domains that exhibit both discrete and continuous behavior. We use action language H to represent the domain and then translate the resulting theory into a logic program. In this way, we reduce the problem of finding solutions to planning and scheduling problems to computing models of logic programs. We present the syntax of H and model a planning and scheduling example in H. We show how to translate the resulting H theory into an equivalent logic program. We compute the models of the resulting program using EZCSP, a solver which allows us to reason about constraints over reals and compute solutions to complex planning and scheduling problems. Results have shown that our approach can be applied to any planning and scheduling problem in hybrid domains.

State of the art extension based argument acceptance is currently biased toward attacks: while the defending extension of an argument a is internally coherent, no such requirement is imposed on its attacking set. On the other hand, if we restrict ourselves only to conflict-free sets of attacking arguments, then we could have different attacking sets for a specified argument a (any two conflicting attackers of a must belong to different a's attacking sets). Having only one defending extension for all these attacking sets would contradict the deliberative nature of argumentation in the real world, where only the coherent sets of attacks matter and the defending sets of arguments depend on the former. In this paper we introduce a new type of acceptability of an argument, in which its attacking and defending sets of arguments are uniformly treated. We call it deliberative acceptance, discuss how this and the classical acceptance notions interrelate and analyze its computational properties. In particular, we prove that the corresponding decision problem is Π^P₂-complete, but its restrictions on bipartite or co-chordal argumentation frameworks are in P.

Contract Net Protocol (CNP) is a high level communication protocol. It is one of the most widely used protocols in multi-agent system (MAS) to resolve decentralized task allocation problem. The main aim of the protocol is to facilitate contract negotiation between a manager agent and many contractor agents. A lot of work has been done for the verification of the protocol and its extensions, but there still a lack of a formalism for representing temporal interaction aspects which are an essential parameter in modeling the protocol . This paper proposes to use Timed Colored Petri Nets (TCPN) to model correctly and formally this temporal dimension often defined as interaction duration and message deadlines. We will use simulation techniques and state space analysis to verify important properties namely model correctness, deadline respect, absence of deadlocks and livelocks, absence of dead code, agent terminal states consistency, concurrency and validity.

This paper addresses the problem of defining, from data, a reward function in a Reinforcement Learning (RL) problem. This issue is applied to the case of Spoken Dialogue Systems (SDS), which are interfaces enabling users to interact in natural language. A new methodology which, from system evaluation, apportions rewards over the system's state space, is suggested. A corpus of dialogues is collected on-line and then evaluated by experts, assigning a numerical performance score to each dialogue according to the quality of dialogue management. The approach described in this paper infers, from these scores, a locally distributed reward function which can be used on-line. Two algorithms achieving this goal are proposed. These algorithms are tested on an SDS and it is showed that in both cases, the resulting numerical rewards are close to the performance scores and thus, that it is possible to extract relevant information from performance evaluation to optimise on-line learning.

In most A.I. planning approaches it is assumed that the planning agent has complete knowledge about its environment. If this is the case the agent acts in two steps: It first plans and then executes its plan. However, humans do usually not behave this simple, as in most real world problems knowledge about the environment is incomplete. To solve real world problems, acting, sensing and planning has to be interleaved in a cyclic manner: Knowledge has to be acquired during plan execution and the plan has to be adopted incrementally to the acquired knowledge. In our work, we employ the Discrete Event Calculus Knowledge Theory (DECKT) and combine it with a Lazy Branching strategy to interleave planning and plan execution for problems with incomplete knowledge: We make optimistic assumptions for unknown contingencies and lazily postpone the planning for a certain contingency until it is resolved. As the Event Calculus accounts for time, the proposed approach allows to combine planning with incomplete knowledge, concurrency and explicit time.

We present a risk-aware utility model for action selection in 2-player, non-cooperative, repeated games of chance. Our model augments expected utility calculations and adapts to changes in accumulated utility, demonstrating rational game play. Motivated by risk aversion and the utility of wealth, our model is parameterized by an agent's wealth, the payoffs of a game, and the probability associated with gain and loss. Using expected utility combined with our model, we can impose desired behavior onto an agent that mimics more closely the types of behaviors we see in social and economic situations where risk is involved. We define our model theoretically and present empirical results showing the effectiveness of a risk-aware utility model against a Nash equilibrium mixed strategy in a repeated game of chance.

Automated negotiation is especially important when tasks, which require many resources, enter a Grid where resources are scarce. The level of resource scarcity dynamically changes in a Grid and the client's negotiation strategy has to adapt to this dynamism. In addition, we consider the non-transparency of a Grid with respect to a client. That is, a client is only able to observe proposals sent to it by the Grid resource allocator (GRA) but it does not have direct knowledge about availability of Grid resources. In our work, the client's strategy is to estimate the dynamism in a Grid by inferring the criteria influencing the GRA's proposals, and to adapt to this dynamism using fuzzy control rules. These rules define whether the client has to make smaller or larger concessions towards the GRA considering Grid dynamism. The simulation results show that a client who applies our adaptive negotiation strategy can obtain higher utility and significantly reduce the number of failed negotiations comparing to a client who applies the non-adaptive negotiation strategy.

This paper provides a framework for argumentation-based persuasion dialogues that enables a participant to implement strategies based on its modelling of its interlocutor's knowledge. The framework is defined on the basis of the recent ASPIC⁺ general model of argumentation, and thus accommodates a range of pos sible instantiations. We extend existing works on persuasion by accounting for both admissible and grounded semantics, and also by allowing participants to not only move arguments that attack those of their interlocutor, but also preferences which undermine the success of these attacks as defeats. We also state formal results for these dialogues, and then use these dialogues to illustrate that appropriate mechanisms for strategising need to account for the logical content of arguments, rather than just rely on their abstract specification.

Valued Constraint Satisfaction Problems (VCSPs) can model many combinatorial problems. VCSPs that involve submodular valuation functions only is a particular class of VCSPs that have the advantage of being tractable. In this paper, we propose a problem decomposition strategy for binary VCSPs which consists in decomposing the problem to be solved into a set of submodular, and then tractable, subproblems. The decomposition strategy combines two problem solving techniques, namely domain partitioning and value permutation.

In this work, we analyze and improve upon reinforcement learning techniques used to build agents that can learn to play Infinite Mario, an action game. We use the object-oriented representation with the hierarchical RL model as a learning framework. We then extend the idea of hierarchical RL by designing a hierarchy in action selection using domain specific knowledge. Using experimental results, we show that this approach facilitates faster and efficient learning for the domain.

We describe NORMC, a model checker for Norm Compliance CTL, a temporal logic for reasoning about compliance in normative systems, implemented in the Haskell programming language. NORMC is intended as a tool for students, researchers, and practitioners to learn about and understand normative systems, and as an exploratory tool for researchers in multi-agent systems. The objectives of the paper are twofold. First, to give a system description of NORMC. Second, to argue and demonstrate that the Haskell programming language is a natural and useful alternative for model checking multi-agent systems; in particular that the full power of Haskell makes it easy to describe arbitrary multi-agent state-transition models in a natural way.

A number of problems in statistical physics and computer science can be expressed as the computation of marginal probabilities over a Markov random field. Belief propagation, an iterative message-passing algorithm, computes exactly such marginals when the underlying graph is a tree. But it has gained its popularity as an efficient way to approximate them in the more general case, even if it can exhibits multiple fixed points and is not guaranteed to converge. In this paper, we express a new sufficient condition for local stability of a belief propagation fixed point in terms of the graph structure and the beliefs values at the fixed point. This gives credence to the usual understanding that Belief Propagation performs better on sparse graphs.

Currently there is extensive theoretical work on inconsistencies in logic-based systems. Recently, algorithms for identifying inconsistent clauses in a single conjunctive formula have demonstrated that practical application of this work is possible. However, these algorithms have not been extended for full knowledge base systems and have not been applied to real-world knowledge. To address these issues, we propose a new algorithm for finding the inconsistencies in a knowledge base using existing algorithms for finding inconsistent clauses in a formula. An implementation of this algorithm is then presented as an automated tool for finding inconsistencies in a knowledge base and measuring the inconsistency of formulae. Finally, we look at a case study of a network security rule set for exploit detection (QRadar) and suggest how these automated tools can be applied.

Multiagent resource allocation deals with distributing (bundles) of resources to agents that specify utility functions over bundles. A natural and important problem in this field is social welfare optimization. We assume resources to be indivisible and nonshareable and that utility functions are represented by the k-additive form or as straight-line programs. We prove NP-completeness for egalitarian and Nash product social welfare optimization for straight-line program representation of utility functions. In addition, we show that social welfare optimization by the Nash product in the 1-additive form is hard to approximate, yet we also give fully polynomial-time approximation schemes for egalitarian and Nash product social welfare optimization in the 1-additive form with a fixed number of agents.

Knowledge compilation structures such as MDDs have been proposed as a way to compile CSPs, to make requests tractable online, in cases where solving is not possible. This paper studies the interest in relaxing two assumptions usually imposed on MDDs, static ordering and read-once property, using a new compilation structure called Set-labeled Diagrams, which are compiled by tracing the search tree explored by a CSP solver. The impact of read-once and static ordering is assessed by simply playing on the variable choice heuristics used during search in the CSP solver.

Resources are taking into account when designing business processes, but, under certain circumstances, they should be scheduled when business processes are enacted. Nowadays, the decentralization of the activities and outsourcing of certain tasks to third party companies is increasing the complexity of the resource allocation for business process. Moreover, some activities cannot be scheduled in advance, because they depend on some decision points in the business process, forcing the allocation of resources to tasks on the go. To deal with these issues we present a multi-attribute auction mechanism. Auctions are a market mechanism that facilitate the resource allocation in open, distributed scenarios. The auction model we are presenting is multi-attribute, so in addition to deal with the economic costs of the allocations, it enables the inclusion of other attributes, such as finishing on time or the quality of the outcomes. We have tested our proposal in a simulated framework and the results show about the benefits of using different attributes, in addition of providing privacy relationships among business process and resource providers.

This work describes a new best-first bidirectional heuristic search algorithm with two phases. The new algorithm is based on a critical review of the basic search reduction operations in previous algorithms like BS* or Switch-A*. The general guideline is to let search fronts meet as close to midground as possible. In a first phase, search is discontinued at nodes as soon as the opposite frontier is met, terminating when one of the fronts runs out of open nodes. In a second phase, unidirectional search is conducted from the discontinued nodes until an optimal solution can be guaranteed. The new algorithm is tested on random instances of the 15-puzzle and on path-finding problems. A significant improvement in efficiency is observed when compared with other bidirectional algorithms.

We propose a non-standard modal logic for specifying agent domains where the agent's actuators and sensors are noisy, causing uncertainty in action and perception. The logic is multi-modal, indexed with actions; the logic is also augmented with observation objects to facilitate knowledge engineers dealing with explicit observations in the environment, and it includes a notion of probability. A tableau method is provided for proving decidability of the proposed logic. It is our conjecture that the tableau rules are complete with respect to the semantics. The proof does not yet exist, however, we discuss the current approach of the proof and provide some examples to motivate our conjecture.

Path-disruption games, recently introduced by Bachrach and Porat [1], are coalitional games played on graphs where one or multiple adversaries each seek to reach a given target vertex from a given source vertex and a coalition of agents seeks to prevent that from happening by blocking every path from the source to the target, for each adversary. We expand their model by allowing uncertainty about the targets. In probabilistic path-disruption games, we assign to each vertex the probability that an adversary wants to reach it. We study the complexity of various problems related to such games.