A Look Into Modified A* Algorithm

 Introduction

This article will give you an insight into some of the most basic graph based AI algorithms building up to further explain the modified A*(A star) algorithm which we are going to use in the subsequent post to solve a simple * Puzzle problem. 

Prerequisite: Breadth first search, queue, priority queue

Best First Search Algorithm

First let us look at one of the most basic and generalized algorithm that we can use to search a value in our graph, Best First Search Algorithm.

It is a simple search algorithm that uses a specific set of rules(cost functions) to select the most promising node among the immediate children of a parent node, it is often seen as akin to a Breadth First Search (BFS) but using a Priority queue instead of normal queue, i.e. FIFO queue.

Here in normal BFS when we iterate through the children nodes we would normally go in whatever order we scanned the children node, i.e C1, C2, C3 if we just read from left to right, whereas in Best First Search, we would use some cost function f(x), to evaluate f(C1). f(C2), f(C3), and search the nodes in ascending order of those values.

 The above diagram explains the main difference between a BFS and Best First Search, in BFS we would have directly put C1, C2, C3 into the FIFO queue, but for Best First Search we would put the child nodes into a priority queue, with their cost functions as the priority number, thus when we later get the nodes from the queue we search them in ascending order of cost.

Normal A* Algorithm

Now since that's out  of the way let us look into one of it's versions, the A* Algorithm. The normal A* Algorithm(or A* Algorithm) is a Best First Search algorithm that uses a specific cost function:

f(x) = h(x) + g(x)

where,

x - signifies a node

f(x) - the cost function

h(x) - the heuristic function

g(x) - the path cost from the starting node to node 'x'

The heuristic function is generally an approximation of cost as seen by the developer/designer from the node to the goal state. Generally a lot research and testing is done to find an appropriate heuristic function, as it tends to vastly effect the performance of the algorithm.

Modified A* Algorithm

A modification we do here is the adding of a depth component to the search as well. This moves the algorithm away from a pure BFS variant to an algorithm that searches the graph up to a certain limited depth before choosing the node with least cost, among all the nodes up to the searched depth.
 

In this graph assuming Node P to be the starting node, a depth of: 1 will act like normal A* Algorithm choosing the least cost node from among: C1,C2,C3. Whereas for depth of 2 will choose the node with least cost among C1,C2...,C8.
 

The above diagram explains the general impact of depth in the modified A* algorithm in terms of the search flow, this is done in an attempt to give the algorithm a certain amount of "foresight" as opposed to doing a shallow check of only one layer.

What's Next?

In the next post we will delving into the implementation of the modified A* algorithm to solve an 8Puzzle problem. See you there!





Popular posts from this blog

Red-Black Tree - Understanding and Implementation.

Image
 Introduction In this article we will attempt to do the following: Gain an understanding on what a Red-Black Tree is, Get an idea on why we take the effort to reorder and recolor the RB-Tree every time we insert or remove a node, further, we will look into the algorithm for a RB-Tree insertion and removal, along with code implementation for the same in Java. Prerequisites: Java, Binary-Search Tree, Tree rotations. What is a Red-Black Tree? A Red-Black Tree (RB-Tree) is a self balancing Binary-Search Tree(BS-Tree), that follows a certain algorithm while inserting and removing nodes from the tree. This is done to guarantee an O(log n) search time(where n is the number of nodes in the tree), for every element. Further along with the usual variables, the nodes of a RB Tree has a bit(or any representation) that signify it as a red or black node. These colors will add a certain order to the nodes(we will get back to this) and is necessary for the algorithm. The main properties of a RB T...
Read more