ReaK Library Overview

Current Version: 0.2.0-00

Main contributor and founder: Sven Mikael Persson, M.Sc.(Tech.) [email protected]

ReaK is a C++ software platform, library and algorithms for multi-body dynamics simulation, control, estimation, and path-planning. Intended for robotics software development and testing. This library is published as open-source under the terms of the GNU General Public License v3 (GPLv3). The library is entirely written in C++, practically no external dependencies, and utilizes three main paradigms, i.e., object-oriented programming, generic programming and template meta-programming, whichever works best in a given situation.

##What the ReaK library is

ReaK (pronounced as the 'reac' in 'reaction' or 'reactor') is a software platform which is the result of many years of accumulation of C++ code used by the original author (Sven Mikael Persson) for various project in the fields of multibody dynamics and control. At the core of the ReaK platform are several general-purpose utilities which facilitate serialization / deserialization of objects, memory sharing between distributed software modules, run-time type identification, and data input / output.

The core math libraries included in ReaK handle basic linear algebra methods (fixed and variable size vectors, variable size matrices of various structures and alignments, and matrix composition, views and slices), 2D and 3D geometric calculations (rotations and kinetostatic frame transformations), matrix numerical methods (LU, Cholesky, QR, Jacobi, SVD, PadeSAS matrix exponentials, Redheffer star-product, and matrix norms), numerical integration methods (fixed-step, variable-step, and multi-step predictor-correctors, both closed-form and iterative), and a set of optimization routines (although out-dated and seldom used). Performance optimization of these libraries is limited to good coding style, but do not expect these math libraries to be the fastest available, they were designed to be easy to use and interoperable, not for performance-critical applications.

The multibody dynamics elements of this library were developed according to the Kinetostatic Transmission Elements (KTEs) framework, as originally developed by Prof. Andres Kesckemethy at Graz University (now at the University of Duisburg-Essen), this is not, however, developed from other existing code that use KTEs, this is an original implementation which was done during the course of a Master's degree, by the original author, in Space Robotics and Automation at Aalto University, School of Science and Technology in Helsinki, Finland. This framework allows serial kinematic chains to be modeled in a modular and flexible fashion, to be used for model-based control of a robotic system and high-fidelity dynamics simulations. The construction of a dynamics model is done via a serial chain of KTEs which model simple (or complex) transmission of motion and forces (hence the 'kineto' and 'static' in Kinetostatic Transmission Elements). Available KTEs include, but not limited to, the following: inertial elements, (torsional) springs, (torsional) dampers, revolute joints, prismatic joints, free joints, rigid links, flexible Euler-Bernoulli beams, force actuators, driving actuators, geometric constraints (point-on-line and point-on-plane), dry and viscous friction, virtual-to-real model interfaces (for Virtual Model Control (VMC)), and state measurements and direct controls (no motor/controller model). Additionally, some utility classes are available, which are not KTEs but work in parallel to KTEs to extract higher-level information about the KTE chain. The main utility class is the mass_matrix_calc class which can, once given a list of degrees-of-freedom, joint motion jacobians and inertial elements, be used to compute the system's mass-matrix as well as its composing elements (twist-shaping matrix and aggregate, constant mass matrix), and their derivatives (and thus, also the time-derivative of the system mass matrix, which is useful in model-based control and estimation).

Finally, for the purpose of estimation and path-planning, the ReaK platform includes several generic algorithms and concepts for state representation and estimation, and probabilistic path-planning methods. Note that this part of ReaK is under active development (as part of the author's Ph.D. research), so it should be considered as very experimental at this stage and incomplete parts are to be expected. First, the state estimation algorithms and concepts include several variations of the Kalman filtering method, including the (Extended-)Kalman Filter ([E]KF), the (Extended-)Kalman-Bucy Filter ([E]KBF), the Hybrid Kalman Filter (HKF), the Unscented Kalman Filter (UKF), the Aggregate Kalman Filter (AKF), the Symplectic Kalman Filter (SKF), and Invariant versions of most of the filters (IKF, IKBF, IAKF, and ISKF). The implementations are all generic, based on a certain number of concepts (using the Boost.Concept-Check library) that define fundamental constructs such as a continuous-time state-space system, a continuous-time linear state-space system (including linear-time-invariant (LTI), linear-time-varying (LTV), and linearized at the current time, state and input), discrete-time versions of those state-space system concepts, an invariant state-space system, a covariance matrix representation, and a belief-state representation. Additionally, a Gaussian belief-state class is also provided for convenience. Second, the path-planning algorithms include several basic implementations and concepts related to classic probabilistic path-planning methods and other related utilities. Most algorithms build upon the framework of the Boost.Graph library, in the same programming style. Algorithms include the Anytime Dynamic A* (AD*), the Rapidly-exploring Random Tree (RRT), the Probabilistic Roadmap (PRM), and the Flexible Anytime Dynamic Probabilistic Roadmap (FADPRM). Several concepts are defined such as a metric space, a temporal space, a reachability space, as well as spatial paths and trajectories. Additionally, some of the utilities provided include linear-search through topological point-sets (for nearest-neighbor queries, through extensive search), a Dynamic Vantage-Point Tree (DVP-tree) implementation for fast nearest-neighbor queries via the partitioning of a general metric space, and a multi-index sorting of points of a reachability space for fast nearest-reachable-neighbor queries. This part of ReaK will be under heavy development during the summer of 2011, contributers are welcomed!

##What the ReaK library is NOT

• A hardware abstraction layer (HAL). ReaK does not include drivers for sensors, motors, cameras, or anything of the sort. This is a conscious design decision. The diversity of peripherals used in robotics, whether it be real hardware or a simulated environment, is vast and hence, most attempts to write one-size-fits-all hardware abstractions suffer from one or more of the following problems: excessively large, heavy-weight code-base; deep levels of indirection; maintainability nightmares; awkward mix of different programming languages; and a large number of external dependencies, and thus, lack of portability, maintainability and scalability. For all these reasons, the hardware abstraction is left to the user to implement or select his or her preferred library. The generic nature of most of the ReaK library allows for minimal requirements for use, much in the style of the C++ STL.

• A virtual environment for robot emulation. ReaK does include an entire multibody dynamics library with several features and elements. However, ReaK is designed as an open-architecture library, its target end-user is a programmer. Several software packages exist, open-source or commercial, to do low-fidelity simulations (mostly using the Open Dynamics Engine (ODE)) with the intent and purpose of creating a virtual environment where a robotic system's dynamics can be emulated in real-time and with visualization, such that high-level controllers can be tested. However, these platforms are often closed-architecture and of too low fidelity to be used to test low-level controllers, or even to compute model-based control laws numerically. On the other hand, ReaK does not include any visualization (e.g. 3D rendering) and is not meant to run simulations in real-time, but is able to compute medium to high fidelity multibody systems efficiently such that it can be used for model-based control, virtual model control, estimation and model prediction.

• A comprehensive multibody dynamics simulation software. Although ReaK does include a decent amount of multibody dynamics code, it would be highly pretentious to paint it as being a serious rival to professional, high-fidelity multibody dynamics software packages such as MSC.Adams and others. The elements of multibody dynamics simulation which are available in ReaK are the most commonly used ones (joints, links, springs/dampers, masses, etc.) and several numerical integrators are provided as well, but, still, it should not be mistaken for a professional engineering tool. The KTE framework which is used for multibody dynamics calculation in ReaK does offer enormous potential for expansion and a very simple framework to develop custom components as needed, and, in that sense, can serve as the basis for the development of multibody dynamics software (e.g. for custom dynamics elements or for research in MBD).

##License

Copyright 2011 Sven Mikael Persson

THIS SOFTWARE IS DISTRIBUTED UNDER THE TERMS OF THE GNU GENERAL PUBLIC LICENSE v3 (GPLv3).

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program (as LICENSE in the root folder).  
If not, see <http://www.gnu.org/licenses/>.

##Dependencies

Supported compilers and platforms:

• Tested on GCC 4.4.x, 4.5.x and 4.6.x.
• C++11 features were tested with GCC 4.6.2 only.
• Compatible with all platforms that support the Boost libraries and the C++ standard libraries, at least in theory.
• Tested on Linux Ubuntu/Kubuntu 9.10, 10.04, 10.10, and 11.04.
• Should be mostly compilable with MSVC 2010, although not officially maintained. Problems are likely to occur when compiling some code that makes heavy use of template meta-programming under MSVC2010, because Microsoft's implementation of templates is still very sloppy with respect to the ISO C++ Standard (1998).

External Dependencies:

• CMake build system (2.8).
• The Boost Library (www.boost.org), version 1.44.0 or later.
• Doxygen for generating the documentation (with hhc.exe for Windows compressed help files, and QHelpGenerator for Qt compressed help files (Qt Assistant files)).

Optional External Dependencies (for test-programs):

• OpenCV
• Qt 4.6 or later

#Detailed Description

##History

The author's earliest work has involved amateur 3D computer game programming (roughly 12 years ago). Back then, the author developed, amongst other things, a comprehensive math library for geometry and linear algebra calculations. These were used for 3D rendering and low-fidelity real-time physics engines, and were mostly written in Delphi (Object Pascal). The author's interest in programming shifted more and more towards dynamics simulations, as he was starting his bachelor's degree in mechanical engineering. The project that gave birth to the first design iteration of the ReaK platform was a two-year bachelor's thesis with the goal of developing a general-purpose multibody dynamics simulator for the purpose of integrating a new closed-form continuous contact dynamics formulation which could not be easily implemented using customization facilities of existing, commercial multibody dynamics packages (MSC.Adams, SimMechanics, etc.). The author, not being entirely comfortable with C++, wrote the graphical user interface in Delphi (VCL), but decided to write all the multibody dynamics software in C++, and so, ReaK was born. The name comes from the fact that this software was originally made for the purpose of resolving contact forces ("reaction" forces) in closed kinematic chains formed by continuously contacting rigid bodies. However, since then, the multibody dynamics calculation framework has been completely changed to be based on Kinetostatic Transmission Elements, which are more appropriate for serial kinematic chains and are just more scalable.

The main outcome of the first design iteration was the amount of lessons learned about managing memory, interfacing modules, creating a plugin system, binary compatibility, and just learning to work effectively with C++. Obviously, since the first iteration involved a GUI written in Delphi, it implied that the C++ code was wrapped in DLLs (back then, ReaK was Windows-only), in fact various sections of the code were bundled in different individual DLLs. Objects which were created from different DLLs would be shared between them, based on standard ABIs. A plugin system was created to allow an extensible amount of new classes to be loaded into the GUI application, with published properties and visual artifacts (OpenGL) for the GUI application to use. This implementation was very tedious to complete successfully and led to hours, days, and months of frustration over difficult bugs, across the different modules, but was eventually finished to a working level (although still buggy). Immediately following it, plans and ideas were starting to form the basis of the next design iteration, which could now be referred to as ReaK 0.1 (thus, explaining the 0.2 minor version number today).

After much thought and planning, the second iteration of the ReaK platform was started in late 2009 and used during a Master's degree in Space Robotics and Automation at Aalto University, School of Science and Technology, in Helsinki, Finland. In this version of ReaK, most of the core code, as it is now, was developed, including the base classes for the platform, the distributed shared-memory model, the custom, cross-module, cross-platform run-time type identification system (RTTI), the serialization library, and data recorders. The math libraries for linear algebra, matrix numerical methods, geometry, and numerical integration were mostly taken from the previous version, with some refactoring, and, eventually, further refactoring led to the current version of those library. Most importantly, the KTE framework was adopted to create a fairly complete suit of multibody dynamics code, which has since remained largely the same in the current version, with some additional elements. This second iteration of ReaK also included a signals-and-systems implementation which allowed a multi-threaded approach to designing behavior-based controllers via systems running on independent threads and a mix of synchronous and asynchronous signals to communicate between and trigger different control loops (or sub-systems of the overall controller). However, this latter part of ReaK 0.1 tended to be somewhat unstable due to certain rare, but possible, occurrences of data races and dead-locks. Nevertheless, ReaK 0.1 was used, in conjunction with the Machine Control Interface (MaCI) (a hardware abstraction layer developed and maintained by the department of Automation and Systems Technology, at Aalto University), to develop controllers for a humanoid torso (on a centaur-like robot, the WorkPartner) to achieve physical human-robot interactions (e.g. cooperative manipulation of large objects). The multibody dynamics library was used to compute Virtual Model Control laws (VMC) and to implement a non-linear disturbance observer which would be able to measure the human operator's force without force-sensing capabilities of any kind on the robot (i.e. no force cells or motor-current sensing). The project was largely successful and the ReaK platform was mature, stable, effective and efficient. However, the library still had some problems which led to the development of the current version of ReaK, version 0.2, making it the third design iteration.

The current version of ReaK started to take form over a period from late 2010 to early 2011. The main switch-over point is when the RTTI system was updated to rely heavily on template meta-programming techniques to produce the type information structures and registering them to a global repository of type descriptors. The main improvement to the RTTI is the formulation of type structures as linked-lists ("typelists") which produce an RTTI system which is truly scalable to templated code (i.e. better support of "typed" class templates). This is when ReaK 0.1 turned into ReaK 0.2 because this fundamental change required a slight refactoring of almost the entire platform, which means a new version of ReaK was born, not compatible with last. All the code from the previous version was ported to ReaK 0.2, with the exceptions of the signals-and-systems implementation due to the lack of stability in this implementation (i.e. a similar module in ReaK 0.2 would be nice to have in the future, but significant redesign is needed to make it stable and efficient enough, this is a low-priority right now). One of the main benefits of the new RTTI system is that it no longer requires explicit instantiation of class templates in order to register and pre-compile them. This is significant because it allowed the entire math library to become header-only and much more generic (more heavily templated).

The project which currently uses the ReaK platform is a project involving the autonomous capture of a large moving target using a mobile robotic manipulator (which is the Ph.D. topic of the author). To this end, several new additions to ReaK were made. First, several probabilistic path-planning methods were implemented, and more are anticipated. Also, spatial trajectory calculations and constructions are under development as well as several methods related to metric and temporal space concepts and point-sets (e.g. spatial partitioning, and nearest-reachable-neighbor queries). Finally, with the intent of estimating the state of a moving target and predicting its future motion, a suit of estimation methods were implemented (and more are expected in the future). These include, at the moment, almost every kind of Kalman Filter that exist (about 10 in total). This completes the historical overview of ReaK, at least, for the moment.

##Philosophy and Programming Paradigms in ReaK

This section explains a number of programming philosophies that the author holds. These are the products of many years of experience in C++ programming and with external open-source libraries. These reflect the opinions of the author, not facts, disagreements are expected and welcomed.

###KISS - Keep It Simple, Stupid!

KISS is a house-hold expression today, but it expresses a fundamental principle for good coding practices, in C++ and other languages. Something simple could also be said to have "irreducible complexity", meaning that if it cannot be made any simpler without rendering it useless, it is simple. An ideal program should be made of such building blocks. In OOP, this translates to one class for one "contract", this promotes clear interfaces, clear sub-problem definitions, and improves modularity (code reuse and flexibility). In GP, this translates to the use of concepts to define a minimal set of requirements for a type to fulfill.

###The Principle of Minimum Requirements

Related to KISS is the principle of minimum requirements. This mainly applies to generic programming, which is used (and abused) in ReaK. In GP, when defining, say, a function template, like a Kalman Filter update, it will accept a number of parameters with a number of type-arguments mostly deduced from those parameters. Those types which parametrize the function template are implicitly required to fulfill certain requirements or characteristics (e.g. be copyable, have certain functions, be callable with certain parameters, etc.) which are commonly referred to as "concepts" in generic programming (which are, in some sense, analogous to base classes in OOP, but without the requirement for a class hierarchy or inheritance, and also without the benefit of dynamic dispatching). ReaK encourages the concept requirements to be explicit, through the use of Boost.Concept-Check utilities, and minimal. For instance, when making a Kalman Filter update function template, the various parameter-types should have minimal requirements, e.g., the state-space system should be at least able to provide four matrices (A,B,C,D) which define a linear state-space system and a few additional information, but should not be required to provide any more functionality than what is strictly required by the algorithm. This principle encourages the development of concept requirements that are easy to fulfill by the user and does not enforce more than what is needed. One can find a plethora of examples of the use of this philosophy when browsing through the C++ STL Algorithms library which always states explicitly what is required of the types of a function template and these requirements are always minimal. ReaK tries to go one step further and use explicit concept-checks, compile-time asserts, and Sfinae switches to make those requirements explicit in declarations, fail to compile if not fulfilled, and use concepts to switch between overloaded function templates, respectively.

###Breaking the plague of OOP

Most C++ programmers who haven't spent the last two decades in a cave or on a distant planet have certainly heard phrases like "C++ is an object-oriented programming language", or have maybe even utters such evil words themselves. Of course, C++ is not an object-oriented programming language, it is a multi-paradigm programming language in which almost every style of programming is supported directly or indirectly. Far too many open-source libraries suffer from the close-mindedness of their authors which leads to an abuse of OOP techniques in places where it is not necessarily the most appropriate paradigm. When one takes a look at professionally developed libraries in C++, namely the standard libraries and the Boost libraries, one sees a mix of several paradigms, and OOP can hardly be seen as dominating the scene, in fact, the predominant paradigm is most probably Generic Programming (GP), and template meta-programming in the case of Boost.

So, what is wrong with OOP? ... Nothing, it just isn't good for everything. The main purpose of OOP is to associate data structures and functionalities, and utilize techniques such as dynamic polymorphism, encapsulation and abstraction. One main problem with OOP is the fact that, very often, it imposes a class hierarchy. Sometimes, a problem simply isn't very well posed as a class hierarchy, leading to awkward design. Most importantly, an imposed class hierarchy can make it difficult to interface between different libraries. For example, typical OOP libraries require that the user derive some particular base classes in order to plug them into the library's functionalities (e.g. derive from "visible_object" to add it to a 3D scene, or derive QWidget to embed it in a GUI element), this often causes difficulties in integration between the user's code, the library's code and potentially other library codes as well, often requiring many custom classes, firewall-classes (PImpl), composition, and multiple inheritance, leading to poor maintainability and strong couplings, and often inefficiencies.

The philosophy here is that OOP should be used only in the circumstances in which it works the best, namely, when dynamic polymorphism is needed, not when static polymorphism is sufficient, when there is a clear association of data elements and related functionalities, and when the class hierarchy is not really meant to be extended (derived from) in user-side code (e.g. much like the C++ iostream library). It is important to remember, in times when an OOP implementation seems awkward, that C++ offers other paradigms such as procedural programming, generic programming, and template meta-programming, that are often more appropriate, and it is that open-mindedness that I consider a break from the plague of OOP (i.e. the plague of OOP is when people see OOP as some Holy superior paradigm that should always be chosen).

###Paradigms per Sections of ReaK

Like C++, ReaK is a multi-paradigm library. Different parts of the library use different paradigms based on the nature of the code. ReaK includes a small hierarchy of bases classes which can be used for any non-POD class which are part of the library or use the library. These bases classes serve the purpose of associating type information and casting to a class (ReaK::rtti::typed_object), making a class serializable (ReaK::serialization::serializable), making class sharable between modules (ReaK::shared_object), and associating a name to the class (ReaK::named_object). Evidently, OOP is best suited for this purpose since dynamic polymorphism is required (dynamic casting) and the separation between contracts is clear. The fact that this hierarchy is small and light-weight reduces the impact this could have on user-side code which do not strictly have to derive from shared_object or named_object, but should if cross-module RTTI and serialization is a feature the user wants to benefit from (i.e. you pay for what you get).

Another fundamental part of ReaK is the RTTI and serialization libraries. The RTTI system relies heavily on template meta-programming to generate, at compile-time, type lists, descriptors and factories such that the serialization library can properly record the types to a file (or other stream) and load them as well. Obviously, the association of type information is fundamentally a compile-time mechanism, and thus, TMP makes most sense. OOP was used to achieve this in past versions of ReaK, but TMP was found to be much more scalable.

The multibody dynamics components of ReaK are certainly object-oriented as they have a natural association of data and functionalities, and a clear contract from the KTE framework (transmit motion and forces). However, in addition to OOP, the workflow for the user of the MBD libraries is most akin to that of Declarative Programming. In other words, building a model is done via what is essentially laying out the structure of the model (constructing the chain of KTEs), while the control flow involved in evaluating or running a model is hidden. In that sense, the user declares his model, and cares not of the control flow details. This is a natural paradigm to use in this case because the control flow is exactly what should be encapsulated, not the data (which is opposite to classic OOP software models where data is encapsulated and the workflow is controlled by the user, i.e., Functional Programming).

Finally, the estimation and path-planning parts of ReaK are very algorithmic in nature (graph searches, Kalman filter updates, nearest-neighbor queries, etc.). Much in the same style as other well known libraries like STL Algorithms and Boost.Graph, this part of ReaK is entirely generic. There are no base classes, no direct couplings to the rest of the ReaK platform, and all requirements are formulated as "concepts", "traits", and "meta-functions". Most of the math libraries are also designed in a similar fashion (especially the linear algebra part). The logic here is that things that are very algorithmic in nature typically apply to a large number of "value-types" (or more complex types) and it is thus more natural that they be implemented generically. This also shows how generic programming interacts with other paradigms, for instance most estimation and path-planning algorithms are simply function templates, expecting more or less complex classes as arguments. In other words, the algorithms are formulated in procedural programming style to interface with object-oriented code via generic concepts and traits. Note that other math libraries of ReaK have the inverse interaction which is also very useful. And again, this renders dependencies very local and imposes very few requirements on the user-side.