1.1.1 what are the aspects of autonomy?

1.5.1 Come back to sensing

Multiple sensors in an autonomous vehicle → need to combine them somehow

sensor fusion

Once we have information from the sensors (fused or otherwise)…

We need state estimation (kalman filter, ekf).

1.6.1 high-order functions

In order to answer the following, we need additional functionality. Let us go through what that might be.

1.6.2 slam

Simultaneous localization and mapping → figure out where we are.

1.6.3 waypoint detection

Understand how to move in the right direction at the micro level, i.e., find waypoints.

1.6.4 yolo

Is it “you only live once”? Actually this stands for: “you only look once”. It is an object detection model that uses convolutional neural networks (cnns)

1.6.5 object avoidance

The objective is to avoid objects in the immediate path.

1.6.6 path planning

i.e., how to get to destination at the macro level → uses waypoints.

1.6.7 compute platform

To run all of these functions, we need low power, embedded platforms.

1.6.8 still some non-functional requirements remain

any guesses what they could be?

1.6.9 safety!

Essentially safety of → operator, other people, the vehicle, environment This is cross-cutting issue → affected by all parts of system.

1.6.10 security

Security is another cross-cutting issue → can affect all components.

1.6.11 Course Structure

Hence this figure is a (loose) map of this course:

2.2.1 Microcontrollers

According to Wikipedia,

“A microcontroller (MC, UC, or μC) or microcontroller unit (MCU) is a small computer on a single integrated circuit.”

These may be among the most common type of “processors” used in embedded systems. According to many studies, more than 55% of the world’s processors are microntrollers! Microcontrollers are typically used in small, yet critical, systems such as car engine control, implantable medical devices, thermal monitoring, fault detection and classification among millions of other applications.

Microcontrollers hardware features typically include,

There are some additional features found on some microcontrollers, viz.,

Some examples of popular microcontroller families:

Atmel ATmega	Microchip Technology	Motorola (Freescale)	NXP

Microcontroller programs and data,

• are small –> must fit in memory (since very little expandable memory exists)
• often directly programmed in assembly!
  • sometimes the assembly code might need hand tuning –> for both, performance as well as fitting into the limited memory
• C is another popular language
• no operating systems (or very rare)!
• sometimes have their own special-purpose programming languages or instructions

2.2.2 Digital Signal Processors (DSPs)

DSPs are specialized microcontrollers optimized for digital signal processing. They find wide use in audio processing, radar and sonar, speech recognition systems, image processing, satellites, telecommunications, mobile phones, televisions, etc. Their main goals are to isoloate, measure, compress and filter analog signals in the real world. They often have stringent real-time constraints.

The Texas Instruments DSP chip, TMS320 Series is one of the most famous example of this type of system:

Typical digital signal processing (of any kind) requires repetitive mathematical operations over a large number of samples, in real-time, viz., - analog to digital conversion - maniupulation (the core algorithm) - digital to analog conversion

Often, the entire process must be completed with low latency, even within a fixed deadline. They also have low power requirements since DSPs are often used in battery-constrained devices such as mobile phones. Hence, the proliferation of specialized DSP chips (instead of pure software implementations, which also exist; MATLAB has an entire DSP System Toolbox).

Typical DSP architecture/flow (credit: Wikipedia):

These types of chips typically have custom instructions for optimizing certain (mathematical) operations (apart from the typical add, subtract, multiply and divide), e.g., - saturate; caps the minimum or maximum value that can be held in a fixed-point representation - ed ; euclidian distance - accumulate instructions ; for multiply-and-accumulate operations, i.e., a ← a + (b * c)

See the Microchip instruction set details for more information for a typical DSP ISA.

DSPs require optimization of streaming data and hence, - require optimized memories and caches → fetch multiple data elements at the same time - code may need to be aware of, and explicitly manipulate caches - may have rudimentary OS but no virtual memory

2.2.3 Microprocessors

Microprocessors are, then, general-purpose chips (as opposed to microcontrollers and DSPs) that are also used extensively in embedded systems. They are used in systems that need more heavy duty computing/memory and/or more flexibility in terms of programming and management of the system. They use a number of commodity processor architectures (e.g,, ARM, Intel x86).

Main features of microprocessors:

The ARM M-85 Embedded Microprocessor architecture:

When compared to microcontrollers (or even SoCs), most microprpcessors do not include components such as DSPs, ADCs, DACs, etc. It is possible to augment the microprocessor to include this functionality → usually by connecting one or more microcontrollers to it!

On the software side, microprocessors typically have the most flexibility:

• general purpose operating systems (e.g., Linux, Android, Windows, UNIX, etc.)
• most programming languages and infrastructures (even Docker!)
• large number of tooling, analysis, debugging capabilities
• complex code can run, but increases analysis difficulty

Due to their power (and cost) these types of systems are only used when really necessary or in higher-end systems such as mobile phones and autonomous cars.

2.2.4 System-on-a-Chip (SoC)

An SoC integrates most components in and around a processor into a single circuit, viz.,

• processor/chip → could be a microcontroller or even a microprocessor
• memory and memory interfaces
• I/O devices
• buses (memory and I/O)
• storage (e.g., flash) and sometimes even secondary storage
• radio modems
• (sometimes) accelerators such as GPUs

All of these are placed on a single substrate.

SoCs are often designed in C++, MATLAB, SystemC, etc. Once the hardware architectures are defined, additional hardware elements are written in hardware description languages, e.g., register transfer levels (RTL) ².

Additional components could include,

• DAC
• ADC
• radio and signal processing
• wireless modems
• programmable logic.
• networks on chip (NoC) ³

In some sense, an SoC is an integration of a processor with peripherals. New hardware elements

Some examples of modern SoCs:

The integration of all hardware components has some interesting side-effects:

Depending on the processor/microcontroller that sits at the center of the SoC, the software stack/capabilities can vary. Many commons SoCs exhibit the following software properties:

• usually use contemporary operating systems, though optimized for embedded/SoC systems → e.g., Raspbian aka Rasberry Pi OS. Hence, they can handle multiprocessing, virtual memory, different scheduling policies, etc.
• can be programmed using most common programming languages → C, C++, python, java, even lisp!

The Raspberry Pi is a common example of a system that uses a Broadcom BCM series of SoCs. We use the BCM2711 SoC in our course for the Raspberry Pi 4-B.

2.2.5 Embedded Accelarators (e.g. GPU-enabled systems)

There are hardware platforms that include accelerators in embedded systems, e.g., GPUs, AI-enabled silicon, extra programmable FPGA fabric, security features, etc. The main idea is that certain computation can be offloaded to these accelerators while the main CPU continues to process other code/requests. The accelerators are specialized for certain computations (e.g., parallel matrix multiplications on GPUs, AES encryption). Some chips include FPGA fabric where the designer/user can implement their own custom logic/accelerators.

In a loose sense, the Navio2 can be considered as a hardware coprocessor for the Raspbery Pi.

The NVidia Jetson Orin is a good example of an AI/GPU focussed embedded processor:

This system’s specifications:

• 1300 MHz clock speeds
• 64 GB Memory
• 256 bit memory bus
• 204 GB/s bandwidth
• supports a variety of graphics features (DirectX, OpenGL, OpenCL, CUDA, Vulkan and Shader Models )
• maximum of 60W power
• 275 trillion operations/s (TOPS)!

These systems are finding a lot of use in autonomous systems since they pack so much processing power into such a small form factor

2.2.6 ASICs and FPGAs

Application-specific integrated circuits (ASICs) and field programmable gate arrays (FPGAs). These platforms combine the advantages of both, hardware (speed) and software (flexibility/programmability). They are similar, yet different. Both are semiconductor devices that include programmable logic gates but an ASIC is static – i.e., once the board has been “programmed” it cannot be changed while an FPGA, as the name implies, allows for “reprogramming”.

ASICs are custom-designed for specific applications and provide high efficiency and performance. FPGAs are reprogramamble devices that provide significant flexibility. Many designers also used it for prototyping hardware components (before they are eventually included either in the processors or custom ASICs). The choice between ASICs and FPGAs depends entirely on the application requirements and other factors such as cost.

An ASIC	Xilinx Spartan FPGA

2.3.1 UART | RS-232

Serial communication standards are used extensively across many domains, mainly due to their simplicity and low hardware overheads. The most common among these are the asynchronous serial communication systems.

From Wikipedia:

Asynchronous serial communication is a form of serial communication in which the communicating endpoints’ interfaces are not continuously synchronized by a common clock signal. Instead of a common synchronization signal, the data stream contains synchronization information in form of start and stop signals, before and after each unit of transmission, respectively. The start signal prepares the receiver for arrival of data and the stop signal resets its state to enable triggering of a new sequence.

The following figure shows a communication sample that demonstrates these principles:

We see that each byte has a start bit, stop bit and eight data bits. The last bit is often used as a parity bit. All of these “standards” (i.e., the start/stop/parity bits) must be agreed upon ahead of time.

A universal asynchronous receiver-transmitter (UART) then is a peripheral device for such asynchronous commnication; the data format and transmission speeds are configurable. It sends data bits one-by-one (from least significant to most). The precise timing is handlded by the communication channel.

The electric signalling levels are handled by an external driver circuit. Common signal levels:

• RS 232
• RS-485
• raw TTL

Here we will focus on the RS-232 standard since it is most widely used UART signaling level standard today. The full name of the standard is: “EIA/TIA-232-E Interface Between Data Terminal Equipment and Data Circuit-Termination Equipment Employing Serial Binary Data Interchange” (“EIA/TIA” stands for the Electronic Industry Association and the Telecommunications Industry Association). It was introduced in 1962 and has since been updated four times to meet evolving needs.

The RS-232 is a complete standard in that it specifies,

• (common) voltage and signal levels
• (common) pin and wiring configurations
• (minimal) control information between host/peripherals

The RS-232 specifies the electrical, functional and mechanical characteristics to meet all of the above criteria.

For instance, the electrical characteristics are defined in the following figure:

Details:

• high level [logical 0] (aka “marking”) → +5V to +15V (realistically +3V to +15V)
• low level [logical 1] (aka “spacing”) → -5V to -15V (realistically -3V to -15V)

Other properties also defined, e.g., “slew rate”, impedance, capacitive loads, etc.

The standard also defines the mechanical interfaces, i.e., the pin connector:

While the official standard calls for a 25-pin connector, it is rarely used. Instead, the 9-pin connector (shown on the right in the above figure) is in common use.

You can read more details about the standard here: RS 232

2.3.2 Synchronous | I²C and SPI

Synchronous Serial Interfaces (SSIs) are a widely used in industrial applications between a master device (e.g. controller) and a slave device (e.g. sensor). It is based on the RS-422 standards and has a high protocol efficiency as well multiple hardware implementations.

SSI properties:

• differential signalling
• simplex (i.e., unidirectional communication only)
• non-multiplexed
• point-to-point and
• uses time-outs to frame the data.

2.3.2.2 SPI

The Serial Peripheral Interface (SPI) has become the de facto standard for synchronous serial communication. It is used in embedded systems, especially between microcontrollers and peripheral ICs such as sensors, ADCs, DACs, shift registers, SRAM, etc.

The main aspect of SPI is that one main device orchestrates communication with one ore more sub/peripheral devices by driving the clock and chip select signals.

SPI interface properties:

• synchronous
• full duplex
• main-subnode (formerly called “master-slave”)
• data from the main or the subnode is synchronized on the rising or falling clock edge
• main and subnode can transmit data at the same time
• interface can be 3 or 4-wire (4 wire version is more popular)

microchip SPI	basic SPI Interface

The SPI interface contains the following wires:

signal	description	function
SCLK	serial clock	clock signal from main
CS	chip/serial select	To select which host to communicate with
MOSI	main out, subnode In	serial data out (SDO) for host to target communication
MISO	main in, subnode Out	serial data in (SDI) for target to host communication

The main node generates the clock signal. Data transmissions between main ahd sub nodes is synchronized by that clock signal generated by main. SPI devices support much higher clock frequencies than I2C. The CS signal is used to select the subnode. Note that this is an active low signal, i.e., a low (0) is a selection and a high (1) is a disconnect. SPI is a full-duplex interface; both main and subnode can send data at the same time via the MOSI and MISO lines respectively. During SPI communication, the data is simultaneously transmitted (shifted out serially onto the MOSI/SDO bus) and received (the data on the bus (MISO/SDI) is sampled or read in).

Example: the following example demonstrates the significant savings and simplification in systems design (reduce the number of GPIO pins required).

Consider the ADG1412 switch being managed by a microcontroller as follows:

Now, as the number of switches increases, the requirement on GPIO pins also increases significantly. A 4x4 configuration requires 16 GPI pins, thus reducing the number of pins available for the microcontroller for other tasks, as follows:

One approach to reduce the number of pins would be to use a serial-to-parallel convertor:

This reduces the pressure on the number of GPIO pins but still introduces additional circuitry.

Using an SPI-enabled microcontroller reduces the number of GPIOs required and and eliminates the overheads of the needing additional chips (serial-to-paralle convertor):

In fact, using a different SPI configuration (“daisy-chain”), we can optimize the GPIO count even further!

You can read more about SPI here.

2.3.3 General-Purpose I/O (GPIO)

A GPIO is a signal pin on an integrated circuit or board that can be used to perform digital I/O operations. By design, it has no predefined purpose → can be used by hardware/software developers to perform functions they choose, e.g.,

• GPIO pins can be enabled or disabled.
• GPIO pins can be configured to be input or output.
• input values are readable, often with a 1 representing a high voltage, and a 0 representing a low voltage.
• input GPIO pins can be used as “interrupt” lines, which allow a peripheral board connected via multiple pins to signal to the primary embedded board that it requires attention.
• output pin values are both readable and writable.

GPIOs can be implemented in a variety of ways,

• as a primary function of the microcontrollers, e.g., Intel 8255
• as an accessory to the chip

While microcontrollers may use GPIOs are their primary external interface, many a time the pins may be capable of other functions as well. In such instances, it may be necessary to configure the pins using other functions.

Some examples of chips with GPIO pins:

Intel 8255	PIC microchip	ASUS Tinker
24 GPIO pins	29 GPIO pins	28 GPIO pins

GPIOs are used in a diverse variety of applications, limited only by the electrical and timing specifications of the GPIO interface and the ability of software to interact with GPIOs in a sufficiently timely manner.

Some “properties”/applications of GPIOs:

• GPIOs use standard logic levels and cannot supply significant current to output loads
• high-current output buffers or relays can be used to control high-power devices
• input buffers, relays, or opto-isolators translate incompatible signals to GPIO logic levels
• GPIOs can control or monitor other circuitry on a board, such as enabling/disabling circuits, reading switch states, and driving LEDs
• multiple GPIOs can implement bit banging communication interfaces like I²C or SPI
• GPIOs can control analog processes via PWM, adjusting motor speed, light intensity, or temperature
• PWM signals from GPIOs can be converted to analog control voltages using RC filters

GPIO interfaces vary widely. Most commonly, they’re simple groups of pins that can switch between input/output. On the other hand, each pin can be set up differently → set up/accept/source different voltages/drive strengths/pull ups and downs.

Programming the GPIO:

• usually pin states are exposed via different interfaces, e.g., memory-mapped I/O peripherals or dedicated I/O port instructions
• input values can be used as interrupts (IRQs)

For more information on programming/using GPIOs, read these: GPIO setup and use, Python scripting the GPIO in Raspberry Pis, general purpose I/O, GPIO setup in Raspberry Pi.

2.3.4 JTAG Debugging Interface

The JTAG standard (named after the “Joint Test Action Group”), technically the IEEE Std 1149.1-1990 IEEE Standard Test Access Port and Boundary-Scan Architecture, is an industry standard for testing and verification of printed circuit boards, after manufacture.

“JTAG”, depending on the context, could stand for one or more of the following:

• implementation of IEEE 1149.x for Board Test, or Boundary Scan testing
• appliance used to program on board flash or eeprom devices on a circuit board
• hardware device used to debug microprocessor software
• hardware device used to test a board using Boundary Scan

The basic building block of a JTAG OCD is the Test Access Point or TAP controller. This allows access to all the custom features within a specific processor, and must support a minimum set of commands. On-chip debugging is a combination of hardware and software.

The off-chip parts are actually PC peripherals that need corresponding drivers running on a separate computer. On most systems, JTAG-based debugging is available from the very first instruction after CPU reset, letting it assist with development of early boot software which runs before anything is set up. The JTAG emulator allows developers to access the embedded system at the machine code level if needed! Many silicon architectures (Intel, ARM, PowerPC, etc.) have built entire infrastructures and extensions around JTAG.

A high-level overview of the JTAG architecture/use:

JTAG now allows for,

• processors can not be halted, single-stepped or run freely
• can set code breakpoints for both, code in RAM as well as ROM/flash
• data breakpoints are available
• bulk data download to RAM
• access to registers and buses, even without halting the processors!
• complex logic routines, e.g., ignore the first seven accesses to a register from one particular subroutine

JTAG allows for device programmer hardware allows for transfering data into internal, non-volatile memory of the system! Hence, we can use JTAGs to program devices such as FPGAs. In fact, many memory chips also have JTAG interfaces. Some modern chips also allow access to the the (internal and external) data buses via JTAG.

JTAG interface: depending on the actual interface, JTAG has 2/4/5 pins. The 4/5 pin versions are designed so that multiple chips on a board can have their JTAG lines daisy-chained together if specific conditions are met.

Schematic Diagram of a JTAG enabled device:

The various pins signals in the JTAG TAP are:

The TAP controller implements the following state machine:

To use the JTAG interface,

• host is connected to the target’s JTAG signals (TMS, TCK, TDI, TDO, etc.) through some kind of JTAG adapter
• adapter connects to the host using some interface such as USB, PCI, Ethernet, etc.
• host communicates with the TAPs by manipulating TMS and TDI in conjunction with TCK
• host reads results through TDO (which is the only standard host-side input)
• TMS/TDI/TCK output transitions create the basic JTAG communication primitive on which higher layer protocols build

For more information about JTAG, read: Intel JTAG Overview, Raspberry Pi JTAG programming, Technical Guide to JTAG and the JTAG Wikipedia Entry is quite detailed.

2.3.5 Controller Area Network (CAN)

CAN is a vehicle bus standard to enable efficient communication between electronic control units (ECUs). CAN is,

• broadcast-based
• message-oriented
• uses arbitration → for data integrity/prioritization

CAN does not need a a host controller. ECUs connected via the CAN bus can easily share information with each other. all ECUs are connected on a two-wire bus consisting of a twisted pair: CAN high and CAN low. The wires are often color coded:

CAN wiring	multi-ecu CAN setup

An ECU in a vehicle consists of:

components	internal architecture
microcontroller to interpret/send out CAN messages CAN controller ensures all communication adheres to CAN protocols CAN transceiver connects CAN controller to the physical wires

Any ECU can broadcast on the CAN bus and the messages are accepted by all ECUs connected to it. Each ECU can either choose to ignore the message or act on it.

what are the implications for security?

While there is no “standard” CAN connector (each vehicle may use different ones), the CAN Bus DB9 connector has become the de facto standard:

The above figure shows the various pins and their signals.

CAN Communication Protocols: CAN is split into:

layer	relation to OSI stack
data link: CAN frame formats, error handling, data transmission, data integrity physical: cable types, electrical signal levels, node requirements, cable impedance, etc.

All communication over the CAN bus is done via the CAN frames. The standard CAN frame (with an 11-bit identifier) is shown below:

While the lower-level CAN protocols described so far work on the two lowest layers of the OSI networking stack, it is still limiting. For instance, the CAN standard doesn’t discuss how to,

• decode RAW data
• handle larger data (more than 8 bytes)

Hence, some higher-order protocols have been developed, viz.,

There also exist other higher-order protocols (numbering in the thousands) the most prominent of which are: ARINC, UAVCAN, DeviceNet, SafetyBUS p, MilCAN, HVAC CAN.

More details about CAN and its variants: CAN Bus Explained.

2.3.6 Other Broadly Used Protocols

Autonomous (and other embedded systems) use a variety of other communication protocols in order to interface with the external world and/or other systems (either other nodes in the system or external components such as back end clouds).

Note that since many of these are well known and publicly documented, we won’t elaborate much here.

Here are some of the well known communication protocols, also used in embedded systems:

3.1.1 Inertial Measurement Units (IMU)

These sensors define the movement of a vehicle, along the three axes, in addition to other behaviors like acceleration and directionality. An IMU typically includes the following sensors:

As we see from the first picture above, an IMU also has a CPU (typically a microcontroller) to manage/collect/process the data from the sensors.

The functions of the three sensors are:

1. gyroscope: is an inertial sensor that measure an object’s angular rate with respect to an inertial reference frame. It measures the following movements:

“yaw”	“pitch”	“roll”

IMUs come in all shapes and sizes. These days they’re very small but the original IMU’s ver really large, as evidenced by the one used in the Apollo space missions:

2. accelerometer: is the primary sensor responsible for measuring inertial acceleration, or the change in velocity over time.

3. magnetometer: measures the strength and direction of magnetic field – to find the magnetic north

3.1.2 Bouncing of Electromagnetic Waves | LiDAR and mmWave

A very common principle for measuring surroundings is to bounce electromagnetic waves off nearby objects and measuring the round trip times. Shorter times indicate closer objects while longer times indicate objects that are farther away. RADAR is a classic example of this type of sensor and its (basic) operation is shown in the following image (courtesy NOAA):

While many autonomous vehicles use RADAR, we will focus on other technologies that are more prevalent and provide much higher precision, viz.,

1. LiDAR
2. millimeter Wave RADAR (mmWave)

3.1.2.1 Light Detection and Ranging (LiDAR)

LiDAR is a sensor that uses (eye safe) laser beams for mapping surroundings and creating 3D representation of the environment. So lasers are used for,

• imaging
• detection
• ranging

We can use LiDAR to distance, angle as well as the radial velocity of some objects – all relative to the autonomous system (rather the sensor). So, in practice, this is how it operates:

We define a roundtrip time, $ au$, as the time between when a pulse is sent out from the transmitter (TX) to when light reflected from the object is detected at the receiver (RX).

So, the target range (i.e., the distance to te object), R, is measured as:

R = raccau2

where, c is the speed of light.

More details (from Mahalati): > Lasers used in lidars have frequencies in the 100s of Terahetrz. Compared to RF waves, lasers have significantly smaller wavelengths and can hence be easily collected into narrow beams using lenses. This makes DOA estimation almost trivial in lidar and gives it significantly better reso- lution than MIMO imaging radar.

The end product of LiDAR is essentially a point cloud, defined as:

a collection of points generated by a sensor. Such collections can be very dense and contain billions of points, which enables the creation of highly detailed 3D representations of an area.

In reality, point cloud representations around autonomous vehicles end up looking like:

Point clouds provide valuable information, viz.,

• 3D coordinates, (x, y, z)
• strength of returned signal → provides valuable information about the density of the object (or even material composition)!
• additional attributes: return number, scan angle, scan direction, point density, RGB color values, and time stamps → each can be used for refining the scan.

There are two types of scene illumination techniques for LiDAR:

type	illumination method	detector
flash lidar	entire scene using wide laser	receives all echoes on a photodetector array
scanning lidar	very narrow laser beams, scan illumination spot with laser beam scanner	single photodetector to sequentially estimate $ au$ for each spot

	flash lidar	scan lidar
architecture
resolution determined by	photodetector array pizel size (like camera)	laser beam size and spot fixing
frame rates	higher (up to 100 fps)	lower (< 30 fps)
range	shorter (quick beam divergence, like photography)	longer (100m+)
use	less common	most common

Now, consider the following scene (captured by a camera):

Compare this to the LiDAR images captured by the two methods:

flash lidar	scan lidar (16 scan lines)	scan lidar (32 scan lines)

A “LiDAR scan line” refers to a single horizontal line of laser pulses emitted by a LiDAR sensor, essentially capturing a cross-section of the environment at a specific angle as the sensor rotates, creating a 3D point cloud by combining multiple scan lines across the field of view; it’s the basic building block of a LiDAR scan, similar to how a single horizontal line is a building block of an image.

Potential Problems:

Atmospheric/environmental conditions can negatively affect the quality of the data captured by the LiDAR. For instance, fog can scatter the laser photons resulting in false positives.

As we see from the above image, the scattering due to the fog results in the system “identifying” multiple objects even though there is only one person in the scene.

Here are additional examples from the Velodyne VLP-32C sensor:

1. light fog (camera vs LiDAR)

The LiDAR does a good job isolating the main subject with very few false positives.

2. heavy fog (camera vs LiDAR)

The LiDAR struggles to isolate the main subject with very high false positives.

In spite of these issues, LiDAR is one of the most popular sensors used in autonomous vehicles. They’re getting smaller and more precise by the day; also decreasing costs means that we will see a proliferation of these types of sensors in many autonomous systems.

For an in-depth study on LiDARs, check this out: Stanford EE 259 LiDAR Lecture.

3.1.2.2 Millimeter Wave Radar [mmWave]

Short wavelengths like the *millimeter wave (mmWave**) in the electromagnetic spectrum allows for:

• smaller antennae
• integration of entire RADAR circuitry in a single chip!
• spectrum of 10 millimeters (30 GHz) to 1 millimeter (300 GHz)

As we see from the above images, the sensors can be very small, yet very precise → some can detect movements up to 4 millionths of a meter!

Advantages of mmWave:

Advantage	Description
small antenna caliber	narrow beam gives high tracking, accuracy; high-level resolution, high-resistance interference performance of narrow beam; high antenna gain; smaller object detection
large bandwidth	high information rate, details structural features of the target; reduces multipath, and enhances anti-interference ability; overcomes mutual interference; high-distance resolution
high doppler frequency	good detection and recognition ability of slow objectives and vibration targets; can work in snow conditions
good anti-blanking performance	works on the most used stealth material
robustness to atmospheric conditions	such as dust, smoke, and fog compared to other sensors
operation under different lights	radar can operate under bright lights, dazzling lights, or no lights
insusceptible to ground clutter	allowing for close-range observations; the low reflectivity can be measured using mmwave radar
fine spatial resolution	for the same range, mmwave radar offers finer spatial resolution than microwave radar >

mmWave is also used for in-cabin monitoring of drivers!

Limitations:

• line of sight operations
• affected by water content, gases in environments
• affected by contaminated environment and physical obstacles

Resources:

For a more detailed description of mmWave RADAR, read: Understanding mmWave RADAR, its Principle & Applications

For programming a LiDAR, see: how to program a LiDAR with an Arduino.

3.1.3 Ultrasonic

Much like lidars, we can use reflected sounds waves to detect objects. They work by emitting high-frequency sound waves, typically above human hearing, and then listening for the echoes that bounce back from nearby objects. The sensor calculates the distance based on the time it takes for the echo to return, using the speed of sound. Popular modules like the HC-SR04 (Used in Lab#2) are easy to integrate with microcontrollers such as Arduino and Raspberry Pi. These sensors are widely used in robotics for obstacle avoidance, automated navigation, and liquid level sensing.

However, unlike optical (electromagnetic waves) detectors, ultrasonic sensors, while useful for basic distance measurements, cannot replicate the functionalities of LiDAR systems due to several key limitations. Unlike LiDAR, which employs laser beams to generate high-resolution, three-dimensional point clouds, ultrasonic sensors emit sound waves that provide only limited, single-point distance data with lower precision. LiDAR offers greater accuracy and longer range, enabling detailed mapping and object recognition essential for applications like autonomous vehicles and advanced robotics. Additionally, LiDAR systems can cover a wider field of view and operate effectively in diverse environments by rapidly scanning multiple directions, whereas ultrasonic sensors typically have a narrow detection cone and struggle with complex or cluttered scenes. Furthermore, LiDAR’s ability to capture data at high speeds allows for real-time processing and dynamic obstacle detection, which ultrasonics cannot match. This is because comparitively, it sounds waves take a lot of time to return since they’re much slower in speed compared to light waves (360m/s vs 299,792,458m/s). These differences in data richness, accuracy, and versatility make ultrasonic sensors unsuitable substitutes for the sophisticated capabilities offered by LiDAR technology.

We’ll be using ultrasonic distance finders in futures MPs to stop our rovers from colliding into objects. Since our rovers don’t moove to fast and complexity is relatively low, only a ultrasonic sensor would suffice.

3.3.1 ADC Sampling Rate

The sampling rate (aka Sampling Frequency) is measured in samples per second (SPS or S/s). It dictates how many samples (data points) are taken in one second. If an ADC records more samples, then it can handle higher frequencies.

The sample rate, f_s is defined as,

f_s = rac1T

where,

Hence, in the previous example,

While this looks slow (20 Hz), the digital signal tracks the original analog signal quite faithfully → the original signal itself is quite slow (1 Hz).

Now, if the sampling signal is considerably slower than the analog signal, then it loses fidelity and we see aliasing, where the reconstructed signal (the digital one in the case) differs from the original. Consider the following example of such a case:

As we see from the above figure, the digital output is nothing like the original. Hence, this (digital) output will not be of much use to the system.

Nyquist-Shannon Sampling Theorem:

to accurately reconstruct a signal from its samples, the sampling rate must be at least twice the highest frequency component present in the signal

If the sampling frequency is less than the Nyquist rate, then aliasing starts to creep in.

Hence,

f_Nyquist = 2 * f_max

where,

For instance, if your analog signal has a maximum frequency of 50 Hz then your sampling frequency must be at least, 100 Hz. If this principle is followed, then it is possible to accurately reconstruct the original signal and its values.

Note that sometimes noise can introduce additonal (high) frequencies into the system but we don’t want to sample those (for obvious purposes). Hence, it is a good idea to add anti-aliasing fitlers to the analog signal before it is passed to the ADC.

3.3.2 ADC Resolution

An ADC’s resolution is directly related to the precision of the ADC, determined by its bit length. The following examples shows the fidelity of the reconstruction, based on various bit lengths:

Increasing bit lengths the digital signal more closely represents the analog one.

There exists a correlation between the bit length and the voltage of the signal. Hence, the true resolution of the ADC is calculated using the bit length and the voltage as follows:

StepSize = racV_refN

where,

This is easier to understand with a concrete example:

consider a sine wave with a voltage, 5 V that must be digitized.

If our ADC precision is 12 bits, then we get
N = 2¹² = 4096

Hence, StepSize = 5V/ 4096 which is 0.00122V (or 1.22mV)

Hence, the system can tell when a voltage level changes by 1.22 mV!

(Repeat the exercise for say, bit length, n = 4)

Visual Example:

The above maybe intuitively understood as follows:

Consider the following signal:

Now, if we want to sample this signal, we can obtain measurements at:

The figure shows 9 measurements.

Suppose, the ADC registers have a width of: 2 bits. Hence it can store at most: 4 values.

Since is is not possible to store 9 values → 2 bits, we must select only 4 values omn the digital side.

We then get the following representation:

which, to be honest, is not really a good representation of the original signal!

Now, consider the case where the ADC registers have a bit width: 4 bits → 16 values! Hence, we can easily store all 9 values easily.

So, we can get a digital representation as follows:

We see that this is a better representation, but still not exact. We can increase the bit length but at this point we are limited by the sampling as well. Since we only have 9 samples, adding more bits won’t help.

Hence, to get a better fidelity representation of the original signal, we see that sampling frequency and resolution need to be increased, since they determine the quality of output we get from an ADC.

Resources

• for more details about ADC, read: Analog-to-Digital Convertor Basics
• an in-depth explanation of how ADCs work: Iowa State CpreE 288 Course Slides
• more details with videos: Analog to Digital Conversion, EE319K Univ. of Texas
• Programming an ADC: 1, 2

4.1.1 Tasks, Jobs, Threads

The design of RTOSes (and RTS in general) deal with tasks, jobs and, for implementation-specific details, threads.

A real-time task, τ_i is defined using the following parameters: (ϕ_i, p_i, c_i, d_i) where,

Hence, a real-time tast set (of size ‘n’) is collection of such tasks, i.e., τ = τ₁, τ₂, ...τ_n. Given a real-time task set, the first step is to check if the task set is schedulable, i.e., check whether all jobs of a task will meet their deadlines (a job is an instance of a task). For this purpose, multiple schedulability tests have been developed, each depending on the scheduling algorithm being used.

• remember that task is a set of parameters.
• We “release” multiple “jobs” of each task, each with its own deadline
• if all jobs of all tasks meet their deadlines, then the system remains safe.

A thread, then, is an implementation of task/job – depending on the actual OS, it could be either, or both.

At a high level, here is a comparison between tasks, jobs and threads (note: these details may vary depending on the specific RTOS):

(++ sometimes tasks do contend for resources, so we need to mitigate access to them, via locks, semaphores, etc. and then have to deal with thorny issues such as priority inversions)

A task is often described using a task control block (TCB):

Tasks typically cycle through a set of states, for instance (taken from the FreeRTOS real-time OS):

While the READY, RUNNING and BLOCKED states are similar to those in general-purpose operating systems (GPOS), periodic RTOSes must introduce an additional state: IDLE or SUSPENDED:

• periodic task enters this state when it (rather one ‘job’) completes its execution → has to wait for the beginning of the next period
• to be awakened by the timer (i.e., to launch the next instance/job), the task must notify the end of its cycle by executing a specific system call, end cycle → puts the job in the IDLE state and assigns the processor to another ready job
• at the right time, each periodic task in IDLE state → awakened by kernel and inserted in the ready queue

This operation is carried out by a routine activated by a timer → verifies, at each tick, whether some task(job) has to be awakened.

TCBs are usually managed in kernel queues (the implementation details may vary depending on the particular RTOS).

Context Switch Overheads:

One of the main issues with multitasking and preepmtion is that of context switch overheads, i.e., the time and resources required to switch from one task to another. For instance, consider this example of two tasks running on an ARM Cortex-M4:

void Task1(void) {
    while(1) {
        // Task 1 operations
        LED_Toggle();
        delay_ms(100);
    }
}

and

void Task2(void) {
    while(1) {
        // Task 2 operations
        ReadSensor();
        delay_ms(200);
    }
}

When switching between Task1 and Task2, an RTOS might need to:

• save 16 general-purpose registers
• save the program counter and stack pointer
• update the memory protection unit settings
• load the new task’s context (program into memory, registers, cache, etc.)

So, on the ARM Cortex-M4,

These costs can add up, especially if the system has,

• many RT tasks and frequent preemption
• high-frequency/short period jobs that execute frequently
• if tasks contend with each other for shared resources

Hence and RTOS must not only be cognizant of such overheads but also actively manage/mitigate them. Some strategies could include:

1. better task/schedule design: e.g., group related operations to reduce context switches

void Task_Sensors(void) {
    while(1) {
        // Handle multiple sensors in one task
        ReadTemperature();
        ReadPressure();
        ReadHumidity();
        delay_ms(500);
    }
}

2. priority-based scheduling: e.g., high priority task gets more CPU

void CriticalTask(void) {
    // Set high priority
    setPriority(HIGH_PRIORITY);
    while(1) {
        ProcessCriticalData();
        delay_ms(50);
    }
}

3. optimizing memory layouts: e.g., align task stacks to cache line boundaries

#define STACK_SIZE 1024
static __attribute__((aligned(32))) 
uint8_t task1_stack[STACK_SIZE];

Note: these are not comprehensive and other strategies could be followed, for instance avoiding multitasking altogether! All functions could be implemented in a single process that runs a giant, infinite loop known as a cyclic executive. Newer RTOSes shun ths cyclic executive in favor of the multitasking model since the latter provides more flexibility, control and adaptability but many critical systems (especially older, long-running ones) still use the cyclic executive. For instance, nuclear reactors, chemical plants, etc.

In any case, a precise understanding of these overheads is crucial for:

• setting appropriate task priorities
• determining minimum task periods
• calculating worst-case execution times
• meeting real-time deadlines
• optimizing system performance

There is significant (ongoing) work, both in industry as well as academia, on how to get a handle on context switch overheads while still allowing for flexibility and modularity in the development of RTS.

4.1.2 (Inter-Task) Communication and Synchronization

RTOSes use various mechanisms like semaphores, mutexes, message queues and event flags for communication and synchronization between tasks. Here are some examples:

1. Semaphores:

• binary semaphores: work like a mutex, with values 0 or 1
• counting semaphores: can have multiple values, useful for managing resource pools

// Example of binary semaphore usage
semaphore_t sem;
sem_init(&sem, 1);  // Initialize with 1

void TaskA(void) {
    while(1) {
        sem_wait(&sem);
        // Critical section
        accessSharedResource();
        sem_post(&sem);
    }
}

2. Mutexes (mutual exclusion):

• mutexes provide exclusive access to shared resources
• they include priority inheritance to prevent priority inversion

mutex_t mutex;
mutex_init(&mutex);

void TaskB(void) {
    mutex_lock(&mutex);
    // Protected shared resource access
    updateSharedData();
    mutex_unlock(&mutex);
}

3. Message Queues:

• they allow ordered data transfer between tasks
• provide for buffering capabilities

queue_t msgQueue;
queue_create(&msgQueue, MSG_SIZE, MAX_MSGS);

void SenderTask(void) {
    message_t msg = prepareMessage();
    queue_send(&msgQueue, &msg, TIMEOUT);
}

void ReceiverTask(void) {
    message_t msg;
    queue_receive(&msgQueue, &msg, TIMEOUT);
    processMessage(&msg);
}

4. Event Flags:

• enable multiple tasks to wait for one or more events
• support AND/OR conditions for event combinations

event_flags_t events;
#define EVENT_SENSOR_DATA 0x01
#define EVENT_USER_INPUT  0x02

void TaskC(void) {
    // Wait for both events
    event_wait(&events, EVENT_SENSOR_DATA | EVENT_USER_INPUT, 
               EVENT_ALL, TIMEOUT);
    processEvents();
}

5. Condition Variables:

• tasks can wait for specific conditions
• used with mutexes for complex synchronization

mutex_t mutex;
cond_t condition;

void ConsumerTask(void) {
    mutex_lock(&mutex);
    while(bufferEmpty()) {
        cond_wait(&condition, &mutex);
    }
    processData();
    mutex_unlock(&mutex);
}

Each mechanism has specific use cases:

Common considerations:

1. Priority Inversion Prevention: a high-priority (HP) task is indirectly preempted by a lower-priority (LP) task; HP → needs resource (R); R held by → LP, LP preempted by medium-priority (MP) task. So HP waits for MP → inversion of priorities! We will discuss solutions (priority inheritance/priority ceiling) later.
2. Deadlock Avoidance: tasks are *permanently blocked** waiting on resources from each other; τ₁ holds resource R_A and waits for R_B; τ₂ holds resource R_B and waits for R_A.
3. Timeout Handling: every synchronization mechanism should have a timeout to avoid indefinite blocking of critical tasks.
4. Error Handling: detecting errors and handling them in a robust manner is critical to maintain system reliability; RTOSes use retry mechanisms, logging and, most importantly, have clear recovery procedures for failure scenarios.

These considerations are crucial for ensuring system reliability, maintaining real-time performance, preventing system deadlocks, managing system resources effectively and handling error conditions gracefully.

4.1.3 Memory Management

Real-time systems require predictable memory allocation and deallocation to avoid delays or fragmentation. Hence, they often use limited memory management techniques often eschewing even the use of dynamic memory allocation in favor of static memory allocation. For instance, many RTS don’t even use malloc() or new (i.e., no heap allocated memory) and very often avoid garbage collection. The main goal is for tight control of the memory management → this makes timing behavior more predictable. Hence, the following become easier:

• wcet analysis
• schedulability and other analyses
• runtime monitoring and management
• recovery/restart

Some goals for memory management in RTOSes:

1. predictable execution times for memory operations
2. fast allocation/deallocation
3. minimal fragmentation, if any
4. protection mechanisms between tasks

In fact, to achieve these goals, many RTSes don’t even use caches since they can be a major source of non-determinism in terms of timing behavior, e.g.,

if we cannot exactly calculate when some data/code will hit/miss in cache, then we cannot estimate its true timing behavior, leading to a lot of uncertainty → bad!

Some RTSes use scratchpads since they provide cache-like performance but have higher predictability since the data onboarding/offloading is explicitly managed (either by the program or the RTOS).

Some common memory-management techniques for RTOSes:

1. static memory allocation: all memory used is allocated/deallocated at compile time.
2. memory pools: fixed-size blocks are pre-allocated for specific purposes → fragmentation and provides deterministic allocation times.
3. careful stack management: careful sizing/placing/management of the stack
4. limited heap memory: using “safe” versions of malloc() for instance
5. memory protection: using hardware such as memory protection units (MPUs)
6. memory partitioning: explicitly partition memory/caches so that tasks cannot read/write in each others’ memory regions
7. runtime mechanisms: such as memory usage monitoring, leak detection and managing the fragmentation

Of course, each of these mechanisms have their own problems and a deliberation on those is left as an exercise for the reader.

4.1.4 Timer and Interrupt Management

Timer and interrupt management are crucial components of an RTOS, ensuring that tasks are executed at precise intervals and that the system responds promptly to (internal and) external events. The role between timers and interrupts is closely related, since they offer the very basic timing mechanism in RTOSes (from Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications):

to generate a time reference, a timer circuit is programmed to interrupt the processor at a fixed rate and the internal system time is represented by an integer variable, which is reset at system initialization and is incremented at each timer interrupt. The interval of time with which the timer is programmed to interrupt defines the unit of time in the system; that is, the minimum interval of time handled by the kernel (time resolution). The unit of time in the system is also called a system tick.

Timers, in general, play important roles in such systems, viz.,

Typically these systems have the following three types of timers:

There are various design considerations for timers in an RTOS, viz.,

1. resolution → the smaller the resolution, the higher the system/hardware/software/runtime overheads
2. accuracy → need to understand and manage drift and jitter; timers may need to be calibrated often++
3. power consumption → more accurate/high-precision a timer, higher the power consumption; also the tick can result in significant power consumption if not implemented/managed well

(++ drift indicates a gradual, long-term change in the timer’s frequency over time, whereas jitter refers to short-term, random fluctuations in the timing of individual clock pulses)

Interrupt Latencies → time from when an interrupt occurs to when the corresponding interrupt service routine (ISR) starts executing. As interrupts are integral to the operation of an RTOS, from the implementation of the system tick to notifcations of internal (watchdog timers) and external events (new sensor data), it is important to minimize interrupt latencies.

Optimization Techniques (to minimize latencies):

• minimize interrupt frequency → oftean an RTOS will disable interrupts in critical sections
• efficient timer and interrupt queue management → “nesting” interrupts,
• power-aware timing strategies → “tickless” operating systems have been tried
• optimize ISRs → keep them short, use other methods (deferred procedure calls or “bottom halves”).

4.1.5 Kernel Performance Metrics

Essentially, the kernel must be designed to minimize jitter and ensure that all operations have bounded and predictable execution times.

Hence, we can try to evaluate whether an RTOS kernel meets these goals using the following metrics (note: not exhaustive):

4.2.1 FreeRTOS

As mentioned earlier, FreeRTOS is one of the most popular open-source RTOS options, widely used in embedded systems due to its simplicity, portability and extensive community support. It supports,

• creation of multiple tasks, each with its own priority
• preemptive and cooperative scheduling
• mechanisms like queues, semaphores, and mutexes for communication and synchronization between tasks
• several memory management schemes, including heap_1, heap_2, heap_3, heap_4, and heap_5, to suit different application requirements
• highly portable and supports a wide range of microcontrollers and development boards, including ARM Cortex-M, ESP32 and STM32
• a large and active community, with [extensive documentation, tutorials and examples available online

Here is an example that uses FreeRTOS to blink the LEDs on a microcontroller:

#include <FreeRTOS.h>
#include <task.h>
#include <gpio.h>

// Task to blink an LED
void vBlinkTask(void *pvParameters) {
    while (1) {
        GPIO_TogglePin(LED_PIN);  // Toggle LED
        vTaskDelay(pdMS_TO_TICKS(500));  // Delay for 500ms
    }
}

int main(void) {
    // Initialize hardware
    GPIO_Init(LED_PIN, GPIO_MODE_OUTPUT);

    // Create the blink task
    xTaskCreate(vBlinkTask, "Blink", configMINIMAL_STACK_SIZE, NULL, 1, NULL);

    // Start the scheduler
    vTaskStartScheduler();

    // The program should never reach here
    for (;;);
}

Resources:

1. FreeRTOS Documentation
2. FreeRTOS Tutorials
3. Raspberry Pi and FreeRTOS [GitHub Repo]

4.2.2 Linux+Real-Time

As mentioned earlier, Linux, as a general-purpose operating system, is not inherently a real-time operating system (RTOS). However, it does provide several features and mechanisms that can be used to achieve real-time performance, especially when combined with real-time patches or specialized configurations.

Some of the real-time features of Linux include:

• Preempt-RT Patch: a set of patches that convert the Linux kernel into a fully preemptible kernel, reducing latency and improving real-time performance; the Preempt-RT patch achieves this by:

  • making almost all kernel code preemptible: allows higher-priority tasks to preempt lower-priority tasks, even when the lower-priority tasks are executing kernel code
  • converting interrupt handlers to kernel threads: reduces time spent with interrupts disabled, for better predictability and lower latency
  • implementing priority inheritance: helps prevent priority inversion by temporarily elevating priority of lower-priority tasks holding a resource needed by higher-priority tasks
  • reducing non-preemptible sections: minimizes time during which preemption is disabled, further reducing latency
  • enhancing timer granularity: allows for more precise timing and scheduling of tasks, crucial for real-time applications

  the Preempt-RT patch is widely used in industries such as telecommunications, industrial automation and audio processing. It is actively maintained and supported by the Linux Foundation’s Real-Time Linux (RTL) collaborative project

• Real-Time scheduling policies: support for real-time scheduling policies such as SCHED_FIFO and SCHED_RR, which provide deterministic scheduling behavior

• High-resolution timers: support for high-resolution timers that allow for precise timing and scheduling of tasks

• basic priority inheritance: mechanism to prevent priority inversion by temporarily elevating the priority of lower-priority tasks holding a resource needed by higher-priority tasks

• CPU isolation: ability to isolate CPUs from the general scheduler, dedicating them to specific real-time tasks; also pinning processes to certain cores

• Threaded interrupts: support for handling interrupts in kernel threads, reducing interrupt latency and improving predictability

• Memory management techniques: such as memory locking to prevent pages from being swapped, the use of “huge” pages and memory pre-allocation

• Control groups (cgroups): mechanism to allocate CPU, memory and I/O resources to specific groups of tasks, ensuring resource availability for real-time tasks

These features, when properly configured, can help achieve real-time performance on Linux, making it suitable for certain real-time and embedded applications.

4.2.3 Raspberry Pi OS+Real-Time

The Raspberry Pi OS can also be made “real-time” in the same manner as decribed above, since it is a Linux variant.

Though, there are some attempts at getting the Pi to behave in a real-time fashion, e.g.,: 1, 2, 3.

4.3.1 ROS Components

Some important components of ROS:

1. node

• a process that performs computation (a program/subprogram)
• combined together into a graph
• communicate via “topics”
• operate at a fine-grained scale
• a full system will have multiple nodes, e.g.,
  • one node controls a laser range-finder
  • one Node controls the robot’s wheel motors
  • one node performs localization
  • one node performs path planning
  • one node provides a graphical view of the system

The use of nodes has several benefits such as fault tolerance, reduced complexity and modularity.

2. topics

• they’re named buses over which nodes exchange “messages”
• anonymous publish/subscribe semantics → decouples production of information from its consumption
• nodes are not aware of who they are communicating with
• nodes that are interested in data subscribe to the relevant topic
• nodes that generate data publish to the relevant topic
• can be multiple publishers and subscribers to a topic
• topic is strongly typed by publisher → nodes can only receive messages with a matching type

Topics are meant for unidirectional, streaming communication. ROS includes other mechanisms such as services and [parameter servers]http://wiki.ros.org/Parameter%20Server) for different types of communciations.

3. messages

• nodes communicate with each other by publishing messages to topics
• simple text files
• simple data structure → typed fields
• support standard primitives (int, float, boolean)
• can include arbitrarily nested structs and arrays
• nodes can exchange → request an response messages

A simple ROS message:

std_msgs/Header header
  uint32 seq
  time stamp
  string frame_id
geometry_msgs/Point point
  float64 x
  float64 y
  float64 z

Example: our first ROS message.

4. ROS Master

• provides naming and registration services to the rest of the nodes in the ROS system
• also runs the parameter server → a shared, multi-variate dictionary that is accessible via network APIs, used by nodes to store/retrieve parameters
• tracks publishers and subscribers to topics as well as services
• enable individual ROS nodes to locate one anothe
• once located, they communicate in a peer-to-peer fashion

Example:

1. consider two nodes → camera node and image_viewer node
2. camera notifies master → wants to publish images on the topic, images

3. no one is subscribing to the topic, yet → no images sent
4. image viewer → subscribe to images topic

5. topic, images has both → publisher and subscriber
6. master notifies both → of each others’ existence

7. both start communicating with each other, directly

A more intricate example of the same:

5. ROS transform

• robotic system typically has many 3D coordinate frames that change over time
  • e.g., world frame, base frame, gripper frame, head frame, etc.
• lets the user keep track of multiple coordinate frames over time
• maintains the relationship between coordinate frames → manages spatial relationships
• in a tree structure buffered in time
• lets the user transform points, vectors, etc. → at any desired point in time
• distributed → coordinate frames of robot available to all ROS components on any computer in the system
• sensor fusion, motion planning, and navigation
• organizes all coordinate frames and their relationships into a transform tree

An example of a ROS transform and tree:

4.3.2 ROS and Real-time?

ROS (the first version) is not real-time. Hence, systems that requires hard real-time guarantees shoud not use it. But ROS can be itegrated into systems that require some latency guarantees. If needed, ROS can be run on top of the RT_PREEMPT real-time patch on Linux. In addition, specific nodes can be designed to handle real-time functions or programmed to behave as real-time control systems.

If better real-time guarantees are required on ROS, then ROS 2 if your best bet.

Resources: more information on real-time and ROS2 can be found at RT ROS2 Xilinx and RT ROS Github.

4.3.3 Ros+Navio2

We use ROS (the original version, not ROS2) in our class. Note: while ROS has no real-time capabilities, one some embedded systems, if it fast enough that we can use it to control safety-critical systems such as drones and other small autonomous systems.

In fact, the basic Raspbian image comes installed with ROS. We can use it communicate between the Navio2 and the controller running on the Pi to exchange critical information, e.g., sensor data.

Resources: please read the step-by-step instructions on how to connect/use the Navio2 and the Pi using ROS.

5.1.1 Workload Model

We have already discussed tasks vs. jobs vs. thread earlier so we understand how to model computation. We also discussed how actual execution is modeled (via threads).

Let us focus on jobs and some of their properties:

note → deadlines and periods don’t have to match, but they usually do, _i.e., D = P

As discussed earlier, we need to get a good understanding of the wcet of jobs.

5.1.2 Utilization

One of the important ways to understand the workload requirements for a task is to compute,

how much utilization is taken up by all jobs of the task?

One might ask: if there are (potentially) an infinite number of jobs for each task, since they’re periodic++ and long running, then how can one campute the utilization?

Recall that a periodic function is of the type → f(t) = f(t + T)

where T is the “period”

Note: utilization is not the time taken by a task (or its jobs). It is,

the fraction of the processor’s total available utilization that is soaked up by the jobs of a task

Hence, the utilization for a single task is,

$$ U_i = \frac{c_i}{T_i} $$

where,

Now, we can compute the utilization for the entire task set,

$$ U = \sum_{i=1}^{n} U_i = \sum_{i=1}^{n} \frac{c_i}{T_i} $$

Simple Exercise: what is the total utilization for the following task set?

what does it mean if U > 1?

5.1.2.1 Precedence Constraints

Jobs can be either precedence constrained or independent → we can use directed acyclic graphs (DAGs) to specify/capture these constraints.

For instance, $ J_a J_b$ implies,

• J_a is a predecessor of J_b
• J_b is a successor of J_a

$ J_a J_b$ implies

• J_a is an immediate predecessor of J_b

Consider the following example:

dag	relationships
	J1 ≺ J2 $ J_1 J_2$ J1 ≺ J4 J1 ↛ J4

Here is a more realistic example → the precedence constraints in an autonomous driving system:

5.1.3 Resource Model

A “resource” is some structure used by task → advance execution.

Type of resources:

• active → e.g., processors (they execute jobs)
  • every job → one or more processors
  • same type if functionally identical and used interchangeably
• passive → e.g., files, network sockets, etc.
• private vs shared

We have already discussed resource sharing and synchronization earlier → mutexes, locks, etc. Esentially there is a need for mutual exclusion that is guaranteed via one of these methods or by the use of critical sections.

5.1.4 Scheduling and Algorithms

Before we proceed, we need to understand → preemption:

preemption is the process of suspending a running task in favor of a higher priority task.

Most OS (real-time & non real-time) allow preemption since they allow,

• greater flexibility in constructing schedules
• exception handling
• interrupt servicing

Preemptions, among others, help define a variety of scheduling events; essentially, these are the time when the scheduler is invoked:

• in a fully preemptive system → task arrival, task completion, resource reauest, resource release, interrupts and exceptions, etc.
• in a non-preemptive system → task completion
• in limited preemptive systems → predefined preemptions points, e.g., POSIX thread cancel (pthread_testcancel())

5.2.1 Cyclic Executives

In the automotive enginer example from earlier, we see that for each cycle, the same set of tasks repeat (i.e.., “periodic behavior”). Note though that the tasks need not execute in parallel – rather, they must execute sequentially for this application. Usually such applications use a scheduling mechanism known as a “cyclic executive”.

Consider this simple example with three tasks:

How would we schedule this? Assuming a single processors (hence a single timeline).

Well, the simplest mechanism is to just use a sequential schedule,

If, as in the case of the engine control example we saw earlier, the tasks repeat ad infinitum, then we see the pattern also repeating…

Cyclic executives were common in many critical RTS, since they’re simple and deterministic. An implementation could look like,

while(1)    // an infinite loop
{
    // Some Initialization

    Task_T1() ;

    // Some processing, maybe

    Task_T2() ;

    // Some other processing, maybe

    Task_T3() ;

    // Cleanup
}

Question: what problems, if any, can happen due to cyclic executives?

The very simplicity of such systems can also be their biggest weakness.

1. lack of flexibility: as the example and code above demonstrate, once a pattern of executions is set, it cannot be changed, unless the system is stopped, redesigned/recompiled and restarted! This may not be possible for critical applications. Even for the engine control application in cars, this doesn’t just mean stopping and restarting the car, but re-flashing the firmware for the engine, which is quite an involved task.

2. scalability: along similar lines, it is difficult to scale the system to deal with additional issues or add functionality.

3. priority: there is no way to assign priority or preemption since all tasks essentially execute a the same priority. Hence, if we want to deal with higher-priority events (e.g., read a sensor) or even atypical (aperiodic/sporadic) events, such as sudden braking in an autonomous car, then a cyclic executive is not the right way to go about it.

4. resource management: certain tasks can corral resources and hold on to them while others may starve – leading to the system becoming unstable. For instance, even in the simple example, we see that T₃ can dominate the execution time on the CPU:

Since the system is one giant executable, it is difficult to stop a “runaway task” – the entire system must be stopped and restarted, which can lead to serious problems.

5.2.2 Frames

One way to mitigate some of the problems with cyclic executives, is to split the resource allocation into “frames” → fixed chunks of time when a task can claim exclusive access to a resource, e.g.. the processor:

• once a frame starts, the task gets to execute uninterrupted
• at the end of the frame, the task must give up the resource → regardless of whether it was done or not

So, if we revisit our simple example and break the processor schedule into frame sizes of 2 units, each,

why 2? Well, it is arbitrary for now. But, as we shall see later, we can calculate a “good” frame size

Now, our schedule looks like,

As we see from this picture, task T₁ doesn’t end up using its entire frame and hence, can waste resources (one of the pifalls of this method).

Continuing further,

Task T₃ is forced to relinquish the processo at t=6 even though it has some execution left → on account of the frame ending. Now T₁ resumes in its own frame. T₃ has to wait until t=10 to resume (and complete) its execution:

Other Static/Table-Driven Scheduling:

Cyclic executives are an example of schedulers where the tasks are fixed, ahead of time, and all that a scheduler has to do is to dispatch them one at a time in the exact same order. Often the tasks are stored in a lookup table (hence the name “table-driven”). Other examples of such systems (with some prioritization and other features built in) have been built, e.g., weighted round robin → also finds use in cloud computing and networking load balancing, etc.

5.2.3 Priority-Based Schedulers

One method that overcomes the disadvantages of a completely static method is to assign priorities for jobs as they arrive. Hence, when a job is released it gets assigned a priority and the scheduler then dispatches/schedules the job accordingly. Hence, it if is the highest priority job so far, it gets scheduled right away, by preempting any currenlty running tasks. If, on the other hand, it is not the highest priority task then it is inserted into the ready queue at the right position (priority level).

To deal with this, we need an online scheduler, i.e., one that is always available to make scheduling decisions – when tasks arrive, complete, miss their deadlines, etc.

Before we go any further, let’s update the task model a little, to make matters simple for us.

• as before, we have a task set comprised of n periodic tasks, τ = τ₁, τ₂...τ_n
• deadline is equal to period, i.e., T = D; task periods are T₁, T₂, ...T_n
• all tasks are independant → no precedence or resource constraints exist
• tasks cannot suspend themselves (or others)
• tasks are preemptible by the OS → each time the highest priority task is executed (under preemptive scheduling)
• execution time of each task is bounded → wcet (c₁, c₂, ...c_n)
• tasks are released (i.e., placed into the ready queue) as soon as they arrive
• all kernel overheads (e.g., context switches) → assumed to be zero

While these may seem to be overly simplifying, they still fit the model of many systems and help us develop fundamental results. And we can always add them back one-by-one and still retain the correctness of the theoretical results we develop, while making the system more realistic.

Now, in the real of online, priority-driven schedulers, we have two options:

Let’s look at one of each (the most popular ones), viz. the Rate-Monotonic (RM) and Earliest-Deadline First schedulers. Note that both were first described and analyzed in a seminal Computer Science Paper, that has since become one of the most cited and influential papers in the field: Scheduling Algorithms for Multiprogramming in a Hard- Real-Time Environment by Liu and Layland.

Interestingly, both of these algorithms are provably optimal, i.e., no other static or dynamic algorithm can do better than RM and EDF respectively! Not bad for the first paper in the area – talk about setting a high bar, or rather bound!

6.1.1 Open-Loop vs Closed-Loop Control

For the control law we just developed, if our model is accurate and there are no disturbances then,

y = y^*

However, note that there is nothing ensuring that the value of y = y^*. We just assume (rather, expect) that it would be the case. This is known as an open loop controller. You desire a certain output and hope that the controller actually gets there.

So, the open loop controller is depicted as:

What we really want, is to somehow ensure that the controllers gets to its setpoint. How do we do that?

The problem is that while the input drives the output, there is no way to guarantee that the controller will get to the set point.

What we really need, is a closed-loop controller → one that uses feedback to,

• adjust u
• ensure that we get to y^* (or, at least as close to it as possible).

The feedback typically comes from the output of the controller model that we created. So,

Note that the feedback can be positive or negative.

[The above description is distillation of the excellent description found here.]

6.4.1 Proportional (P) Control

The correction is proportional to the size of the error, i.e.,

So, going back to our example of lateral control, let us try to apply the proportional control methodology to it:

We have the following choices:

• K_p > 0
• K_p < 0

We pick the K_p > 0 since we want the following relationship to hold (following from e(t) = −y(t)):

K_pe(t) = −K_py(t)

We see that this proportional controller helps us move the car towards our goal, y = 0.

Now, let’s consider a few situations:

1. what happens if K_p → too small (small “gain”)?

The response is too slow/gradual. We may never get to the goal in this case.

2. what happens if K_p → too large (large “gain”)?

The response is too sudden. The system may overshoot the goal!

So, the next question that comes up → can the car be stabilized at y = 0? This is unlikely using just the proportional control method since,

The question then becomes → how can we reduce oscillation, i.e., can we get to the following situation (smoother, actual approach to the goal)?

6.4.2 Derivative (D) Control

Derivative control improves the dynamic response of the system by,

• studying the rate of change of the error and
• decreasing oscillation

So, what does this mean, in practice? What we’re measuring and trying to control, is the rate of change, i.e., the change from,

y(t − 1) → y(t)

Typically, proportional and derivative control are often used together, as a way to counteract each others’ influences. So, we get:

As with the proportional controller, we have two options for the derivative as well. Should,

• $\frac{dy(t)}{dt} < 0$
• $\frac{dy(t)}{dt} > 0$

Note that the derivative controller’s job is to steer away from the reference line, to act as a counter to the proportional controller pushing in the opposite direction. Hence, we pick $\frac{dy(t)}{dt} < 0$.

The derivative controller acts like a brake and counteracts the correctional force. It reduces overshoot by slowing the correctional factor → as the reference goal approaches.

We see numerous uses of the combination, known as the P-D controllers in every day life, from the smallest to the largest, even rocket ships!

6.4.3 Integral (I) Control

Are we done? Not quite. Let’s take a closer look at the results:

As we see from this image, even though we reached the reference, the behavior is not smooth! There could be many reasons for this, such as steering drift, caused by the mechanical design of the system:

There are a variety of unmodeled disturbances and systemic errors (“bias”):

• actuators and processes → not ideal
• friction, steering, drift, changing workloads, misalignments, etc.

Hence, the signal may never reach the set points! It will end up “settling” near the reference, which is not always ideal.

To deal with this, we need integral (I) control.

First, let’s define steady state error (SSE):

difference between the reference and the steady-state process variable

Hence, when time goes to infinity,

SSE = lim_{x → ∞}[r(t) − y(t)]

The correction must be proportional to both → error and duration of the error. Essentially it sums the error over time.

Note: unless the error is zero, this term will grow! In fact, the error keeps adding up, so the correction must also increase → this drives the steady state error to zero.

In many instances, integral control is used in conjunction with the P and D controllers,

This is known as: PID Control,

Let’s look at some examples of tuning the various paramters of a PID controller, as applied to our problem:

Let’s increase K_p now and see the effect:

We see that the system has stabilized well around the reference point and, if we zoom in, we will see fewer disturbances.

Now, let’s keep increasing K_p,

Wait, the signal oscillates? The main reason is that the I term is not zero when crossing the reference, y(t) = 0 and it takes a little while to wash out the cumulative error.

In summary:

• P is required
• depending on the system, one or both of I/D is combined with P
  • PI, PD or PID

Tuning P, I, D gains. There is no “optimal” way to tune the PID gains

1. start with → K_p = 0, K_d = 0, K_i = 0
2. slowly increase K_p until → system oscillates around set point
3. slowly increase K_d until → system settles around set point
4. if steady-state error exists → slowly increase K_i until corrected without causing additional oscillations

6.4.4 Some additional feedback control applications:

1. Segway balance control

2. Drone control

3. Motor speed control

References:

1. Control theory introductions: 1, 2, 3
2. Map of Control Theory
3. What is PID Control by Mathworks
4. Control Theory Lectures by Brian Douglas.
5. Introduction to Control Theory and Application to Computing Systems by Abdelzaher et al.
6. Automotive Control Systems
7. PID Controller Design
8. Introduction to PID controllers
9. Construction and theoretical study of a ball balancing platform by Frank and TJERNSTRÖM.
10. Understanding PID Control: 2-DOF Ball Balancer Experiments
11. Control Engineering for Industry from Stanford University.
12. A Line Following Robot Using PID Controller
13. Ball and Beam: System Modeling
14. Open Loop Control System

7.1.1 Duty Cycle

Recall that logic high → on (or off depending on the system, but pick one for consistency). To represent an on time, we use the concept of the duty cycle, defined as:

duty cycle describes the proportion of ‘on’ time to the regular interval or ‘period’ of time.

Duty cycles are represented as percentages (of time that the signal is on, relative to its period).

The duty cycle can be calculated as:

$$D = \frac{T_{on}}{T} * 100$$

where,

Consider the periodic pulse wave, f(t), with a low value, y_min, high value, y_max, and constant duty cycle, D, as shown below:

The average value of a wave is,

$$\bar{y} = \frac{1}{T}\int^T_0f(t)\,dt$$

Since f(t) is a pulse wave, its value is,

Now, we can expand the above expression as,

$$ \begin{align*} \bar{y} &= \frac{1}{T} \left(\int_0^{DT} y_\text{max}\,dt + \int_{DT}^T y_\text{min}\,dt\right)\\ &= \frac{1}{T} \left(D \cdot T \cdot y_\text{max} + T\left(1 - D\right) y_\text{min}\right)\\ &= D\cdot y_\text{max} + \left(1 - D\right) y_\text{min} \end{align*} $$

So we can now compute how long the signal should be at y_max and how much at y_min.

7.1.2 PWM Period

The period (or frequency, recall that $f=\frac{1}{T}$) is another important parameter that defines a PWM signal. It essentially determines the number of times a signal repeats per second. The choice of T depends heavily on the application. For instance, when controlling an LED,

the frequency of a PWM signal should be sufficiently high if we wish to see a proper dimming effect while controlling LEDs. A duty cycle of 20% at 1 Hz will be noticeable to the human eye that the LED is turning ON and OFF. However, if we increase the frequency to 100Hz, we’ll get to see the proper dimming of the LED.

7.1.3 PWM Sampling Theorem

Is directly related to the Nyquist-Shannon Sampling Theorem discussed earlier. A simple summary,

number of pulses in the waveform is equal to the number of Nyquist samples.

Recall that the Nyquist rate is, a value equal to twice the highest frequency.

7.1.4 Example | Servo Motor Control

Servos (also RC servos) are small, cheap, mass-produced servomotors or other actuators used for radio control and small-scale robotics.

They’re controlled by sending the servo a PWM (pulse-width modulation) signal, a series of repeating pulses of variable width where either the width of the pulse (most common modern hobby servos) or the duty cycle of a pulse train (less common today) determines the position to be achieved by the servo.

7.1.5 PWM Generation in Microcontrollers

We can use the built-in PWM components in many microcontrollers or timer ICs. Using Arduino, generating a PWM is as simple as writing out a few lines of code!

analogWrite(pin, value)

Note that not all pins of an Arduino can generate a PWM signal. In the case of Arduino Uno, there are only 6 I/O pins (3,5,6,9,10,11) that support PWM generation and they are marked with a tilde (~) in front of their pin number on the board.

Examples of various duty cycles:

analogWrite(PWM_PIN, 64);   // 25% Duty Cycle or 25% of max speed
analogWrite(PWM_PIN, 127);  // 50% Duty Cycle or 50% of max speed
analogWrite(PWM_PIN, 191);  // 75% Duty Cycle or 75% of max speed
analogWrite(PWM_PIN, 255);  // 100% Duty Cycle or full speed

The Raspberry Pi also has a variety of GPIO pins that can be used for generating PWM signals:

Consider this code for controlling the brightness of an LED:

import RPi.GPIO as IO       #calling header file which helps us use GPIO’s of PI
import time                 #calling time to provide delays in program
IO.setwarnings(False)       #do not show any warnings
IO.setmode (IO.BCM)         #we are programming the GPIO by BCM pin numbers. (PIN35 as ‘GPIO19’)
IO.setup(19,IO.OUT)         # initialize GPIO19 as an output.
p = IO.PWM(19,100)          #GPIO19 as PWM output, with 100Hz frequency
p.start(0)                  #generate PWM signal with 0% duty cycle
while 1:                    #execute loop forever
    for x in range (50):    #execute loop for 50 times, x being incremented from 0 to 49.
        p.ChangeDutyCycle(x) #change duty cycle for varying the brightness of LED.
        time.sleep(0.1)      #sleep for 100m second
    for x in range (50):     #execute loop for 50 times, x being incremented from 0 to 49.
        p.ChangeDutyCycle(50-x)  #change duty cycle for changing the brightness of LED.
        time.sleep(0.1)          #sleep for 100m second