# ND2 - project - path planning

Path planning = How do I get there?

Obstacle avoidance = decisions the robot must make as it moves along its path.

## Other applications

Computer graphics and animation = use path planning to generate the motion of characters.

Computational biology = apply path planning to the folding of protein chains.

## Terminology

path planning

1. Complete - able to find a path between the start and the goal when one exists.
2. Optimal - able to find the best solution.

Complexity

1. Time complexity
2. Space(memory) complexity
3. Generality

Holonomic systems = systems where every constraint depends only on the current pose and time, and not on any derivatives with respect to time.

## Types

### Discrete Planning

Configuration space (continuous) -> Discretization -> Graph search

| ![](https://548312962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lq83PzYaksJkirwod4I%2F-Lq83Un_qn4pNS1_E1_u%2F-Lq83VQxXAzQcYblvB99%2Fconfiguratioin_space.png?generation=1569962723869641\&alt=media) | ![](https://548312962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lq83PzYaksJkirwod4I%2F-Lq83Un_qn4pNS1_E1_u%2F-Lq83VR-mZOSHD_PCTiz%2Fdiscrete.png?generation=1569962723883935\&alt=media) | ![](https://548312962-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lq83PzYaksJkirwod4I%2F-Lq83Un_qn4pNS1_E1_u%2F-Lq83VR1Nz9Hg9fq7VfN%2Fgraph_search.png?generation=1569962723915742\&alt=media) |
| ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |

It discretizes the robot’s workspace into a connected graph, and apply a graph-search algorithm to calculate the best path.

best suited for low-dimensional problems

**Graph search** = \[1]Breadth-first \[2]Depth-first \[3]Uniform cost \[4]A\* search

path planning complexity \~ exponentially with the number of dimensions in the C-space.

### Sample-Based Planning

Instead of discretizing every segment of the workspace, sample-based planning takes a number of samples and uses them to build a discrete representation of the workspace.

### Probabilistic Path Planning

While the first two approaches looked at the path planning problem generically - with no understanding of who or what may be executing the actions - probabilistic path planning takes into account the uncertainty of the robot’s motion.
