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

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.