Shortest Path Problem with Obstacles: A Modified Dijkstra's Algorithm

Introduction

The shortest path problem with obstacles requires dynamic adaptation of traditional graph algorithms to handle real-world constraints like blocked nodes/edges. While Dijkstra’s algorithm guarantees optimal paths in static graphs, its modified version addresses NP-hard obstacle constraints through iterative replanning and sensor integration, making it viable for robotics, autonomous vehicles, and disaster response systems

 

Historical Context

• 1956: Dijkstra’s algorithm introduced for shortest paths in weighted graphs.
• 2022: Improved Dijkstra variants emerged for mobile robots (MRs), integrating ultrasonic sensors for real-time obstacle detections.
• 2023: The ETJ study introduced adjustable weight adaptation, enabling real-time updates to edge weights for obstacle avoidance[ETJ, 2023].

• 2023: Hybrid approaches like MEDWA combined vector fields with Dynamic Window Approach (DWA) for dense obstacle scenarios

 

 

 

Theoretical Foundations

Time Complexity Breakdown:

• Dijkstra’s Algorithm: Uses a priority queue (Min-Heap), leading to O((V + E) log V) complexity.
• Modified Approach:

o   If restricted nodes reduce the number of edges, it improves efficiency.

o   In a worst-case scenario, if many nodes are restricted, a complete re-run might be required, keeping the complexity the same.

Space Complexity Breakdown:

• Graph Storage: O(V + E) for adjacency list representation.
• Priority Queue Storage: O(V).
• Total Space Complexity: O(V + E).

 

Theoretical Foundations

Time Complexity Breakdown:

• Dijkstra’s Algorithm: Uses a priority queue (Min-Heap), leading to O((V + E) log V) complexity.
• Modified Approach:

o   If restricted nodes reduce the number of edges, it improves efficiency.

o   In a worst-case scenario, if many nodes are restricted, a complete re-run might be required, keeping the complexity the same.

Space Complexity Breakdown:

• Graph Storage: O(V + E) for adjacency list representation.
• Priority Queue Storage: O(V).
• Total Space Complexity: O(V + E).

Modified Dijkstra’s Algorithm

1.  Offline path generation: Compute initial shortest path using standard Dijkstra.

2.  Iterative obstacle checking:

while current_node != target: 

    if obstacle_detected(next_node): 

        G.remove_edge(current_node, next_node) 

        recompute_path()  # Runs Dijkstra on updated graph 

    move_to(next_node) 

3.  Dynamic graph updates: Sensor data invalidates obstructed edges, reducing exploration space.[Link]

 

Case Study: Mobile Robot Navigation-[Link]

Setup

• Environment: 9 nodes, 19 edges, 2 obstacles.
• Hardware: STEAM-based MR with ultrasonic sensors.

Results

• Path efficiency: 15% shorter trajectories vs. MEDWA in dense obstacles.
• Computational load: 5949 iterations for convergence in dynamic environments.

 

Problem Statement 

In this scenario, we adapt the traditional shortest path algorithm, such as Dijkstra’s, to account for obstacles within the graph: 

• Certain edges are damaged. 

• Some nodes are off-limits. 

• The goal is to determine the shortest path while avoiding restricted nodes. 

     

What Makes This Approach Stand Out? 

Many classic shortest path algorithms, like Dijkstra’s, BFS, or DFS, typically ignore obstacles. Our method is different because: 

•      We adapt Dijkstra’s algorithm to steer clear of restricted nodes. 

•      We guarantee that the shortest path is determined while avoiding obstacles. 

•      It has practical uses, such as planning routes in urban areas where roads could be closed. 

  

Research Background 

The idea of shortest path algorithms has been extensively explored. Some well-known algorithms are: 

• Dijkstra’s Algorithm – Determines the shortest route from one starting point to all other points. 

  

• A* Algorithm – Employs heuristics to enhance the search process. 

  

• Floyd-Warshall Algorithm – Calculates the shortest paths for every pair of points. 

However, many of these algorithms operate under the assumption that all edges and nodes are available. Our approach aims to make the problem more realistic by factoring in obstacles. 

A recent study titled "A Modification of Shortest Path Algorithm According to Adjustable Weights Based on Dijkstra Algorithm" (ETJ, 2023) examines how to adapt Dijkstra’s algorithm to accommodate changing weights. This adaptation is beneficial for our project since obstacles can be modeled as edges with very high weights or as nodes that should be avoided.

Java Code Implementation

 Java implementation of the Shortest Path with Obstacles using a modified Dijkstra's algorithm:

 

 Algorithm: Optimized Dijkstra with Restricted Nodes

 

public void simpleDijkstra(int start, int end) {

1.   Create a priority queue for nodes to visit (smallest distance first)

 

    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

    Map<Integer, Integer> distance = new HashMap<>();

    Set<Integer> visited = new HashSet<>();

   

2.   Set all distances to infinity, except the start node

 

    for (int i = 0; i < vertices; i++) {

        distance.put(i, Integer.MAX_VALUE);

    }

    distance.put(start, 0);

    pq.add(new int[]{start, 0});

3. Process each node in the queue

    while (!pq.isEmpty()) {

        int[] current = pq.poll();

        int node = current[0];

        int dist = current[1];

 

4. Skip if already visited or restricted

 

        if (visited.contains(node) || restrictedNodes.contains(node)) {

            continue;

        }

        visited.add(node);

       

5.  If we reach the destination, print result and stop

 

        if (node == end) {

            System.out.println("Shortest Path Distance: " + dist);

            return;

        }

   

 6. Update distances for neighbors

        for (int[] neighbor : adjList.getOrDefault(node, new ArrayList<>())) {

            int nextNode = neighbor[0];

            int weight = neighbor[1];

            if (!visited.contains(nextNode) && !restrictedNodes.contains(nextNode)) {

                int newDist = dist + weight;

                if (newDist < distance.get(nextNode)) {

                    distance.put(nextNode, newDist);

                    pq.add(new int[]{nextNode, newDist});

                }

            }

        }

    }

   

7.  If we can't reach the end node, print message

 

    System.out.println("No valid path found.");

}

}

      

 Figure Representation:

  

Output of the program:

code: https://github.com/vivek4344/Daaise

        

Explanation of the Code

1.  Graph Representation:

o   Uses an adjacency list (HashMap) to store edges and weights.

o   Uses a HashSet to store restricted nodes.

2.  Dijkstra’s Algorithm Modification:

o   Uses a priority queue to select the shortest path.

o   If a node is restricted, it is skipped in the traversal.

o   The algorithm continues until it finds the shortest path or determines no valid path exists.

 

Comparative Analysis

Against Other Methods

1.  A*: Faster but struggles with moving obstacles.

2.  Artificial Potential Fields: Prone to local minima.

3.  MEDWA: Hybrid vector-DWA approach reduces path deviation by 15%.

Limitations

• Scalability: Frequent graph updates increase latency in large graphs (>10,000 nodes).
• Sensor dependency: False positives disrupt path continuity.

  

Applications

1.  Autonomous Vehicles: Rerouting around accidents using real-time traffic data.

2.  Warehouse Robots: Kiva Systems uses similar logic for AGV navigation.

3.  Disaster Response: Dynamic path updates for evacuation routes.

 

Future Directions

1.  Machine Learning: Predict obstacle movements using LSTM networks.

2.  Quantum Optimization: Solve NP-hard constraints with Grover’s algorithm.

3.  GPU Acceleration: NVIDIA’s cuGraph achieves 2B-edge traversal in 0.5s

Conclusion 

The Shortest Path Problem with Obstacles presents a significant twist on traditional shortest path algorithms. By adapting Dijkstra’s algorithm to steer clear of blocked nodes and damaged edges, we enhance its usability in real-life situations. Future improvements could involve AI-based updates and changes to the graph in real-time, further increasing its effectiveness.

Reference

1.  ETJ(2023). A Modification of Shortest Path Algorithm According to Adjustable Weights Based on Dijkstra Algorithm. Engineering and Technology Journal, University of Technology Iraq. Retrieved from https://etj.uotechnology.edu.iq/article_176121_e8b183087d04069243b59d403c34e7a9.pdf

2.   TechScience (2023). Improved Dijkstra Algorithm for Mobile Robot Path Planning and Obstacle Avoidance. CMC-Computers, Materials & Continua. Retrieved from https://www.techscience.com/cmc/v72n3/47552/html.

3.  PMC(2023). Microrobot Path Planning Based on the Multi-Module DWA Method in Crossing Dense Obstacle Scenario. PubMed Central. Retrieved from https://pmc.ncbi.nlm.nih.gov/articles/PMC10302263/.

4.  PMC(2024). Obstacle Avoidance and Path Planning Methods for Autonomous Navigation of Mobile Robot. PubMed Central. Retrieved from https://pmc.ncbi.nlm.nih.gov/articles/PMC11175283/.

 

Visual Representation in video form: