Indexed Priority Queue in C++

Basics

Priority queues are a useful data structure e.g. when you repeatedly need to access the largest or smallest element of a set of values but want more efficiency than keeping an array ordered. The C++ standard library contains std::priority_queue, which works well for basic use cases. It offers insertion of elements as well as access and removal of the minimum (or maximum). It does not, however, offer a method for changing the priority of a value, which is needed for some applications (like Dijkstra’s algorithm to find shortest paths in graphs). Often such a method is called decreaseKey or changeKey. This post offers an implementation using a binary heap which supports this operation in O(log(n)) time.

Read More

Efficient Union-Find in C++ – or: Disjoint-set forests with Path Compression and Ranks

tl;dr: https://github.com/nspo/graphs-cpp/blob/master/general/include/DisjointSets.h

Basics

Disjoint-set data structures are useful in cases where you have a (possibly very large) number of elements and want to repeatedly execute two operations: marking two elements as connected, and checking whether two elements are connected. A query of the latter kind does not necessarily mean that the two elements p and q were explicitly connected to each other by the caller – it is possible, e.g., that p was first connected to the element r, and only much later in time q was also connected to r.

The disjoint sets in the data structure are commonly represented by trees, where each node in the tree contains a link to its parent, the parent in turn contains a link to the parent’s parent, and so on. The node at the root of the tree contains contains a link to itself, i.e. it is its own parent. All nodes of a tree are in the same set. It can be easily checked whether two elements are in the same set by evaluating whether they have the same root. The set of trees is called the disjoint-set forest. While this approach is common and can be implemented efficiently, the C++ standard library does not contain an implementation – this post tries to offer one.

Let us assume the data structure is used for N elements, each having an index between 0 and N-1. The links to the parent nodes of all elements can then easily be saved in an array of length N. If parent[p] == q, then q is the parent of p. Whenever two sets containing the elements p and q should be merged, this can be achieved by attaching the root of one element to the root of the other.

Read More

NMPC with CasADi and Python – Part 3: State-space equations of a 2-DOF robot with SymPy or MATLAB

CasADi is a powerful open-source tool for nonlinear optimization. It can be used with MATLAB/Octave, Python, or C++, with the bulk of the available resources referencing the former two options. This post series is intended to show a possible method of developing a simulation for an example system controlled by Nonlinear Model Predictive Control (NMPC) using CasADi and Python.

In this post, we will look at determining the system equations of a robot with two degrees of freedom in stace-space form. These state-space equations can be used for simulation and for developing a nonlinear model predictive controller. For some transformation tasks, Python with SymPy will be utilized and an alternative using the MATLAB Symbolic Math Toolbox will be shown.

During the following, we are considering a robot with two links, two masses at the end of the links, and motors applying torque as control input at the joints. A diagram of the robot is shown below.

Read More

NMPC with CasADi and Python – Part 2: Simulation of an uncontrolled system

CasADi is a powerful open-source tool for nonlinear optimization. It can be used with MATLAB/Octave, Python, or C++, with the bulk of the available resources referencing the former two options. This post series is intended to show a possible method of developing a simulation for an example system controlled by Nonlinear Model Predictive Control (NMPC) using CasADi and Python.

In this post, we will try to simulate an uncontrolled system with a forward Euler and a 4th order Runge-Kutta integration method. The latter can be the base for future closed-loop simulations.

Read More

NMPC with CasADi and Python – Part 1: ODE and steady state

CasADi is a powerful open-source tool for nonlinear optimization. It can be used with MATLAB/Octave, Python, or C++, with the bulk of the available resources referencing the former two options. This post series is intended to show a possible method of developing a simulation for an example system controlled by Nonlinear Model Predictive Control (NMPC) using CasADi and Python.

In this post, a file describing the system equations and a script to determine a steady-state setpoint will be developed. This older post contains similar code for CasADi inside MATLAB.

Read More

Linearize nonlinear state space equation in MATLAB at steady state setpoint

This post shows one way to linearize a nonlinear state equation \dot{x} = f(x,u) at a steady state setpoint (x_0, u_0) in MATLAB. It is assumed that a function ode.m exists in which the state equation is implemented:

function dx = ode(t, x, u)
    % example ODE
    dx1 = tan(x(4)) * x(2) + 2*u(2) - 1;
    dx2 = x(1) - sin(x(2));
    dx3 = 13 * x(4) + u(1) + 1;
    dx4 = 2*x(1);

    dx = [dx1; dx2; dx3; dx4];
end

Read More

Calculate Levenshtein distance in MATLAB (words or characters) with Wagner–Fischer algorithm

This is a MATLAB implementation of the Wagner–Fischer algorithm.

Read More

Convert dSPACE ControlDesk measurements to MATLAB/Simulink timeseries (updated)

(Old version here)

  • With this updated MATLAB script, multiple dSPACE ControlDesk measurements can be imported with a single execution
  • The result is saved as a tscollection (collection of timeseries) and all signals are saved with their corresponding name
  • Access imported data with Simulink ‘From Workspace’ block and, e.g., dsp_tscs{1}.my_signal

Read More

Fix for Latex4CorelDraw with CorelDraw 2017

I was not able to make the official build of Latex4CorelDraw work with CorelDraw 2017 (and Windows 10). The ‘Latex’ Docker window was always empty. The solution was to recompile it with Visual Studio 2017 Community.

Read More

Convert dSPACE ControlDesk measurement to MATLAB timeseries that can be used in Simulink

(Updated version here)

  • dSPACE ControlDesk can export measurements to mdf4 files or mat files
  • mat file exports can be converted to timeseries with this MATLAB script
  • The timeseries can then be imported into Simulink with the ‘From Workspace’ blog
  • Multiple signals can be imported at once

Example output:

>> import_dspace_mat_to_simulink_ts
--Imported dSPACE mat file 
C:\Users\Nicolai\Nextcloud\foo.mat
into workspace variable dsp_ts
--Time: 0.000000 s to 42.399572 s, 423980 steps
--2 variables are in dsp_ts:
 'In1' 'In1_1'

Read More

1 2 3