For my first post on the subject, using information from lectures at UWE, I’m going to attempt to define the concept and working processeses of AI in general and then outline a simple working framework whose behaviour can be “tweaked” slightly (in each case) to implement any of the other, more advanced AI algorithms that will be discussed further in future posts on this blog.

AI is a way of solving problems and as such can be thought of as a way of searching through data to find the best solution in the shortest time (most efficient / economical / cost effective way) possible. When it comes to problem solving or indeed search, there are three main areas of operation: optimisation, modelling and prediction.

Optimisation: Given a model finds the inputs so that the output is minimized/maximized.

Modelling: Given specific input / output pairs find the model which maps as many of the inputs as possible to the appropriate output.

Prediction: Finds the output of a system which occurs when a given input is applied to the model.

The process of finding something is in all three of these areas of problem solving and the only thing that differs in each type are the set of alternatives that are considered.

The process of describing a problem as search

1. Work out what variables are needed to define any possible solution
   • Moves or actions, set of design variables, rules, weights etc.
   • How many decisions are needed to specify a solution?
   • Define a type of “Candidate Solution” that contains those variables.
2. Decide if all solutions have the same complexity or not
   • For example, in a game where you can shoot one ball or multiple balls at the same time.
   • Decide on each individual candidate solution with specific variable values.
3. Define operators to move between candidate solutions
   • Perturbative search has the same complexity and changes some values
   • Constructive search has differing complexity and adds or removes values

The representation and move operator is what defines the search landscape (decides where our hills are).

If we’ve written code to change the solutions then we will know which are neighbors to each other; at 1 step, 2 steps, … n steps etc. Knowing this defines a neighborhood structure and turns our list of possible solutions into a landscape; now containing an added dimension which can be thought of as the “quality of solution” (a z axis value for our (x,y) values). This new dimension turns our landscape into something that resembles an ordinance survey map; containing both global and local optima (hills or gradients on the map etc). We can also use this new “quality” value to inform any successive searches that are made to get to the solution quicker if we so wish but we will discuss this concept in future posts.

The adaptive landscape metaphor

Our minds are so accustom to living on the surface of the earth so this is a really useful metaphor first coined by Sewall-Wright, in 1932 and now used intensively in theoretical studies of search.

Take all of the solutions characterized by n variables and add a new dimension of quality which can be embedded in a n+1-dimensional space which can also be though of as the “landscape”. A point on this landscape is a potential solution and our aim is to find the point with the highest value (the biggest hill on the map – or at least one that is big enough). Thus search is a path through space.

Continuous Search Spaces

The variables that define our candidate solutions are real numbers (double or floats) and the number of solutions are only limited by the precision of our coding and can often have mathematical techniques (like integration or differentiation) applied to them. In our landscape we get a sense of space (distance) between solutions which allows us to begin talking about local and global optima.

Combinatorial Search Spaces

Some defining characteristics of our variables used in our candidate solutions are as follows:

• They are binary / Boolean
• Categorical labels
• Ordinal variables i.e. integers or permutations
• A finite (countable) number of solutions

Sometimes the problem definition will tell us how they can be connected but other times not which means we need a different kind of method, especially considering we’re looking to achieve the “best” solution.

Generating our candidate solutions (defining our move operators) in varying ways will create varying landscapes; changing how we move within the space. A good example of this would be how each piece on a chess board moves in different ways. Our solution needs to be the best solution, made in the quickest time ensuring nothing in the data is missed.

A common AI framework

Below is a common framework for our AI code that we can use to find solutions (paths) in search landscapes that we create. This framework can be adapted to implement the various search algorithms and is as follows:

Set WorkingMemory = Empty
CandidateSolution = Generate(Node)
Result = Test(CandidateSolution)
UpdateWorkingMemory(Result)
While (goal_not_found AND possibilities_left) DO
      CandidateSolution = Generate(Node)
      Result = Test(CandidateSolution)
      UpdateWorkingMemory(Result)
OD // End while loop.
Return // Success or failure as appropriate.

This is the common framework for all AI algorithms and can be developed further to achieve all kinds of solutions, in all kinds of different ways. To get a better understanding of the working process of this algorithm read the post titled “Exploring the Basic AI Framework in More Detail“.

To summarise this post: if we want to get a computer to solve a problem for us we need to define a set of variables relating to the problem for the computer to consider. We then assign a value to each variable which in turn generates our candidate solution which is then tested. We then apply move operators to past solutions.

During the generation process, if some variables can be left undefined or are added during generation then we have a constructive search, but If we must specify each value during generation, we have a perturbative search.

Problem solving for a computer can be likened to if a human were to search a landscape on foot. It does this by generating and testing (and keeping track of) each of our candidate solutions and identifying the best (optimal) path for us to take to our goal. The search methods that make up the AI framework do nothing more than manage ordered lists and the solutions to our problems are simply nodes in a vast network of information; each node holding following properties: the depth, the cost of reaching it and some form of measure of quality. The structure of this network of nodes (and how we move between them) is defined by our move operators. Some problems come with a natural measure of quality whereas sometimes we aren’t given that information at all (in the case of cracking a password or a lock for example).

In the next post we are going to look at the different types of AI searches.

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.