wiki:NavGraph
Last modified 5 years ago Last modified on 04/10/15 13:37:33

Topological Graph formatted in YAML

For global path planning using the navgraph plugin a topological graph grounded in the global (map) frame is required. Additionally, specific properties of points of interest might be of interest for the behavior system. This page describes the YAML-based description file format to specify such graphs and properties.

YAML is a "human friendly data serialization standard for all programming languages". It is a superset of the JavaScript Object Notation (JSON) that more people seem to be familiar with. It's particular aim is to be human-friendly to read and edit, while still providing structures easy to parse by machines.

Graph Specification Example

Here is a small example that should give a brief overview of the most important features:

NavGraph example visualized in rviz

%YAML 1.2
%TAG ! tag:fawkesrobotics.org,navgraph/
---
graph-name: My Graph

default-properties:
    # Max. distance between actual and target positions to deem the target
    # reached. This value is for intermediate nodes on a path; m
    # The value can be overwritten per node in the graph file.
    - travel_tolerance: 0.7

    # Max. distance between actual and target positions to deem the target
    # reached. This value is for the last node on a path; m
    # The value can be overwritten per node in the graph file.
    - target_tolerance: 0.3

    # Max. distance between actual and target orientation to deem the target
    # reached. This value is for the last node on a path; rad
    - orientation_tolerance: 0.6

    # When following a plan the robot will check all upcoming nodes if they
    # are close to the robot within this tolerance. If so, they take a shortcut
    # and will go to the node in the plan after the shortcut node.
    # This is potentially dangerous depending on the graph and navigator as it
    # might violate the typical graph constraint of only having direct-line-of-tavel
    # connections. The value can be overidden with a node property of the same name; m
    - shortcut_tolerance: 0.7

nodes:
  - name: Node A
    pos: [17.3, 7.55]

  - name: Node B
    pos: [15.5, 7.55]
    properties:
      - Hallway
      - orientation: -1.57

  - name: Node C
    pos: [19.0, 7.0]
    properties: [orientation: 0]

  - name: Node D
    pos: [19.0, 8.0]

# Possible directional tags:
# !bidir (bidirectional, default), !dir (directed)
connections:
  - [Node A, Node B]
  - !dir [Node A, Node C]
  - [Node C, Node D]
  - !dir [Node D, Node A]

First, some general settings for the graph are stored, like a name for the graph (if multiple graphs are used at the same time) or default properties.

The graph specifies four nodes along a hallway as you can also see on the screenshot. Each node must have a unique name and a position in the global (map) frame.

The nodes are connected with four edges, where the edges between the nodes A->C and D->A are directed, they can only be travelled in one particular direction. For Node B and D we have given an orientation. If the robot is send to one of these two locations it will turn in the end to reach the given orientation. Note the two seemingly different ways to specify the properties. In fact they are both the same, a sequence/list of mappings. Node B has an additional scalar property. It will be represented as a boolean property which is set to true. The "Hallway" property is not used by navgraph. Rather it can be used by the behavior system to query the graph. For example, it could ask for the "closest node on the hallway" (by searching for the closest node which has the "Hallway" property) and then call navgraph to go there.

Nodes

Nodes are specified in global YAML key "nodes" as a sequence of maps.

Mandatory Entries

name
Name of the node. The name must be unique within the graph. The node is often used in the behavior system to mark points of interest.
pos
Position in the global (map) frame of the node. It must be a sequence with exactly two number values specifying the X and Y coordinates (in that order) of the node.

Optional Entries

properties
Properties are a sequence of scalar or key/value pairs (maps with a single entry). Scalar values are stored as a boolean value with the value set to "true". Key value pairs are stored with their respective values. See below for certain well-known properties with a fixed meaning. Apart from these you can freely specify properties relevant to your application.

Well-known Properties for Nodes

Some well-known properties exist (not necessarily constrained to the navgraph plugin).

orientation
Applies to nodes, used by navgraph. If a node is the final target of a path then the local planner will be instructed to turn to this orientation in the global frame at the destination.
tolerance
Applies to nodes, used by navgraph. Overrides the default tolerance. The tolerance is the radius of a circle around the node (in meters). As soon as the robot enters this circle the node is assume to have been reached. For intermediate nodes navgraph will switch to the next node on the path, for the target node it will wait until the local planner is final or the target time has been exceeded (see below).
target-time
Applies to nodes, used by navgraph. Overrides the default target time. The target time is the time to wait for the local planner to become final for the final target node (and not for intermediate nodes). For example, the target is assumed to have been reached as soon as the tolerance circle has been entered. But the motion still needs to go on. This time specifies the maximum time to wait to achieve the final destination. Even if the time runs out before the local planner is final the operation will still be accounted as a success.
insert-mode
This allows to specify one of the following modes for inserting a node into the graph. It mainly regards what connections shall be made for a node.

  • closest-node: After inserting all nodes, connect the node with this particular property to the next closest node in the graph. (value alias: CLOSEST_NODE)
  • closest-edge: After inserting all nodes and pre-configured edges, connect the node with this particular property to the next closest node. That is an edge for which there is a line perpendicular to the edge going through the node in question, for which the endpoint on the edge lies within the line segment boundaries. It may be that no such edge exists, in which case graph generation will fail. (value alias: CLOSEST_EDGE)
  • closest-edge-or-node: First try to connect as if closest-edge was given. If that fails, try to connect to the closest node. (value alias: CLOSEST_EDGE_OR_NODE).

Tags for Nodes

YAML tags allow for a more concise definition of properties. Some have been defined. These are:

!unconnected
The node is known not to be connected to any other node through an edge. This can be useful for example to specify points with certain properties but where the robot will not directly travel to. To allow the connectedness assertion to still apply, mark such nodes with this tag. Example:

nodes:
  - !unconnected
    name: Unconnected-Node
    pos: [0, 0]
It is an error to add any connection for an unconnected edge.

Edges

Edges are specified as a sequence of two-entry sequences. Each of the two-entry sequences specifies a connection. The elements are exactly two node names which to connect. By default, edges are bidirectional/undirected, meaning that they can be traveled in both directions. Directed edges can be marked using the !dir tag. Then, the edge will go from the first node in the sequence to the second.

Properties for Edges

Properties for edges cannot be specified directly in the YAML file. Rather, properties are induced by tags (see below) or from graph generation. Plugins that add edges might also choose to add properties. Some well-known properties are:

created-for
This property is added for generated nodes to indicate for which connection the edge was initially created. The property is propagated, e.g. when splitting edges add intersections using the !split-intersection tag. Therefore, sub-edges can be mapped to their original intended connection. The property is added when connecting a node to a closest node or edge, or when inserting an edge with the !split-intersection tag. The value is a string of the form "N1--N2" where N1 and N2 are the names of the start and end node of the edge.
generated
This flag is added to nodes which are generated implicitly by a navgraph operation such as automatically connecting a node to the closest node or edge.
insert-mode
Set if one of the tags !no-intersection, !allow-intersection, or !split-intersection was set.

Tags for Edges

Tags are specified that give an additional meaning or hint to the processor of the file. Note that for an edge at most one tag may be given at a time. Example:

connections:
  - !dir [Node1, Node2]
  - !split-intersection [Node3, Node4]
!dir
Applies to edges. If set, the edge is directed (see above).
!bidir
Applies to edges. If set, the edge is bidirectional (see above). This is the default and it is not necessary to specify !bidir explicitly, but you can do so to make things clear if you like.
!no-intersection
Do not allow that the specific edge intersects with any other already existing edge (edges specified later may still violate this constraint). This is the default for edges.
!allow-intersection
Allow that the specific edge intersects with any other already existing edge. Note that the edge might still violate the !no-intersection constraint of other edges.
!split-intersection
For each edge that the specific edge intersects with on insertion, add a new uniquely named node at the intersection point and split the existing and the inserted edge. Each existing edge that intersects will thus be split into two sub-edges. The inserted edge will be split at each intersection point, therefore resulting in one or more edges to be added. For each of the latter kind of edges added, the "created-for" property will be added (see above).

Assertions

Several assertions apply to a graph which are check when the graph is loaded.

  • Each node name must be unique
  • Each node mention in an edge must exist
  • The graph must be fully connected, meaning that there may be no two nodes within the graph for which no path can be found that connects the two nodes. Not that unconnected nodes are exempt from this check.

Attachments