Analysis-of-Search-Algorithms

Conducting and examining Search Algorithms within a basic testing environment:

• Breadth-First Search Algorithm
• Depth-First Search Algorithm
• Iterative Deepening Depth-First Search Algorithm
• Greedy Best-First Search Algorithm
• Astar Search Algorithm

Testing Environment

The warehouse has P parking positions, where each position can accommodate N equally sized boxes. The figure below shows a warehouse with P=4 and N=5. The warehouse is managed by a robotic arm, which can only access the top box at each parking position. The robotic arm recognizes the command: "MOVE p,r", which takes the top box at the p-th position (1 ≤ p ≤ P) and places it on top of the stack at the r-th position (1 ≤ r ≤ P). If the r-th position is empty, the box is placed on the ground. If the p-th position is empty, nothing happens. The operator of the robotic arm is provided with the start and final configurations of the warehouse, and then seeks the shortest sequence of commands that will rearrange the boxes according to the desired pattern.

AnalysisOfSearchAlgorithms.java Structure

class AnalysisOfSearchAlgorithms {
  main {
    // start and final warehouse configuration from /input
    // run search algorithms
    // print stats and path
  }
}

class Tree {
  public String BFS {} // return path
  public String DFS {}
  // + other search algorithms
}

class Node {
  // a node represents one possible warehouse configuration
  // + heuristics
}

class Move {
  // stores last move of the box
}

In-Depth Code Explanation

The program receives two text files as input, representing the start and final configurations of boxes in a warehouse, converts them to a two-dimensional string array, and prints them to the screen.

String[][] start_config = readInput("input/input5_start.txt");
String[][] final_config = readInput("input/input5_final.txt");

The next step is to declare and initialize a tree or a state graph using the Tree class, where each state is represented by a Node class, which represents one of the possible configurations of the warehouse.

Tree tree = new Tree(new Node(null, null, zacetna), new Node(null, null, koncna));

When the new Node constructor is called, in addition to links to the previous box configuration previousNode and the previous box movement previousMove, aar two-dimensional array of the current box configuration boxes and a list of all possible movements from the current configuration allPossibleMoves are also stored. The array is generated using the generateAllPossibleMoves() method.

public Node(Node previousNode, Move previousMove, String[][] boxes) {
  this.previousNode = previousNode;
  this.previousMove = previousMove;
  this.boxes = boxes;
  this.allPossibleMoves = this.generateAllPossibleMoves();
}

Inside the Node class, there is also a method called move(), which takes a Move object as an argument, representing a movement of a box from one column to another. The applyMove() method confirms the movement and returns a new node or a new configuration of the warehouse.

public Node move(Move move) {
  String[][] tmpBoxes = this.copy2dArray(this.boxes);
  this.applyMove(tmpBoxes, move.s, move.d);
  return new Node(this, move, tmpBoxes);
}

The above move() method is applied in search algorithms written within the Tree class as public methods. Five search algorithms have been implemented, which are called in the main() method of the AnalysisOfSearchAlgorithms class as follows. The IDDFS algorithm takes a number as an argument representing the limit or depth of iterative deepening, while GreedyBestFirstSearch and Astar take a number that only allows the choice of a particular heuristic. All algorithms return a path or string of commands generated by the move() method.

tree.BFS(); 
tree.DFS();
tree.IDDFS(100);
tree.GreedyBestFirstSearch(0); 
tree.Astar(0);

Heuristics

Two search algorithms, GreedyBestFirstSearch and Astar are implemented using five different heuristics:

• heuristicBoxesOnRightPosition number of boxes in the correct position
• heuristicMaxXYDistance: maximum distance a box is from its correct position, in terms of X and Y coordinates
• heuristicWrongRows: number of boxes in the wrong row
• heuristicWrongCols: number of boxes in the wrong column
• heuristicSumOfDistances: the sum of the distances a box is from its correct position, in terms of both X and Y coordinates

The heuristics are implemented as methods inside the Node class and are written as functions that take in two arguments: the current warehouse configuration curNode and the final warehouse configuration endNode. Each method calculates the result of a specific function in its own way and returns an integer that represents the heuristic on the edge between the nodes curNode and endNode.

public static int heuristicBoxesOnRightPosition(Node curNode, Node endNode)
public static int heuristicMaxXYDistance(Node curNode, Node endNode)
public static int heuristicWrongRows(Node curNode, Node endNode)
public static int heuristicWrongCols(Node curNode, Node endNode)
public static int heuristicSumOfDistances(Node curNode, Node endNode)

In the code of both algorithms, switch statement is used to select which heuristic to use, with the difference being that in GreedyBestFirstSearch, we only use the heuristic h to select the next node, while in the Astar algorithm, we use the sum of the heuristic h and the cost of the edge g. In our implementation, this is represented by the variable dist, which indicates the number of moves made up to that point.

int h;
switch (heuristic) {
  case 0 -> { h = Node.heuristicBoxesOnRightPosition(nextNode, endNode); }
  case 1 -> { h = Node.heuristicSumOfDistances(nextNode, endNode); }
  case 2 -> { h = Node.heuristicWrongCols(nextNode, endNode); }
  case 3 -> { h = Node.heuristicWrongRows(nextNode, endNode); }
  default -> { h = Node.heuristicMaxXYDistance(nextNode, endNode); }
}
fScore.put(nextNode, dist + h);

Statistics

When running investigative algorithms in the method main, we measure the following properties:

• Execution Time [ms] (endTime - startTime)
• Average Time to Process One Node [ms] (time / visitedNodes)
• Number of All Processed Nodes (visitedNodes)
• All Nodes (Generated + Processed) in Memory (allNodes)
• Maximum Number of Nodes in Memory (maxGeneratedNodes)
• Depth of Solution (depthOfSolution)

After each algorithm execution, the counters for the properties need to be reset with the method resetCounters().

public static void executeAlgorithm(Tree tree, int i, String algorithm) {
  String path = "";
  long startTime = System.currentTimeMillis();
  switch (i) {
    case 0 -> path = tree.BFS();
    // ...
  }
  long endTime = System.currentTimeMillis();
  printStats(algorithm, (endTime - startTime), tree.allNodes, 
  tree.depthOfSolution,  tree.visitedNodes, tree.maxGeneratedNodes, path);
  tree.resetCounters();
}

The above properties, except for Execution Time and Average Time to process one node, which are calculated, are directly measured during the execution of the algorithm. In fact, these are attributes of the Tree class.

class Tree {
  int allNodes = 0;
  int visitedNodes = 0;
  int maxGeneratedNodes = 0;
  int depthOfSolution = 0;
  // ...
}

Results

Testing of search algorithms is conducted on input/input5_start.txt and input/input5_final.txt, as they cover a significantly larger state space, which allows the algorithm properties to be best observed.

Search Algorithm	runT	avgT	allN	maxN	visN	depth
BFS	2046	0.02059	132617	53505	99362	8
DFS	864	0.13329	129579	123168	6482	123096
IDDFS(100)	1639	0.08155	45694	19	20098	17
GreedyBestFirstSearch(Boxes-On-Right-Position)	6	0.06061	603	505	99	24
GreedyBestFirstSearch(Sum-Of-X-Y-Distance)	38	0.09819	2063	1677	387	46
GreedyBestFirstSearch(Wrong-Cols)	9	0.07258	1088	965	124	19
GreedyBestFirstSearch(Wrong-Rows)	3	0.03797	507	429	79	16
GreedyyBestFirstSearch(Max-X-Y-Distance)	5	0.03817	735	605	131	36
A*(Boxes-On-Right-Position)	75	0.16854	2401	1957	445	8
A*(Sum-Of-X-Y-Distance)	882	0.63317	6067	4675	1393	21
A*(Wrong-Cols)	14792	3.13789	17689	12976	4714	10
A*(Wrong-Rows)	23152	3.89306	21497	15551	5947	9
A*(Max-X-Y-Distance)	81	0.125	2970	2323	648	15

Findings

Based on the obtained results, I compared the search algorithms with already known properties assigned to a certain algorithm.

BFS (Breadth First Search) algorithm returned the shortest path among all the algorithms, which is trivial since it works on the principle of queue, therefore it generated and processed the most nodes. From that fact, I can conclude that it consumes the most resources (memory).

DFS (Depth First Search) algorithm is faster and less wasteful compared to the previous algorithm. Due to the depth-first traversal, it has to generate more nodes. For the same reason, the path is longer, and the depth is greater.

IDDFS (Iterative Deepening Depth First Search) algorithm combines the advantages of the two above two algorithms, which is evident in its speed and lower resource consumption.

Greedy Best First Search is the algorithm that performed the fastest in our research using the Wrong-Rows heuristic, it returned a fairly good solution in only 3ms. In all five cases, the effectiveness of the algorithm is nicely visible, which achieved the lowest number of processed nodes.

Astar Search Algorithm is the algorithm that should surpass all the algorithms in the battle with time. In this case, this did not happened, only the Max-X-Y-Distance heuristic bearly held with the best times. It also proved to be the most effective heuristic, because it significantly outperformed the other four and three heuristics in the previous algorithm. The weakness of the algorithm is evident in the consumption of resources, which is higher than the above Greedy Best First Search algorithm. We can console ourselves with the returned paths, which are the shortest of all.