Last modified 5 years ago Last modified on 03.07.2013 14:19:37

Graph-based Locomotion Path Planning

The task of moving a robot from one point in the environment to another is traditionally split up into two parts: the global and local planners. The local planner performs collision avoidance and calculates the parameters to instruct the locomotion component like a holonomic or differential drive. The global planner calculates a longer path through the environment and uses the local planner to execute it.

The navgraph plugin constitutes a simple global planner. It takes a graph of target and intermediate path nodes and edges among those nodes which are suitable to be followed by the local planner. In Fawkes, the colli plugin constitutes the local planner. The graph can be created manually or automatically and can have certain properties which the path planner can obey. The graph file format is described in NavGraph.

The plugin can be instructed to either travel to a specified node, or to any position in free space. In any case it will search for the nearest graph node to the current position as the starting point. It will then perform an A* search in the graph to either the target node, or the graph node closest to the free position. After travelling to the first node, following the route and reaching the final graph node, the goal has been reached, or another local navigation is performed to the free space position.

The plugin has been ported from the AllemaniACs' RCSoft where it was named "pathplan". The file format has been modified to use YAML rather than YAML, and it got several improvements and extensions.


Config Values

Besides the configuration values listed below, certain transformations must exist. In particular, there must be a transform from the base frame to the local frame (typically /base_link to /map). For example, the amcl plugin can provide self-localization and the required transform. For testing, you can also use the map-lasergen plugin.

/plugins/navgraph/base_framestringBase Frame ID/base_link*
/plugins/navgraph/global_framestringGlobal Frame ID/map*
/plugins/navgraph/navigator_interface_idstringBlackboard interface ID for navigator interface of locomotion componentNavigator*
/plugins/navgraph/graph_filestringGraph file to use for path planning *
/plugins/navgraph/tolerancefloatDistance between actual and target position to consider traveling to a node finished; m0.25*
/plugins/navgraph/visualizationboolVisualize graph and current actions?1*
/plugins/navgraph/resend_intervalfloatInterval in which the resend the goto command; sec0.25*
/plugins/navgraph/target_timefloatTime to keep moving after the target tolerance has been reached; sec2.5*
/plugins/navgraph/monitor_fileboolMonitor graph file and automatically reload on changes?1*


BlackBoard Interfaces

  • NavigatorInterface::Pathplan: provides target information and receives CartesianGotoMessage and PlaceGotoMessage.


BlackBoard Interfaces

  • NavigatorInterface::<Navigator Interface ID>: Local motion planner interface, ID is read from config file.


  • Base frame to Global frame: position of laser robot in global frame

Usage Instructions

First prepare a map of the environment to localize in. Based on this map, create a graph where the node positions match the map positions. Note that if you change the origin or increase the size of the map the node positions might need adjustments. Read the NavGraph page for information on the graph file format. Create a graph and start Fawkes loading the navgraph plugin. If you have enabled the ros integration run the ros and ros-tf? plugins. Start rviz and add the MarkerArray display type. Afterwards, the graph will be shown. Note that this required the /map fixed frame to be properly published.

Use the ppgoto skill to move to a specified position using navgraph.