**Lodestar: An Unabridged Rationale** Hamza El-Kebir ![Lodestar logo.](img/LodestarLogoOnly.png width="17%") On this page[^lastupdated], I describe in detail the rationale and philosophy that underpins the development of [Lodestar](https://github.com/helkebir/Lodestar), an open-source real-time C++ control library. The greatest driver behind this project is the lack of a fast and accessible library for applying control theoretic concepts on real-life (embedded) systems. While platforms such as [ROS](https://www.ros.org/)[^ros] are popular in robotics, people working with applications that require real-time viable code and thread safety are often compelled to write their own solutions, with propiertary implementations being the norm, and a single unified solution is left to be desired. With this in mind, I set out to develop a unified and approachable control library, with the explicit intention to make it as real-time viable as possible while maintaining code transparency and providing a flexible API[^api]. !!! WARNING This page is still under construction. [^lastupdated]: _Last updated_: June 17, 2021 Core Principles ======================================================================== Lodestar is built on the following core principles: 1. ***Firm real-time* first**: * Memory demands should be known at compile-time, minimum/no dynamic memory allocation/paging. * Dynamically and statically allocated objects should share a common API. * Exceptions should be thrown with care; status-based fallbacks are preferred. * Processes should be timed, with fallback mechanisms and deadline violation reporting. 2. **Wide platform support**: * Maintain minimum demands should be imposed on compiled libraries, preferring header-only libraries instead. * Use only ISO/ANSI C++11 features. * Make full use of POSIX[^posix] RT (real-time) mechanisms (`pthread`s, `sigaction`s, etc.). 3. **Flexible interfacing and extension**: * Extendible, documented, and transparent core API. * Inproc and outproc non-blocking communication framework. * Thread-safe data types, with object-bound `mutex`es. Levels of Real-time ------------------------------------------------------------------------ The following is a common classification of levels of real-time: 1. **Soft real-time**: Delayed process completion may degrade a system's quality of service, but is tolerable. 2. **Firm real-time**: Delayed process completion may degrade a system's quality of service, but is tolerable if infrequent. 3. **Hard real-time**: Delayed process completion results in system failure. At least for the initial stages, Lodestar will try to get to the level where one could reliably call it a firm real-time framework. With sufficient testing and profiling in a hardware emulator, it is possible to extend a firm real-time system to a hard real-time system, but it could be the case that additional safety features and fallbacks are expected. This is, for now, beyond the scope of the library. What Constitutes Control? ------------------------------------------------------------------------ !!! WARNING Opinions ahead. Current and Future Features ======================================================================== For now, this section will be a checkboxed list; more details will follow. We adhere in most cases to the classification system used in [SLICOT](http://slicot.org/the-control-and-systems-library-slicot/slicot-library-organization)[^slicot]. Cursive identifiers are extensions to the SLICOT system that we devised for additional features that Lodestar provides. - [ ] **A**: Analysis Routines - [ ] **AB**: State-Space Analysis - [x] **AB04**: Continuous/Discrete Time - [x] **AB04MD**: Discrete-time <-> continuous-time conversion by bilinear transformation. - Generalized bilinear transformations have been implemented, with specialization for Tustin, Euler, and backward differencing transforms.
[ls::analysis::BilinearTransformation](https://github.com/helkebir/Lodestar/blob/master/src/analysis/BilinearTransformation.hpp) - Beyond the SLICOT spec, zero-order hold transformations based on exponential and logarithmic matrices have been implemented.
[ls::analysis::ZeroOrderHold](https://github.com/helkebir/Lodestar/blob/master/src/analysis/ZeroOrderHold.hpp) - [ ] **AB07**: Inverse and Dual Systems - [x] **AB07ND**: Inverse of a given state-space representation - Continuous-time state space inverses have been implement, but error handling is not properly done.
[ls::analysis::LinearSystemInverse](https://github.com/helkebir/Lodestar/blob/master/src/analysis/LinearSystemInverse.hpp) - [ ] **F**: Filtering - [ ] **FB**: Kalman Filters - [ ] **FB01**: _N/A_ - [ ] **FB01VD**: One recursion of the conventional Kalman filter - We currently have an implementation for finite horizon Kalman gain computation for discrete-time linear time invariant systems.
[ls::filter::DiscreteLQE](https://github.com/helkebir/Lodestar/blob/master/src/filter/DiscreteLQE.hpp) - [ ] **S**: Synthesis Routines - [ ] **SB**: State-Space Synthesis - [ ] **SB02**: Riccati Equations - [ ] **SB02MD**: Solution of continuous- or discrete-time algebraic Riccati equations (Schur vectors method) - A discrete-time ARE solver is currently in development.
[ls::synthesis::AlgebraicRiccatiEquation::solveDARE](https://github.com/helkebir/Lodestar/blob/master/src/synthesis/AlgebraicRiccatiEquation.hpp) - [ ] **T**: Transformation Routines - [ ] **TD**: Rational Matrix - [x] **TD05**: Rational Matrix to State-Space Conversion - [x] **TD05AD**: Minimal state-space representation for a proper transfer matrix - This is currently implemented for scalar transfer functions, but can easily be extended to transfer function matrices.
[ls::systems::TransferFunction::toStateSpace](https://github.com/helkebir/Lodestar/blob/master/src/systems/TransferFunction.hpp) - [ ] **U**: Utility Routines - [ ] **UD**: Numerical Data Handling - [ ] **UD01**: _N/A_ - [x] **UD01BD**: Reading a matrix polynomial - This is achieved using _GiNaC_[^ginac] routines; currently only scalar transfer functions are implemented, but this is easily extendable.
[ls::systems::TransferFunction::copyFromExpression](https://github.com/helkebir/Lodestar/blob/master/src/systems/TransferFunction.hpp) - [ ] ***US***: _Symbolic Manipulation/Data Handling_ - [ ] ***US01***: _Ordinary Differential Equations_ Code Style ======================================================================== Letter Prefixes ------------------------------------------------------------------------ The letter 'k' is used to denote constant (const, /ˈkɑnst/) variables, whereas 'K' is reserved for constant expressions (constexpr); 'k' is the 5th least frequently used letter in English[^letterfreq]. The letter 'z' is used to denoted static functions or variables whenever deemed necessary, because of its morphological similarity to 's'; 'z' is the least frequently used letter in English[^letterfreq]. [^letterfreq]: See [_Letter frequency_](https://en.wikipedia.org/wiki/Letter_frequency), Wikipedia. We consider the frequency in texts. Underscores ------------------------------------------------------------------------ Sometimes, prefixed underscores are used to denote private/protected member variables. In some cases, this can lead to clashes with reserved C/C++ symbols used by implementation macros. Most notably, this includes `_X*` (where `X` is any capital letter) and `__*`; in the global namespace, `_*` is reserved in general[^reservedsymbols]. For this reason, `*_` as a suffix poses an easy spec-compliant alternative for denoting private/protected member variables. [^reservedsymbols]: C++03 Sec. on global names, and C99 Sec. 7.1.3 on reserved identifiers; see [this answer on StackOverflow](https://stackoverflow.com/a/228797) for an excellent summary. Architecture ======================================================================== Blocks ------------------------------------------------------------------------ A commonly encountered construct in control theory are block diagrams, in which functional blocks are interconnected in various ways, not just serially, but also in parallel, with feedback, or feedforward, etc. A block can have multiple inputs and multiple outputs, and one expects that the block does _something_ with its input updates. Almost always, a change in the input triggers a change in the output of a block. Conceptually, blocks are a great visual and logical guide in any complex control system design. In terms of implementation in code, blocks require a significant amount of foresight during architectural design to cover all edge cases. In its most basic form, a block is simply a container that houses an arbitrary number of inputs and outputs (known as _slots_), each being of arbitrary type. Whenever an input or output is updated, function callbacks specific to each input or output slot will be invoked. While this is conceptually simple to grasp, it implies that there are infinitely many blocks that one could devise, each of which should have some degree of interoperability with the next. This is solved using a variadic template design, which allows slots to be defined at compile time, and illegal combination of slots and callbacks to be caught by the compiler, before any harm can be done at run time. With this degree of flexibility, it is easy to imagin a myriad of ways in which blocks and callbacks could be "abused" to create unintended changes in the system state. One could go as far as to constrain the effects of callbacks, such as outputs not changing the internal state of an external block, or outputs from one block being barred from directly feeding back into its own inputs. In spite of any of these safeguards, the user can still easily bypass any restrictions. With this, I want to quote some words of wisdom due to [Eric Niebler](http://ericniebler.com/2014/12/07/a-slice-of-python-in-c/): > "I can’t keep people from writing bad code. > But I’m guilty of collusion if I make it easy." For this reason, Lodestar sets out to provide a range of standard blocks that are guaranteed to be interoperable, with active measures to prevent unintended use of their features. It is the intention that these blocks cater to a user's basic needs, with the ability to easily conjure up new block types (inherited, or otherwise). In the latter case, it is of course the user's responsibility to exercise prudence in the way they use their custom blocks. With this said, it's time for a simple example, in which we define a block with inputs {int, double, bool} and outputs {double, double, double}. We show that an update to a single input slot can cascade down to multiple changes in the outputs by using callback functions. ### Example We have the following block layout: ************************************ * .---------. * * I0 *-->| +-->o O0 * * I1 *-->| BLOCK +-->o O1 * * I2 *-->| +-->o O2 * * '---------' * * * * .--> CB_I0_0 --. * * I0 *--+---> CB_I0_1 ---+-->o O0 * * +---> CB_I0_2 --' * * '--> CB_I0_3 --+--->o O1 * * '-->o O2 * ************************************ [Figure [block]: Block with callbacks.] Messages ------------------------------------------------------------------------ ### Message Passing In a setting in which we would like to have multiple monitoring (and perhaps interacting) clients, a (bidirectional) publisher-subscriber communication paradigm provides most flexibility. However, one must be mindful of the performance demands of such a communication protocol, making a communication library with large overhead and numerous callbacks unsuitable. For this reason, we chose to use [_NNG_](https://nng.nanomsg.org/) (_Nanomsg Next Generation_), which is a very light-weight library that provides an abstraction on top of platform-specific communication APIs, as well as providing a baseline implementation of a number of popular messaging solutions. ### Serialization We use [nanopb](https://jpa.kapsi.fi/nanopb/), a light-weight header-only implementation of Google's [Protocol Buffers](https://developers.google.com/protocol-buffers) (protobuf) for serialization. Nanopb provides a number of advantages over vanilla protobuf in the context of embedded and real-time systems. The main advantage lies in the fact that dynamic types can be constrained to have a fixed maximum length. As an example, a `string` object may have abitrary length, whereas if we constrain it to be of length 16 characters, we can allocate it as char[17] instead (the `+1` comes from '\0'). This provides yet another mechanism for statically allocating memory at compile time. Thread Safety ------------------------------------------------------------------------ Instead of using context-specific `mutex`es, it is often safer to simply assign a purpose built mutex to each object that needs to be thread-safe. A great header-only package that achieves this is [_safe_](https://github.com/LouisCharlesC/safe). The following is a thread-safe example of three threads, two of which that increment and decrement an integer, and one that prints its value. These threads run on different timescales, but write access to a shared variable can be easily made thread-safe using _safe_. We use _NNG_ utilities to create simple cross-platform threads (see [here](https://nng.nanomsg.org/man/v1.3.2/nng_thread_create.3supp.html) for more information). License & Dependencies ======================================================================== Lodestar is licensed under the permissive [BSD-3-Clause](https://opensource.org/licenses/BSD-3-Clause) license. All other content on this website is licensed under the [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.ast) license, unless stated otherwise. Lodestar currently is currently dependent on the following packages: - **Eigen**: [Eigen 3.3.9](https://eigen.tuxfamily.org/index.php?title=Main_Page) is bundled with Lodestar. Only MPL'ed elements are used (see `CMakeLists.txt` for the `EIGEN_MPL2_ONLY` flag). The [Mozilla Public License 2.0](https://www.mozilla.org/en-US/MPL/2.0/FAQ/) is not as invasive as (L)GPL, in that is requires attribution, directions to obtain the original MPL'ed source code, and an obligation to shared edits made to MPL'ed code under the MPL license. MPL was created to allow for compatiblity with the BSD family of licenses out of the box. - **GiNaC**: [GiNaC](https://www.ginac.de/) is not bundled with Lodestar, and has to be provided as a library. Since GiNaC is licensed under the terms of [GPL 3.0](https://www.gnu.org/licenses/gpl-3.0.en.html), it is not suitable for use in closed-source project. For this reason, GiNaC will mostly be used for code generation, after which it will not be included in compiled binaries. - **Nanopb**: [Nanopb 0.4.5](https://github.com/nanopb/nanopb) is bundled with Lodestar. Nanopb is licensed under the [zlib](https://opensource.org/licenses/Zlib) license, which is directly compatible with Lodestar's BSD-3 license. - **NNG** (_Nanomsg Next Generation_): [NNG](https://nng.nanomsg.org/) has to be provided as a library, and is not bundled with Lodestar. NNG uses the [MIT](https://opensource.org/licenses/MIT) license, which is directly compatible with Lodestar's BSD-3 license. (##) Glossary *Terms are listed in order of first appearance.* [^ros]: **ROS**: Robot Operating System. [^api]: **API**: Application Programming Interface. [^posix]: **POSIX**: Portable Operating System Interface, a family of standards described in IEEE 1003 and ISO/IEC 9945. [^slicot]: **SLICOT**: Subroutine Library in Systems and Control Theory. [^ginac]: **GiNaC**: GiNac is Not a CAS (Computer Algebra System). [^bsd]: **BSD**: Berkeley Software Distribution, a family of licenses.