Skip to main content
main-content

Über dieses Buch

The 33rd Annual German Conference on Arti?cial Intelligence (KI 2010) took place at the Karlsruhe Institute of Technology KIT, September 21–24, 2010, under the motto “Anthropomatic Systems.” In this volume you will ?nd the keynote paper and 49 papers of oral and poster presentations. The papers were selected from 73 submissions, resulting in an acceptance rate of 67%. As usual at the KI conferences, two entire days were allocated for targeted workshops—seventhis year—andone tutorial. The workshopand tutorialma- rials are not contained in this volume, but the conference website, www.ki2010.kit.edu,will provide information and references to their contents. Recent trends in AI research have been focusing on anthropomatic systems, which address synergies between humans and intelligent machines. This trend is emphasized through the topics of the overall conference program. They include learning systems, cognition, robotics, perception and action, knowledge rep- sentation and reasoning, and planning and decision making. Many topics deal with uncertainty in various scenarios and incompleteness of knowledge. Summarizing, KI 2010 provides a cross section of recent research in modern AI methods and anthropomatic system applications. We are very grateful that Jos´ edel Mill´ an, Hans-Hellmut Nagel, Carl Edward Rasmussen, and David Vernon accepted our invitation to give a talk.

Inhaltsverzeichnis

Frontmatter

Cognition

Vision, Logic, and Language – Toward Analyzable Encompassing Systems

Some time ago, Computer Vision has passed the stage where it detected changes in image sequences, estimated Optical Flow, or began to track people and vehicles in videos. Currently, research in Computer Vision has expanded to extract descriptions of single

actions

or concatenations of actions from videos, sometimes even the description of agent

behavior

in the recorded scene.

This transition from treating mostly

quantitative, geometric

descriptions to becoming concerned with more

qualitative, conceptual

descriptions creates contacts between Computer Vision, Computational Linguistics, and Computational Logic. The latter two disciplines have studied the analysis and combination of conceptual constructs already for decades.

Based on selected examples, attention will be drawn to the potential which can be tapped if the emerging thematic overlap of research in these three disciplines is investigated collaboratively. This applies in particular to the development of encompassing systems which rely on methods from all three disciplines, for example by providing Natural Language interfaces to more generally applicable combinations of Knowledge Bases with Computer Vision systems.

Hans-Hellmut Nagel

A Computational Model of Human Movement Coordination

Due to the numerous degrees of freedom in the human motor system, there exists an infinite number of possible movements for any given task. Unfortunately, it is currently unknown how the human central nervous system (CNS) chooses one movement out of the plethora of possible movements to solve the task at hand. The purpose of this study is the construction of a computational model of human movement coordination to unravel the principles the CNS might use to select one movement from plethora of possible movements in a given situation. Thereby, different optimization criteria were examined. The comparison of predicted and measured movement patterns exhibited that a minimum jerk strategy on joint level yielded the closest fit to the human data.

Thorsten Stein, Christian Simonidis, Wolfgang Seemann, Hermann Schwameder

BiosignalsStudio: A Flexible Framework for Biosignal Capturing and Processing

In this paper we introduce

BiosignalsStudio

(BSS), a framework for multimodal sensor data acquisition. Due to its flexible architecture it can be used for large scale multimodal data collections as well as a multimodal input layer for intelligent systems. The paper describes the software framework and its contributions to our research work and systems.

Dominic Heger, Felix Putze, Christoph Amma, Michael Wand, Igor Plotkin, Thomas Wielatt, Tanja Schultz

Local Adaptive Extraction of References

The accurate extraction of scholarly reference information from scientific publications is essential for many useful applications like

BibTeX

management systems or citation analysis. Automatic extraction methods suffer from the heterogeneity of reference notation, no matter wether the extraction model was handcrafted or learnt from labeled data. However, references of the same paper or journal are usually homogeneous. We exploit this local consistency with a novel approach. Given some initial information from such a reference section, we try to derived generalized patterns. These patterns are used to create a local model of the current document. The local model helps to identify errors and to improve the extracted information incrementally during the extraction process. Our approach is implemented with handcrafted transformation rules working on a meta-level being able to correct the information independent of the applied layout style. The experimental results compete very well with the state of the art methods and show an extremely high performance on consistent reference sections.

Peter Kluegl, Andreas Hotho, Frank Puppe

Logic-Based Trajectory Evaluation in Videos

The study of 3D-model-based tracking in videos frequently has to be concerned with details of algorithms or their parameterisation. Time-consuming experiments have to be performed in this context which suggested to (at least partially) automate the evaluation of such experimental runs. A logic-based approach has been developed which generates Natural Language textual descriptions of evaluation runs and facilitates the formulation of specific hints. The implementation of this approach is outlined, results obtained with it on an extended complex real-world road traffic video are presented and discussed.

Nicola Pirlo, Hans-Hellmut Nagel

Human-Machine Interaction

A Testbed for Adaptive Human-Robot Collaboration

This paper presents a novel method for developing and evaluating INTELLIGENT robot behavior for joint human-robot activities. We extended a physical simulation of an autonomous robot to interact with a second, human-controlled agent as in a computer game. We have conducted a user study to demonstrate the viability of the approach for adaptive human-aware planning for collaborative everyday activities. The paper presents the details of our simulation and its control for human subjects as well as results of the user study.

Alexandra Kirsch, Yuxiang Chen

Human Head Pose Estimation Using Multi-appearance Features

Non-verbal interaction signals are of great interest in the research field of natural human-robot interaction. These signals are not limited to gestures and emotional expressions since other signals - like the interpersonal distance and orientation - do also have large influence on the communication process. Therefore, this paper presents a marker-less mono-ocular object pose estimation using a model-to-image registration technique. The object model uses different feature types and visibilities which allow the modeling of various objects. Final experiments with different feature types and tracked objects show the flexibility of the system. It turned out that the introduction of feature visibility allows pose estimations when only a subset of the modeled features is visible. This visibility is an extension to similar approaches found in literature.

Norbert Schmitz, Gregor Zolynski, Karsten Berns

Online Full Body Human Motion Tracking Based on Dense Volumetric 3D Reconstructions from Multi Camera Setups

We present an approach for video based human motion capture using a static multi camera setup. The image data of calibrated video cameras is used to generate dense volumetric reconstructions of a person within the capture volume. The 3d reconstructions are then used to fit a 3d cone model into the data utilizing the Iterative Closest Point (ICP) algorithm. We can show that it is beneficial to use multi camera data instead of a single time of flight camera to gain more robust results in the overall tracking approach.

Tobias Feldmann, Ioannis Mihailidis, Sebastian Schulz, Dietrich Paulus, Annika Wörner

On-Line Handwriting Recognition with Parallelized Machine Learning Algorithms

The availability of mobile devices without a keypad like Apple’s iPad and iPhone grows continuously and the demand for sophisticated input methods with them. In this paper we present classifiers for on-line handwriting recognition based on SVM and kNN algorithms and provide a comparison of the different classifiers using the freely available handwriting corpus UjiPenchars2. We further investigate how their performance can be improved by parallelization and how these improvements can be utilized on a mobile device.

Sebastian Bothe, Thomas Gärtner, Stefan Wrobel

Planning Cooperative Motions of Cognitive Automobiles Using Tree Search Algorithms

A tree search algorithm is proposed for planning cooperative motions of multiple vehicles. The method relies on planning techniques from artificial intelligence such as A* search and cost-to-go estimation. It avoids the restrictions of decoupling assumptions and exploits the full potential of cooperative actions. Precomputation of lower bounds is used to restrict the search to a small portion of the tree of possible cooperative actions. The proposed algorithm is applied to the problem of planning cooperative maneuvers for multiple cognitive vehicles with the aim of preventing accidents in dangerous traffic situations. Simulation results show the feasibility of the approach and the performance gain obtained by precomputing lower bounds.

Christian Frese, Jürgen Beyerer

Static Preference Models for Options with Dynamic Extent

Models of user preferences are an important resource to improve the user experience of recommender systems. Using user feedback static preference models can be adapted over time. Still, if the options to choose from themselves have temporal extent, dynamic preferences have to be taken into account even when answering a single query. In this paper we propose that static preference models could be used in such situations by identifying an appropriate set of features.

Thomas Bauereiß, Stefan Mandl, Bernd Ludwig

Towards User Assistance for Documents via Interactional Semantic Technology

As documents become disseminated widely, establishing the context for interpretation becomes difficult. We argue that high-impact documents require embedded user assistance facilities for their readers (

not

authors) to cope with their semantic complexity. We suggest to illustrate such documents and their players with a semiformal background ontology, an interpretation mapping between domain concepts and semantic objects, and to enable with this setup semantic interaction. We showcase the feasibility and interactional potential of user assistance for documents based on interactional semantic technology with an exemplary implementation for a high-impact Excel spreadsheet.

Andrea Kohlhase

Knowledge

Flexible Concept-Based Argumentation in Dynamic Scenes

Argumentation systems can be employed for detecting spatiotemporal patterns. While the idea of argumentation consists in defending specific positions, complex patterns are influenced by several factors that can be regarded as arguments against or in favor of the realisation of those patterns. The idea is to determine consistent positions of arguments which speak for specific patterns. This becomes possible by means of algorithms which have been defined for argumentation systems. The introduced method of conceptual argumentation is new in comparison to classical, i.e. value-based, argumentation systems. It has the advantage to be more flexible by enabling the definition of conceptual arguments influencing relevant patterns. There are two main results: first, conceptual argumentation frameworks do scale significantly better; secondly, investigating our approach by examining soccer games, we show that specific patterns, such as passes, can be detected with different retrieval performances depending on the chosen spatial granularity level.

Jörn Sprado, Björn Gottfried, Otthein Herzog

Focused Belief Revision as a Model of Fallible Relevance-Sensitive Perception

We present a framework for incorporating perception-induced beliefs into the knowledge base of a rational agent. Normally, the agent accepts the propositional content of perception and other propositions that follow from it. Given the fallibility of perception, this may result in contradictory beliefs. Hence, we model high-level perception as belief revision. Adopting a classical AGM-style belief revision operator is problematic, since it implies that, as a result of perception, the agent will come to believe everything that follows from its new set of beliefs. We overcome this difficulty in two ways. First, we adopt a belief revision operator based on relevance logic, thus limiting the derived beliefs to those that relevantly follow from the new percept. Second, we focus belief revision on only a subset of the agent’s set of beliefs—those that we take to be within the agent’s current focus of attention.

Haythem O. Ismail, Nasr Kasrin

Multi-context Systems with Activation Rules

Multi-Context Systems provide a formal basis for the integration of knowledge from different knowledge sources. Yet, it is easy to conceive of applications where not all knowledge sources may be used together all the time. We present a natural extension of Multi-Context Systems by adding the notion of activation rules that allows modeling the applicability or relevance of contexts depending on beliefs in the various contexts and their mutual dependencies. We give a short account on possible consequence relations for Multi-Context System with Activation Rules and discuss a potential application in information retrieval.

Stefan Mandl, Bernd Ludwig

Pellet-HeaRT – Proposal of an Architecture for Ontology Systems with Rules

The ongoing research on integration of rules and ontologies has resulted in multiple solutions, rule languages and systems. They differ in terms of aims and scope, semantics and architecture. The paper describes a proposal of a hybrid system combining a Description Logics reasoner with a forward-chaining rule engine. An integration of a dedicated tool for modularized rule bases, called HeaRT, and a widely-used DL reasoner Pellet, is sketched. An outline of main concepts and architecture of HeaRT-Pellet system is given, explained on an example case. The benefit of this solution is the ability to use a mature rule design, analysis and inference solution together with large fact bases from ontologies.

Grzegorz J. Nalepa, Weronika T. Furmańska

Putting People’s Common Sense into Knowledge Bases of Household Robots

Unlike people, household robots cannot rely on commonsense knowledge when accomplishing everyday tasks. We believe that this is one of the reasons why they perform poorly in comparison to humans. By integrating extensive collections of commonsense knowledge into mobile robot’s knowledge bases, the work proposed in this paper enables robots to flexibly infer control decisions under changing environmental conditions. We present a system that converts commonsense knowledge from the large Open Mind Indoor Common Sense database from natural language into a Description Logic representation that allows for automated reasoning and for relating it to other sources of knowledge.

Lars Kunze, Moritz Tenorth, Michael Beetz

Recognition and Visualization of Music Sequences Using Self-organizing Feature Maps

Music consists of sequences, e.g., melodic, rhythmic or harmonic passages. The analysis and automatic discovery of sequences in music has an important part to play in different applications, e.g., intelligent fast-forward to new parts of a song, assisting tools in music composition, or automated spinning of records. In this paper we introduce a method for the automatic discovery of sequences in a song based on self-organizing maps and approximate motif search. In a preprocessing step high-dimensional music feature vectors are extracted on the level of bars, and translated into low-dimensional symbols, i.e., neurons of a self-organizing feature map. We use this quantization of bars for visualization of the song structure and for the recognition of motifs. An experimental analysis on real music data and a comparison to human analysis complements the results.

Tobias Hein, Oliver Kramer

Searching for Locomotion Patterns that Suffer from Imprecise Details

Today, a number of positioning technologies exist in order to track moving objects. While GPS devices enable wayfinding in outdoor environments, several techniques have been devised for indoor tracking, to enable smart spaces, for example. But even at the microscopic scale objects are tracked by researchers of the natural sciences with imaging technologies. Regardless of the spatial scale and application at hand, a common problem consists in the ever growing quantities of movement data which are to be managed. One strategy asks for how to simplify the data, such that compact representations save space but do still capture relevant information. Such an abstraction is described in this paper. It is shown how it can be applied to constraint programming techniques in order to search for movement patterns of groups of objects. Instead of exhaustively searching by means of

generate and test

, the representation allows the application of

constraint propagation

. As a consequence, search space can be reduced significantly. Moreover, it is shown how the chosen representation aids the dealing with a specific class of imprecise data. The domain of biological cells is used for illustrating the presented methods. The resulting observations, made by light microscopes, suffer from the addressed class of imprecise data.

Björn Gottfried

World Modeling for Autonomous Systems

This contribution proposes a universal, intelligent information storage and management system for autonomous systems, e. g., robots. The proposed system uses a three pillar information architecture consisting of three distinct components: prior knowledge, environment model, and real world. In the center of the architecture, the environment model is situated, which constitutes the fusion target for prior knowledge and sensory information from the real world. The environment model is object oriented and comprehensively models the relevant world of the autonomous system, acting as an information hub for sensors (information sources) and cognitive processes (information sinks). It features mechanisms for information exchange with the other two components. A main characteristic of the system is that it models uncertainties by probabilities, which are handled by a Bayesian framework including instantiation, deletion and update procedures. The information can be accessed on different abstraction levels, as required. For ensuring validity, consistence, relevance and actuality, information check and handling mechanisms are provided.

Ioana Gheţa, Michael Heizmann, Andrey Belkin, Jürgen Beyerer

Machine Learning and Data Mining

A Probabilistic MajorClust Variant for the Clustering of Near-Homogeneous Graphs

Clustering remains a major topic in machine learning; it is used e.g. for document categorization, for data mining, and for image analysis. In all these application areas, clustering algorithms try to identify groups of related data in large data sets.

In this paper, the established clustering algorithm

MajorClust

([12]) is improved; making it applicable to data sets with few structure on the local scale—so called near-homogeneous graphs. This new algorithm

MCProb

is verified empirically using the problem of image clustering. Furthermore,

MCProb

is analyzed theoretically. For the applications examined so-far,

MCProb

outperforms other established clustering techniques.

Oliver Niggemann, Volker Lohweg, Tim Tack

Acceleration of DBSCAN-Based Clustering with Reduced Neighborhood Evaluations

DBSCAN is a density-based clustering technique, well appropriate to discover clusters of arbitrary shape, and to handle noise. The number of clusters does not have to be known in advance. Its performance is limited by calculating the

ε

-neighborhood of each point of the data set. Besides methods that reduce the query complexity of nearest neighbor search, other approaches concentrate on the reduction of necessary

ε

-neighborhood evaluations. In this paper we propose a heuristic that selects a reduced number of points for the nearest neighborhood search, and uses efficient data structures and algorithms to reduce the runtime significantly. Unlike previous approaches, the number of necessary evaluations is independent of the data space dimensionality. We evaluate the performance of the new approach experimentally on artificial test cases and problems from the UCI machine learning repository.

Andreas Thom, Oliver Kramer

Adaptive ε-Greedy Exploration in Reinforcement Learning Based on Value Differences

This paper presents “Value-Difference Based Exploration” (VDBE), a method for balancing the exploration/exploitation dilemma inherent to reinforcement learning. The proposed method adapts the exploration parameter of

ε

-greedy in dependence of the

temporal-difference error

observed from value-function backups, which is considered as a measure of the agent’s uncertainty about the environment. VDBE is evaluated on a multi-armed bandit task, which allows for insight into the behavior of the method. Preliminary results indicate that VDBE seems to be more parameter robust than commonly used ad hoc approaches such as

ε

-greedy or softmax.

Michel Tokic

Learning the Importance of Latent Topics to Discover Highly Influential News Items

Online news is a major source of information for many people. The overwhelming amount of new articles published every day makes it necessary to filter out unimportant ones and detect ground breaking new articles.

In this paper, we propose the use of Latent Dirichlet Allocation (LDA) to find the hidden factors of important news stories. These factors are then used to train a Support Vector Machine (SVM) to classify new news items as they appear. We compare our results with SVMs based on a bag-of-words approach and other language features. The advantage of a LDA processing is not only a better accuracy in predicting important news, but also a better interpretability of the results. The latent topics show directly the important factors of a news story.

Ralf Krestel, Bhaskar Mehta

Methods for Automated High-Throughput Toxicity Testing Using Zebrafish Embryos

In this paper, an automated process to extract experiment-specific parameters out of microscope images of zebrafish embryos is presented and applied to experiments consisting of toxicological treated zebrafish embryos. The treatments consist of a dilution series of several compounds.

A custom built graphical user interface allows an easy labeling and browsing of the image data. Subsequently image-specific features are extracted for each image based on image processing algorithms. By means of feature selection, the most significant features are determined and a classification divides the images in two classes. Out of the classification results dose-response curves as well as frequently used general indicators of substance’s acute toxicity can be automatically calculated. Exemplary the median lethal dose is determined. The presented approach was designed for real high-throughput screening including data handling and the results are stored in a long-time data storage and prepared to be processed on a cluster computing system being build up in the KIT. It provides the possibility to test any amount of chemical substances in high-throughput and is, in combination with new screening microscopes, able to manage ten thousands of risk tests required e.g. in the REACH framework or for drug discovery.

Rüdiger Alshut, Jessica Legradi, Urban Liebel, Lixin Yang, Jos van Wezel, Uwe Strähle, Ralf Mikut, Markus Reischl

Visualizing Dissimilarity Data Using Generative Topographic Mapping

The generative topographic mapping (GTM) models data by a mixture of Gaussians induced by a low-dimensional lattice of latent points in low dimensional space. Using back-projection, topographic mapping and visualization can be achieved. The original GTM has been proposed for vectorial data only and, thus, cannot directly be used to visualize data given by pairwise dissimilarities only. In this contribution, we consider an extension of GTM to dissimilarity data. The method can be seen as a direct pendant to GTM if the dissimilarity matrix can be embedded in Euclidean space while constituting a model in pseudo-Euclidean space, otherwise. We compare this visualization method to recent alternative visualization tools.

Andrej Gisbrecht, Bassam Mokbel, Alexander Hasenfuss, Barbara Hammer

Planing and Reasoning

An Empirical Comparison of Some Multiobjective Graph Search Algorithms

This paper compares empirically the performance in time and space of two multiobjective graph search algorithms, MOA* and NAMOA*. Previous theoretical work has shown that NAMOA* is never worse than MOA*. Now, a statistical analysis is presented on the relative performance of both algorithms in space and time over sets of randomly generated problems.

Enrique Machuca, Lorenzo Mandow, Jose L. Pérez de la Cruz, Amparo Ruiz-Sepulveda

Completeness for Generalized First-Order LTL

A new first-order fixpoint logic, FL, is introduced as a Gentzen-type sequent calculus. FL is regarded as a generalization of the first-order linear-time temporal logic. The completeness and cut-elimination theorems for FL are proved using some theorems for embedding FL into infinitary logic.

Norihiro Kamide

Instantiating General Games Using Prolog or Dependency Graphs

This paper proposes two ways to instantiate general games specified in the game description language GDL to enhance exploration efficiencies of existing players. One uses Prolog’s inference mechanism to find supersets of reachable atoms and moves; the other one utilizes dependency graphs, a datastructure that can calculate the dependencies of the arguments of predicates by evaluating the various formulas from the game’s description.

Peter Kissmann, Stefan Edelkamp

Plan Assessment for Autonomous Manufacturing as Bayesian Inference

Next-generation autonomous manufacturing plants create individualized products by automatically deriving manufacturing schedules from design specifications. However, because planning and scheduling are computationally hard, they must typically be done offline using a simplified system model, meaning that online observations and potential component faults cannot be considered. This leads to the problem of

plan assessment

: Given behavior models and current observations of the plant’s (possibly faulty) behavior, what is the probability of a partially executed manufacturing plan succeeding? In this work, we propose 1) a statistical relational behavior model for a class of manufacturing scenarios and 2) a method to derive statistical bounds on plan success probabilities for each product from confidence intervals based on sampled system behaviors. Experimental results are presented for three hypothetical yet realistic manufacturing scenarios.

Paul Maier, Dominik Jain, Stefan Waldherr, Martin Sachenbacher

Positions, Regions, and Clusters: Strata of Granularity in Location Modelling

Location models are data structures or knowledge bases used in Ubiquitous Computing for representing and reasoning about spatial relationships between so-called smart objects, i.e. everyday objects, such as cups or buildings, containing computational devices with sensors and wireless communication. The location of an object is in a location model either represented by a

region

, by a coordinate

position

, or by a

cluster

of regions or positions. Qualitative reasoning in location models could advance intelligence of devices, but is impeded by incompatibilities between the representation formats: topological reasoning applies to regions; directional reasoning, to positions; and reasoning about set-membership, to clusters. We present a mathematical structure based on scale spaces giving an integrated semantics to all three types of relations and representations. The structure reflects concepts of granularity and uncertainty relevant for location modelling, and gives semantics to applications of RCC-reasoning and projection-based directional reasoning in location models.

Hedda R. Schmidtke, Michael Beigl

Soft Evidential Update via Markov Chain Monte Carlo Inference

The key task in probabilistic reasoning is to appropriately update one’s beliefs as one obtains new information in the form of evidence. In many application settings, however, the evidence we obtain as input to an inference problem may be uncertain (e.g. owing to unreliable mechanisms with which we obtain the evidence) or may correspond to (soft) degrees of belief rather than hard logical facts. So far, methods for updating beliefs in the light of soft evidence have been centred around the iterative proportional fitting procedure and variations thereof. In this work, we propose a Markov chain Monte Carlo method that allows to directly integrate soft evidence into the inference procedure without generating substantial computational overhead. Within the framework of Markov logic networks, we demonstrate the potential benefit of this method over standard approaches in a series of experiments on synthetic and real-world applications.

Dominik Jain, Michael Beetz

Strongly Solving Fox-and-Geese on Multi-core CPU

In this paper, we apply an efficient method of solving two-player combinatorial games by mapping each state to a unique bit in memory. In order to avoid collisions, such perfect hash functions serve as a compressed representation of the search space and support the execution of an exhaustive retrograde analysis on limited space. To overcome time limitations in solving the previously unsolved game

Fox-and-Geese

, we additionally utilize parallel computing power and obtain a linear speed-up in the number of CPU cores.

Stefan Edelkamp, Hartmut Messerschmidt

The Importance of Statistical Evidence for Focussed Bayesian Fusion

Focussed Bayesian fusion reduces high computational costs caused by Bayesian fusion by restricting the range of the Properties of Interest which specify the structure of the desired information on its most task relevant part. Within this publication, it is concisely explained how Bayesian theory and the theory of statistical evidence can be combined to derive meaningful focussed Bayesian models and to rate the validity of a focussed Bayesian analysis quantitatively. Earlier results with regard to this topic will be further developed and exemplified.

Jennifer Sander, Jonas Krieger, Jürgen Beyerer

The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles

Electric vehicles (EV) powered by batteries will play a significant role in the road traffic of the future. The unique characteristics of such EVs – limited cruising range, long recharge times, and the ability to regain energy during deceleration – require novel routing algorithms, since the task is now to determine the most economical route rather than just the shortest one. This paper proposes extensions to general shortest-path algorithms that address the problem of energy-optimal routing. Specifically, we (i) formalize energy-efficient routing in the presence of rechargeable batteries as a special case of the constrained shortest path problem (CSPP) with hard and soft constraints, and (ii) present an adaption of a general shortest path algorithm (using an energy graph, i.e., a graph with a weight function representing the energy consumption) that respects the given constraints and has a worst case complexity of

O

(

n

3

). The presented algorithms have been implemented and evaluated within a prototypic navigation system for energy-efficient routing.

Andreas Artmeier, Julian Haselmayr, Martin Leucker, Martin Sachenbacher

Robotics

A Systematic Testing Approach for Autonomous Mobile Robots Using Domain-Specific Languages

One aspect often neglected during the development of autonomous mobile robots is the systematic validation of their overall behavior. Especially large robots applied to real-world scenarios may cause injuries or even human death and must therefore be classified as safety-critical. In this paper, a generic approach to defining and executing purposeful test runs using domain-specific languages (

dsl

s) is presented. Test cases can be defined in an appropriate test description language (first

dsl

). These test cases can be derived automatically using a model-based testing approach, for which a test model has to be created. Hence, a second

dsl

for the creation of the test model is presented. It is further shown how the generated test cases are automatically executed and evaluated. The paper concludes with the application of the approach to the autonomous off-road robot

ravon

.

Martin Proetzsch, Fabian Zimmermann, Robert Eschbach, Johannes Kloos, Karsten Berns

Collision Free Path Planning for Intrinsic Safety of Multi-fingered SDH-2

This paper presents a collision free path planning algorithm for the multi-fingered SDH2. The goal of this algorithm is the autonomous transfer of all fingers into a desired target position. The algorithm is independent of the initial finger position and may be used irrespective of any collision detection algorithm. It will be presented how forbidden finger movements can be discovered. The need for this feature, advantages and important Real-Time characteristics as well as further possibilities are discussed.

Thomas Haase, Heinz Wörn

Dynamic Bayesian Networks for Learning Interactions between Assistive Robotic Walker and Human Users

Detection of individuals intentions and actions from a stream of human behaviour is an open problem. Yet for robotic agents to be truly perceived as human-friendly entities they need to respond naturally to the physical interactions with the surrounding environment, most notably with the user. This paper proposes a generative probabilistic approach in the form of Dynamic Bayesian Networks (DBN) to seamlessly account for users attitudes. A model is presented which can learn to recognize a subset of possible actions by the user of a gait stability support power rollator walker, such as standing up, sitting down or assistive strolling, and adapt the behaviour of the device accordingly. The communication between the user and the device is implicit, without any explicit intention such as a keypad or voice.The end result is a decision making mechanism that best matches the users cognitive attitude towards a set of assistive tasks, effectively incorporating the evolving activity model of the user in the process. The proposed framework is evaluated in real-life condition.

Mitesh Patel, Jaime Valls Miro, Gamini Dissanayake

From Neurons to Robots: Towards Efficient Biologically Inspired Filtering and SLAM

We discuss recently published models of neural information processing under uncertainty and a SLAM system that was inspired by the neural structures underlying mammalian spatial navigation. We summarize the derivation of a novel filter scheme that captures the important ideas of the biologically inspired SLAM approach, but implements them on a higher level of abstraction. This leads to a new and more efficient approach to biologically inspired filtering which we successfully applied to real world urban SLAM challenge of 66 km length.

Niko Sünderhauf, Peter Protzel

Haptic Object Exploration Using Attention Cubes

This paper presents a new approach to generate a strategy for haptic object exploration. Each voxel of the exploration area is assigned to an attention value which depends on the surrounding structure, the distance to the hand, the distance to already visited points and the focus of the exploration. The voxel with the highest attention value is taken as the next point of interest. This exploration loop results in a point cloud which is classified using an Iterative-Closest-Point algorithm. The approach is evaluated in a simulation environment which includes in particular a simulation of tactile sensors.

Nicolas Gorges, Peter Fritz, Heinz Wörn

Task Planning for an Autonomous Service Robot

In the DESIRE project an autonomous robot capable of performing service tasks in a typical kitchen environment has been developed. The overall system consists of various loosely coupled subcomponents providing particular features like manipulating objects or recognizing and interacting with humans. To bring all these subcomponents together to act as monolithic system, a high-performance planning system has been implemented. In this paper, we present this system’s basic architecture and some advanced extensions necessary to cope with the various challenges arising in dynamic and uncertain environments like those a real world service robot is usually faced with.

Thomas Keller, Patrick Eyerich, Bernhard Nebel

Towards Automatic Manipulation Action Planning for Service Robots

A service robot should be able to automatically plan manipulation actions to help people in domestic environments. Following the classic sense-plan-act cycle, in this paper we present a planning system based on a symbolic planner, which can plan feasible manipulation actions and execute it on a service robot. The approach consists of five steps.

Scene Mapping

formulates object relations from the current scene for the symbolic planner.

Discretization

generates discretized symbols for

Planning

. The planned manipulation actions are checked by

Verification

, so that it is guaranteed that they can be performed by the robot during

Execution

. Experiments of planned pick-and-place and pour-in tasks on real robot show the feasibility of our method.

Steffen W. Ruehl, Zhixing Xue, Thilo Kerscher, Rüdiger Dillmann

Towards Opportunistic Action Selection in Human-Robot Cooperation

A robot that is to assist humans in everyday activities should not only be efficient, but also choose actions that are understandable for a person. One characteristic of human task achievement is to recognize and exploit opportunities as they appear in dynamically changing environments. In this paper we explore opportunistic behavior for robots in the context of pick and place tasks with human interaction. As a proof of concept we prototypically embed an opportunistic robot control program, showing that the robot exhibits opportunistic behavior using spatial knowledge, and we validated the feasibility of cooperation in a simulator experiment.

Thibault Kruse, Alexandra Kirsch

Trajectory Generation and Control for a High-DOF Articulated Robot with Dynamic Constraints

In this paper, we propose a novel and alternative approach to the task of generating trajectories for an articulated robot with dynamic constraints. We demonstrate that by focusing the effort on the generation process, the design of a trajectory controller becomes a straightforward problem. Our method is efficient and particularly suited for applications involving high-DOF articulated systems such as robotics arms or legs. We claim that our algorithm can be easily implemented by roboticists that do not share a deep background in control theory. Nevertheless, the resulting trajectories ensure a robust state-of-the-art control performance. We show, in simulation and practice, that the approach is well prepared for integration with graph-based planning techniques and yields smooth trajectories.

Marc Spirig, Ralf Kaestner, Dizan Vasquez, Roland Siegwart

Adaptive Motion Control: Dynamic Kick for a Humanoid Robot

Automatic, full body motion generation for humanoid robots presents a formidable computational challenge. The kicking motion is one of the most important motions in a soccer game. However, at the current state the most common approaches of implementing this motion are based on key frame technique. Such solutions are inflexible and cost a lot of time to adjust robot’s position. In this paper we present an approach for adaptive control of the motions. We implemented our approach in order to solve the task of kicking the ball on a humanoid robot Nao. The approach was tested both in simulation and on a real robot.

Yuan Xu, Heinrich Mellmann

Special Session: Situation, Intention and Action Recognition

An Extensible Modular Recognition Concept That Makes Activity Recognition Practical

In mobile and ubiquitous computing, there is a strong need for supporting different users with different interests, needs, and demands. Activity recognition systems for context aware computing applications usually employ highly optimized off-line learning methods. In such systems, a new classifier can only be added if the whole recognition system is redesigned. For many applications that is not a practical approach. To be open for new users and applications, we propose an extensible recognition system with a modular structure. We will show that such an approach can produce almost the same accuracy compared to a system that has been generally trained (only 2 percentage points lower). Our modular classifier system allows the addition of new classifier modules. These modules use Recurrent Fuzzy Inference Systems (RFIS) as mapping functions, that not only deliver a classification, but also an uncertainty value describing the reliability of the classification. Based on the uncertainty value we are able to boost recognition rates. A genetic algorithm search enables the modular combination.

Martin Berchtold, Matthias Budde, Hedda R. Schmidtke, Michael Beigl

Online Workload Recognition from EEG Data during Cognitive Tests and Human-Machine Interaction

This paper presents a system for live recognition of mental workload using spectral features from EEG data classified by Support Vector Machines. Recognition rates of more than 90% could be reached for five subjects performing two different cognitive tasks according to the flanker and the switching paradigms. Furthermore, we show results of the system in application on realistic data of computer work, indicating that the system can provide valuable information for the adaptation of a variety of intelligent systems in human-machine interaction.

Dominic Heger, Felix Putze, Tanja Schultz

Situation-Specific Intention Recognition for Human-Robot Cooperation

Recognizing human intentions is part of the decision process in many technical devices. In order to achieve natural interaction, the required estimation quality and the used computation time need to be balanced. This becomes challenging, if the number of sensors is high and measurement systems are complex. In this paper, a model predictive approach to this problem based on online switching of small, situation-specific Dynamic Bayesian Networks is proposed. The contributions are an efficient modeling and inference of situations and a greedy model predictive switching algorithm maximizing the mutual information of predicted situations. The achievable accuracy and computational savings are demonstrated for a household scenario by using an extended range telepresence system.

Peter Krauthausen, Uwe D. Hanebeck

Towards High-Level Human Activity Recognition through Computer Vision and Temporal Logic

Most approaches to the visual perception of humans do not include high-level activity recognitition. This paper presents a system that fuses and interprets the outputs of several computer vision components as well as speech recognition to obtain a high-level understanding of the perceived scene. Our laboratory for investigating new ways of human-machine interaction and teamwork support, is equipped with an assemblage of cameras, some close-talking microphones, and a videowall as main interaction device. Here, we develop state of the art real-time computer vision systems to track and identify users, and estimate their visual focus of attention and gesture activity. We also monitor the users’ speech activity in real time. This paper explains our approach to high-level activity recognition based on these perceptual components and a temporal logic engine.

Joris Ijsselmuiden, Rainer Stiefelhagen

Towards Semantic Segmentation of Human Motion Sequences

In robotics research is an increasing need for knowledge about human motions. However humans tend to perceive motion in terms of discrete motion primitives. Most systems use data-driven motion segmentation to retrieve motion primitives. Besides that the actual intention and context of the motion is not taken into account. In our work we propose a procedure for segmenting motions according to their functional goals, which allows a structuring and modeling of functional motion primitives. The manual procedure is the first step towards an automatic functional motion representation. This procedure is useful for applications such as imitation learning and human motion recognition. We applied the proposed procedure on several motion sequences and built a motion recognition system based on manually segmented motion capture data. We got a motion primitive error rate of 0.9 % for the marker-based recognition. Consequently the proposed procedure yields motion primitives that are suitable for human motion recognition.

Dirk Gehrig, Thorsten Stein, Andreas Fischer, Hermann Schwameder, Tanja Schultz

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise