Structure and Strategies for State Space Search AI

1
137

Historically many people link intelligence with the capability to solve a problem. Problem-solving is one of the factors that demonstrate intelligence. The classical approach that is used is “hit and trial” that check for various solutions to that problem. We use this approach to solve small problems.

For example:

Consider the maze searching problem. The mouse travels through one path and finds that the path leads to a dead-end, it then backtracks somewhat and goes along some other path and again finds that there is no way to proceed. It goes on performing such search, trying different paths to solve the problem until a sequence of turns in the maze takes it to the cheese. Hence, from all the solutions the mouse tries, the one that reached the cheese was the one that solved the problem.

Another Example:

Consider that a toddler is to switch on the light in a dark room. He sees the switchboard having a number of buttons on it. He presses one, nothing happens, he presses the second one, the fan gets on, he goes on trying different buttons till at last the room gets lighted and his problem gets solved.

Generate and Test:

We call this “hit and trial” approach the “Generate and Test” approach. We generate different combinations to solve our problem, and the one which solves the problem is taken as the correct solution. The rest of the combinations that we try are considered as incorrect solutions and hence are destroyed.

 

Also Read: What is Artificial Intelligence?

Problem Representation:

For a simple problem or smaller problem, we can use a hit and trial approach to solve the problem. However when the problem is complex then we need a systematic way to solve the problem. The key to solving a complex problem is its representation. Normally the problems are represented in the form of a diagram (such as graphs or trees).

For example:

It shows the problem of switching on the light by a child in a graphical form. Each rectangle represents the state of the switchboard. OFF | OFF| OFF means that all the three switches are OFF. Similarly OFF| ON | OFF means that the first and the last switch is OFF and the middle one is ON. Starting from the state when all the switches are OFF the child can proceed in any of the three ways by switching either one of the switches ON.

This brings the child to the next level in the tree. Now from here, he can explore the other options, till he gets to a state where the switch corresponding to the light is ON. Hence our problem was reduced to finding a node in the tree which ON is the place corresponding to the light switch.

Components of Problem Solving:

  • Problem Statement
  • Goal State
  • Solution Space
  • Operators

First of all it must ensure that the given problem is guaranteed to be solve and it is guaranteed to solve with an infinite amount of time. In addition to time complexity, it should be noted that all the resources are available and in order to understand and find the solution all rules must be known.

Problem Solution/ Goal State: It means what is required as an output or what would be considered as the correct solution to the given problem. For example, in the mouse maze problem, the solution state is mouse reached the cheese.

Solution Space: Different states while following a strategy to reach goal state from start state is known as solution space.

For example

When the mouse was in the lower-left corner of the maze, it represents a state i.e. the start state. When it was stuck in some corner of the maze represents a state. When it was stuck somewhere else represents another state. When it was traveling on a path represents some other state and finally when it reaches the cheese represents a state called the goal state. The set of the start state, the goal state, and all the intermediate states constitute something which is called a solution space.

Operator:

The traveling inside a solution space requires something called “operators”. In the case of the mouse example, turn left, turn right, go straight are the operators which help us travel inside the solution space.

The Two-One Problem

The above game can be better represented as a tree to find possible solutions. A tree sort of structure enumerates all the possible states and moves. Looking at this diagram we can easily figure out the solution to our problem. This tree-like structure actually represents the “Solution Space” of this problem.

Tree and Graphs Terminology:  

 A graph is a set of nodes and arc/edges that connect them. A graph is said to be directed its arcs contain directionality using arrows. If arcs do not contain arrow then this graph is known as the undirected graph.

 

Undirected Graph Directed Graph
 

 

A tree is a graph in which two nodes have at most one path between them. Trees often have roots, in which case they are usually drawn with the root at the top, like a rooted graph. Because each node in the tree has only one of access from any other node, it is impossible for a path to loop or cycle continuously through a sequence of nodes.

Also Read: What are Agent and Environment in AI?

The Tick-Tac-Toe Game:

 The state-space graph for games is usually rooted in graphs with the start of the game as root.  For example, the tic-tac-toe game graph is represented by the rooted graph. The player cannot undo so the tree is a better choice as it does not allow cycle.

The start state is an empty board, and the termination or goal description is a board state having three Xs in a row, column or diagonal (Assuming that the goal is a win for X). The path from the start state to goal state gives the series of moves in a winning game.

9! Different paths can be generated in tic-tac-toe.

Tree Representation of 8-Puzzle Game:

The Traveling Salesperson:

Suppose a salesperson has five cities to visit and then must return home. The goal of the problem is to find the shortest path for the salesperson to travel, visiting each city, and they returning to the starting city.

Searching:

 All the problems that we have looked at can be converted to a form where we have to start from a start state and search for a goal state by traveling through a solution space. Searching is a formal mechanism to explore alternatives.

Most of the solution spaces for problems can be represented in a graph where nodes represent different states and edges represent the operator which takes us from one state to the other. If we can get our grips on algorithms that deal with searching techniques in graphs and trees, we’ll be all set to perform problem-solving in an efficient manner.

Search Strategies:

  • Blind/uninformed,
  • Informed/heuristic,
  • Any path/non-optimal
  • Optimal path search algorithms

Blind or Uninformed Search: Without knowing how far the goal is and totally blind to the search space. Just doing “hit and trial” to achieve the goal.

Informed/ heuristic: Search that takes place on the basis of some hints/ heuristics.

In any-path/non-optimal searches we are concerned with finding any one solution to our problem. As soon as we find a solution, we stop, without thinking that there might be a better way to solve the problem which might take a lesser time or fewer operators. In optimal path searches, we try to find the best solution. Hence in optimal searches, we find solutions that are least costly, where the cost of the solution may be different for each problem.

Also Read: What is Security Information and Event Management (SIEM) Tool? A Beginner’s Guide

Simple Back Tracking Searching Algorithm:

In solving a problem either data-driven or goal-driven, a problem solver must find a path from a start state to a goal through the state space graph. Backtracking is a technique for systematically trying all paths through state space.

 SL: for the state list, lists the states in the current path being tried If a goal is found, SL contains the ordered list of states on the solution path.

NSL: for new state list, contains nodes awaiting evaluation, i.e., nodes whose descendants have not yet been generated and searched.

DE: for Dead end, list states whose descendants have failed to contain a goal node. If these states encountered again, they will be detected as an element of DE and eliminated from the consideration list.

CS: Current State.

To avoid loop, each newly generated state will be checked with these three lists, If new state belongs to any of these lists, then it has already been visited and may be ignored.