Global planner (A*, Dijkstra) in ROS - Deep Dive

Overview - Global planner (A*, Dijkstra)

What is it?

A global planner is a software component in robotics that finds the best path from a start point to a goal point on a map. It uses algorithms like A* and Dijkstra to calculate this path by exploring possible routes and choosing the shortest or least costly one. These planners help robots move safely and efficiently in their environment. They work on a map that represents obstacles and free space.

Why it matters

Without a global planner, a robot would not know how to reach a destination safely or efficiently. It might bump into obstacles or take a very long route. Global planners solve the problem of navigation by providing a clear path, which is essential for robots to perform tasks like delivery, cleaning, or exploration. This makes robots more useful and reliable in real life.

Where it fits

Before learning global planners, you should understand basic robotics concepts like maps, coordinate systems, and robot movement. After mastering global planners, you can learn local planners that handle immediate obstacle avoidance and dynamic environments. This topic fits into the broader study of robot navigation and autonomous systems.

Mental Model

Core Idea

A global planner finds the best path on a map by exploring possible routes and choosing the shortest or least costly one using algorithms like A* or Dijkstra.

Think of it like...

Imagine you are in a city and want to walk from your home to a friend's house. You look at a map and try to find the shortest or easiest route avoiding blocked roads or construction. The global planner does the same for a robot, but with a map of its environment.

Map Grid Representation:
┌───────────────┐
│ S . . # . G │
│ . # . # . . │
│ . # . . . . │
│ . . # # . . │
└───────────────┘
S = Start, G = Goal, # = Obstacle, . = Free space

Pathfinding explores this grid to find the best route from S to G.

Build-Up - 7 Steps

1

Foundation

Understanding Robot Maps and Grids

Concept: Robots use maps divided into grids to represent their environment, marking obstacles and free spaces.

A robot's map is like a chessboard where each square can be free or blocked. The robot uses this grid to know where it can move. Each cell in the grid has a cost: usually zero for free space and high for obstacles. This grid is the playground for pathfinding algorithms.

Result

You can visualize the robot's environment as a grid with obstacles and free cells, ready for path planning.

Understanding the map as a grid with costs is essential because pathfinding algorithms work by exploring these cells.

2

Foundation

Basics of Pathfinding Algorithms

Concept: Pathfinding algorithms explore the grid to find a path from start to goal by checking neighbors step-by-step.

Imagine standing on a grid cell and looking around at adjacent cells to decide where to go next. Algorithms like Dijkstra and A* systematically check these neighbors, keeping track of the cost to reach each cell. They continue until they find the goal or run out of options.

Result

You understand how algorithms explore the grid stepwise to find paths.

Knowing that pathfinding is about exploring neighbors and costs helps grasp how planners decide routes.

3

Intermediate

Dijkstra's Algorithm for Global Planning

🤔Before reading on: Do you think Dijkstra's algorithm always finds the shortest path even if it explores many nodes? Commit to your answer.

Concept: Dijkstra's algorithm finds the shortest path by exploring all possible routes in order of increasing cost from the start.

Dijkstra starts at the start cell and explores all neighbors, updating the cost to reach them. It always picks the next cell with the lowest cost to explore. This continues until it reaches the goal. It guarantees the shortest path but can be slow because it explores many cells.

Result

You get the shortest path on the grid but may see many explored cells around the start.

Understanding Dijkstra's exhaustive search explains why it is reliable but sometimes inefficient.

4

Intermediate

A* Algorithm and Heuristics

🤔Before reading on: Does adding a heuristic to pathfinding always make it faster? Commit to yes or no.

Concept: A* improves on Dijkstra by using a heuristic to estimate the distance to the goal, guiding the search more directly.

A* adds a guess (heuristic) of how far each cell is from the goal. It explores cells that seem closer to the goal first, reducing unnecessary exploration. The heuristic must never overestimate the true distance to guarantee the shortest path.

Result

You get the shortest path faster than Dijkstra by focusing search towards the goal.

Knowing how heuristics guide search helps understand why A* is often preferred in robotics.

5

Intermediate

Integrating Global Planners in ROS

🤔Before reading on: Do you think global planners in ROS handle dynamic obstacles automatically? Commit to yes or no.

Concept: ROS global planners use algorithms like A* or Dijkstra to compute paths on static maps, providing a path for the robot to follow.

In ROS, global planners take a map and start/goal positions as input. They output a path as a list of points. This path is then used by local planners to handle real-time obstacles. Global planners do not react to moving obstacles themselves.

Result

You understand the role of global planners in ROS navigation stacks and their limitations.

Knowing the separation of global and local planning clarifies system design and responsibilities.

6

Advanced

Optimizing Global Planner Performance

🤔Before reading on: Can changing the grid resolution affect planner speed and path quality? Commit to yes or no.

Concept: Adjusting map resolution and heuristic functions can balance speed and path accuracy in global planners.

Finer grid resolution means more cells and more computation but more precise paths. Coarser grids speed up planning but may produce less smooth paths. Choosing an appropriate heuristic and pruning explored nodes can also improve performance.

Result

You can tune global planners for your robot's needs, balancing speed and path quality.

Understanding trade-offs in resolution and heuristics helps build efficient navigation systems.

7

Expert

Handling Complex Maps and Real-World Challenges

🤔Before reading on: Do you think global planners alone can guarantee collision-free paths in dynamic environments? Commit to yes or no.

Concept: Global planners assume static maps and may fail in dynamic or partially known environments, requiring integration with local planners and sensor feedback.

In real-world use, maps can be incomplete or change over time. Global planners provide a rough path, but local planners must adjust for moving obstacles. Also, planners may need to replan if the environment changes. Understanding these limits is key to robust navigation.

Result

You appreciate the need for combined planning strategies and continuous environment sensing.

Knowing the limits of global planners prevents overreliance and guides system design for real robots.

Under the Hood

Global planners work by representing the environment as a graph or grid where each node is a position and edges represent possible moves with costs. Dijkstra's algorithm explores nodes in order of increasing cost from the start, updating the shortest known distance to each node until reaching the goal. A* adds a heuristic estimate of the remaining distance to prioritize nodes closer to the goal, reducing exploration. Internally, these algorithms maintain data structures like priority queues to efficiently select the next node to explore and track visited nodes to avoid loops.

Why designed this way?

These algorithms were designed to guarantee finding the shortest path in a weighted graph. Dijkstra's method is simple and reliable but can be slow because it explores all nodes equally. A* was introduced to speed up search by using heuristics, balancing speed and optimality. The design reflects a trade-off between completeness, optimality, and efficiency. Alternatives like greedy search or breadth-first search either sacrifice optimality or efficiency, so A* and Dijkstra remain foundational.

┌───────────────┐
│ Start Node (S)│
└──────┬────────┘
       │ Explore neighbors with costs
       ▼
┌───────────────┐
│ Priority Queue│
│ (lowest cost) │
└──────┬────────┘
       │ Select next node
       ▼
┌───────────────┐
│ Update costs  │
│ and paths    │
└──────┬────────┘
       │ Repeat until goal
       ▼
┌───────────────┐
│ Goal Node (G) │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does A* always explore fewer nodes than Dijkstra? Commit to yes or no.

Common Belief: A* always explores fewer nodes than Dijkstra because it uses heuristics.

Reality: A* can explore more nodes if the heuristic is poor or overestimates distances, which breaks optimality and can cause extra exploration.

Why it matters: Using a bad heuristic can slow down planning and produce suboptimal paths, causing inefficient robot navigation.

Quick: Can global planners handle moving obstacles without replanning? Commit to yes or no.

Common Belief: Global planners can handle moving obstacles on their own without needing updates.

Reality: Global planners assume static maps and do not react to moving obstacles; local planners or replanning are needed for dynamic environments.

Why it matters: Relying only on global planners in dynamic settings can cause collisions or navigation failures.

Quick: Is a finer grid always better for path quality? Commit to yes or no.

Common Belief: Using a very fine grid always produces better paths without downsides.

Reality: Finer grids increase computation time and memory use, which can slow down planning and may not be necessary for all tasks.

Why it matters: Choosing grid resolution without balance can cause slow response times, reducing robot effectiveness.

Quick: Does Dijkstra's algorithm require a heuristic to find the shortest path? Commit to yes or no.

Common Belief: Dijkstra's algorithm needs a heuristic to find the shortest path efficiently.

Reality: Dijkstra's algorithm does not use heuristics; it explores all nodes in order of cost and always finds the shortest path but can be slower.

Why it matters: Confusing Dijkstra with heuristic-based algorithms can lead to wrong expectations about performance and behavior.

Expert Zone

1

The choice of heuristic in A* must be admissible (never overestimate) to guarantee optimal paths, but slight underestimation can speed up planning with acceptable path quality trade-offs.

2

In ROS, global planners often work with costmaps that include inflation layers around obstacles to create safer paths, which affects path shape and planner behavior subtly.

3

Some advanced global planners combine A* with graph pruning or hierarchical maps to handle large environments efficiently, a detail often missed by beginners.

When NOT to use

Global planners like A* and Dijkstra are not suitable for highly dynamic or unknown environments where obstacles move unpredictably. In such cases, reactive local planners or learning-based planners that adapt in real-time are better. Also, for very large maps, sampling-based planners like RRT (Rapidly-exploring Random Trees) may be more efficient.

Production Patterns

In real-world ROS systems, global planners run once or periodically to generate a rough path on a static map. This path is passed to local planners that handle obstacle avoidance and path smoothing. Developers tune grid resolution, costmap parameters, and heuristics to balance speed and safety. Some systems implement replanning triggers based on sensor updates to handle map changes.

Connections

Graph Theory

Global planners use graph search algorithms that are fundamental concepts in graph theory.

Understanding graph theory helps grasp why nodes and edges represent positions and moves, and why shortest path algorithms work.

GPS Navigation Systems

Both global planners and GPS systems calculate routes on maps to guide movement from start to destination.

Knowing how GPS finds routes on road maps helps understand how robots plan paths on grid maps.

Human Problem Solving

Global planning algorithms mimic how humans plan routes by estimating distances and avoiding obstacles.

Recognizing this connection reveals that algorithms formalize intuitive human strategies into precise, repeatable steps.

Common Pitfalls

#1 Using a heuristic that overestimates distance in A*.

Wrong approach:

function heuristic(node, goal) { return actualDistance(node, goal) * 1.5; } // Overestimates

Correct approach:

function heuristic(node, goal) { return actualDistance(node, goal); } // Admissible heuristic

Root cause:

Misunderstanding that heuristics must never overestimate to guarantee shortest path.

#2 Expecting global planner to avoid moving obstacles without replanning.

Wrong approach:

Run global planner once at start and follow path blindly despite dynamic obstacles.

Correct approach:

Combine global planner with local planner and trigger replanning when obstacles detected.

Root cause:

Confusing static map planning with dynamic environment navigation.

#3 Setting grid resolution too fine causing slow planning.

Wrong approach:

Use 1cm grid cells for a large map without performance considerations.

Correct approach:

Use coarser grid (e.g., 10cm) balancing detail and speed.

Root cause:

Not balancing computational cost with path precision.

Key Takeaways

Global planners use algorithms like A* and Dijkstra to find the best path on a map by exploring possible routes and costs.

Dijkstra explores all nodes equally and guarantees shortest paths but can be slow; A* uses heuristics to guide search faster while still finding optimal paths if heuristics are correct.

In ROS, global planners work on static maps and provide paths for local planners to follow and adjust in real time.

Choosing the right grid resolution and heuristic affects planner speed and path quality, requiring careful tuning.

Global planners alone cannot handle dynamic obstacles; combining them with local planners and sensor feedback is essential for real-world robot navigation.

Practice

1. What is the main difference between the A* algorithm and Dijkstra's algorithm in ROS global planners?

easy

A. Dijkstra uses a heuristic, while A* explores all paths evenly.

B. A* uses a heuristic to guide the search, while Dijkstra explores all paths evenly.

C. Both algorithms use heuristics but in different ways.

D. Neither algorithm considers obstacles in the map.

Solution

1. Step 1: Understand Dijkstra's algorithm behavior

   Dijkstra explores all possible paths evenly without using heuristics, ensuring the shortest path but potentially slower.

2. Step 2: Understand A* algorithm behavior

   A* uses a heuristic function to estimate the cost to the goal, guiding the search more efficiently and often faster.

3. Final Answer:

   A* uses a heuristic to guide the search, while Dijkstra explores all paths evenly. -> Option B

4. Quick Check:

   Heuristic guides A*; Dijkstra explores evenly [OK]

Hint: Remember: A* uses heuristics, Dijkstra does not [OK]

Common Mistakes:

• Confusing which algorithm uses heuristics
• Thinking both ignore obstacles
• Assuming both explore paths the same way

2. Which of the following is the correct way to initialize a Dijkstra planner in ROS using C++?

easy

A. auto planner = new DijkstraPlanner();

B. DijkstraPlanner planner = new DijkstraPlanner();

C. auto planner = DijkstraPlanner();

D. DijkstraPlanner planner();

Solution

1. Step 1: Understand object initialization in modern C++

   Using 'auto' with direct initialization calls the constructor properly and manages type automatically.

2. Step 2: Analyze each option

   auto planner = new DijkstraPlanner(); uses 'new' which returns a pointer, not an object. DijkstraPlanner planner = new DijkstraPlanner(); attempts to assign a pointer to an object, causing a type mismatch compile error. DijkstraPlanner planner(); is a function declaration, not an object. auto planner = DijkstraPlanner(); correctly initializes an object with automatic type deduction.

3. Final Answer:

   auto planner = DijkstraPlanner(); -> Option C

4. Quick Check:

   Use auto with constructor for clean initialization [OK]

Hint: Use 'auto planner = ClassName();' for simple object creation [OK]

Common Mistakes:

• Using parentheses that declare a function, not an object
• Using 'new' without managing pointers
• Not using auto for type deduction

3. Given the following ROS global planner code snippet using A*:

std::vector<Point> path = planner.makePlan(start, goal);
std::cout << path.size() << std::endl;

If the planner finds a path with 5 points, what will be printed?

medium

A. 0

B. 4

C. 6

D. 5

Solution

1. Step 1: Understand the return value of makePlan()

   The makePlan function returns a vector of points representing the path from start to goal, including both points.

2. Step 2: Analyze the output of path.size()

   If the planner finds a path with 5 points, the vector size is 5, so printing path.size() outputs 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Path points count equals vector size [OK]

Hint: Path size equals number of points including start and goal [OK]

Common Mistakes:

• Assuming path size excludes start or goal
• Confusing index with size
• Thinking path size counts edges, not points

4. You have this snippet in your ROS global planner node:

std::vector<Point> path = planner.makePlan(start, goal);
for (int i = 0; i <= path.size(); i++) {
  std::cout << path[i].x << "," << path[i].y << std::endl;
}

What is the error in this code?

medium

A. Using <= in the loop causes out-of-bounds access.

B. The loop variable should be a float, not int.

C. The path vector is not initialized.

D. The makePlan function does not return a vector.

Solution

1. Step 1: Analyze the loop condition

   The loop runs from i = 0 to i <= path.size(), which means it tries to access path[path.size()] on the last iteration.

2. Step 2: Understand vector indexing

   Vectors are zero-indexed, so valid indices are 0 to path.size() - 1. Accessing path[path.size()] causes out-of-bounds error.

3. Final Answer:

   Using <= in the loop causes out-of-bounds access. -> Option A

4. Quick Check:

   Loop index must be less than size, not less or equal [OK]

Hint: Use i < path.size() in loops to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= instead of < in loops
• Confusing vector size with last index
• Assuming makePlan returns empty vector

5. In a ROS global planner using A*, you want to modify the heuristic to prefer paths farther from obstacles for safety. Which approach correctly applies this change?

hard

A. Add a penalty to the heuristic cost for points near obstacles.

B. Subtract a penalty from the heuristic cost for points near obstacles.

C. Add a penalty to the heuristic cost for points far from obstacles.

D. Ignore the heuristic and use Dijkstra instead.

Solution

1. Step 1: Understand heuristic modification goal

   To prefer paths farther from obstacles, the heuristic should favor those points by lowering their cost or penalizing points near obstacles.

2. Step 2: Analyze penalty application

   Adding a penalty to the heuristic cost for points near obstacles increases their cost, which discourages paths near obstacles, as desired for safety.

3. Step 3: Choose correct approach

   Add a penalty to the heuristic cost for points near obstacles. correctly adds a penalty to points near obstacles, increasing their heuristic cost and discouraging proximity for safer paths.

4. Final Answer:

   Add a penalty to the heuristic cost for points near obstacles. -> Option A

5. Quick Check:

   Modify heuristic cost to prefer points near obstacles [OK]

Hint: Adjust heuristic cost to favor desired path traits [OK]

Common Mistakes:

• Confusing penalty direction for heuristic
• Ignoring heuristic and switching algorithms unnecessarily
• Not understanding heuristic impact on path choice