I. INTRODUCTIONII. Related WorkA. A* AlgorithmB. SMA* AlgorithmC. Frontier Search A* AlgorithmIII. Thesis and ExpectationsIV. Platform and MethodologyA. PlatformB. MethodologyV. ResultsVI. Remaining WorkVII. REFERENCESComparison of Frontier Search with SMA*: OZDEMIR, Tayfun Abstract – A* is one of the most commonly used search algorithms in Artificial Intelligence. The biggest problem with A* is that its memory requirements may grow exponentially. Simplified Memory Bounded A* (SMA*) and Frontier Search A* are two different memory efficient search algorithms based on A*. In this paper, memory and space efficiency of Frontier Search A* will be compared to SMA*.Index Terms— A*, SMA*, Frontier Search A*I. INTRODUCTIONArtificial Intelligence is commonly used in many real-world applications including but not limited to autonomous planning and scheduling, game playing, autonomous control, diagnosis, logistics planning, robotics, natural language understanding, and problem solving. Search is commonly used in Artificial Intelligence applications designed to find solutions to the real world applications listed above. One of the most commonly used search algorithms in Artificial Intelligence is A*. The potential growth of memory required is A*'s biggest problem [3]. There have been several algorithms developed to overcome the memory need of A*. Two of them are the Simplified Memory Bounded A* (SMA*) [2] and the Frontier Search A* [1]. SMA* and Frontier Search A* use different approaches to solve the memory needs of A*. SMA* tries to reduce the memory needs by avoiding unlikely paths. In addition to that, SMA* deletes the most expensive nodes from memory. It re-expands the deleted node if it ever becomes the cheapest node. Frontier Search A*, on the other hand, tries to use a divide and conquer method to reduce the memory needs.Original intention of this paper was to conduct an empirical study on the memory requirements and the execution time efficiency of SMA* and Frontier Search A*. I was planning to implement Comparison of Frontier Search with SMA* T.Ozdemir is a MS candidate in Computer Science at California State University, Chico, CA 95929-0410 USA (e-mail: [email protected])1Comparison of Frontier Search with SMA*: OZDEMIR, Tayfunthe both algorithms and run them on the same set of problems for comparison. Due to health and time restrictions this empirical study became impossible. Instead, in this paper, I will do a theoretical comparison between SMA* and Frontier Search A*. I will also explain my proposed methodology and testing environment as a reference to future work.II.RELATED WORKA. A* AlgorithmA* is an informed search algorithm developed by Hart in 1968 [6]. An informed search algorithm is a type of algorithm which has an estimation about the distance of the current node from the goal node. A* is a form of best first search algorithm, it keeps progressing by expanding the best (cheapest) cost nodes first. A* algorithm uses two lists. The first list is called the Closed list. The nodes which are already expanded are stored in the Closed list. The second list is called the Open list. Nodes which are not expanded yet are stored in the Open list. A* algorithm starts by putting the initial node into the Open list. It then starts expanding the nodes in the Open list. It puts generated nodes into the Open list and it moves expanded nodes to the Closed list. It results in a failure when there are no more nodes to expand in the Open list or when there is no more available memory. It results in a success when the goal node is expanded. It decides which nodes to expand by calculating the value of f(n) = g(n) + h(n), where g(n) is the actual cost to reach this node from the initial node, and h(n) is the expected cost to reach the goal from this node. The h function is also called the heuristic function. In addition to that, A* algorithm uses a hash table to avoid going over the same state more than once. The pseudocode for A* is given in Fig. 1 which has the same logic as the one described by Hart. However it is improved for readability.2Comparison of Frontier Search with SMA*: OZDEMIR, Tayfun Fig. 1. Pseudocode for A* algorithm from [6].In the original paper written in 1968, Hart stated that A* was optimal for a graph search as long as the heuristic function was admissible. An admissible heuristic function will never overestimate the cost to reach the goal node from the current node. In 1972, Hart sent a letter correcting a problem in his paper. In his letter, he corrected that A* was optimal for graph search only if the heuristic function was admissible and consistent. A consistent heuristic function will always estimate the cost of reaching the goal node from the parent node less than the estimated cost of reaching the goal from the child node plus the real cost of going to child node from the parent node. In other words, a consistent heuristic function should always satisfy h(n) <= c(n, a, n') + h(n') rule, in which n is a parent node, n' is a child node, a is the action to go to the child node from the parent node, h is a heuristic function, and c is a cost function [6, 7].B. SMA* AlgorithmSMA* is an algorithm developed by Russell in 1992 [3]. It is very similar to Memory Bonded A* (MA*) which was developed by Chakrabarti in 1989 [5]. Both SMA* and MA* are based on A*. They try to reduce the memory needs of A*. SMA* works just like A* until it runs out of 3Algorithm A*(initial):put initial on OPEN; initialize CLOSED as empty list;loopif empty (OPEN) return with failure;best = best f cost leaf in OPEN;if goal (best) then return with success;successor = next successor (best);insert successor on OPEN;insert best on CLOSED;Comparison of Frontier Search with SMA*: OZDEMIR, Tayfunmemory. When it runs out of memory it starts deleting the nodes with the highest f(n) value and with the highest level (the most distant). This is done to provide memory space for the new node. SMA* implements the Open list as a list of binary trees in a binary tree. The first level of the binary tree holds the f(n) values of the nodes. In the second level of the binary tree the depth of the nodes are kept. This implementation reduces the amount of the time required to find the node to expand as well as the node to delete. SMA* updates the parent of a node with the node's f(n) value. When it deletes a node it