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)

Theta* algorithm

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

It offers an optimization over the A star algorithm to generate any-angle paths. Unlike A star, which always assigns the current node as the parent of the successor, Theta star checks for a line-of-sight (unblocked path) from an earlier node (typically the parent of the current node) to the successor, and directly assigns it as a parent if visible. This reduces cost by replacing staggered segments with straight lines.

Checking for line of sight involves verifying that no obstacles block the straight line between two nodes. On a grid, this means identifying all the discrete cells that the line passes through to determine if they are empty. Bresenham’s line algorithm is commonly used for this purpose. Starting from one endpoint, it incrementally steps along one axis, while considering the gradient to determine the position on the other axis. Because it relies only on integer addition and subtraction, it is both efficient and precise for grid-based visibility checks in Theta star.

As a result, Theta star produces shorter, smoother paths than A star, ideal for ground or aerial robots operating in continuous environments where smoother motion enables higher acceleration and reduced travel time.

In the animation, each cyan arrow represents a node pointing to its parent.

Reference

• Theta*: Any-Angle Path Planning on Grids

• Bresenham’s line algorithm

Code Link

PathPlanning.ThetaStar.theta_star.ThetaStarPlanner(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