So far on this blog, we’ve spoken about and established what AI is and outlined a simple AI framework that we can develop further in the article titled “What is AI?” and we’ve also spoken about a specific type of problem that we could face in the real world which was an optimisation problem; we spoke about the kinds of search we can do based on both the type of search problem that we’re dealing with and the information that we have to hand to help us solve the problem.

We took the framework from the first post and saw how that could be used to implement a constructive depth-first and breadth-first search by making a small adjustment to just one bit of code in the post titled “Depth vs Breadth First Search” and saw the difference between constructive and perturbative methods of search where the information on what needs to happen next is either coming out of a queue (breadth-first) or off of a stack (depth-first) and what each type does to the quality of the solution.

How could we improve on this on what we already know?

Depth and Breadth first are both “blind” or “uninformed” searches and form a structure that form the shape of a tree. One way to improve our solution would be to add another variable to our Candidate Solution that told us how far we are away from the start at each node. The idea is to look for any information we can use whilst minimizing the constraints to get a better-quality solution.

We’ve established in previous posts that there are three types of search problems which are optimisation, modelling and predicting and each of these will have different kinds of qualities or properties that can be assigned to them and often, more than one can be assigned hence we say “heuristic” (rule of thumb) values. When simulations run at different fidelities (for instance different sized focus groups in a user study) it will inevitably take more effort to calculate.

Estimated quality measures

For other problems we can define a “heuristic evaluation function” for each node n – h(n). Doing so provides information to guide and inform our search as well as estimate how far a node is from the goal state i.e. by comparing two nodes h(m) < h(n) we can see that m is closer to the goal. This kind of quality score could be thought of as a “cost” function which would need to be minimised, whereas quality function (fitness, score etc) would look to be maximized.

Discussing the “openList” in our program

The previous framework that we have discussed up to this point does not have any information about how our system selects each node as it tests its way through the data we’ve only kept track of solutions that weren’t correct (stuff we did in the past) whereas when we talk about our open or todo list we’re looking at what we’re going to do in the future and how we deal with the openList will determine how we operate or move within our “space”; these are the steps we take as we travel through the data, generating and testing our potential solutions and mapping out our progress as we go.

Once a candidate solution has been generated and subsequently tested and the result commited to memory, that information can be used to inform future searches because the openList determines our next course of action in our digital landscape (the next node we’re going to try out). We’ve already discussed how using this list as a stack would achieve a depth-first (highly uninformed) search whereas if we turn the stack into a queue we achieve a more optimal and complete solution which we call breadth-first search.

We can turn a “blind” search into an informed search by adding this new measure of quality and assessing these values before generating a new candidate solution by adding an evaluate function into our loop which is simply a line that sorts the openList that we’re using to consider each potential solution.

Pseudocode for informed search

Variables workingCandidate, openList, closedList
SET workingCandidate = StartSolution
Evaluate (workingCandidate)
SET goalReached = CheckIfAtGoal(workingCandidate)
	WHILE (! goalReached AND Openlist not empty) DO
		// These lines generate new candidates
		Foreach (1-step neighbor)
			neighbour = ApplyMoveOperator(workingCandidate)
			// This line tests the solution
			Evaluate(neighbor)
			// These lines update working memory
			IF (neighbor is feasible) // We can go there
				ADD( neighbor to end of openList)
			ELSE // If we're at a dead end
				ADD( neighbor to end of closedList)
			COPY (working candidate to closedList)
			SORT(OpenList)
			// End update working memory
			MOVE (first item from openList to working candidate)
			SET goalReached = CheckIfAtGoal(workingCandidate)
	OD //End loop
OUTPUT (goalReached, workingCandidate)

The difference between this method and the previously discussed “basic AI framework” methods is that for each itteration of each candidate solution we’re informing ourselves of our surroundings (known qualities of our neighbours are monitored as we move and evaluated in each instance to help us decide whether we’re interested in them or not) and storing relevant information along the way to help guide our search. We’re then, before generating a new candidate to test, simply sorting the openList (deciding on or changing our next move) before proceeding.

Informed search + hill climbing

Hill climbing is our first of the more complex AI algorithms and works by sorting the openlist either by decreasing quality or by increasing distance to goal and doesn’t allow back-tracking but rather discards everything but the top node after sorting. The best parctice method is to examine child-nodes then move to one with better heuristic value if exists or if that’s not possible then stop (even if we’ve not reached the goal). A greedy/steepest ascent variant of this would be where where all child nodes are examined and then the path of first / best improvement is taken. This method is quick but can get stuck in local optima.

Pseudocode for “best-first” search and “hill climbing” algorithms

Variables workingCandidate, openList, closedList
SET workingCandidate = StartSolution
Evaluate (workingCandidate)
SET goalReached = CheckIfAtGoal(workingCandidate)
	WHILE (! goalReached AND Openlist not empty) DO
		// These lines generate new candidates
		Foreach (1-step neighbor)
			neighbour = ApplyMoveOperator(workingCandidate)
			// This line tests the solution
			Evaluate(neighbor)
			// These lines update working memory
			IF (neighbor is feasible) // We can go there
				ADD( neighbor to end of openList)
			ELSE // If we're at a dead end
				ADD( neighbor to end of closedList)
			SORT(OpenList by increasing distance to goal)

			// Added for "hill climbing" method
			DELETE(all but first item in openlist)
			// End "hill climbing" code

			MOVE (first item from openList to working candidate)
			SET goalReached = CheckIfAtGoal(workingCandidate)
	OD //End loop
OUTPUT (goalReached, workingCandidate)

In this hill climbing example, the only difference to this and the “informed search” pseudocode is, at the end of our loop, before performing the calculation on the next candidate solution, we’re firstly sorting the openlist by increasing distance to goal (getting the next, closest value to the start) and then, if we’re “hill climbing”, deleting everything but the first value off this list or if we’re “best-first”ing, we keep unused nodes in the openList.

When considering the best-first method; at every iteration, the whole openList queue is sorted by quality (decreasing – giving the next candidate with the highest quality) instead of just sorting the children of current node which means it doesn’t remove unexplored nodes. This gives us an informed search that allows for backtracking and tends to produce shorter paths than depth or breadth first search.

That concludes this post where we have taken our basic AI working framework and adapted it from a “blind” search to perform a more “informed” search using “heuristic” properties of our data, adding a dimension of quality to our process and informing our future decisions with this added dimension.

Reference: Information for this post was collected from lecture notes of a lecture written by Jim Smith who is a Professor in Interactive Artificial Intelligence (AI) in the Department of Computer Science and Creative Technologies at the University of the West of England.

Leave a Comment

Your email address will not be published. Required fields are marked *