**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. 17.4.3.1.2 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.