# Artificial Intelligence [Part 1]

# What is Artificial Intelligence:-

Branch of computer science which is concerned with making **computers behave like a human**. As a human associate with other human minds for “learning,” “problem-solving,” we want machines to mimic these cognitive functions too. In 1956 artificial intelligence field was founded by John McCarthy, Marvin Minsky, Allen Newell, Arthur Samuel and Herbert Simon at a conference at Dartmouth College.

### Specialization of AI

- Game Playing- Programming computers to play a game against some opponent(whether it be human or another computer system).
- Expert System-Programming computers to make decisions in real time situation. Example-: some system helps doctors to diagnose disease based on symptoms.
- Natural language- Programming computers to understand natural human language and to work as a translator.
- Robotics- Programming computers to see and hear and react to other stimuli.

**Artificial intelligence** is a copy of Human brain; it is based on working with human brain through neuron connection. As in brain, there is neuron connection for full processing and cognition functions, etc., In artificial intelligence also we have an artificial neural network- a computing system where some highly interconnected simple processing elements process information.

## Problem-solving in Artificial Intelligence:-

Problem-solving includes- defining a problem, finding the cause of the problem, finding best and least cost solution and implementing the solution.

A problem can be of two types

**Deterministic problem**– A problem for which all required information required for the solution are available, where the result is fixed, and effect of any variable can be computed with certainty. E.g.- finding the volume of a cylinder.**Un-deterministic problem**– Problem which is of stochastic in nature and is unpredictable, where the effect of any variable remains uncertain, where next step cannot be found from the present step. E.g.- Chess game.

We use Artificial intelligence to solve problems which are of stochastic in nature. Here search framework is used to solve these type of problems.

We use Artificial intelligence to solve problems which are of stochastic in nature. Here search framework is used to solve these type of problems.

## Search Framework-

Search is an ideal set of operation by which a goal is achieved.

The boundary of any problem is known as problem space.

### Types of search framework

- Uninformed search or Blind search- No idea of where to go, no guideline so explore whole search tree.
- Goal oriented search- Pre-information or instructions are given, it is known that what path should be opted to reach the goal
- Problem reduction search- Hybrid of Blind search and goal oriented search.
- Game tree search- Game playing and designing strategy to win a game.

**An Example of AI puzzle:**

**Missionary- cannibal problem**

Puzzle can be defined as-

There are three Missionaries and three cannibals on one bank of the river; one boat is there that can hold up to two animals. If the animals ever are more than missionaries on either of the river’s bank; missionaries will get eaten. How can the boat be used to carry all the cannibals and missionaries across the river safely?

The problem is solved in the figure.

**SEARCH ALGORITHM**

The way of searching solution for a problem using some standard algorithm.

**OUTLINE**

- Initialize- Set OPEN={S} where S is start state
- FAIL- OPEN={ }, terminate with failure i.e. where goal state is not achieved, and OPEN list is empty.
- Select- Select state “n” from OPEN, mark “n” visited.
- Terminate= If “n” belongs to goal state then terminate with success.
- Expand= Generate all the successors of “n” & add them in OPEN using operator O. (O will define rules which are permit-able for current state)
- Loop= Go to SELECT.

NOTE- If OPEN{ } is stack, DFS or if OPEN{ } is queue then its BFS. The algorithm will be same as previously defined.

## TRADE-OFF of DFS and BFS

**DFS and BFS** create problem when we have Problems with infinite state space e.g. A program which generates a random number.

For this kind of problem (where state space = infinity), When and how DFS and BFS will terminate is an issue.

In the case of DFS, suppose tree has two branches with infinite depth, and the goal is the 2^{nd} branch. According to the algorithm, we are moving in the first branch. Because depth is infinity, we are lost.

In the case of BFS, since BFS doesn’t work depth wise but breadth wise; if the goal is present at any finite, the state will be reached; because at one time, BFS opens each successor of a node. So it will expand the whole tree till the goal is not reached. But since queue will be long and long, BFS fails due to very high memory consumption.

### SOLUTION OF THIS PROBLEM

Hybrid of BFS and DFS algorithm i.e. Iterative deeply algorithm

- Initialize: Set OPEN={S}, d=1
- Failure: OPEN={ }, terminate with failure.
- Select Select state n from OPEN{ } and mark n as visited.
- Terminate: If n belongs to G then terminate with success.
- Expand: Generate the successors of depth “d” using operator O and insert them in OPEN, d=d+1
- Loop: Go to step Select

So using Iterative deep algorithm, we can reduce the time of search and memory consumption also we can improve the performance of DFS and BFS specifically when Problem space is enormous.

# SEARCH WITH OPTIMISATION

### Cost search-

Here we consider cost (path cost) as a parameter. We mind these points here

- We opt for minimum transaction i.e. for minor moves.
- We opt for states with lower cost always
- If there is more than one goal nearby, choose a goal with minimum cost.

__Uninformed cost search__

Here we don’t have information about path; at every expansion, we test if target state is present there, if not; we move towards low-cost states.

Cost of B= c(1)+c(1,B)

There are three alternative moves from “1”, we will move towards B because the cost(1,2) is the least.

**ALGORITHM**

- INITIALISE- set OPEN {S}, and CLOSED={ }, c(S)=0

Here CLOSED is a list which contains all visited nodes.

- FAILURE- If OPEN={ } & the goal is not achieved then terminate with failure.
- SELECT- Select minimum cost node n from open and insert it to CLOSED.
- TERMINATE- if n belongs to goal state, end with success.
- EXPAND- develop all the successors (say m) of n and insert m into OPEN. m will be of least cost.

If m doesn’t belong to [OPEN U COSED] i.e. if you are visiting m for first time/

Cost of m=c(n)+c(n to m)

Else,

If current cost of m< as stored in OPEN or CLOSED, update the list with new cost and visit m.

- LOOP- Go to step SELECT.

CLOSED | OPEN |

a(0) | |

a(0) | b(2) e(1) |

e(1) | b(2) i(2) |

b(2) | i(2) c(3) f(5) |

i(2) | c(3) f(5) j(10) |

c(3) | f(5) j(10) d(5) |

f(5) | j(10) d(5) g(6) j(9) j(10)>j(9), remove j(10) and update |

d(5) | g(6) j(9) h(6) |

g(6) | j(9) h(6) k(16) |

h(6) | j(9) k(16) l(21) |

j(9) | k(16) k(12) l(21) k(16)>k(12), remove and update |

k(12) | l(13) l(21) remove l(21) from list; goal reached. |

#### Venu Sudha

#### Latest posts by Venu Sudha (see all)

- Artificial Intelligence [Part 1] - February 9, 2017