Grid based search

Breadth First Search

This is a 2D grid based path planning with Breadth first search algorithm.

In the animation, cyan points are searched nodes.

Depth First Search

This is a 2D grid based path planning with Depth first search algorithm.

In the animation, cyan points are searched nodes.

Dijkstra algorithm

This is a 2D grid based shortest path planning with Dijkstra’s algorithm.

In the animation, cyan points are searched nodes.

A* algorithm

This is a 2D grid based shortest path planning with A star algorithm.

In the animation, cyan points are searched nodes.

Its heuristic is 2D Euclid distance.

Bidirectional A* algorithm

This is a 2D grid based shortest path planning with bidirectional A star algorithm.

In the animation, cyan points are searched nodes.

D* algorithm

This is a 2D grid based shortest path planning with D star algorithm.

The animation shows a robot finding its path avoiding an obstacle using the D* search algorithm.

Ref:

• D* search Wikipedia

D* lite algorithm

This is a 2D grid based path planning and replanning with D star lite algorithm.

Ref:

• Improved Fast Replanning for Robot Navigation in Unknown Terrain

Potential Field algorithm

This is a 2D grid based path planning with Potential Field algorithm.

In the animation, the blue heat map shows potential value on each grid.

Ref:

• Robotic Motion Planning:Potential Functions