Smac Planner

The SmacPlanner is a plugin for the Nav2 Planner server. It includes currently 2 distinct plugins:

• SmacPlanner: a highly optimized fully reconfigurable Hybrid-A* implementation supporting Dubin and Reeds-Shepp models.
• SmacPlanner2D: a highly optimized fully reconfigurable grid-based A* implementation supporting Moore and Von Neumann models.

It also introduces the following basic building blocks:

• CostmapDownsampler: A library to take in a costmap object and downsample it to another resolution.
• AStar: A generic and highly optimized A* template library used by the planning plugins to search. Template implementations are provided for grid-A* and SE2 Hybrid-A* planning. Additional template for 3D planning also could be made available.
• CollisionChecker: Collision check based on a robot’s radius or footprint.
• Smoother: A Conjugate-gradient (CG) smoother with several optional cost function implementations for use. This is a cost-aware smoother unlike b-splines or bezier curves.

We have users reporting using this on:

• Delivery robots
• Industrial robots

Introduction

The smac_planner package contains an optimized templated A* search algorithm used to create multiple A*-based planners for multiple types of robot platforms. It was built by Steve Macenski while at Samsung Research. We support differential-drive and omni-directional drive robots using the SmacPlanner2D planner which implements a cost-aware A* planner. We support cars, car-like, and ackermann vehicles using the SmacPlanner plugin which implements a Hybrid-A* planner. This plugin is also useful for curvature constrained planning, like when planning robot at high speeds to make sure they don’t flip over or otherwise skid out of control. It is also applicable to non-round robots (such as large rectangular or arbitrary shaped robots of differential/omnidirectional drivetrains) that need pose-based collision checking.

The SmacPlanner fully-implements the Hybrid-A* planner as proposed in Practical Search Techniques in Path Planning for Autonomous Driving, including hybrid searching, CG smoothing, analytic expansions and hueristic functions.

In summary…

The SmacPlanner is designed to work with:

• Ackermann, car, and car-like robots
• High speed or curvature constrained robots (as to not flip over, skid, or dump load at high speeds)
• Arbitrary shaped, non-circular differential or omnidirectional robots requring SE2 collision checking

The SmacPlanner2D is designed to work with:

• Circular, differential or omnidirectional robots
• Relatively small robots with respect to environment size (e.g. RC car in a hallway or large robot in a convention center) that can be approximated by circular footprint.

Features

We further improve on the Hybrid-A* work in the following ways:

• Remove need for upsampling by searching with 10x smaller motion primitives (same as their upsampling ratio).
• Multi-resolution search allowing planning to occur at a coarser resolution for wider spaces (O(N^2) faster).
• Cost-aware penalty functions in search resulting in far smoother plans (further reducing requirement to smooth).
• Additional cost functions in the CG smoother including path deflection.
• Approximated smoother Voronoi field using costmap inflation function.
• Fixed 3 mathematical issues in the original paper resulting in higher quality smoothing.
• Faster planning than original paper by highly optimizing the template A* algorithm.
• Automatically adjusted search motion model sizes by motion model, costmap resolution, and bin sizing.
• Closest path on approach within tolerance if exact path cannot be found or in invalid space.
• Multi-model hybrid searching including Dubin and Reeds-Shepp models. More models may be trivially added.
• Time monitoring of planning to dynamically scale the maximum CG smoothing time based on remaining planning duration requested.
• High unit and integration test coverage, doxygen documentation.
• Uses modern C++14 language features and individual components are easily reusable.
• Speed optimizations: Fast approximation of shortest paths with wavefront hueristic, no data structure graph lookups in main loop, near-zero copy main loop, Voronoi field approximation, et al.
• Templated Nodes and A* implementation to support additional robot extensions.

All of these features (multi-resolution, models, smoother, etc) are also available in the 2D SmacPlanner2D plugin.

The 2D A* implementation also does not have any of the weird artifacts introduced by the gradient wavefront-based 2D A* implementation in the NavFn Planner. While this 2D A* planner is slightly slower, I believe it’s well worth the increased quality in paths. Though the SmacPlanner2D is grid-based, any reasonable local trajectory planner - including those supported by Navigation2 - will not have any issue with grid-based plans.

Metrics

The original Hybrid-A* implementation boasted planning times of 50-300ms for planning across 102,400 cell maps with 72 angular bins. We see much faster results in our evaluations:

• 2-20ms for planning across 147,456 (1.4x larger) cell maps with 72 angular bins.
• 30-120ms for planning across 344,128 (3.3x larger) cell map with 72 angular bins.

For example, the following path (roughly 85 meters) path took 33ms to compute.

Design

The basic design centralizes a templated A* implementation that handles the search of a graph of nodes. The implementation is templated by the nodes, NodeT, which contain the methods needed to compute the hueristics, travel costs, and search neighborhoods. The outcome of this design is then a standard A* implementation that can be used to traverse any type of graph as long as a node template can be created for it.

We provide by default a 2D node template (Node2D) which does 2D grid-search with either 4 or 8-connected neighborhoods, but the smoother can be used to smooth it out. We also provide a SE2 node template (NodeSE2) which does SE2 (X, Y, theta) search and collision checking on Dubin or Reeds-Shepp motion models. Additional templates could be easily made and included for 3D grid search and non-grid base searching like routing.

Additional node templates could be added into the future to better support other types of robot path planning, such as including a state lattice motion primitive node and 3D path planning. Pull requests or discussions aroudn this point is encouraged.

In the ROS2 facing plugin, we take in the global goals and pre-process the data to feed into the templated A* used. This includes processing any requests to downsample the costmap to another resolution to speed up search and smoothing the resulting A* path. For the SE2 and SmacPlanner plugins, the path is promised to be kinematically feasible due to the kinematically valid models used in branching search. The 2D A* is also promised to be feasible for differential and omni-directional robots.

We isolated the A*, costmap downsampler, smoother, and Node template objects from ROS2 to allow them to be easily testable independently of ROS or the planner. The only place ROS is used is in the planner plugins themselves.

Parameters

See inline description of parameters in the SmacPlanner. This includes comments as specific parameters apply to SmacPlanner2D and SmacPlanner in SE2 place.

``` planner_server: ros__parameters: planner_plugins: [“GridBased”] use_sim_time: True

GridBased:
  plugin: "smac_planner/SmacPlanner"
  tolerance: 0.5                    # tolerance for planning if unable to reach exact pose, in meters, for 2D node
  downsample_costmap: false         # whether or not to downsample the map
  downsampling_factor: 1            # multiplier for the resolution of the costmap layer (e.g. 2 on a 5cm costmap would be 10cm)
  allow_unknown: false              # allow traveling in unknown space
  max_iterations: -1                # maximum total iterations to search for before failing
  max_on_approach_iterations: 1000  # maximum number of iterations to attempt to reach goal once in tolerance, 2D only
  max_planning_time_ms: 2000.0      # max time in ms for planner to plan, smooth, and upsample. Will scale maximum smoothing and upsampling times based on remaining time after planning.
  smooth_path: false                # Whether to smooth searched path
  motion_model_for_search: "DUBIN"  # 2D Moore, Von Neumann; SE2 Dubin, Redds-Shepp

File truncated at 100 lines see the full file