Deterministic, asynchronous message
driven task execution with ROS
Brian Cairl

ROSCon2018
ROSCon2018

● Motivations○ Preamble on determinism○ Drawbacks of a timing-dependence in testability○ Event-driven software in testing● Asynchronous event-driven software framework○ Where synchronization meets ROS abstraction○ High-level implementation details

Overview

ROSCon2018
ROSCon2018

Motivations

ROSCon2018
ROSCon2018

● With given inputs, can we make any guarantees about
software outputs and behavior?
● If we “playback” record sensor data/partial state data, canwe get the same outputs as when our software was runninglive?
● Why do we care?
○ Incident reproproducability○ Robustness to timing variations
Preamble: Determinism

ROSCon2018
ROSCon2018

To qualify:● This talk will address algorithmic determinism as a “besteffort” attempt at having some level of reproducibility
between live scenarios and testing○ Also, reproducibility between offline test cases● This will not deal with real-time system determinism
Preamble: Determinism

ROSCon2018
ROSCon2018

● Typically working with an operating system (e.g. Linux)
which is scheduling events and dealing withthreads/processing● During runtime:○ Thread wake up delays○ Context switching delays○ Some inherent TCP message transmission andserialization delay○ Logging, file IO, etc.
Preamble: A few practical considerations

ROSCon2018
ROSCon2018

● We are usually dealing with:○ Software which is relatively low-frequency (<200 Hz) andcan tolerate some delay (0.1ms - 500ms)○ a system that is somewhat tolerant to command jitter

Preamble: A few practical considerations

ROSCon2018
ROSCon2018

● The host system needs to run fast enough to keep up withincoming data
● Use diagnostic information to figure out whether or not thisis (nominally) the case
○ Message output rates○ Difference between wall time and message stamps

Preamble: A few practical considerations

ROSCon2018
ROSCon2018

SensorFusion

IMUs
OpticalSensors

Navigation
andLocalization
Stack(50 Hz)(15 Hz)OpticalFilters

Perception
Stack(20 Hz)(20 Hz)ROSCon2018
ROSCon2018

Control Inputs

Encoders

High Level Software Stack (Communicates with ROS)

Periodic ormessage-driven
Update Loop

A ROS Node

Node graph

InMessage 1 CallbackInMessage 2 Callback

In

Message 3 Callback

The polling ROS node

Program State●●Cached messages/tf

Update Callback

OutROSCon2018
ROSCon2018

A ROS NodeIn

Message 1 Callbackclass NodeObj{Public:...
// includes some constructors, init stuff
private:ros::Subscriber msg_a_sub;
MsgA::ConstPtr msg_a;};...

InMessage 2 Callback{}

Node graphIn

Message 3 Callback// in a method to init things
sub = nh.subscribe(“msg_a”, 10, &NodeObj::callback, this);...
void NodeObj::callback(const MsgA::ConstPtr msg){
this->msg_a = msg;}

The polling ROS nodeROSCon2018
ROSCon2018

class NodeObj{...
private:ros::Timer updater;...
// includes cached messages};

Periodic or
message-driven
Update Loop

A ROS Node

...
{}

In

Message 1 Callback// in a method to init things
updater = nh.createTimer(ros::Duration(.1),this);
Message 2 Callback
In &NodeObj::update,Program State

Update Callback...

ROSNodeObj::update(constCorevoidros::TimerEvent&evt)
Message 3 Callback
In{if (this->msg_a && this->msg_b && ... ){// do a thing}}

The polling ROS node

OutROSCon2018
ROSCon2018

Periodic or
message-driven
Update Loop

A ROS Node

Node graphIn

Message “A” Callback

In

Message “B” Callback

In

Message “C” Callback

Program State

Update Callback

Out

The polling ROS node

ROSCon2018
ROSCon2018

Periodic or
message-driven
Update Loop

A ROS Node

Node graphIn

Message “A” Callback

In

Message “B” Callback

In

Message “C” Callback

Program State

Update Callback

OutThe polling ROS node

ROSCon2018
ROSCon2018

Periodic or
message-driven
Update Loop

A ROS Node

Node graphIn

Message “A” Callback

InMessage “B” Callback

In

Message “C” Callback

Program State

Update Callback

OutThe polling ROS node

ROSCon2018
ROSCon2018

No strict execution dependence
A ROS Node

Node graphIn

Message “A” Callback

In

Message “B” Callback

In

Message “C” Callback

Periodic Update
Loop

Program State

Update Callback

Out

The polling ROS node

ROSCon2018
ROSCon2018

System state and output are dependent on when messages arrived
A ROS Node

Node graphIn

Message “A” Callback

In

Message “B” Callback

InMessage “C” Callback

Periodic Update
Loop

Program State

Update Callback

OutThe polling ROS node

ROSCon2018
ROSCon2018

● Can have “zero” delay, since we can output with whatever we have(besides waiting on /tf)
BUT

● Update (output) rate is decoupled from input data
○ Essentially sampling our inputs○ Output is dependent on when we sampled● Cannot be run at or faster than real-time and guarantee the same
results

The polling ROS node

ROSCon2018
ROSCon2018

A ROS Node

Node graph

InMessage “A” Callback

InMessage “B” CallbackBuffering andsynchronization

In

Message “C” Callback

Sync. Policy

Update on asynchronization
condition
Update Callback

Out

The event-driven ROS node

ROSCon2018
ROSCon2018

A ROS NodeIn

Message “A” Callback

Message “B” Callbackbool sync(const MsgA::ConstPtr& msg_a,const MsgB::ConstPtr& msg_b,...){ROS Core that checks
Message “C” Callback// somethingIn//‘msg_a->header.stamp’// against//‘msg_b->header.stamp’, etc.
}
InThe event-driven ROS nodeUpdate on asynchronization
condition
Buffering andsynchronization

Update Callback

Sync. Policy
OutROSCon2018
ROSCon2018

Every 0.1 seconds

A ROS NodeIn

Message “A” Callback

Update on asynchronization
condition

Every Q seconds
InMessage “B” Callback

Buffering andsynchronization

Update Callback

Every 3.1416 seconds

Node Graph

In

Message “C” Callback

Sync. Policy
OutThe event-driven ROS node

ROSCon2018
ROSCon2018

Single synchronized data
frame

A ROS NodeROS CoreIn

Message “A” Callback

In

Message “B” Callback

Buffering andsynchronization

In

Message “C” Callback

Sync. Policy

Update Callback

OutThe event-driven ROS node

ROSCon2018
ROSCon2018

A ROS NodeROS Core

InMessage “A” Callback

InMessage “B” Callback

Buffering andsynchronization

InMessage “C” Callback

Sync. Policy

Update CallbackOuthttp://wiki.ros.org/message_filters

The event-driven ROS node

ROSCon2018
ROSCon2018

● Can be robust against message interleaving at runtime, atthe expense of delay● Delay is passed on from one node to dependent nodes, butdelay can be calculated beforehand● Running with the same input data will always produce thesame outputs
The event-driven ROS nodeROSCon2018
ROSCon2018

● Removes ambiguity about software brittleness under
different timing/system load conditions○ Repeatable functional tests● Can run faster than real-time○ Important for simulation where randomized system
configurations/inputs can be tested quickly● We can test with real data and be reasonably confident that
we can reproduce errors with said data
Importance in functional testing

ROSCon2018
ROSCon2018

● Recorded data could represent conditions
that uncovered an edge case that caused anincident, e.g.:● To guarantee that an edge case can becircumvented, software determinism is key
to guarantee repeatability

Importance in functional testing

ControlInputs
Intermediate
Messages○ Robot didn’t track an important object of interest

Control Inputs

System Outputs

Navigation Stack
Outputs
SensorOutputs○ Robot stuck behind an obstacle

ROS Bag File

Perception Stack
Outputs

ROSCon2018
ROSCon2018

With an event-driven system:● We don’t need a ROS core and wedon’t need write ros_test cases● Make test cases from bag files (seerosbag API)● This requires a some extra
architectural considerationsImportance in functional testing

ROSCon2018
ROSCon2018

FlowAn asynchronous, event-driven
framework
ROSCon2018
ROSCon2018

● Maintain overarching ROS node-based structure● Decouple execution portion and communication portion of thecode● Make execution event-driven (deterministic)● Support intra/extra node communication○ Support message injection/production without a ROS core
● Allow multiple execution units (blocks) to run in the same
program, similar to nodelets

Flow Framework: Stated requirements

ROSCon2018
ROSCon2018

Input Transport
Layer

Output Transport
Layer

Abstraction/synchronization block

Message buffer
Driving sync policy

Message buffer

ROS subscriber
message injection

Following syncpolicy

ROS publisher

Synchronizer

ROS subscriber
message injection

Execution
Callback

Diagnostics Update
Hook

Flow Framework: Desired unit structure

ROS publisher

ROSCon2018
ROSCon2018

Input Transport
Layer

ROS subscriber
message injection

ROS subscriber
message injection● Only responsible for pumping messages in andmoving messages out from our abstractions
layer● Not really dependent on ROS

Output Transport
Layer

ROS publisher○ In the case of ROS subscribers, we caninject/received messages with ROS
callback queue from single thread○ Replace with ROS2 subs/pubs

ROS publisher○ Directly inject messages from a bag

Flow Framework: Desired unit structure

ROSCon2018
ROSCon2018

● Nodes can contain 1 or more blocks● Blocks run in parallel, each in a separate thread● Blocks are connected through input and output channels○ Can interface with ROS or another transport layer○ Can interface with other blocks○ Blocks pass messages (or any data type, if intraprocess)○ Input channels govern synchronization behavior

Flow Framework: Block-based design

ROSCon2018ROSCon2018

Block 2 (Child Thread)

Execution CB

Execution CB

Block 3 (Child Thread)
Execution CB

Main thread (ros::spin)

Flow Framework: Block-based design

ROSCon2018
ROSCon2018

ROS publications

ROS subscriptions

Block 1 (Child Thread)Blocks obfuscate parallel design● Thread execution is driven by incoming data
● Thread will sleep when not executing● Thread safety is enforced by the wrapping structure● System design comes down to what the block will execute, andhow its connected to other things● The connection methods are interchangeable

Flow Framework: Block-based design

ROSCon2018
ROSCon2018

● Diagnostic hooks can be
attached to each block, as partof the block design● Enables per-task execution
monitoring
diagnostic_msgs

Flow Framework: Per block diagnostics

ROSCon2018
ROSCon2018

● First input “drives” synchronization
Message buffer● Additional inputs are synchronized basedon a time range from driving input

Message buffer
Following sync
policySynchronizer

Driving sync policy● Each sync. policy knows how to deal withdiscarding irrelevant data or skipping
framesMessage buffer
Following syncpolicy● Synchronizer outputs a data frame withmessages for each input channel

Flow Framework: Synchronization behaviors

ROSCon2018
ROSCon2018

Message buffer

Message buffer
Following sync
policyMessage buffer
Following sync
policySynchronizer

Driving sync policy● Synchronization policies are part of thechannel, which determine overall
synchronization behavior● There are a few extra directives that eachpolicy can emit to skip or abort on asynchronization attempt

Flow Framework: Synchronization behaviors

ROSCon2018
ROSCon2018

Message buffer

Older

Sync Policy

0Newer12345678

Synchronizer

9Channel::inject(TimeType t, PayloadType data)
MyMessage
headerframe_id
stampSeq
other_fields...

Flow Framework: Synchronization behaviors

ROSCon2018
ROSCon2018

Not Ready
Message buffer

On new messages

Message buffer
Following sync
policySynchronizer

Driving sync policy

Check bufferedmessages w.r.t policy
Readyt_begin, t_end

Message buffer
Following sync
policyFlow Framework: Synchronization behaviors

ROSCon2018
ROSCon2018

Not Ready
Message buffer

Following sync
policySynchronizer

Message buffer

Check bufferedmessages w.r.t policy

On new messages

Driving sync policy

Not ReadyOn new messages

Message buffer
Following sync
policyFlow Framework: Synchronization behaviors

t_begin,t_end

DriverReadyCheck bufferedmessages w.r.t policy
and driving time range
t_begin,t_end

ROSCon2018
ROSCon2018

Follower
ReadyMessage buffer

Message buffer
Following sync
policySynchronizer

Driving sync policy

Frame
Driver Messages

Follower[0] Messages

Follower[N-1] Messages

Execution Callback

Message buffer
Following sync
policyOutput for
t_end

Flow Framework: Synchronization behaviors

ROSCon2018
ROSCon2018

Next-N (sliding window)● Return latest message, and N-1 messages before, ordered in time
● Synchronize on time range between (N-1)th message stamp and latest message stamp● Discard oldest message
NewerOlder

iteration 00123456789104567891011Captured
iteration 1
10iteration 2, 3, ...

23
CapturedAnd so on...

Flow Framework: Driving input policies

ROSCon2018
ROSCon2018

Next-N (without replacement)● Return latest message, and N-1 messages before, ordered in time
● Synchronize on time range between (N-1)th message stamp and latest message stamp● Discard all captured messages
NewerOlder

iteration 001234567891089101112131415

Capturediteration 1
50...4

iteration 2, 3, ...

67
CapturedAnd so on...

Flow Framework: Driving input policies

ROSCon2018
ROSCon2018

N-Before, M-after● Return N messages before the earliest driving stamp, and M messages after the lateststamps● Invalidate frame if N before cannot be grabbed from the buffer● Wait for data if M after cannot be cannot be captured

t_begin
01

t_end
2345678Flow Framework: Following input policies

910ROSCon2018
ROSCon2018

Closest Before● Assumes an input rate, r, and a period of delay, d● Return closests message before earliest driving time stamp that fallse within (0.5/r) s of thisstamp minus delay period● Wait if there are only messages earlier than (0.5/r) s● Discard frame if there are only messages after the earliest driving stampt_begin - d
01

t_end
2

3

45

6789100.5 / r

Flow Framework: Following input policies

ROSCon2018
ROSCon2018Latched● Return latest message that occured before the earliest driving stamp● If such a messages does not exist, invalidate all frames until earliest driving stamp is older
than latched stampActivation● Same as latched, but returns message only when input data satisfies a particular condition● Used to dump frames and effectively deactivate a block

Flow Framework: Following input policies

ROSCon2018
ROSCon2018

● Using the described input policies, we can “fake” output-driven
events by attaching driving inputs to periodic clock messagepublishers

Message buffer
Next-1

Synchronizer

Periodic Clock
Message

Execution
Callback

Flow Framework: Output-driven execution

Outputs atclock rate

ROSCon2018
ROSCon2018

Execution portion of our code remains unchanged between test and live softwarerosbag topic
injectorpass/failMessage buffer
Driving sync policy

Message buffer

Synchronizer

rosbag topicinjector

Execution
Callback

rosbag topic writer

Following sync
policyTest Evaluatorrosbag topic writer

Flow Framework: Tying back to functional tests ROSCon2018
ROSCon2018

●Deterministic software is critical in testing and reproducing issues● If software is deterministic, you can have higher confidence in edge-case
avoidance when testing against data from incidents○ A good way to perform this testing is with rosbag file data
● Flow is a framework built on event-driven execution that with ROS
agnostic message passing in mind
○ In the process to become an open source framework

Summary

ROSCon2018
ROSCon2018