# Grid based search — PythonRobotics documentation

# 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