---
# System prepended metadata

title: 'Unit 03: Motion Planning'
tags: [RNE]

---

# 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
![圖片](https://hackmd.io/_uploads/r1x8TgB6T.png)
![圖片](https://hackmd.io/_uploads/SkTdaxHpT.png)

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