We present a new and compelling approach to the efficient solution of important computational problems that arise in the context of abstract argumentation. Our approach makes known algorithms defined for restricted fragments generally applicable, at a computational cost that scales with the distance from the fragment. Thus, in a certain sense, we gradually augment tractable fragments. Surprisingly, it turns out that some tractable fragments admit such an augmentation and that others do not. More specifically, we show that the problems of credulous and skeptical acceptance are fixed-parameter tractable when parameterized by the distance from the fragment of acyclic argumentation frameworks. Other tractable fragments such as the fragments of symmetrical and bipartite frameworks seem to prohibit an augmentation: the acceptance problems are already intractable for frameworks at distance 1 from the fragments. For our study we use a broad setting and consider several different semantics. For the algorithmic results we utilize recent advances in fixed-parameter tractability.

We present Constituent Grammatical Evolution (CGE), a new evolutionary automatic programming algorithm that extends the standard Grammatical Evolution algorithm by incorporating the concepts of constituent genes and conditional behaviour-switching. CGE builds from elementary and more complex building blocks a control program which dictates the behaviour of an agent and it is applicable to the class of problems where the subject of search is the behaviour of an agent in a given environment. It takes advantage of the powerful Grammatical Evolution feature of using a BNF grammar definition as a plug-in component to describe the output language to be produced by the system. The main benchmark problem in which CGE is evaluated is the Santa Fe Trail problem using a BNF grammar definition which defines a search space semantically equivalent with that of the original definition of the problem by Koza. Furthermore, CGE is evaluated on two additional problems, the Los Altos Hills and the Hampton Court Maze. The experimental results demonstrate that Constituent Grammatical Evolution outperforms the standard Grammatical Evolution algorithm in these problems, in terms of both efficiency (percent of solutions found) and effectiveness (number of required steps of solutions found).

This paper examines an extended double auction model where market clearing is restricted by temporal constraints. It is found that the allocation problem in this model can be effectively transformed into a weighted bipartite matching in graph theory. By using the augmentation technique, we propose a Vickrey-Clarke-Groves (VCG) mechanism in this model and demonstrate the advantages of the payment compared with the classical VCG payment (the Clarke pivot payment). We also show that the algorithms for both allocation and payment calculation run in polynomial time. It is expected that the method and results provided in this paper can be applied to the design and analysis of dynamic double auctions and futures markets.

In this work we propose an approach for generalization in continuous domain Reinforcement Learning that, instead of using a single function approximator, tries many different function approximators in parallel, each one defined in a different region of the domain. Associated with each approximator is a relevance function that locally quantifies the quality of its approximation, so that, at each input point, the approximator with highest relevance can be selected. The relevance function is defined using parametric estimations of the variance of the q-values and the density of samples in the input space, which are used to quantify the accuracy and the confidence in the approximation, respectively. These parametric estimations are obtained from a probability density distribution represented as a Gaussian Mixture Model embedded in the input-output space of each approximator. In our experiments, the proposed approach required a lesser number of experiences for learning and produced more stable convergence profiles than when using a single function approximator.

Query containment has been studied extensively in KR and databases, for different kinds of query languages and domain constraints. We address the longstanding open problem of containment under expressive description logic (DL) constraints for two-way regular path queries (2RPQs) and their conjunctions, which generalize conjunctive queries with the ability to express regular navigation. We show that, surprisingly, functionality constraints alone make containment of 2RPQs already ExpTime-hard. By employing automata-theoretic techniques, we also provide a matching upper bound that extends to very expressive DL constraints. For conjunctive 2RPQs we prove a further exponential jump in complexity, and provide again a matching upper bound for expressive DLs. Our techniques provide also a solution to the problem of query entailment over DL knowledge bases in which individuals in the ABox may be related through regular role-paths.

In agent-oriented programming and planning, agents' actions are typically specified in terms of postconditions, and the model of execution assumes that the environment carries the actions out exactly as specified. That is, it is assumed that the state of the environment after an action has been executed will satisfy its postcondition. In reality, however, such environments are rare: the actual execution of an action may fail, and the envisaged outcome is not met. We provide a conceptual framework for reasoning about success and failure of agents' behaviours. In particular, we propose a measure that reflects how "good" an environment is with respect to agent's capabilities and a given goal it might pursue. We also discuss which types of goals are worth pursuing, depending on the type of environment the agent is acting in.

We report on results from experiments where human traders interact with software-agent traders in a real-time asynchronous continuous double auction (CDA) experimental economics system. Our experiments are inspired by the seminal work reported by IBM at IJCAI 2001, where it was demonstrated that software-agent traders could consistently outperform human traders in real-time CDA markets. IBM tested two trading-agent strategies, ZIP and a modified version of GD, and in a subsequent paper they reported on a new strategy called GDX that was demonstrated to outperform GD and ZIP in agent vs. agent CDA competitions, on which basis it was claimed that GDX "...may offer the best performance of any published CDA bidding strategy.". In this paper, we employ experiment methods similar to those pioneered by IBM to test the performance of "Adaptive Aggressive" (AA) algorithmic traders. The results presented here confirm Vytelingum's claim that AA outperforms ZIP, GD, and GDX in agent vs. agent experiments. We then present the first results from testing AA against human traders in human vs. agent CDA experiments, and demonstrate that AA's performance against human traders is superior to that of ZIP, GD, and GDX. We therefore claim that, on the basis of the available evidence, AA may offer the best performance of any published bidding strategy.

This paper concerns the creation of an efficient, continuous, non-parametric representation of surfaces implicit in 3D laser data as typically recorded by mobile robots. Our approach explicitly leverages the probabilistic nature of Gaussian Process regression to provide for a principled, adaptive subsampling which automatically prunes redundant data. The algorithm places no restriction on the complexity of the underlying surfaces and enables predictions at arbitrary locations and densities. We present results using real and synthetic data and show that our approach attains decimation factors in excess of two orders of magnitude without significant degradation in fidelity of the workspace reconstructions.

This paper is concerned with the use of conversational agents as an interaction paradigm for accessing open domain encyclopedic knowledge by means of Wikipedia. More precisely, we describe a dialogue-based question answering system for German which utilizes Wikipedia-based topic models as a reference point for context detection and answer prediction. We investigate two different per- spectives to the task of interfacing virtual agents with collaborative knowledge. First, we exploit the use of Wikipedia categories as a basis for identifying the broader topic of a spoken utterance. Second, we describe how to enhance the conversational behavior of the virtual agent by means of a Wikipedia-based question answering component which incorporates the question topic. At large, our approach identifies topic-related focus terms of a user’s question, which are subsequently mapped onto a category taxonomy. Thus, we utilize the taxonomy as a reference point to derive topic labels for a user’s question. The employed topic model is thereby based on explicitly given concepts as represented by the document and category structure of the Wikipedia knowledge base. Identified topic categories are subsequently combined with different linguistic filtering methods to improve answer candidate retrieval and reranking. Results show that the topic model approach contributes to an enhancement of the conversational behavior of virtual agents.

Statutory records of underground utility apparatus (such as pipes andcables) are notoriously inaccurate, so street surveys are usually undertakenbefore road excavation takes place to minimize the extent and duration ofexcavation and for health and safety reasons. This involves the use ofsensors such as Ground Penetrating Radar (GPR). The GPR scans are thenmanually interpreted and combined with the expectations from the utilityrecords and other data such as surveyed manholes. The task is complex owingto the difficulty in interpreting the sensor data, and the spatialcomplexity and extent of under street assets. We explore the application ofAI techniques, in particular Bayesian data fusion (BDF), to automaticallygenerate maps of buried apparatus. Hypotheses about the spatial location anddirection of buried assets are extracted by identifying hyperbolae in theGPR scans. The spatial location of surveyed manholes provides further inputto the algorithm, as well as the prior expectations from the statutoryrecords. These three data sources are used to produce the most probable mapof the buried assets. Experimental results on real and simulated data setsare presented.