Dijkstra`s Algorithm vs A* Algorithm

In order to find the shortest path, the two well-known algorithms that are used widely in the field of robotics are the Dijkstra`s Algorithm and the A* Algorithm.

In Dijkstra's algorithm, we calculate the weight of the adjacent nodes and then visit the node that has the least weight. This process is continued until the goal node is reached. Djikstra`s algorithm becomes very similar to the Grassfire Algorithm in case of grids where the weight of each iteration is equal to 1. In such cases, we end up visiting all the nodes until the goal node is reached. This makes it very difficult to use it on larger grids because we visit all the unnecessary nodes. 


Whereas the A* algorithm uses the concept of a Heuristic function. In this algorithm, we visit only the nodes that can be on the shortest path by finding the distance of the adjacent nodes to the goal node and choosing the node that is the closest.


Comments

Post a Comment

Popular posts from this blog

The move_base ROS node

Image
move_base package provides the move_base node which is a major element of ROS Navigation stack. It moves the robot from its current position to a goal position. When path planning is done, the user gives uses the 2D Nav Goal in RVIZ to specify the goal position and orientation. This position (x,y,z) and orientation(x,y,z,w) are actually published in move_base/goal topic. The move_base node links together a global and local planner to accomplish its global navigation task. The Global Planner It is in charge of calculating the safe path in order to arrive at goal pose. Note that the path is calculated before the robot starts moving so it will not take into account the laser readings while moving i.e. unscanned obstacles that are not in the map. Navfn Planner The Navfn planner is the most commonly used global planner for ROS Navigation. It uses Dijkstra's algorithm in order to calculate the shortest path between the initial pose and the goal pose. Carrot Planner This plann
Read more

Three Wheeled Omnidirectional Robot : Motion Analysis

Image
A Three-wheeled omnidirectional robot is capable to moving in any given direction without rotating by giving velocities to the three wheels in a certain ratio. All motors are situated at an angle of 120 degrees from each other. f B ,  f L ,  f R  are for back , left and right wheel respectively. a x  and a y  are accelerations in X R  and Y R  axis in Robot frame and w is the angular velocity in Robot frame. Hence putting the values of alpha and making it into a matrix form we get : As we need to obtain the f values, we will invert the matrix. We need  a x  , a y  and w is the world frame, so we apply transformation. The transformation angle is    α 1  = 30 degrees.  Putting this in the previous equation, Multiplying the two matrices, we get the final relation as : For example, if you want to move the robot along X axis(world frame), put  a x W  = 1 , a y W  = 0 , w = 0 You will get the ratio of velocities as : 1 : -2 : 1 .
Read more