Metadata-Version: 2.1
Name: rsplan
Version: 1.0.7
Summary: Reeds-Shepp algorithm implementation in Python
Home-page: https://github.com/builtrobotics/rsplan
Author: Built Robotics
Author-email: Built Robotics <tarakapoor9@gmail.com>
License: MIT License
        
        Copyright (c) 2023 Built Robotics
        
        Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Keywords: reeds-shepp,path,planning
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python
Classifier: Programming Language :: Python :: 3
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy >=1.22.4
Requires-Dist: matplotlib
Provides-Extra: dev
Requires-Dist: pytest ; extra == 'dev'

## README

- [Overview](#overview)
- [Usage](#usage)
  - [Installation](#installation)
  - [Running](#running)
- [FAQ](#faq)
- [Exhibits](#exhibits)
- [References](#references)

## 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](https://github.com/builtrobotics/mariana/assets/44348827/eed5e06c-059e-48cb-9dc3-e56346f84476)




## 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 
