Skip to content

Latest commit

 

History

History
466 lines (312 loc) · 23.9 KB

rep-2009.rst

File metadata and controls

466 lines (312 loc) · 23.9 KB

REP: 2009 Title: Type Negotiation Feature Author: Audrow Nash <[email protected]>, Chris Lalancette <[email protected]>, Gonzalo de Pedro <[email protected]>, William Woodall <[email protected]> Status: Final Type: Standards Track Content-Type: text/x-rst Created: 04-Nov-2021 Post-History:

Abstract

This REP proposes a new set of classes ROS 2 that will make it possible to negotiate the message types used by publishers and subscriptions.

Motivation

The primary reason for this change is to allow nodes to publish different types of messages that better allow the system to optimize its behavior. For example, a node may be more efficient with one image format (say, YUV420) than another (say, ARGB888). What's more, the optimal message type to publish may change over time, if say, a different part of the ROS 2 network becomes active to accomplish a different task. Perhaps the node with the original subscription is no longer needed so the node goes into an idle mode, and another node with a different subscription would prefer images in ARGB888, over YUV420, for resource reasons. Currently, this behavior could be accomplished with ROS 2 nodes or lifecycle nodes, however doing so would require a significant amount of work for the programmer and are potential sources of errors.

A second reason for this change is that it can improve developer experience by giving the developer more flexibility in how they interface with different nodes. The result of which is that they may need to spend less time writing code to convert a message type into the one message type accepted by the node they're using; instead the node may support additional types, so they may not need to perform any conversion. This may reduce the number of errors in the user's code, and it may allow them to prototype more efficiently, as they may not have to write as much code to perform conversions.

The final reason for this change is that it will enable vendors of hardware accelerators to provide the most efficient operations. That is, it may be the case that a node can do hardware-accelerated operations on a YUV420 image, but (slower) CPU conversions on a ARGB8888 image. In that case, the hardware vendor's node would mark a preference on YUV420 since that uses the hardware more efficiently.

Terminology

ROS Message Type:A ROS message type always refers to ROS messages, such as std_msgs/msg/String. This is the canonical string representation of a ROS message type, and represents the data sent over the ROS network.
Type Adapted Type:These are custom types that are defined through type adaptation (see REP 2007 [1]). The user directly interacts with these types, but they are never sent over the network. Instead these types are converted to and from ROS message types as necessary to send between publishers and subscriptions.
Regular Publisher:A publisher that publishes a single ROS message type on a single topic. The publisher can be created either with a ROS Mesasage Type or a Type Adapted Type.
Regular Subscription:A subscription that subscribes to a single ROS message type on a single topic. The subscription can be created either with a ROS Message Type or a Type Adapted Type.
Supported Message Type:A message type that can be selected for use during negotiation. As will be seen later, this is a combination of a ROS Message Type or a Type Adapted Type, along with an arbitrary name.
Supported Message Priority Map:A data structure that maps supported message types to their respective priority. The exact function used to determine how to use these priorities can be overwritten by the user. In general, higher numbers indicate higher priority, zero indicates no preference, and negative numbers indicate a vote against using a supported message type.
Selected Message Type:A supported message type that has been selected for use during negotiation.
Negotiating Publisher:A publisher with preferences as to which supported message type it prefers to publish. It can publish one or more selected message types on the same number of topics.
Negotiating Subscription:A subscription with preferences as to which supported message type it prefers to subscribe to. It subscribes to a single selected message type on a single topic.
Negotiating Publisher and Subscription Pair:A single node with a negotiating publisher/negotiating subscription pair that are related to each other. The preferences of the subscription may be based on the selected message type of the publisher. An example would be if the subscription receives data, modifies it, and then publishes it. In this case, it is desirable to have the publisher and subscription use the same selected message type. However, the selected message type may not be known before the publisher negotiates it.
Negotiation topic:A topic that negotiating publishers and subscriptions will use to negotiate the selected types that will be used.

Specification

High-level Goals

The proposed change has a few goals:

  • Provide a way for nodes to publish different types of messages.
  • Support publishing in multiple formats at the same time.
  • Only necessary publishers and subscriptions are active at any given time.
  • A publisher or subscription can delay stating its preferences to wait for additional information.
  • Core functions are exposed to the user to overwrite.

Defining Supported Message Types

For each supported message type, the following information must be known:

  • The ROS message type that will be sent (a ROS message type, such as sensor_msgs/msg/Image, or a custom Type Adapted type that can be converted into a ROS message type).
  • A string identifier for the supported message type. For example, "YUV420" could be the identifier for a supported message type that publishes images in YUV420 format. This will remove ambiguity in the case that the same ROS 2 message type is used for multiple supported message types.
  • The relative priority of the supported message type.

The combination of the ROS message type and the string identifier must form a unique tuple, since multiple supported message types may be sent with the same ROS message type. For example, a publisher may publish image data in the format of YUV420 or ARGB8888, both of which could be sent in a sensor_msgs/msg/Image.

Defining Negotiating Publishers and Subscriptions

Negotiating publishers and subscriptions both require a list of supported message types and a negotiation topic that will be used to negotiate the selected message types.

A user may do arbitrary work that determines the supported message priority map before revealing their preferences to the system. This may introspect the system looking for particular hardware and compute resources. Once the introspection is complete, the user can then inform the negotiating publisher or negotiating subscription about these preferences, and then reveal these preferences to the rest of the system.

A special case of using a function to return a supported message priority map is when there is a negotiating publisher and subscription pair, which is useful for a node that receives data on a subscription, manipulates the data, and re-publishes it on a topic. In this case, the user should delay revealing preferences on the negotiating subscription until the type of the negotiating publisher is known.

One thing to note is that there are potentially many combinations of supported message types in negotiating publisher and subscription pairs. For example, if there are four supported types for a negotiating publisher and subscription and the developer wants to support all combinations, then the developer must implement six conversions between the supported message types (three choose two). However, the developer can choose to only implement a subset of these conversions, and only reveal the supported types for the ones that are supported.

Negotiation Algorithm

Negotiating Publisher

The negotiating publisher will select zero or more supported message types (zero when publisher and subscriptions have incompatible supported message types). To do this, the negotiating publisher performs the following steps:

  1. Use discovery to find all the connected subscriptions that are using the user specified negotiation topic.
  2. Receive the supported message priority maps from all connected subscriptions.
  3. Decide the selected message types by considering the supported message priority maps of the publisher itself and of all subscriptions.
    • This can result in zero or more matches, as mentioned above. In the case that there are zero matches, an error should be returned.
    • While there is a built-in negotiation algorithm that works for most cases, the user can also provide a custom negotiation algorithm.
  4. The negotiating publisher then creates a regular publisher for each supported message type.
  5. Notify all of the connected negotiating subscriptions of the selected message types.

Negotiating Subscription

The negotiating subscription will send its supported message priority map to the negotiating publisher and then wait on the negotiating publisher to tell it the selected message types. Upon receiving the selected message types from the negotiating publisher, the subscription will choose the match with the highest priority in its own supported message priority map. In the case that the multiple messages are of the same priority to the subscription, the negotiating subscription will choose a selected message type randomly. The negotiating subscription will then create exactly one subscription corresponding to the chosen type and topic name.

Negotiating Publisher and Subscription Pair

The negotiating publisher and subscription pair is a single node that has both a negotiating publisher and subscription. In this case, the negotiating subscription will wait on the negotiating publisher to pick selected message types and then make it's supported message priority map based on the publisher selected message types. Doing so allows the negotiating subscription to prioritize the selected message types of the publisher, which may be desirable for efficient data transfer.

The negotiating publisher and subscription pair operates much as described in the previous two sections, with one exception: the negotiating subscription will delay revealing its preferences until the negotiating publisher has determined its type. At that point, the negotiating subscription will reveal its preferences, and take part in the upstream negotiation network.

Renegotiating Selected Message Types

In the case that the ROS 2 network is changing, the negotiating publisher may need to renegotiate its selected message types. The process looks similar to the original negotiation, however the negotiating publisher remains active until it determines that the selected messages must be changed. If the selected messages must change, the negotiating publisher destroys its publishers. The negotiating publisher will then notify its subscriptions of the new selected message types on the user specified negotiation topic and create new publishers for the selected message types. When there is no change required in the selected types, the publisher will continue to be active.

Similarly, the negotiating subscription may need to change its selected message type. Once the negotiating publisher relays the new selected message types, the subscription decides if it needs to be updated. If the selected type or types match the subscription's current selected message type, the subscription does nothing and continues to be active. If the selected type or types do not match the subscription's current selected message type, the subscription recreates the subscription with the new select message type.

User Defined Functions

There are two types of custom functions in the negotiation process that the user can define:

Negotiating Publisher - Determining the set of selected message types:
 This is the function that takes in the preferences from all of the negotiating subscription along with the negotiating publisher, and generates a set of results that satisfy the network. The implementation of the negotiating publisher will have a built-in algorithm for determining the best set of matches for the network, but the user may want to override this decision making process. As an example, it may be the case that the default negotiation algorithm would have chosen 3 matches, but the hardware only supports 2 types simultaneously. In this case, the user would override the default negotiation algorithm to enhance it with one that can consult the hardware before making choices.
Negotiating Subscription - Picking selected message types:
 This is the function that receives the preferences as given by the negotiating publisher, and chooses the one this negotiating subscription should subscribe to. For instance, the default type selection may end up arbitrarily choosing the first supported type in the list, but the user may want to consult hardware before deciding which one to choose.

Negotiation Examples

Using the following notation, let N_n(T_1, T_2, ..., T_m) be node n, where n is a positive integer, and let the arguments in parentheses, T_1, T_2, ..., T_m, be the supported message types. Note that there can be m supported types for each node, where m is a positive integer. For convenience, let's also assume that the supported types are prioritized in their respective order, such that the priority of T_1 is the highest, T_2 is the second highest, and so on.

Using the node notation described above, we can then use the following notation to describe the selected message type between multiple nodes. In the example below, node 1 (N_1) supports only type x, and node 2 (N_2) supports types x and y. In this case, the selected message type is x, as shown by the x over the arrow pointing from node 1 to node 2. More practically, N_1 is publishing x, and N_2 is subscribing to a topic with the selected message type x.

         x
N_1(x) ----> N_2(x, y)

Simple Examples

We can now use this notation to reason about the agreed upon the selected message type in several different scenarios. There are several cases that are clear.

(1a)
                 x
        N_1(x) ----> N_2(x)

(1b)

        N_1(x) ----> N_2(y)  # FAILED NEGOTIATION

(1c)
                 y
        N_1(y) ----> N_2(x, y)

(1d)
                 x
     N_1(x, y) ----> N_2(x)

(1e)
                 y
     N_1(x, y) ----> N_2(y)

(1f)
                 x
  N_1(x, y, z) ----> N_2(x, a, b)

(1g)
                 x
  N_1(x, y, z) ----> N_2(a, b, x)

Publishing to Multiple Nodes

There are also the cases where there are more than two nodes.

In the following case, N_3 has the limiting supported type, y, so N_1 will publish y, despite the fact that both N_1 and N_2 prefer x. This is assuming that the function for picking the selected types prioritizes sending one message over sending multiple messages.

(2a)
              y
  N_1(x, y) -------> N_2(x, y)
                 |
                 |-> N_3(y)

In the following case, the two nodes receiving data from N_1 both require different supported message types. Thus, N_1 has two selected message types, x and y, and thus N_1 has two publishers.

(2b)
              x
  N_1(x, y) ----> N_2(x)
          |
          |   y
          |-----> N_3(y)

Negotiating Publisher and Subscription Pairs

To discuss negotiating publisher and subscription pairs, we'll have to use additional notation. The following notation shows the result of a custom function that uses the negotiating publishers selected message type to decide the supported message priority map for the negotiating subscription.

Let N_p([x, y, z], {x: [x, y, z], y: [y, z, x], z: [z, x, y]}) be a node p thats negotiating publishers and subscription. The first argument [x, y, z] is the prioritized supported type map for the negotiating publisher, that is, in this case, the negotiating publisher prefers x more than y, and y more than z. The second argument {x: [x, y, z], y: [y, z, x], z: [z, x, y]} is the prioritized supported type map for the negotiating subscription. This second argument is in the form of a dictionary ({key1: value1, key2: value2, ...}), where

  • the key is the selected message type of the negotiating publisher in the negotiating publisher subscription pair and
  • the value is the prioritized supported type map for the negotiating subscription given that key.

For example, for the node N_p([x, y, z], {x: [x, y, z], y: [y, z, x], z: [z, x, y]}), if the negotiating publisher negotiates with its subscriptions and determines that the selected message type is y, then the negotiating subscription in the negotiating publisher/subscription pair will state its supported message priority map as [y, z, x]. This is because in the second argument (the negotiating subscriptions preference map) the key y is mapped to the value [y, z, x]. Similarly, if the publisher chooses z, then the subscription will use the supported message priority map of [z, x, y].

As a shorthand in figures, we'll define a node that differs its preference beforehand and add an asterisk to separate it from other nodes. For example:

N_p*(x, y, z) := N_p([x, y, z], {x: [x, y, z], y: [y, z, x], z: [z, x, y]})

or

N_p* := N_p([x, y, z], {x: [x, y, z], y: [y, z, x], z: [z, x, y]})

Also, note that regular nodes with the standard notation (e.g., N_n(x, y, z), with no *) reveal their preferences when queried.

(3a)

  N_2*(x, y, z) := N_2([x, y, z], {x: [x, y, z], y: [y, z, x], z: [z, x, y]})

                 y                   y
  N_1(x, y, z) ----> N_2*(x, y, z) ----> N_3(y, z, x)

This approach can also be useful in networks that contain loops. In the case below, node 2 will cause node 1 to wait to pick its preference until it has determined its selected message type.

(3b)

  N_2*(x, y, z) := N_2([x, y, z], {x: [x, y, z], y: [y, z, x], z: [z, x, y]})

                  y
               |--------------------------
               |                         |
               |                     y   v
  N_1(x, y, z) ----> N_2*(x, y, z) ----> N_3(y, z, x)

It is possible with this method to have a deadlock. In the following case all nodes will delay their preference indefinitely. In this case, the only way out will be a timeout.

(3c)

  N_1* := N_1([x, y, z], {x: [x, y, z], y: [y, z, x], z: [z, x, y]})
  N_2* := N_1*
  N_3* := N_1*

    -- N_3* <--
    |         |
    v         |
  N_1* ----> N_2*

Notice, however, that the deadlock is fixed by one node readily revealing its preferences.

(3d)

  N_1* := N_1([x, y, z], {x: [x, y, z], y: [y, z, x], z: [z, x, y]})
  N_2* := N_1*

    -- N_3(x, y, z) <--
  x |                 |
    v    x          x |
  N_1* ----> N_2* -----

Rationale

Having the Publisher Pick the Selected Message Type

Consider a network with m negotiating publishers and n negotiating subscriptions, where m and n are positive integers. Also imagine that there are at least two publishers that are publishing with the same selected message type. In this case, it is possible to have each of the negotiating publishers consider the other negotiating publishers in their decision of what supported message type to select.

It is also true that loops in the network may occur. For example, imagine nodes A, B, and C. A sends a message to B, and B sends a message to C. This gets more complicated if A also sends a message to C.

In both of the above cases, it is much more challenging to find the best selected message type than the simple strategy detailed in a previous section. It was thought that the simpler approach described above in the specifications gets us almost all the way there, while being much simpler to implement. In addition, if it turns out to be necessary, the simpler approach can always be replaced by a better method for getting the optimal selected message type in future work.

To Take a Centralized or Decentralized Approach

The specification above takes a decentralized approach to negotiating publishers and subscriptions. That is, each negotiating publisher and subscription negotiates its own selected message type. It is also possible to take a centralized approach, where all publishers and subscriptions broadcast their preferences to a higher system that decides the selected message types.

The primary advantage of a decentralized approach is that it is easier to implement, especially given the greedy approach that we are using in computing the selected message type. If we wanted to find the optimal selected message types taking the entire system into account, we would most likely have to implement a centralized approach, which would have a full understanding of the entire system before making a decision.

Using in Conjunction with Lifecycle Nodes

Very much of the stateful behavior that is required for the negotiation process is implemented in lifecycle nodes. Thus, while this REP does not prescribe using lifecycle nodes for negotiation, it makes sense for users to combine these two features when implementing nodes.

Implementation in the ROS 2 Core or in a Separate Project

While there are some advantages to having this project in the ROS 2 core, all of the needed APIs are available to make this a separate package. Thus, in the spirit of keeping the ROS 2 core smaller, this should be implemented in a separate project.

Backwards Compatibility

The proposed feature adds new functionality while not modifying existing functionality.

Feature Progress

Currently, there has been some prototyping to understand how the proposed feature may be implemented in C++.

  • @audrow/type-negotiation-fusing-examples shows how supported messages can be defined and used by a negotiating publisher. The approach taken in this example is most likely the closest to how the proposed feature will be implemented.
  • @audrow/type-negotiation-type-mapping shows how the proposed feature may use C++ templating and a type map class to access publishers and subscriptions. Note that the types used in this approach will have to be replaced with structs in the future to allow for multiple supported types to use the same ROS message type.
  • @audrow/type-negotiation-possible-usage shows another approach which uses inheritance to implement the proposed feature. This approach requires some additional work from the user to implement functions that create typed publishers and subscriptions.

The current implementation is also available: https://github.com/osrf/negotiated

References

[1]REP 2007 (https://ros.org/reps/rep-2007.html)

Copyright

This document has been placed in the public domain.