Dijkstra's Algorithm

Dijkstra's algorithm solves the Single-Source Shortest Path (SSSP) problem. From a designated source node, it computes the shortest path distance (and can reconstruct the path) to every other reachable node in the graph. This is in contrast to algorithms like Floyd-Warshall, which compute all-pairs shortest paths, or A*, which finds a path to a single goal. The algorithm maintains a tentative distance for each node, which it iteratively finalizes in order of increasing distance from the source.

The algorithm operates on a greedy principle. At each step, it selects the unvisited node with the smallest known tentative distance and finalizes it, declaring that distance as optimal. This greedy choice is guaranteed to be correct only if all edge weights are non-negative. A negative weight could create a cycle that reduces the total path distance, violating the assumption that a finalized distance is minimal. For graphs with negative weights, the Bellman-Ford algorithm must be used instead.

The time complexity of Dijkstra's algorithm depends heavily on the data structure used for the priority queue that selects the next node to visit.

• Simple Array: O(|V|²) - Suitable for dense graphs.
• Binary Heap Priority Queue: O((|E| + |V|) log |V|) - The standard efficient implementation for sparse graphs common in robotics.
• Fibonacci Heap: O(|E| + |V| log |V|) - Asymptotically better for very large, sparse graphs.

Here, |V| is the number of vertices (nodes) and |E| is the number of edges.

In motion planning, the robot's configuration space (C-space) is discretized into a graph for Dijkstra's algorithm to search.

• Nodes represent discrete robot states or configurations.
• Edges represent feasible transitions between states (e.g., small motions).
• Edge Weights encode the cost of a transition, such as distance, time, energy consumption, or a penalty for proximity to obstacles. This transforms the continuous planning problem into a discrete graph search, where the output is the minimum-cost sequence of states from start to goal.

While both find shortest paths, key differences are crucial for performance:

• Dijkstra: Explores uniformly in all directions from the source. It finds optimal paths to all nodes.
• A*: Uses a heuristic function (e.g., Euclidean distance to goal) to guide exploration preferentially toward the goal. It is typically faster for single-goal queries but requires an admissible heuristic (never overestimates cost) to guarantee optimality. Dijkstra is equivalent to A* with a heuristic function of zero. In robotics, A* is often preferred for point-to-point planning, while Dijkstra's property of exploring the entire reachable space can be useful for multi-goal planning or building distance maps.

Dijkstra's algorithm is not just a standalone planner; it is a core subroutine in more advanced robotic systems:

• Distance Transform: Used to compute a gradient or cost-to-go map from goal regions, which can guide local planners or sampling-based algorithms.
• Probabilistic Roadmap (PRM): Once a roadmap graph is constructed, Dijkstra's algorithm is used to find the shortest path within it.
• Dynamic Window Approach (DWA): The global path, often computed by Dijkstra or A*, provides the objective for the local, reactive planner. Its guarantee of global optimality (within the discretized graph) makes it a trusted component for generating reference paths in hierarchical planning architectures.

A* is an informed graph search and pathfinding algorithm that extends Dijkstra's by incorporating a heuristic function to estimate the cost to the goal. This prioritizes exploration towards the target, making it dramatically more efficient for single-goal queries.

• Core Mechanism: Combines the actual cost from the start (g(n)) with a heuristic estimate to the goal (h(n)), evaluating nodes by f(n) = g(n) + h(n).
• Relation to Dijkstra: When the heuristic h(n) is set to zero for all nodes, A* degenerates exactly into Dijkstra's algorithm.
• Primary Use: Favored in robotics and video games for finding optimal paths when a good heuristic (like Euclidean distance) is available.

Configuration Space is the fundamental abstraction where motion planning occurs. It represents every possible state of a robot as a single point, transforming the physical world into a mathematical space where obstacles become forbidden regions.

• Purpose: Converts the complex problem of moving a physical shape into the simpler problem of navigating a point through a space.
• Connection to Dijkstra: Dijkstra's algorithm operates on a discrete graph representation of the free space within C-Space. The graph's nodes are sampled configurations, and edges are valid transitions between them.
• Dimensionality: For a robotic arm with N joints, C-Space is N-dimensional, making exhaustive search (like a naive grid-based Dijkstra) computationally intractable, leading to sampling-based methods.

Probabilistic Roadmap is a sampling-based motion planning algorithm that constructs a graph network (roadmap) in the robot's free configuration space. It is designed for multiple queries in the same static environment.

• Two-Phase Process: 1) Learning Phase: Randomly sample collision-free configurations and connect nearby ones with local paths. 2) Query Phase: Connect specific start/goal points to the roadmap and use a graph search (like Dijkstra or A*) to find a path.
• Contrast with Dijkstra: PRM does not search the entire space exhaustively. It builds a sparse graph that captures the connectivity of the environment, upon which Dijkstra's algorithm can then efficiently find paths.
• Application: Ideal for high-dimensional C-Spaces where constructing a complete grid for Dijkstra is impossible.

A Weighted Graph is the fundamental data structure on which Dijkstra's algorithm operates. It consists of vertices (nodes) and edges, where each edge has an associated numerical weight or cost.

• Representation in Robotics: Nodes represent discrete robot states (e.g., grid cells, sampled configurations). Edge weights can represent distance, time, energy consumption, traversal difficulty, or risk.
• Algorithm Requirement: Dijkstra's algorithm requires non-negative edge weights. The presence of negative weights invalidates its optimality guarantee and can cause infinite loops.
• Construction: The challenge in motion planning is often in constructing a meaningful graph that accurately reflects the robot's dynamics and environmental costs before Dijkstra is even applied.

The Shortest Path Problem is the classic optimization problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. Dijkstra's algorithm is one of the most famous and fundamental solutions.

• Problem Class: Dijkstra solves the single-source shortest path problem, finding the shortest path from a source node to all other nodes in the graph.
• Optimality: For graphs with non-negative weights, Dijkstra's algorithm is guaranteed to produce optimal (minimum-cost) paths.
• Extensions in Robotics: In physical systems, the "shortest" path is often not just geometric distance but may optimize for smoothness (jerk), energy, or time, leading to trajectory optimization built on top of an initial geometric path.

Breadth-First Search is a fundamental graph traversal algorithm that explores all nodes at the present "depth" level before moving to nodes at the next depth level. It operates on unweighted graphs.

• Relation to Dijkstra: Dijkstra's algorithm can be viewed as a generalization of BFS for weighted graphs. If all edge weights are equal and positive, Dijkstra's exploration order becomes identical to BFS.
• Cost Metric: BFS finds the path with the fewest number of edges (hops). Dijkstra finds the path with the lowest cumulative edge weight.
• Use Case: In robotics, BFS might be used for simple grid-based planning where movement cost to all adjacent cells is identical (e.g., a vacuum robot). Dijkstra is used when costs vary (e.g., rough terrain vs. smooth floor).