Path-Planning Approaches

Path-Planning Approaches

1. Roadmap

Represent the connectivity of the free space by a network of 1-D curves

1. Cell decomposition

Decompose the free space into simple cells and represent the connectivity of the free space by the adjacency graph of these cells

1. Potential field

Define a function over the free space that has a global minimum at the goal configuration and follow its steepest descent


Cell-Decomposition Methods

Two classes of methods:

§Exact cell decomposition
The free space F is represented by a collection of non-overlapping cells whose union is exactly F
Example: trapezoidal decomposition ( phân hủy hình thang)