Artificial Intelligence aims at making such systems which are capable of solving various problems on its own. AI Problem solving is a process where an AI agent tries to reach a goal with an intention to find the solution to a certain problem.
When a new problem is solved by the AI process, the AI agent maps the problem States into action. If the problem is too large and cannot be mapped directly by the agent, then the agent splits the problem domain into sub problems. It now solves the sub problems separately and then it clubs the results so obtained in order to get to the solution for the whole problem.
Based on the type of problem, different agents employ different techniques like trees, heuristics, b-trees etc. to reach to the solution of the problem. Such agents are also referred to as problem solving agents.
Problem solving agents are goal based agents which work with an aim to reach the goal with an apt solution for the problem.
Examples of problems in AI
AI is being used widely in order to reduce the time and effort required to solve the problems and increase the efficiency in the applied area. AI has been applied in the following areas efficiently:
- Gaming
- Chess
- Sudoku
- Logical Puzzle Solving
- Boolean Formulas
- N Queens Problem
- Real World Problems
- Travelling Salesman Problem (or touring problem, here the objective is to find the shortest distance possible from a starting point to a destination.)
- VLSI Layout Problem (related to
the positioning of various components and connections on the chip so as to
maximize the manufacturing yield and minimize the costs related to area,
circuit delays etc.)
- Cell Layout
- Channel Routing
- Protein Design (the objective here is to find a sequence of amino acids which fold into 3D proteins which help in curing some diseases.)
- Tower of Hanoi
- Water Jug Problem
AI Problem Solving – The Steps Involved
Solving any kind of problem requires certain systematic steps to be followed. Similar is the case with solving problems by AI agents. Have a look at the flowchart below. This flowchart shows the basic steps which are followed by any of the AI agents in order to solve any problem in an AI environment.
Let us now discuss the above steps taken in order to solve a problem by the AI agents.
- Goal Formulation–In this step as soon as a problem arises, the agent sets a goal or a target. This requires the agent to promptly analyse and define the problem. This is a crucial step as if the goal for the problem is wrongly formulated then all the steps taken in order to reach the goal would be of no use.
- Problem Definition–This is one main step of problem solving. It is here that whenever a problem arises, then the agent decides on what actions must be taken so as to reach till the formulated goal. This is done in the following steps:
- Defining the State Space–A state space can be defined as a collection of all the valid states in which an agent can be in when finding a solution to the problem.
- Defining Initial State–In order for an agent to start solving the problem, it needs to start from a state. The first state from where the agent starts working is referred to as the initial state.
- Gather Knowledge–Now the agent gathers information and uses the information required by it to solve the problem. This knowledge will be gathered with past experiences as well as current learnings.
- Planning the Transitions–Some problems are small and so these can be solved easily. But most of the times problems will be such where proper planning and execution is needed. Hence this requires proper data structures and control strategies well in advance.
- Defining the State Space–A state space can be defined as a collection of all the valid states in which an agent can be in when finding a solution to the problem.
Here the problem is divided into sub problems. The results of the various actions taken in solving the previous sub problem are forwarded to the next sub problem and the combined effect of the sub problems leads to the final solution. This requires proper planning and execution of transitions.
- Testing the Goal State–In this step, the results yielded from the agent are compared with
that of the goal state. If the goal has been reached, then the agents stop any
further actions and the problem reaches the last state. But if the goal is not
reached then the agent continues to find actions to reach till the goal.
- Calculating the Cost of Path taken–Whenever an agent takes a path in order to solve a problem it allots a numeric value (or cost) to that path. These values are then evaluated using a cost function. The evaluated result is hence used in the agent’s performance measure. The solution which is reached with the minimum or lowest cost of path is termed as an optimal solution.
Measuring Performance in Problem Solving
Performance measure is one of the important things in AI problem solving which defines the worth of the algorithm used to solve the problem. There are four ways in which the performance of an algorithm is measured. These are as follows:
- Completeness – Completeness measures the algorithms guarantee to find the solution for the problem if there exists any solution for it.
- Optimality – This measure is used in order to measure the search strategies which find an optimal solution to the given problem.
- Time Complexity – This measures the amount of time the algorithm takes in order to reach till the solution for the given problem.
- Space Complexity – This is the measure which is used to determine the amount of space (in memory) which the algorithm requires in order to perform the search.
The complexity of an algorithm depends on various factors like: maximum number of successors also known as branching factor, depth or shallowness of the goal state, and the maximum length of any path in the state space representation.