MID SEM PAPER SOLUTION AI

Paper solution of your mid sem exam**

Answer 1

Artificial intelligence is the search for a way to map intelligence into mechanical hardware and enable a structure into that system to formalize thought.

Artificial Intelligence is the study of human intelligence and actions replicated artificially, such that the resultant bears to its design a reasonable level of rationality.

There are numerous definitions of what artificial intelligence is

1. Systems that think like humans (focus on reasoning and human framework)
2. Systems that think rationally (focus on reasoning and a general concept of intelligence)
3. Systems that act like humans (focus on behavior and human framework)
4. Systems that act rationally (focus on behavior and a general concept of intelligence)

Artificial intelligence is a branch of computer science that aims to create intelligent machines. It has become an essential part of the technology industry. 

Research associated with artificial intelligence is highly technical and specialized. The core problems of artificial intelligence include programming computers for certain traits such as:
Machine learning is another core part of AI. Learning without any kind of supervision requires an ability to identify patterns in streams of inputs, whereas learning with adequate supervision involves classification and numerical regressions. Classification determines the category an object belongs to and regression deals with obtaining a set of numerical input or output examples, thereby discovering functions enabling the generation of suitable outputs from respective inputs. Mathematical analysis of machine learning algorithms and their performance is a well-defined branch of theoretical computer science often referred to as computational learning theory. 
Machine perception deals with the capability to use sensory inputs to deduce the different aspects of the world, while computer vision is the power to analyze visual inputs with few sub-problems such as facial, object and speech recognition.
Robotics is also a major field related to AI. Robots require intelligence to handle tasks such as object manipulation and navigation, along with sub-problems of localization, motion planning and mapping. 

• Knowledge
• Reasoning
• Problem solving
• Perception
• Learning
• Planning
• Ability to manipulate and move objects

Knowledge engineering is a core part of AI research. Machines can often act and react like humans only if they have abundant information relating to the world. Artificial intelligence must have access to objects, categories, properties and relations between all of them to implement knowledge engineering. Initiating common sense, reasoning and problem-solving power in machines is a difficult and tedious approach. 

For further read this article http://www.ucs.louisiana.edu/~isb9112/dept/phil341/wisai/WhatisAI.html

Answer-2

Water – Jug problem

The state space for this problem can be described as the set of ordered pairs of

integers (x, y) such that x = 0, 1,2, 3 or 4 and y = 0,1,2 or 3; x represents the number of

gallons of water in the 4-gallon jug and y represents the quantity of water in 3-gallon jug

• The start state is (0,0)

• The goal state is (2,n)

Production rules for Water Jug Problem

The operators to be used to solve the problem can be described as follows:

Sr. No Current state Next State Description

1 (x, y) if x < 4 (4,y) Fill the 4 gallon jug

2 (x, y) if y <3 (x,3) Fill the 3 gallon jug

3 (x, y) if x > 0 (x-d, y) Pour some water out of the 4 gallon jug

4 (x, y) if y > 0 (x, y-d) Pour some water out of the 3-gallon jug

5 (x, y) if x>0 (0, y) Empty the 4 gallon jug

6 (x, y) if y >0 (x,0) Empty the 3 gallon jug on the ground

7 (x, y) if x + y

>= 4 and y >0

(4, y-(4-x)) Pour water from the 3 –gallon jug into the 4 –

gallon jug until the 4-gallon jug is full

8 (x, y) if x + y

>= 3 and x>0

(x-(3-y), 3) Pour water from the 4-gallon jug into the 3-

gallon jug until the 3-gallon jug is full

9 (x, y) if x + y

<=4 and y>0

(x + y, 0) Pour all the water from the 3-gallon jug into the

4-gallon jug

10 (x, y) if x + y

<= 3 and x>0

(0, x + y) Pour all the water from the 4-gallon jug into the

3-gallon jug

11 (0,2) (2,0) Pour the 2 gallons from 3-gallon jug into the 4-

gallon jug

12 (2,y) (0,y) Empty the 2 gallons in the 4-gallon jug on the

ground

To solve the water jug problem

• Required a control structure that loops through a simple cycle in which some

rule whose left side matches the current state is chosen, the appropriate change

to the state is made as described in the corresponding right side, and the

resulting state is checked to see if it corresponds to goal state. • One solution to the water jug problem

• Shortest such sequence will have a impact on the choice of appropriate

mechanism to guide the search for solution.

Gallons in the 4-gallon jug||| Gallons in the 3-gallon jug|||Rule applied

0                                             0                                    2

0                                             3                                    9

3                                             0                                    2

3                                             3                                    7 

4                                             2                                    5 or 12

0                                             2                                     9 0r 11

2                                             0

Answer-3

Hill climbing is a variant of generate-and-test in which feedback from the test

procedure is used to help the generator decide which direction to move in the

search space. In a pure generate-and-test procedure, the test function

responds with only a yes or no. But if the test function is augmented with a

heuristic function2

that provides an estimate of how close a given state is to a

goal state, the generate procedure can exploit it .as shown in the procedure

below. This is particularly nice because often the computation of the heuristic

function can be done at almost no cost at the same time that the test for a

solution is being performed. Hill climbing is often used when a good heuristic

function is available for evaluating state. For example, suppose you are in an unfamiliar city

without a map and you want to get downtown. You simply aim for the tall

buildings. The heuristic function is just distance between the current location

and the location of the tall buildings and the desirablestates are those in which

this distance is minimized.

variants

simple, steepest,simulated etc

Problems of hill climbing

1. LOCAL MAXIMUM

A local maximum is a state i.e. better than all its neighbor but not better than some other state further away

At local maximum all moves appear to make thing worse.

Remedy for Local Maximum

Back track to some earlier node and try to go in some different direction.

2. PLATEAU

A flat area of the search space in which all neighbouring states have the same value.

On a plateau it is not possible to determine the best direction in which to move by making a local comparison.

Remedy

Make a big jump in some direction and try to get a new section of search space.

3.RIDGE

It is a special kind of local maximum.

The orientation of the high region, compared to the set of available moves, makes it impossible to climb up.

Remedy

Apply two or more rules before doing the test.

Answer-4

A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.

It uses a knowledge-plus-heuristic cost function of node x (usually denoted f(x)) to determine the order in which the search visits nodes in the tree. The cost function is a sum of two functions:

• the past path-cost function, which is the known distance from the starting node to the current node x (usually denoted g(x))
• a future path-cost function, which is an admissible "heuristic estimate" of the distance from x to the goal (usually denoted h(x)).

The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal. Thus, for an application like routing, h(x) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points or nodes.

If the heuristic h satisfies the additional condition  for every edge (x, y) of the graph (where d denotes the length of that edge), then h is called monotone, or consistent. In such a case, A* can be implemented more efficiently—roughly speaking, no node needs to be processed more than once (see closed set below)—and A* is equivalent to running Dijkstra's algorithm with the reduced cost d'(x, y) := d(x, y) + h(y) – h(x)

Starting with the initial node, it maintains a priority queue of nodes to be traversed, known as the open set or fringe. The lower f(x) for a given node x, the higher its priority. At each step of the algorithm, the node with the lowest f(x) value is removed from the queue, the f and g values of its neighbors are updated accordingly, and these neighbors are added to the queue. The algorithm continues until a goal node has a lower f value than any node in the queue (or until the queue is empty). (Goal nodes may be passed over multiple times if there remain other nodes with lower f values, as they may lead to a shorter path to a goal.) The f value of the goal is then the length of the shortest path, since hat the goal is zero in an admissible heuristic.

The algorithm described so far gives us only the length of the shortest path. To find the actual sequence of steps, the algorithm can be easily revised so that each node on the path keeps track of its predecessor. After this algorithm is run, the ending node will point to its predecessor, and so on, until some node's predecessor is the start node.

Additionally, if the heuristic is monotonic (or consistent, see below), a closed set of nodes already traversed may be used to make the search more efficient

Algorithm

• Put the initial node on a list START
• If (START is empty) or (START == GOAL) terminate search
• Remove the first node from START. Call this node ‘a‘.
• If (a == GOAL) terminate search with success.
• Else if node ‘a‘ has successors generate all of them. Estimate the fitness number by the successors by totaling the evaluation function value and cost function value. Sort the list by fitness number.
• Name this list as START1.
• Replace START with START1.
• Goto step 2

Answer-4

(i) Monkey – Banana problem

A monkey is in a cage and bananas are suspended from the ceiling, the monkey

wants to eat a banana but cannot reach them

– in the room are a chair and a stick

– if the monkey stands on the chair and waves the stick, he can knock a banana

down to eat it

what are the actions the monkey should take?

Initial state:

monkey on ground with empty hand bananas suspended

Goal state:

monkey eating bananas.

Actions:

climb chair/get off

grab X

wave X

eat X

Answer-5

Will explain in class.

Answer-6

Topic 3.3 and 3.4 in the book Artificial Intelligence by Elaine rich

Answer-7

Topic 3.3 and 3.4 in the book Artificial Intelligence by Elaine rich

**This post may have content taken from other sites; Since adding content and designing is a time consuming process some things may have been presented in a simplified manner and diagrams might not have been drawn or examples may have been ommited.