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.

Code Link

PathPlanning.BreadthFirstSearch.breadth_first_search.BreadthFirstSearchPlanner(ox, oy, reso, rr)

Depth First Search

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

In the animation, cyan points are searched nodes.

Code Link

PathPlanning.DepthFirstSearch.depth_first_search.DepthFirstSearchPlanner(ox, oy, reso, rr)

Dijkstra algorithm

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

In the animation, cyan points are searched nodes.

Code Link

PathPlanning.Dijkstra.dijkstra.DijkstraPlanner(ox, oy, resolution, robot_radius)

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.

Code Link

PathPlanning.AStar.a_star.AStarPlanner(ox, oy, resolution, rr)

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.

Code Link

PathPlanning.BidirectionalAStar.bidirectional_a_star.BidirectionalAStarPlanner(ox, oy, resolution, rr)

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.

Code Link

class PathPlanning.DStar.dstar.Dstar(maps)

Reference

• D* search Wikipedia

D* lite algorithm

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

Code Link

class PathPlanning.DStarLite.d_star_lite.DStarLite(ox: list, oy: list)

Reference

• 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.

Code Link

PathPlanning.PotentialFieldPlanning.potential_field_planning.potential_field_planning(sx, sy, gx, gy, ox, oy, reso, rr)

Reference

• Robotic Motion Planning:Potential Functions