Pirates On Mars

This is a path finding application that covers three path finding and optimization problems. Imagine you and your friends are on a rover on Mars. You could be faced with all kinds of unprecedented problems like water bodies, frozen regions, volcanos, mountains, food shortage, low fuel, and what not! We have modelled this application, keeping in mind such scenarios. The application allows you to choose the locations of the source and destination, set obstacles on Mars, and define difficult environments as weighted nodes for every problem. Before we understand the remaining features and functionalities, let's look at the three aforementioned problems:

1. Find the shortest path from source to destination. You can define the state of the space using various features, choose an algorithm from the panel, set the visualization speed, select weights of all the weighted nodes, and click visualize to see the pathfinder build the path.

2. Traveling Salesman - Define intermediate stations and find the least cost path that starts from source, covers all intermediate points stations, reaches destination at some point and returns to the source.

3. Path optimization with a maximum cost constraint - Suppose your rover is on a mission. Every intermediate station is a food refilling station. But alas, your rover has a limited amount of fuel, and you must reach the destination before you run out. The Multiple Stops algorithm tries to optimize at every point, so that with the available fuel, you can reach your destination, while visiting as many stations as you can, on your way there. The default maximum value of the cost that can be incurred on the journey is set to 100. You can change it by entering the value in the Maximum Cost input box.

Algorithm Division:

• Shortest Path Between 2 Nodes:

  1. ID Depth First Search
  2. Best First Search
  3. AStar
  4. IDAStar
  5. Dijkstra

• Traveling Salesman:

  1. Traveling Salesman (branch and bound)

• Path Optimization with Multiple Nodes and a Maximum Cost:

  1. Multiple Stops (f-score optimization like AStar) : The algorithm finds all distances between the involved nodes (Start, End and Station Nodes). It uses these distances to populate an adjacency matrix. The optimization method used is similar to A*, wherein for every station node that is being considered, we calculate a g value, heuristic and take their weighted sum as the f-score. We start by assuming that only the start node and end node are present in the current route. To find the best node to be visited on the path from start to end, we store the distances of all station nodes from the start as their respective g values, and the distances to the end nodes as their respective heuristic values. The F-Score is then the weighted sum of 'g' and 'h'. We then select the station node with the minimum F-Score to be included in the route from start to end. The next step is to assume that our route is Start -> Station Node 1(previously included) -> End . We now look for a station node which can be inserted in between station node 1 and the end node. For this, we calculate the F-Scores of the remaining station nodes as weighted sum of g & h wherein
     

        g = dist(start -> station node1) + dist(station node1 -> current station node) 
        h = dist(current station node -> End Node)

The algorithm then finds the station node with the least F-Score to include in the path which would then be Start -> Station Node 1 -> Station Node 2 -> End . Then, it finds the best position to insert this node in the existing array. For instance, Start -> Station Node 1 -> Station Node 2 -> End may become Start -> Station Node 2 -> Station Node 1 -> End if that is shorter. This is repeated until all eligible station nodes are included in the path such that the total cost of traversal is less than the maximum cost given by the user. The nodes will be visited in the order described by the algorithm. One can get an intuition by imagining that the station nodes are included in the increasing order of their distance from the line connecting the Start Node and End Node.

The last two algorithms may be used for the first case too.

Using The Web Interface:

The navigation panel contains various radio buttons to set different nodes :

• Start Node (source - green) - To change the location of the starting point.

• End Node (destination - red) - To change the location of the end point.

• Wall Node (obstacles - black) - To set obstacles in the space. These are essentially nodes with their weights set to Infinity

• Weight Node (difficult regions to traverse - yellow) - To set regions in the space that are difficult to traverse, i.e., would cost more. The Weight dropdown allows you to set the weight values of these nodes.

• Station Node (intermediate points for problems 2 and 3 - blue) - To set intermediate points, you must first check the Allow Stations checkbox. This would enable the Station Node button. These are taken into consideration only in the Traveling Salesman and Multiple Stops algorithms. Note: As long as there are Station Nodes on the grid, you can only run the two algos listed above.

• Random Grid - To randomly add Walls in space.

• Dropdowns - Speed to select the speed of visualization for problem 1, Weight to set weight value of the Weight nodes.

• Checkboxes - Show Unweighted to display the unweighted algorithm, i.e., Breadth First Search in the Algorithm Panel on the right, Allow Stations to enable the Station Node radio button.

• Maximum Cost - To input a value for the Maximum Cost used in the Multiple Stops algorithm. Should you choose to set no value, a default of 100 is considered as the maximum cost.

• Reset Graph - To clear the traversals and path of the previous visualization.

• Clear Graph - To clear the Grid and set the Start and End nodes to default positions.

• Tutorial - i - A basic tutorial to using the web application.

• Algorithm Panel - Contains the algorithms listed above. Allow Diagonal will enable diagonal traversal, Dont Cross Corners will prevent the path from crossing the corners of Wall Nodes, Bi-Directional allows the algorithm start searching from the start and end simultaneously and Heuristic allows you to choose a heuristic function for algorithms that have the feature.

• Used Paper.js to build the Grid and for visualizations.

Code Organization:

---- index.html     
---- assets     
         ---- DiagonalOptions.js        
         ---- EnableDisableStations.js      
         ---- block_generators.js       
         ---- draggable.js      
         ---- logo.png      
         ---- utilities.js      
---- finders        
         ---- AStar.js      
         ---- BiAStar.js        
         ---- BiBreadthFirstSearch.js       
         ---- BranchAndBound.js     
         ---- BreadthFirstSearch.js     
         ---- IDAStar.js        
         ---- IDDepthFirstSearch.js     
         ---- MultipleStops.js      
         ---- TravelingSalesman.js      
---- src        
         ---- App.js        
         ---- DataStructures.js     
         ---- Graph.js      
         ---- Grid.js       
         ---- Heuristic.js      
         ---- Node.js       
         ---- Path.js       
         ---- Runner.js     
         ---- States.js     
---- style      
         ---- css       
                 ---- main.css      
         ---- scss      
                 ---- main.scss