KI 2011: Advances in Artificial Intelligence

Domain-independent planning is one of the long-standing sub-areas of Artificial Intelligence (AI), aiming at approaching human problem-solving flexibility. The area has long had an affinity towards playful illustrative examples, imprinting it on the mind of many a student as an area concerned with the rearrangement of blocks, and with the order in which to put on socks and shoes (not to mention the disposal of bombs in toilets). Working on the assumption that this “student” is you – the readers in earlier stages of their careers – I herein aim to answer three questions that you surely desired to ask back then already:

What is it good for? Does it work? Is it interesting to do research in?

Answering the latter two questions in the affirmative (of course!), I outline some of the major developments of the last decade, revolutionizing the ability of planning to scale up, and the understanding of the enabling technology. Answering the first question, I point out that modern planning proves to be quite useful for solving practical problems - including, perhaps, yours.

One of the key components for achieving flexible, robust, adaptive and open-ended language-based communication between humans and robots - or between robots and robots - is rich deep semantics. AI has a long tradition of work in the representation of knowledge, most of it within the logical tradition. This tradition assumes that an autonomous agent is able to derive formal descriptions of the world which can then be the basis of logical inference and natural language understanding or production. This paper outlines some difficulties with this logical stance and reports alternative research on the development of an ‘embodied cognitive semantics’ that is grounded in the world through a robot’s sensori-motor system and is evolutionary in the sense that the conceptual frameworks underlying language are assumed to be adapted by agents in the course of dialogs and thus undergo constant change.

Introduced in 2005 as a new AI Challenge and Competition, general game playing has quickly evolved into an established research area. More recently it is also gaining popularity as a useful addition to AI curricula at universities around the world. The first part of this paper will survey the research landscape of general game playing, which covers a broad range of classic AI topics, including knowledge representation, search, planning and learning. The second part will argue that general game playing provides a unique approach to teaching a number of different topics such as problem solving by search, logic, logic programming and planning. The inherent competitive aspect also can be used as a great motivator for students to design and implement their own AI systems.

This paper presents a system that builds on theoretical and experimental insights from linguistic pragmatics, uses novel techniques from computational linguistics and combines them with robust baseline technologies to provide intelligent Non Player Characters (NPCs), which naturally act and talk in a virtual world. Current NPCs still lack the necessary linguistic knowledge and methods to apply them to the numerous conversational application areas in virtual worlds. The system presented in this paper manages two NPCs, a barkeeper and a furniture sales agent, which highly depend on conversational abilities.

In this paper, we propose to use dependency graphs rather than trees as the interface between a parser and the rule acquisition module of a relation extraction (RE) system. Dependency graphs are much more expressive than trees and can easily be adapted to the output representations of various parsers, in particular those with richer semantics. Our approach is built on top of an existing minimally supervised machine learning system for relation extraction. We extend its original tree-based interface to a graph-based representation. In our experiments, we make use of two different dependency parsers and a deep HPSG parser. As expected, switching to a graph representation for the parsers outputting dependency trees does not have any impact on the RE results. But using the graph-based representation for the extraction with deep HPSG analyses improves both recall and

f

-score of the RE and enables the system to extract more relation instances of higher arity. Furthermore, we also compare the performance among these parsers with respect to their contribution to the RE task. In general, the robust dependency parsers are good in recall. However, the fine-grained deep syntactic parsing wins when it comes to precision.

In the past ten years, the areas of

probabilistic inductive logic programming

and

statistical relational learning

put forth a large collection of approaches to combine relational representations of knowledge with probabilistic reasoning. Here, we develop a series of evaluation and comparison criteria for those approaches and focus on the point of view of knowledge representation and reasoning. These criteria address abstract demands such as language aspects, the relationships to propositional probabilistic and first-order logic, and their treatment of information on individuals. We discuss and illustrate the criteria thoroughly by applying them to several approaches to probabilistic relational knowledge representation, in particular, Bayesian logic programs, Markov logic networks, and three approaches based on the principle of maximum entropy.

Natural body movements are temporal sequences of individual actions. In order to realise a visual analysis of these actions, the human visual system must accomplish a temporal segmentation of action sequences. We attempt to reproduce human temporal segmentations with Bayesian binning (BB) [8]. Such a reproduction would not only help our understanding of human visual processing, but would also have numerous potential applications in computer vision and animation. BB has the advantage that the observation model can be easily exchanged. Moreover, being an exact Bayesian method, BB allows for the automatic determination of the number and positions of segmentation points. We report our experiments with polynomial (in time) observation models on joint angle data obtained by motion capture. To obtain human segmentation points, we generated videos by animating sequences from the motion capture data. Human segmentation was then assessed by an interactive adjustment paradigm, where participants had to indicate segmentation points by selection of the relevant frames. We find that observation models with polynomial order ≥ 3 can match human segmentations closely.

In real-world machine learning scenarios, labeled data is often rare while unlabeled data can be obtained easily. Semi-supervised approaches aim at improving the prediction performance by taking both the labeled as well as the unlabeled part of the data into account. In particular, semi-supervised support vector machines favor decision hyperplanes which lie in a “low-density area” induced by the unlabeled patterns (while still considering the labeled part of the data). The associated optimization problem, however, is of combinatorial nature and, hence, difficult to solve. In this work, we present an efficient implementation of a simple local search strategy that is based on matrix updates of the intermediate candidate solutions. Our experiments on both artificial and real-world data sets indicate that the approach can successfully incorporate unlabeled data in an efficient manner.

This paper presents a method for recognizing objects in 3D point clouds. Based on a structural model of these objects, we generate hypotheses for the location and 6DoF pose of these models and verify them by matching a CAD model of the object into the point cloud. Our method only needs a CAD model of each object class; no previous training is required.

For special applications in diagnostics for oncology the analysis of imaging data from Positron Emission Tomography (PET) is obfuscated by low contrast and high noise. To deal with this issue we propose a segmentation algorithm based on Ant Colony Optimization (ACO) and evolutionary selection of ants for self reproduction. The self reproduction approach is no standard for ACO, but appears to be crucial for volume segmentation. This investigation was focused on two different ways for reproduction control and their contribution to quantity and quality of segmentation results. One of the evaluated methods appears to be able to replace the explicit ant movement through transition rules by implicit movement through reproduction. Finally the combination of transition rules and self reproduction generates best reproducible segmentation results.

Lifted message passing approaches can be extremely fast at computing approximate marginal probability distributions over single variables and neighboring ones in the underlying graphical model. They do, however, not prescribe a way to solve more complex inference tasks such as computing joint marginals for

k

-tuples of distant random variables or satisfying assignments of CNFs. A popular solution in these cases is the idea of turning the complex inference task into a sequence of simpler ones by selecting and clamping variables one at a time and running lifted message passing again after each selection. This naive solution, however, recomputes the lifted network in each step from scratch, therefore often canceling the benefits of lifted inference. We show how to avoid this by efficiently computing the lifted network for each conditioning directly from the one already known for the single node marginals. Our experiments show that significant efficiency gains are possible for lifted message passing guided decimation for SAT and sampling.

While associations between concepts in our memory have different strengths, explicit strengths of links (edge weights) are missing in Linked Data. In order to build a collection of such edge weights, we created a web-game prototype that ranks triples by importance. In this paper we briefly describe the game, Linked Data preprocessing aspects, and the promising results of an evaluation of the game.

For evaluating activity recognition results still classical error metrics like

Accuracy

,

Precision

, and

Recall

are being used. They are well understood and widely accepted but entail fundamental problems: They can not handle fuzzy event boundaries, or parallel activities, and they over-emphasize decision boundaries. We introduce more generic performance metrics as replacement, allowing for soft classification and annotation while being backward compatible. We argue that they can increase the expressiveness and still allow more sophisticated methods like event and segment analysis.

With Bayesian logic networks (BLNs), we present a practical representation formalism for statistical relational knowledge. Based on the concept of mixed networks with probabilistic and deterministic constraints, BLNs combine the probabilistic semantics of (relational) Bayesian networks with constraints in first-order logic. In practical applications, efficient inference in statistical relational models such as BLNs is a key concern. Motivated by the inherently mixed nature of models instantiated from BLNs, we investigate two novel importance sampling methods: The first combines backward simulation, i.e. sampling backward from the evidence, with systematic search, while the second explores the possibility of recording abstract constraints during the search for samples.

A major challenge in knowledge representation is to express uncertain knowledge. One possibility is to combine logic and probability. In this paper, we investigate the logic FO-PCL that uses first-order probabilistic conditionals to formulate uncertain knowledge. Reasoning in FO-PCL employs the principle of maximum entropy which in this context refers to the set of all ground instances of the conditionals in a knowledge base

$\mathcal R$

. We formalize the syntactic criterion of FO-PCL interactions in

$\mathcal R$

prohibiting the maximum entropy model computation on the level of conditionals instead of their instances. A set of rules is developed transforming

$\mathcal R$

into an equivalent knowledge base

$\mathcal R^{\prime}$

without FO-PCL interactions.

Estimation of distribution algorithms (EDAs) are derivative-free optimization approaches based on the successive estimation of the probability density function of the best solutions, and their subsequent sampling. It turns out that the success of EDAs in numerical optimization strongly depends on scaling of the variance. The contribution of this paper is a comparison of various adaptive and self-adaptive variance scaling techniques for a Gaussian EDA. The analysis includes: (1) the Gaussian EDA without scaling, but different selection pressures and population sizes, (2) the variance adaptation technique known as Silverman’s rule-of-thumb, (3)

σ

-self-adaptation known from evolution strategies, and (4) transformation of the solution space by estimation of the Hessian. We discuss the results for the sphere function, and its constrained counterpart.

The paper investigates the self-stabilization of hierarchically structured markets. We propose a new approach that is motivated by the physical structure of the energy grid and generalizes classical market structures in a natural way. Hierarchical markets have several advantages compared to monolithic markets, i.e., improved reliability and scalability, locality of information, and proximity of energy production and consumption. By simulating scenarios based on real world consumption and production data including households, different renewable energy sources, and other plant types, we present a proof-of-concept of stability of the hierarchical markets in various simulations.

In engineering domains, AI decision making is often confronted with problems that lie at the intersection of logic-based and probabilistic reasoning. A typical example is the plan assessment problem studied in this paper, which comprises the identification of possible faults and the computation of remaining success probabilities based on a system model. In addition, AI solutions to such problems need to be tailored towards the needs of engineers. This is being addressed by the recently developed high-level, expressive modeling formalism called probabilistic hierarchical constraint automata (PHCA).

This work introduces a translation from PHCA models to statistical relational models, which enables a wide array of probabilistic reasoning solutions to be leveraged, e.g., by grounding to problem-specific Bayesian networks. We illustrate this approach for the plan assessment problem, and compare it to an alternative logic-based approach that translates the PHCA models to lower-level logic models and computes solutions by enumerating most likely hypotheses. Experimental results on realistic problem instances demonstrate that the probabilistic reasoning approach is a promising alternative to the logic-based approach.

We propose an algorithm for determining optimal transition paths between given configurations of systems consisting of many objects. It is based on the Principle of Least Action and variational equations for Freidlin–Wentzell action functionals in Gaussian networks set-up. We use our method to construct a system controlling motion and redeployment between unit’s formations. Another application of the algorithm allows a realistic transformation between two sequences of character animations in a virtual environment. The efficiency of the algorithm has been evaluated in a simple sandbox environment implemented with the use of the NVIDIA CUDA technology.

In this paper, a novel approach to hierarchical planning under partial observability in relational domains is presented. It combines hierarchical task network planning with the finite state controller (FSC) policy representation for partially observable Markov decision processes. Based on a new first-order generalization of FSCs, action hierarchies are defined as in traditional hierarchical planning, so that planning corresponds to finding the best plan in a given decomposition hierarchy of predefined, partially abstract FSCs. Finally, we propose an algorithm for solving planning problems in this setting. Our approach offers a way of practically dealing with real-world partial observability planning problems: it avoids the complexity originating from the dynamic programming backup operation required in many present-day policy generation algorithms.

Probabilistic systems for image analysis have enjoyed increasing popularity within the last few decades, yet principled approaches to incorporating occlusion

as a feature

into such systems are still few [11,10,7]. We present an approach which is strongly influenced by the work on

noisy-or

generative factor models (see e.g. [3]). We show how the intractability of the hidden variable posterior of

noisy-or

models can be (conditionally) lifted by introducing gates on the input combined with a sparsifying prior, allowing for the application of standard inference procedures. We demonstrate the feasibility of our approach on a computer vision toy problem.

Plans synthesized by Temporal Planning and Scheduling systems may be temporally flexible hence they identify an envelope of possible solutions. Such flexibility can be exploited by an executive systems for robust on-line execution. Recent works have addressed aspects of plan execution using a quite general approach grounded on formal modeling and formal methods. The present work extends such an approach by presenting the formal synthesis of a plan controller associated to a flexible temporal plan. In particular, the controller synthesis exploits Timed Game Automata (TGA) for formal modeling and UPPAAL-TIGA as a model checker. After presenting a formal extension, the paper introduces a detailed experimental analysis on a real-world case study that demonstrates the viability of the approach. In particular, it is shown how the controller synthesis overhead is compatible with the performance expected from a short-horizon planner.

In this paper a new criterion for clusters validation is proposed. This new cluster validation criterion is used to approximate the goodness of a cluster. A clustering ensmble framework based on the new metric is proposed. In the framework first a large number of clusters are prepared and then some of them are selected for final ensmble. The clusters which satisfy a threshold of the proposed metric are selected to participate in final clustering ensemble. For combining the chosen clusters, a co-association based consensus function is applied. Since the Evidence Accumulation Clustering (EAC) method cannot derive the co-association matrix from a subset of clusters, a new EAC based method which is called Extended EAC, EEAC, is applied for constructing the co-association matrix from the subset of clusters. Employing this new cluster validation criterion, the obtained ensemble is evaluated on some well-known and standard data sets. The empirical studies show promising results for the ensemble obtained using the proposed criterion comparing with the ensemble obtained using the standard clusters validation criterion.

Solving number series poses a challenging problem for humans and Artificial Intelligence Systems. The task is to correctly predict the next number in a given series, in accordance with a pattern inherent to that series. We propose a novel method based on Artificial Neural Networks with a dynamic learning approach to solve number series problems. Our method is evaluated on an own experiment and over 50.000 number series from the Online Encyclopedia of Integer Sequences (OEIS) database.

Besides the classification performance, the training time is a second important factor that affects the suitability of a classification algorithm regarding an unknown dataset. An algorithm with a slightly lower accuracy is maybe preferred if its training time is significantly lower. Additionally, an estimation of the required training time of a pattern recognition task is very useful if the result has to be available in a certain amount of time.

Meta-learning is often used to predict the suitability or performance of classifiers using different learning schemes and features. Especially landmarking features have been used very successfully in the past. The accuracy of simple learners are used to predict the performance of a more sophisticated algorithm.

In this work, we investigate the quantitative prediction of the training time for several target classifiers. Different sets of meta-features are evaluated according to their suitability of predicting actual run-times of a parameter optimization by a grid search. Additionally, we adapted the concept of landmarking to time prediction. Instead of their accuracy, the run-time of simple learners are used as feature values.

We evaluated the approach on real world datasets from the UCI machine learning repository and StatLib. The run-time of five different classification algorithms are predicted and evaluated using two different performance measures. The promising results show that the approach is able to reasonably predict the training time including a parameter optimization. Furthermore, different sets of meta-features seem to be necessary for different target algorithms in order to achieve the highest prediction performances.

This paper describes a new approach to language generation for simulated users based on the construction of flexible templates extracted from a corpus. In our opinion a realistic user simulation on the speech level is based on two parts: user behavior and language generation. In this work we mainly concentrate on the language generation for simulated user interaction with spoken dialog systems (SDS). The presented approach could be used as part of a user simulation for intensive end-to-end system tests and evaluations and for testing purposes of the speech recognition and natural language understanding modules of an SDS.

In this paper, a systematic comparative analysis of laser-based tracking methods, at feet and upper-body height, is performed. To this end, we created a well defined dataset, including challenging but realistic person movement trajectories, appearing in public operational environments, recorded with multiple laser range finders. In order to evaluate and compare the tracking results, we applied and adapted a performance metric, known from the Computer Vision area. The dataset in combination with this performance metric enables us to perform systematic and repeatable experiments for benchmarking laser-based person trackers.

Empirical research supports the belief that structural commonalities between two domains are the main guidance for the construction of analogies. Restricted higher-order anti-unification has been shown suitable to find structural commonalties and generate mappings between domains in the symbolic analogy model Heuristic-Driven Theory Projection (HDTP). This paper will describe how to enforce and integrate restrictions on mappings between symbols from a many-to-many up to a one-to-one symbol correspondence. We will also discuss how sorts together with sortal ontologies can be incorporated into anti-unification within HDTP and thereby restrict possible mappings between domains.

In this paper we introduce a normal form for

$\mathcal{ALC}$

concepts and TBoxes called

linkless normal form

. We investigate properties of concepts given in this normal form such as an efficient satisfiability test and the calculation of uniform interpolants. We further show a way to approximate a TBox by a concept in linkless normal form, which allows us to check certain subsumptions efficiently. This makes the linkless normal form interesting from the viewpoint of knowledge compilation. Furthermore, we show how to use the approximation of a TBox in linkless normal form to efficiently construct an approximation of a uniform interpolant of a TBox w.r.t. a given signature.

Manifold approaches exist in the field of similarity-based shape retrieval. Although many of them achieve good results in reference tests, there has been less focus on systematically examining the factors influencing both retrieval performance and computational effort. Such an investigation, however, is important for the structured development and improvement of shape descriptors. This paper contributes a thorough investigation of the influence of the shape part-order and approximation precision. Firstly, two shape descriptors based on qualitative spatial relations are introduced and evaluated. These descriptors are particularly suited for the intended investigation because their only distinction is that one of them preserves the part-order, the other abandons it. Secondly, the recall and precision values are related to the degree of approximation in three-dimensional recall-precision-approximation diagrams. This helps choose an appropriate approximation precision. Finally, it turns out that remarkable retrieval results can be achieved even if only qualitative position information is considered.

TV news reviews are of strong interest in media and communication sciences, since they indicate national and international social trends. To identify such trends, scientists from these disciplines usually work with manually annotated video data. In this paper, we investigate if the time-consuming process of manual annotation can be automated by using the current pattern recognition techniques. To this end, a comparative study on different combinations of local and global features sets with two examples of the pyramid match kernel is conducted. The performance of the classification of TV new scenes is measured. The classes are taken from a coding scheme that is the result of an international discourse in media and communication sciences. For the classification of studio vs. non-studio, football vs. ice hockey, computer graphics vs. natural scenes and crowd vs. no crowd, recognition rates between 80 and 90 percent could be achieved.

We present an approach for the generative modeling of human interactions with emotional style variations. We employ a hierarchical Gaussian process latent variable model (GP-LVM) to map motion capture data of handshakes into a space of low dimensionality. The dynamics of the handshakes in this low dimensional space are then learned by a standard hidden Markov model, which also encodes the emotional style variation. To assess the quality of generated and rendered handshakes, we asked human observers to rate them for realism and emotional content. We found that generated and natural handshakes are virtually indistinguishable, proving the accuracy of the learned generative model.

This paper proposes “Value-Difference Based Exploration combined with Softmax action selection” (VDBE-Softmax) as an adaptive exploration/exploitation policy for temporal-difference learning. The advantage of the proposed approach is that exploration actions are only selected in situations when the knowledge about the environment is uncertain, which is indicated by fluctuating values during learning. The method is evaluated in experiments having deterministic rewards and a mixture of both deterministic and stochastic rewards. The results show that a VDBE-Softmax policy can outperform

ε

-greedy, Softmax and VDBE policies in combination with on- and off-policy learning algorithms such as

Q

-learning and Sarsa. Furthermore, it is also shown that VDBE-Softmax is more reliable in case of value-function oscillations.

Most pedestrian navigation systems are intended for single users only. But pedesterians often prefere going out with other people, meeting friends and covering distances together. Thus we built a navigation system which allows calculating routes for multiple people who want to meet departing at different locations. In this paper we present, how satisfying meeting points can be found. We discuss two approaches, one based on the Steiner Tree Problem in Networks and one based on the Euclidian Steiner Problem which neglects the street network. Both approaches are evaluated and a user study demonstrates the applicability of our solution.

Cognitive modelling in intelligent tutoring systems aims at identifying a learner’s skills and knowledge from his answers to tutor questions and other observed behaviour. In this paper, we propose an innovative variant of Shapiro’s algorithmic debugging technique whose application can be used to pin-point learners’ erroneous behaviour in terms of an irreducible disagreement to the execution trace of an expert model. Our variant has two major benefits: in contrast to traditional approaches, it does not rely on an explicit encoding on mal-rules, and second, it induces a natural teacher-learner dialogue with no need for the prior scripting of individial turns or higher-level dialogue planning.