Reeds-Shepp algorithm implementation in Python.


Keywords
reeds-shepp, path, planning
License
MIT
Install
pip install rsplan==1.0.10

Documentation

README

Overview

This package is a Reeds-Shepp library implementation with Python that is compatible with Python versions >= 3.9, including 3.11.

Contains the following files:

  • planner: Path planning code. path function outputs the optimal Reeds-Shepp path with or without a runway.
  • curves: Curve formulas for all of the curve types in the Reeds-Shepp paper.
  • primitives: Three class architectures (Waypoint, Segment, and Path).
    • Waypoint class (stores x, y, yaw of the waypoint and the curvature and length of the segment the waypoint is on as well as if the segment is a runway)
    • Segment class (stores left/right/straight type, forward/backward direction, length, and turn radius of the segment)
    • Path class (stores start and end points, turn radius, step size, and list of Segments. Also contains a cached waypoints function to get a list of Waypoints for the path)
  • helpers: Helper functions for planner, primitives, and curves files.
  • demo: Demo/visualization of paths.

Usage

Installation

You can install this software using pip:

$ pip3 install -U rsplan

Running

See demo.py for example usage

path(start_pose, end_pose, turn_radius, runway_length, step_size, length_tolerance (optional))

  • return a Reeds-Shepp path from start_pose to end_pose with specified turning radius and step_size between points. The length_tolerance default is 2 meters but can be set to user preference — if paths’ total lengths are within length tolerance of each other, the path function will choose the one with fewer segments as the optimal path. The runway_length is for the runway at the end of the path that helps improve accuracy in reaching the final position — this can be set to 0, or a positive or negative number for a forwards or backwards driving runway.
  • start_pose and end_pose are in the format Tuple[float, float, float] of x, y, yaw values.

FAQ

What are t, u, and v parameters?

  • As a whole, t, u, v are segment parameters generated in each of the curve helper functions that represent the distance (angular distance for curved segments, linear distance for straight segments) of their respective segments.
  • If there are 3 segments (ccc or csc), t is for segment 1, u is for segment 2, and v is for segment 3.
  • If there are 4 or 5 segments, the format is:
    • t, u, u, v for cccc paths (2nd and 3rd segments have same angular distance)
    • t, pi/2, u, v for ccsc paths (2nd segment has angle pi/2)
    • t, u, pi/2, v for cscc paths (3rd segment has angle pi/2)
    • t, pi/2, u, pi/2, v for ccscc paths (2nd and 4th segments have angle pi/2)
  • These are represented generally in the Segment class in the "distance" parameter, which we pass in t, u, v, or pi/2 for depending on the segment.

Exhibits

How to run the demo

  • Clone this repository

  • Update _END_POSES path coordinates in demo.py to the paths you would like to visualize

  • In terminal in the rsplan subfolder of this rsplan repository, run: $ python3 demo.py

Example paths visualized from demo.py:

Paths start from origin

Format: (end x, end y, yaw, turn radius, runway length)

  1. (5, 6, np.pi, 1, 0)
  2. (15, 3, np.pi / 2.0, 2, 6)
  3. (-2, -4, np.pi, 4, 3)
  4. (-7, 2, np.pi, 4, 0)
  5. (-7, -7, 0.0, 6, 1)
  6. (0.7, 1.8, 1, 1, 1)
  7. (-5, 6, np.pi / 3.0, 2, 1)
  8. (7, 2, 0.0, 6, 3)
  9. (-4, -1, -np.pi / 2.0, 1, 3)

Screenshot from 2023-07-18 11-50-32

References

Paper providing more information on the algorithm: Reeds, J., & Shepp, L. (1990). Optimal paths for a car that goes both forwards and backwards. https://msp.org/pjm/1990/145-2/pjm-v145-n2-p06-s.pdf

Curve formulas can be found on page 390-391. Inspiration for this Python implementation of the Reeds-Shepp algorithm: https://github.com/boyali/reeds_and_shepp_curves/tree/master