Self-Morphing Adaptive Replanning Tree (SMART) 3D

Table of Contents

• SMART Algorithm
• Usage
  • Running the Examples
    • 2D Scenarios
    • 3D Scenarios
    • Standard RRT and RRT*
  • Using the Library
• Citation

SMART Algorithm

Self-Morphing Adaptive Replanning Tree (SMART) is an RRT* based path-planning algorithm for fast reactive replanning in dynamic environments. The original SMART algorithm is limited to 2D environments. This repository implements a higher-dimensional version of Self-Morphing Adapative Replanning Trees. Compared to the original SMART, the main difference is the removal of the grid based decomposition. Instead of hot-spots, this implementation uses hot-nodes, which do not require a grid. Therefore, this implementation can be used in higher dimensional environments. It can also still be used in 2D environments and achieves similar performance to the original SMART. Although this implementation is not limited to 3D, we refer to it as SMART-3D.

Original SMART Repository: https://github.com/ZongyuanShen/SMART

Original SMART Paper:

• arxiv: https://arxiv.org/abs/2305.06487
• IEEE: https://ieeexplore.ieee.org/document/10250928/

The SMART-3D paper will be published on arxiv and a link will be added here shortly.

Usage

Running the Examples

The examples can be used to reproduce all results from the SMART-3D arxiv paper. To build and run the examples, you must have cargo and uv (for Python) installed.

SMART-3D in 2D Scenarios

• run_2d_scenarios.rs
  • cargo run --release --example run_2d_scenarios
  • Runs the SMART algorithm for many trials in 2D scenarios with random spherical obstacles
  • Number of obstacles and obstacle speed is varied
  • The environment, scenario and planning parameters are configured at the beginning of the main function
  • Creates a directory called output/2d_scenarios which stores the outcome of each scenario
    • output/2d_scenarios/2d_scenarios.json contains each information about parameters and result of each trial
    • output/2d_scenarios/runs contains a .bin for each trial which contains the full serialized trial recording
    • By passing the output-dir argument to run_2d_scenarios, the output/2d_scenarios can be changed to another location
• replay_2d_scenario.rs
  • cargo run --release --example replay_2d_scenario -- --filepath <path/to/runs/scenario_run.bin>
    • To optionally generate a video, add: --output-video <path/to/save/video.mp4>
  • Takes a scenario .bin file generated by run_2d_scenarios.rs and replays the entire run
• plot_scenario_stats.py
  • uv run ./examples/plot_scenario_stats.py <path/to/2d_scenarios.json>
  • uv run ./examples/plot_scenario_stats.py ./output/2d_scenarios/2d_scenarios.json
  • Creates a plots folder within the same directory as the scenarios json and populates with plots of:
    • Success rates
    • Replanning times
    • Number of Replannings
    • Travel times
    • Travel distances
  • Each variable is plotted against both the varying obstacle speed and the varying number of obstacles

SMART-3D in 3D Scenarios

• run_3d_scenarios.rs
  • cargo run --release --example run_3d_scenarios
  • Runs the SMART algorithm for many trials in 3D scenarios with random spherical obstacles
  • Number of obstacles and obstacle speed is varied
  • The environment, scenario and planning parameters are configured at the beginning of the main function
  • Creates a directory called output/3d_scenarios which stores the outcome of each scenario
    • output/3d_scenarios/3d_scenarios.json contains each information about parameters and result of each trial
    • output/3d_scenarios/runs contains a .bin and a .json for each trial which contains the full serialized trial recording
      • Unlike the 2D scenarios, the .bin files do not contain the tree information at each timestep (to save disk space)
    • By passing the output-dir argument to run_3d_scenarios, the output/3d_scenarios can be changed to another location
• replay_3d_scenario.py
  • uv run ./examples/replay_3d_scenario.py <path/to/3d_scenarios/runs/scenario_run.json>
    • To optionally generate a video, add: --video <path/to/save/video.mp4>
  • Takes a scenario .json file (for a specific run) generated by run_3d_scenarios.rs and replays the entire run
  • Run uv run ./examples/replay_3d_scenario.py -h to see information about additional arguments
• plot_scenario_stats.py
  • uv run ./examples/plot_scenario_stats.py <path/to/3d_scenarios.json>
  • uv run ./examples/plot_scenario_stats.py ./output/3d_scenarios/3d_scenarios.json
  • Creates a plots folder within the same directory as the scenarios json and populates with plots of:
    • Success rates
    • Replanning times
    • Number of Replannings
    • Travel times
    • Travel distances
  • Each variable is plotted against both the varying obstacle speed and the varying number of obstacles

Standard RRT and RRT*

• rrt_2d.rs
  • cargo run --release --example rrt_2d
  • Runs and visualizes RRT in a 2D environment
• rrt_star_2d.rs
  • cargo run --release --example rrt_star_2d
  • Runs and visualizes RRT* in a 2D environment

Using the Library

This Rust crate provides a library that implements SMART-3D. To understand how to use it, please refer to the scenarios/scenario2d.rs and scenarios/scenario3d.rs files within the examples. In each of these scenario examples, the run function sets up SMART with an initial RRT* and then calls the run_simulation function. The run_simulation function continuously updates robot and obstacle positions at each timestep and calls the SMART update function for replanning.

In addition to the implementation of SMART, the implementations of RRT and RRT* can also be used on their own. The rrt module within the src folder provides everything needed for these algorithms. Please refer to the rrt_2d.rs and rrt_star_2d.rs examples to understand how to use these.

Citation

If you use the code from the repository, please cite the following papers:

@article{shen2023smart,
title={SMART: Self-Morphing Adaptive Replanning Tree},
author={Shen, Zongyuan and Wilson, James P and Gupta, Shalabh and Harvey, Ryan},
journal={IEEE Robotics and Automation Letters},
year={Sep. 2023},
volume={8},
number={11},
pages={7312-7319}
}

Once the SMART-3D paper is published on arxiv, it will also be added here.