# Unit 03: Motion Planning
[TOC]
## Intro
- Motion planning aims to find the motion steps that moves the robot from the source to destination.
- Requirements:
- avoid collision
- smooth path
- minimal length
- motion constraints(e.g. maximum speed)
#### Path Planning
- Find the ==way-points== from the source position to the target position.
#### Trajectory Planning
- Plan the motion sequence that contains ==speed and acceleration==
information to handle the dynamic environment

## Path Planning
### Graph Search Based Methods
- Single-source shortest paths
– **Dijkstra** : Non-negative weights graphs (high complexity)
– **Best-First Search (BFS)** : Heuristic Greedy Search (fast but non-optimal)
– **A*** : BFS with Dijkstra

### Sampling Based Method
Sampling based methods decrease the search state in 2D space, while the algorithms only output sub-optimal solution (probabilistic completeness).
- **Probabilistic Road-Map (PRM)**
- **Rapidly Exploring Random Tree (RRT)**
- **RRT***<span class="red">&lt;-現在主流</span>

## Curve Interpolation
- Least Square Curve Fitting
- Cubic Interpolating Curves
- Hermite Curves
- Bezier Curves
- Cubic B‐spline Curves

## Trajectory Planning
### State Lattices Planning
- State Lattice Planning Workflow
1. Sample the candidate trajectories.
2. Compute the cost by pre-defined cost function.
3. Check the collision and Motion constraints and select the low-cost trajectory as output.

<style>
.blue {
color: blue;
}

.red {
color: red;
}
</style>