The high agility of legged systems allows them to operate in rugged outdoor environments. In these situations, knowledge about the terrain geometry is key for foothold planning to enable safe locomotion. However, on penetrable or highly compliant terrain (e.g. grass) the visibility of the supporting ground surface is obstructed, i.e. it cannot directly be perceived by depth sensors. We present a method to estimate the underlying terrain topography by fusing haptic information about foot contact closure locations with exteroceptive sensing. To obtain a dense support surface estimate from sparsely sampled footholds we apply Gaussian process regression. Exteroceptive information is integrated into the support surface estimation procedure by estimating the height of the penetrable surface layer from discrete penetration depth measurements at the footholds. The method is designed such that it provides a continuous support surface estimate even if there is only partial exteroceptive information available due to shadowing effects. Field experiments with the quadrupedal robot ANYmal show how the robot can smoothly and safely navigate in dense vegetation.

Robots working in natural, urban, and industrial settings need to be able to navigate challenging environments. In this paper, we present a motion planner for the perceptive rough-terrain locomotion with quadrupedal robots. The planner finds safe footholds along with collision-free swing-leg motions by leveraging an acquired terrain map. To this end, we present a novel pose optimization approach that enables the robot to climb over significant obstacles. We experimentally validate our approach with the quadrupedal robot ANYmal by autonomously traversing obstacles such steps, inclines, and stairs. The locomotion planner re-plans the motion at every step to cope with disturbances and dynamic environments. The robot has no prior knowledge of the scene, and all mapping, state estimation, control, and planning is performed in real-time onboard the robot.

The development of robots that can dance has received considerable attention. However, they are often either limited to a pre-defined set of movements and music or demonstrate little variance when reacting to external stimuli, such as microphone or camera input. In this paper, we contribute with a novel approach allowing a legged robot to listen to live music while dancing in synchronization with the music in a diverse fashion. This is achieved by extracting the beat from an onboard microphone in real-time, and subsequently creating a dance choreography by picking from a user-generated dance motion library at every new beat. Dance motions include various stepping and base motions. The process of picking from the library is defined by a probabilistic model, namely a Markov chain, that depends on the previously picked dance motion and the current music tempo. Finally, delays are determined online by time-shifting a measured signal and a reference signal, and minimizing the least squares error with the time-shift as parameter. Delays are then compensated for by using a combined feedforward and feedback delay controller which shifts the robot whole-body controller reference input in time. Results from experiments on a quadrupedal robot demonstrate the fast convergence and synchrony to the perceived music.

Quadrupedal locomotion can be described as a constrained optimization problem that is very hard to solve due to the high dimensional, nonlinear and non-smooth system dynamics. In this paper, we propose a formulation that can be solved within few seconds using sequential quadratic programming. This method considers only a simplified model that just sufficiently represents the system dynamics. The output is a very coarse plan, which can be accurately and robustly followed on a real system using hierarchical whole-body control combined with inverted pendulum-based reactive stepping. Using the fully torque controllable quadrupedal robot ANYmal, we present successful experiments for walking, trotting, and gait transitions even under substantial external disturbances.

This paper presents a framework which allows a quadrupedal robot to execute dynamic gaits including trot, pace and dynamic lateral walk, as well as a smooth transition between them. Our method relies on an online ZMP based motion planner which continuously updates the reference motion trajectory as a function of the contact schedule and the state of the robot. The planner is coupled with a hierarchical whole-body controller which optimizes the whole-body motion and contact forces by solving a cascade of prioritized tasks. We tested our framework on ANYmal, a fully torque controllable quadrupedal robot which is actuated by series-elastic actuators.

Flying and walking robots can use their complementary features in terms of viewpoint and payload capability to the best in a heterogeneous team. To this end, we present our online collaborative navigation framework for unknown and challenging terrain. The method leverages the flying robot's onboard monocular camera to create both a map of visual features for simultaneous localization and mapping and a dense representation of the environment as an elevation map. This shared knowledge from the flying platform enables the walking robot to localize itself against the global map, and plan a global path to the goal by interpreting the elevation map in terms of traversability. While following the planned path, the absolute pose corrections are fused with the legged state estimation and the elevation map is continuously updated with distance measurements from an onboard laser range sensor. This allows the legged robot to safely navigate towards the goal while taking into account any changes in the environment. In this setup, our approach is independent of external localization, relative observations between the robots, and does not require an initial guess about the pose of the robots. The presented methods are fully integrated and we demonstrate their capabilities in an experiment with a hexacopter and a quadrupedal robot.

This paper introduces ANYmal, a quadrupedal robot that features outstanding mobility and dynamic motion capability. Thanks to novel, compliant joint modules with integrated electronics, the 30 kg, 0.5 m tall robotic dog is torque controllable and very robust against impulsive loads during running or jumping. The presented machine was designed with a focus on outdoor suitability, simple maintenance, and user-friendly handling to enable future operation in real world scenarios. Performance tests with the joint actuators indicated a torque control bandwidth of more than 70 Hz, high disturbance rejection capability, as well as impact robustness when moving with maximal velocity. It is demonstrated in a series of experiments that ANYmal can execute walking gaits, dynamically trot at moderate speed, and is able to perform special maneuvers to stand up or crawl very steep stairs. Detailed measurements unveil that even full-speed running requires less than 280 W, resulting in an autonomy of more than 2 h.

Legged robots require a robust and fast responding feet contact detection strategy. Common force sensors are often too heavy and can be easily damaged during impacts with the terrain. Therefore, it is desirable to detect a contact without a force sensor. This paper introduces a probabilistic contact detection strategy which considers full dynamics and differential/forward kinematics to maximize the use of available information for contact estimation. This papers shows that such strategy is much more accurate than the state-of-the-art strategy that only take one measure into account, with a quadrupedal robot.

This paper presents a framework for planning safe and efficient paths for a legged robot in rough and unstructured terrain. The proposed approach allows to exploit the distinctive obstacle negotiation capabilities of legged robots, while keeping the complexity low enough to enable planning over considerable distances in short time. We compute typical terrain characteristics such as slope, roughness, and steps to build a traversability map. This map is used to assess the costs of individual robot footprints as a function of the robot-specific obstacle negotiating capabilities for steps, gaps and stairs. Our sampling-based planner employs the RRT* algorithm to optimize path length and safety. The planning framework has a hierarchical architecture to frequently replan the path during execution as new terrain is perceived with onboard sensors. Furthermore, a cascaded planning structure makes use of different levels of simplification to allow for fast search in simple environments, while retaining the ability to find complex solutions, such as paths through narrow passages. The proposed navigation planning framework is integrated on the quadrupedal robot StarlETH and extensively tested in simulation as well as on the real platform.

We analyze the linguistic evolution of selected scientific disciplines over a 30‐year time span (1970s to 2000s). Our focus is on four highly specialized disciplines at the boundaries of computer science that emerged during that time: computational linguistics, bioinformatics, digital construction, and microelectronics. Our analysis is driven by the question whether these disciplines develop a distinctive language use—both individually and collectively—over the given time period. The data set is the English Scientific Text Corpus (scitex), which includes texts from the 1970s/1980s and early 2000s. Our theoretical basis is register theory. In terms of methods, we combine corpus‐based methods of feature extraction (various aggregated features [part‐of‐speech based], n‐grams, lexico‐grammatical patterns) and automatic text classification. The results of our research are directly relevant to the study of linguistic variation and languages for specific purposes (LSP) and have implications for various natural language processing (NLP) tasks, for example, authorship attribution, text mining, or training NLP tools.

Quadrupedal locomotion on sloped terrains poses different challenges than walking in a mostly flat environment. The robot's configuration needs to be explicitly controlled in order to avoid slipping and kinematic limits. To this end, information about the terrain's inclination is required for carefully planning footholds, the pose of the main body, and modulation of the ground reaction forces. This is even more important for dynamic trotting, as only two support legs are available to compensate for gravity and drive a desired motion. We propose a reliable method for estimating the parameters of the terrain quadrupedal robots move on, in the face of limited perception capabilities and drifting robot pose estimates. By fusing inertial measurements, kinematic data from joint encoders and contact information from force sensors, the local inclination can be robustly estimated and used to optimize the contact forces to reduce slippage. The estimated terrain information, namely the pitch and roll angles of the ground plane, is exploited in an extended version of our previous model-based control approach. Our improved control framework enabled StarlETH, a medium-sized, fully autonomous, torque-controllable quadrupedal robot, to trot on slopes of up to 21°.

Methods of optimizing a single trajectory are mature enough for planning in many applications. Yet such optimization methods applied to high Degree-Of-Freedom robots either consume too much time to be real-time or approximate the dynamics such that they lack physical consistency. In this paper, we present a method of precomputing optimized trajectories and compressing the information to get a compact representation of the optimal policy function. By varying the initial configuration of a robot and optimizing multiple trajectories, the controller gains knowledge about the optimal policy function. Such computation can be performed on a powerful workstation or even supercomputers instead of an onboard computer of the robot. The precomputed optimal trajectories are stored in a Single-hidden Layer Feedforward neural Network (SLFN) using Optimally Pruned Extreme Learning Machine (OP-ELM). This ensures minimal representation of the model and fast evaluation of the SLFN. We first explain our method using a simple time-optimal control problem with an analytical solution. We then demonstrate how this method can work even for high dimensional state by optimizing a foothold strategy of a full quadruped robot in simulation.

Developing control methods that allow legged robots to move with skill and agility remains one of the grand challenges in robotics. In order to achieve this ambitious goal, legged robots must possess a wide repertoire of motor skills. A scalable control architecture that can represent a variety of gaits in a unified manner is therefore desirable. Inspired by the motor learning principles observed in nature, we use an optimization approach to automatically discover and fine-tune parameters for agile gaits. The success of our approach is due to the controller parameterization we employ, which is compact yet flexible, therefore lending itself well to learning through repetition. We use our method to implement a flying trot, a bound and a pronking gait for StarlETH, a fully autonomous quadrupedal robot.

Legged robots come in a range of sizes and capabilities. By combining these robots into heterogeneous teams, joint locomotion and perception tasks can be achieved by utilizing the diversified features of each robot. In this work we present a framework for using a heterogeneous team of legged robots to detect slippery terrain. StarlETH, a large and highly capable quadruped uses the VelociRoACH as a novel remote probe to detect regions of slippery terrain. StarlETH localizes the team using internal state estimation. To classify slippage of the VelociRoACH, we develop several Support Vector Machines (SVM) based on data from both StarlETH and VelociRoACH. By combining the team's information about the motion of VelociRoACH, a classifier was built which could detect slippery spots with 92% (125/135) accuracy using only four features.

This paper describes a hierarchical operational space control (OSC) method based on least square optimization and outlines different ways to reduce the dimensionality of the optimization vector. The framework allows to emulate various behaviors by prioritized task-space motion, joint torque, and contact force optimization. Moreover, a methodology is introduced to partially excite the natural dynamics of the robot by open-loop motor regulation while the entire behavior is stabilized by hierarchical OSC. As a major contribution, the presented control strategies are tested and validated in real hardware walking, trotting, and pronking experiments using a fully torque controllable quadrupedal robot.

In this paper we present a method for fusing optical flow and inertial measurements. To this end, we derive a novel visual error term which is better suited than the standard continuous epipolar constraint for extracting the information contained in the optical flow measurements. By means of an unscented Kalman filter (UKF), this information is then tightly coupled with inertial measurements in order to estimate the egomotion of the sensor setup. The individual visual landmark positions are not part of the filter state anymore. Thus, the dimensionality of the state space is significantly reduced, allowing for a fast online implementation. A nonlinear observability analysis is provided and supports the proposed method from a theoretical side. The filter is evaluated on real data together with ground truth from a motion capture system.

This paper presents a state estimation approach for legged robots based on stochastic filtering. The key idea is to extract information from the kinematic constraints given through the intermittent contacts with the ground and to fuse this information with inertial measurements. To this end, we design an unscented Kalman filter based on a consistent formulation of the underlying stochastic model. To increase the robustness of the filter, an outliers rejection methodology is included into the update step. Furthermore, we present the nonlinear observability analysis of the system, where, by considering the special nature of 3D rotations, we obtain a relatively simple form of the corresponding observability matrix. This yields, that, except for the global position and the yaw angle, all states are in general observable. This also holds if only one foot is in contact with the ground. The presented filter is evaluated on a real quadruped robot trotting over an uneven and slippery terrain.

This paper presents the application of reinforcement learning to improve the performance of highly dynamic single legged locomotion with compliant series elastic actuators. The goal is to optimally exploit the capabilities of the hardware in terms of maximum jump height, jump distance, and energy efficiency of periodic hopping. These challenges are tackled with the reinforcement learning method Policy Improvement with Path Integrals (PI2) in a model-free approach to learn parameterized motor velocity trajectories as well as highlevel control parameters. The combination of simulation and hardware-based optimization allows to efficiently obtain optimal control policies in an up to 10-dimensional parameter space. The robotic leg learns to temporarily store energy in the elastic elements of the joints in order to improve the jump height and distance. In addition, we present a method to learn time-independent control policies and apply it to improve the energetic efficiency of periodic hopping.

The dynamics of micro coaxial helicopters are coupled, especially in the presence of a stabilizer bar and in dynamic maneuvers. This paper presents a model-based approach for active decoupling of the dynamics of a micro coaxial helicopter. This allows for easier and more accurate operation of the system. The nonlinear model covers all degrees of freedom for attitude and altitude. It accounts for hover and cruise flight situations and explicitly captures the off-axis dynamics and the dynamics of the stabilizer bar. A six-axis force/torque sensor and an RPM measurement system are used in a custom built test bench. It is applied for analysis of the forces and torques generated by the rotors in combination with the dynamics of the drive train and the swashplate. The parameter identification and the model validation is obtained with flight data recorded with a vision-based motion tracking system. The decoupling controller is implemented on the commercial robotic helicopter CoaX and its performance is shown via a motion experiment.

We have recently witnessed an enormous growth in the volume of structured and semi-structured data sets available on the Web. An important prerequisite for using and combining such data sets is the detection and merge of information that describes the same real-world entities, a task known as Entity Resolution. To make this quadratic task efficient, blocking techniques are typically employed. However, the high dynamics, loose schema binding, and heterogeneity of (semi-)structured data, impose new challenges to entity resolution. Existing blocking approaches become inapplicable because they rely on the homogeneity of the considered data and a-priory known schemata. In this paper, we introduce a novel approach for entity resolution, scaling it up for large, noisy, and heterogeneous information spaces. It combines an attribute-agnostic mechanism for building blocks with intelligent block processing techniques that boost blocks with high expected utility, propagate knowledge about identified matches, and preempt the resolution process when it gets too expensive. Our extensive evaluation on real-world, large, heterogeneous data sets verifies that the suggested approach is both effective and efficient.

The Semantic Web is constantly gaining momentum, as more and more Web sites and content providers adopt its principles. At the core of these principles lies the Linked Data movement, which demands that data on the Web shall be annotated and linked among different sources, instead of being isolated in data silos. In order to materialize this vision of a web of semantics, existing resource identifiers should be reused and shared between different Web sites. This is not always the case with the current state of the Semantic Web, since multiple identifiers are, more often than not, redundantly introduced for the same resources.

Keyword queries over structured databases are notoriously ambiguous. No single interpretation of a keyword query can satisfy all users, and multiple interpretations may yield overlapping results. This paper proposes a scheme to balance the relevance and novelty of keyword search results over structured databases. Firstly, we present a probabilistic model which effectively ranks the possible interpretations of a keyword query over structured data. Then, we introduce a scheme to diversify the search results by re-ranking query interpretations, taking into account redundancy of query results. Finally, we propose α-nDCG-W and WS-recall, an adaptation of α-nDCG and S-recall metrics, taking into account graded relevance of subtopics. Our evaluation on two real-world datasets demonstrates that search results obtained using the proposed diversification algorithms better characterize possible answers available in the database than the results of the initial relevance ranking.

More and more content on the Web is generated by users. To organize this information and make it accessible via current search technology, tagging systems have gained tremendous popularity. Especially for multimedia content they allow to annotate resources with keywords (tags) which opens the door for classic text-based information retrieval. To support the user in choosing the right keywords, tag recommendation algorithms have emerged. In this setting, not only the content is decisive for recommending relevant tags but also the user's preferences. In this paper we introduce an approach to personalized tag recommendation that combines a probabilistic model of tags from the resource with tags from the user. As models we investigate simple language models as well as Latent Dirichlet Allocation. Extensive experiments on a real world dataset crawled from a big tagging system show that personalization improves tag recommendation, and our approach significantly outperforms state-of-the-art approaches.

In addition to the actual content Web pages consist of navi-gational elements, templates, and advertisements. This boil-erplate text typically is not related to the main content, may deteriorate search precision and thus needs to be detected properly. In this paper, we analyze a small set of shallow text features for classifying the individual text elements in a Web page. We compare the approach to complex, state-of-the-art techniques and show that competitive accuracy can be achieved, at almost no cost. Moreover, we derive a simple and plausible stochastic model for describing the boilerplate creation process. With the help of our model, we also quantify the impact of boilerplate removal to re-trieval performance and show significant improvements over the baseline. Finally, we extend the principled approach by straight-forward heuristics, achieving a remarkable accuracy.

Tagging systems have become major infrastructures on the Web. They allow users to create tags that annotate and categorize content and share them with other users, very helpful in particular for searching multimedia content. However, as tagging is not constrained by a controlled vocabulary and annotation guidelines, tags tend to be noisy and sparse. Especially new resources annotated by only a few users have often rather idiosyncratic tags that do not reflect a common perspective useful for search. In this paper we introduce an approach based on Latent Dirichlet Allocation (LDA) for recommending tags of resources in order to improve search. Resources annotated by many users and thus equipped with a fairly stable and complete tag set are used to elicit latent topics to which new resources with only a few tags are mapped. Based on this, other tags belonging to a topic can be recommended for the new resource. Our evaluation shows that the approach achieves significantly better precision and recall than the use of association rules, suggested in previous work, and also recommends more specific tags. Moreover, extending resources with these recommended tags significantly improves search for new resources.

Collaborative Filtering systems are essentially social systems which base their recommendation on the judgment of a large number of people. However, like other social systems, they are also vulnerable to manipulation by malicious social elements. Lies and Propaganda may be spread by a malicious user who may have an interest in promoting an item, or downplaying the popularity of another one. By doing this systematically, with either multiple identities, or by involving more people, a few malicious user votes and profiles can be injected into a collaborative recommender system. This can significantly affect the robustness of a system or algorithm, as has been studied in recent work [5, 7]. While current detection algorithms are able to use certain characteristics of spam profiles to detect them, they suffer from low precision, and require a large amount of training data. In this work, we provide a simple unsupervised algorithm, which exploits statistical properties of effective spam profiles to provide a highly accurate and fast algorithm for detecting spam.

Statistical relationship determination among terms is one of the key issues in automatic thesaurus construction. We systematically analyze existing relevant approaches based on their underlying probabilistic assumptions, and propose a combined approach that overcomes their limitations.

Complex services are composed of simple services which typically need to be processed in a particular order. Two complex services only match if they agree on both, their simple services and their processing order. This matching semantics can be formalized by means of modelling complex services as finite state automata (FSAs), and analysing the intersection of the FSAs. However, computing the intersection of FSAs is computationally expensive, and thus, does not scale for large service repositories. This paper presents an approach for indexing and matching complex services using an abstraction that transforms the underlying FSA via its grammar into a form that can be indexed using available index mechanisms. Evaluation of this approach shows a performance gain of several orders of magnitude as compared to sequential matching.

Web services advocate loosely coupled systems, although current loosely coupled applications are limited to stateless services. The reason for this limitation is the lack of a method supporting matchmaking of state dependent services exemplarily specified in BPEL. In particular, the sender's requirement that the receiver must support all possible messages sent at a certain state are not captured by models currently used for service discovery. Annotated deterministic finite state automata provide this expressiveness. In this paper the transformation of a local process specification given in BPEL to annotated deterministic finite state automata is presented.

Interactive multimedia sessions cause high variations in workload due to presenting different media streams at different points in time. As users interact, the workload variations can not be predicted precisely. But admission control mechanisms need to at least estimate the workload in order to provide Quality of Service. In this paper, we investigate two approaches to estimate workloads and on this basis introduce admission control mechanisms that give stochastic QoS guarantees for such sessions. The observation based approach uses bookkept workload data for the prediction. The model based approach employs knowledge about usage patterns and media streams. For both approaches we introduce a uniform stochastic admission control criterion. Furthermore, we illustrate the relative benefits of these approaches for various session scenarios by means of simulations.

The exchange of goods and services between bargaining software agents requires new forms of brokering mechanisms which achieve consensus between conflicting parties. Such mechanisms have to be designed in a way that they give rational self-interested agents no incentives for insincere behavior. We introduce an arbiter as third party that resolves conflicting bargaining situations between the agents. To achieve non-manipulative agent behavior, we investigate three arbitration protocols that avoid different forms of manipulations and show how each trades net efficiency for robustness against manipulations. We describe the applicability of the protocols in bilateral bargaining situations and, analyze their robustness against manipulations analytically and by simulations. We compare the protocols with Nash's arbitration1 and the Groves-Clarke tax2 and characterize situations in which our protocols are superior.

One major approach to realise database integration is to adapt and merge the database schemas by defining views. When integrating object-oriented databases, the views need to adequately support object identity and methods. View objects need to be identified on the basis of the objects they have been derived from. Methods must be callable from the query processor without impeding query optimisation. Our view system for ODMG-93 supports both declarative and procedural integration of object-oriented databases. It provides flexible integration semantics without sacrificing the optimisation potential.

Jedi (Java based Extraction and Dissemination of Information) is a lightweight tool for the creation of wrappers and mediators to extract, combine, and reconcile information from several independent information sources. For wrappers it uses attributed grammars, which are evaluated with a fault-tolerant parsing strategy to cope with ambiguous grammars and irregular sources. For mediation it uses a simple generic object-model that can be extended with Java-libraries for specific models such as HTML, XML or the relational model. This paper describes the architecture of Jedi, and then focuses on Jedi's wrapper generator.

We present a methodology to semi-automatically propagate semantic modifications on local schemas of a federated database to the integrated schema. Our approach is based on a declarative schema integration methodology, called SIM, which accomplishes schema integration by resolving a set of equivalence correspondences between arbitrarily complex local subschemas. This paper extends this methodology with a more diversified set of semantic correspondences and with an approach to integrate schemas incrementally. On this basis, local schema changes can be modelled as semantic correspondences between subschemas, which extend or alter the correspondences that have led to the existing integrated schema. Propagating these changes to the integrated schema then amounts in incrementally revising the affected original schema correspondences and reintegrating the affected portions of the integrated schema.

From the beginning of 1994 to the end of 1996, the IRO-DB (Interoperable Relational and Object-Oriented Databases) ESPRIT project has developed tools for accessing relational and object-oriented databases in an integrated way, and for designing and maintaining integrated applications on large federations of heterogeneous databases. IRO-DB is based on the ODMG pivotal object model and gives an OQL/OML-C++ interface to users on a federation of relational and object-oriented databases. This paper summarizes the main problems and choices done during the system design, describes the IRO-DB architecture and components, presents the project's achievements and gives a synthesis of the lessons learned during the project's development. It also introduces future plans for the system.