Artificial Intelligence Unit 2

 

Unit II

 

Heuristic Search Strategies:

Heuristic (Informed) Search Strategies:

 

To solve large problems with large number of possible states, problem-specific knowledge needs to be added to increase the efficiency of search algorithms.

 

Heuristic Evaluation Functions

 

They calculate the cost of optimal path between two states. A heuristic function for sliding-tiles games is computed by counting number of moves that each tile makes from its goal state and adding these number of moves for all tiles.

 

Pure Heuristic Search

 

It expands nodes in the order of their heuristic values. It creates two lists, a closed list for the already expanded nodes and an open list for the created but unexpanded nodes.

 

In each iteration, a node with a minimum heuristic value is expanded, all its child nodes are created and placed in the closed list. Then, the heuristic function is applied to the child nodes and they are placed in the open list according to their heuristic value. The shorter paths are saved and the longer ones are disposed.

 

Hill-Climbing Search

 

It is an iterative algorithm that starts with an arbitrary solution to a problem and attempts to find a better solution by changing a single element of the solution incrementally. If the change produces a better solution, an incremental change is taken as a new solution. This process is repeated until there are no further improvements.

 

function Hill-Climbing (problem), returns a state that is a local maximum. inputs: problem, a problem

local variables: current, a node neighbor, a node current <-Make_Node(Initial-State[problem]) loop

do neighbor <- a highest_valued successor of current

 

if Value[neighbor] ≤ Value[current] then return State[current]

current <- neighbor end Disadvantage –

This algorithm is neither complete, nor optimal.

 

Local Beam Search

 

In this algorithm, it holds k number of states at any given time. At the start, these states are generated randomly. The successors of these k states are computed with the help of objective function. If any of these successors is the maximum value of the objective function, then the algorithm stops.

 

Otherwise the (initial k states and k number of successors of the states = 2k) states are placed in a pool. The pool is then sorted numerically. The highest k states are selected as new initial states. This process continues until a maximum value is reached.

 

function BeamSearch( problem, k), returns a solution state.

 

start with k randomly generated states loop

generate all successors of all k states

 

if any of the states = solution, then return the state else select the k best successors

end

 

Simulated Annealing

 

Annealing is the process of heating and cooling a metal to change its internal structure for modifying its physical properties. When the metal cools, its new structure is seized, and the

 

 

 

metal retains its newly obtained properties. In simulated annealing process, the temperature is kept variable.

 

We initially set the temperature high and then allow it to ‘cool' slowly as the algorithm proceeds. When the temperature is high, the algorithm is allowed to accept worse solutions with high frequency.

 

Start

 

1.                    Initialize k = 0; L = integer number of variables;

2.                    From i → j, search the performance difference Δ.

3.                    If Δ <= 0 then accept else if exp(-Δ/T(k)) > random(0,1) then accept;

4.                    Repeat steps 1 and 2 for L(k) steps.

5.                    k = k + 1;

 

Repeat steps 1 through 4 till the criteria is met. End

Travelling Salesman Problem

 

In this algorithm, the objective is to find a low-cost tour that starts from a city, visits all cities en-route exactly once and ends at the same starting city.

 

Start

Find out all (n -1)! Possible solutions, where n is the total number of cities. Determine the minimum cost by finding out the cost of each of these (n -1)!

solutions.

 

Finally, keep the one with the minimum cost. end

 

 

 

A * Search

 

It is best-known form of Best First search. It avoids expanding paths that are already expensive, but expands most promising paths first.

 

f(n) = g(n) + h(n), where

 

·                     g(n) the cost (so far) to reach the node

·                     h(n) estimated cost to get from the node to the goal

·                     f(n) estimated total cost of path through n to goal. It is implemented using priority queue by increasing f(n).

 

Greedy Best First Search

 

It expands the node that is estimated to be closest to goal. It expands nodes based on f(n) = h(n). It is implemented using priority queue.

 

Disadvantage

 

It can get stuck in loops. It is not optimal.

 

Breadth-First Search

 

It starts from the root node, explores the neighboring nodes first and moves towards the next

 

level neighbors. It generates one tree at a time until the solution is found. It can be implemented using FIFO queue data structure. This method provides shortest no of nodes created in worst case is b + b² + b³ + … + b^d.

 

Disadvantage –

 

Since each level of nodes is saved for creating next one, it consumes a lot of memory space. Space requirement to store nodes is exponential.

 

Its complexity depends on the number of nodes. It can check duplicate nodes.

 

Bidirectional Search

 

It searches forward from initial state and backward from goal state till both meet to identify a common state.

 

The path from initial state is concatenated with the inverse path from the goal state. Each search is done only up to half of the total path.

 

Knowledge Representation

 

Knowledge-representation is the field of artificial intelligence that focuses on designing computer representations that capture information about the world that can be used to solve complex  problems.  The  justification  for  knowledge  representation  is  that conventional procedural code is not the best formalism to use to solve complex problems. Knowledge representation makes complex software easier to define and maintain than procedural code and can be used in expert systems.

 

For example, talking to experts in terms of business rules rather than code lessens the semantic gap between users and developers and makes development of complex systems more practical.

 

In simple terms knowledge, representation is a technique which is used in artificial intelligence with the fundamental goal of representing knowledge in a standard manner such that it facilitates inferencing or reasoning or resolution from that knowledge.

 

It analyzes how to think formally and how to use a symbol to represent a knowledge along with different situation that allows inferencing knowledge representation to help to address the different problems like how do we represent facts about the world, how do we reason about the facts, what kinds of representations are appropriate and how can an agent perform well in reasoning.

 

There are the variety of ways to represent knowledge or facts which have been exploited in AI programs. In all variety of knowledge representations we deal with two kinds of entities and they are facts which are referred to the truth in some relevant world.

 

These are the things we want to represent and the second entity will be the representations of facts which are acquired from some chosen formalism. These are the things which we will actually be able to manipulate.

 

The above two entities can be structured at two levels : The knowledge level of which facts is described. The symbol level at which representations of objects at the knowledge level are defined in terms of symbols that can be manipulated by programs.

 

The facts and the representations are linked with the two-way mappings. This link is called representation mappings. The forward representation mapping maps from the facts to the representations. The backward representation mapping goes the other way that is from representations to facts.

 

Knowledge representation goes hand in hand with automated reasoning because one of the main purposes of explicitly representing knowledge is to be able to reason about that knowledge, to make inferences, assert new knowledge, etc. Virtually all knowledge representation languages have a reasoning or inference engine as part of the system.

 

Knowledge representation Issues:

 

Representation and Mapping:

 

In simple terms knowledge, representation is a technique which is used in artificial intelligence with the fundamental goal of representing knowledge in a standard manner such that it facilitates inferencing or reasoning or resolution from that knowledge. It analyzes how to think formally and how to use a symbol to represent a knowledge along with different situation that allows inferencing knowledge representation to help to address the different problems like:

 

1.                    How do we represent facts about the world?

2.                    How do we reason about the facts?

3.                    What kinds of representations are appropriate?

4.                    How can an agent perform well in reasoning?

 

 

 

 

 

 

 

 

 

For the purpose of solving complex problems that are encountered in artificial intelligence, we need both a large amount of knowledge and some mechanism for manipulating that knowledge in order to create solutions to those new problems. There are the variety of ways to represent knowledge or facts which have been exploited in AI programs. In all variety of knowledge representations we deal with two kinds of entities and they are:

 

1.                    Facts: It is referred to the truth in some relevant world. These are the things we want to represent.

2.                    The second entity will be the representations of facts which are acquired from some chosen formalism. These are the things which we will actually be able to manipulate.

 

The above two entities can be structured at two levels:

 

1.                    The knowledge level of which facts is described.

2.                    The symbol level at which representations of objects at the knowledge level are defined in terms of symbols that can be manipulated by programs.

 

The facts and the representations are linked with the two-way mappings. This link is called representation mappings. The forward representation mapping maps from the facts to the representations. The backward representation mapping goes the other way that is from representations to facts.

 

One common representation is natural language (particularly English) sentences. Regardless of the representation of facts that we use in a program, we may also need to be concerned with an English representation of those facts in order to facilitate for getting the information into and out of the system. We need the mapping functions from English sentences to the representation which we actually use and from it back to sentences.

 

A good knowledge representation system should have the following approach to representing the given information so that the reasoning becomes easy.

 

1.     Representational Adequacy: It is the ability to represent all kinds of knowledge that are needed in a particular domain. This means a good knowledge representation should be able to represent any kind of knowledge in a standard manner.

 

2.     Inferential Adequacy: It is the ability to manipulate the different facts that are represented in a standard format in such a way that it derives new structured knowledge from an old one. In short, a good knowledge representation system should be able to infer the new facts from                the                     given                                      facts.

 

3.     Inferential Efficiency: It is the ability to derive the new facts from the given fact in an efficient or optimal manner that is a good knowledge representation should be able to incorporate some additional information which can be used to focus the attention of inference engine              in the                   most                 promising            direction.

 

4.     Acquisitional Adequacy: It is the ability to acquire new knowledge from the environment in an efficient manner.

 

Types of Knowledge:

 

1.                    Simple Relational Knowledge:It is the simplest way of storing facts by using a relational method where each fact about a set of objects is set out systematically in columns. This representation gives little opportunity for inference but it can be used as the knowledge basis for inference engines.A simple way to store facts. Each fact about a set of objects is set out systematically in                columns.Little         opportunity          for             inference. Knowledge                  basis                               for                        inference                           engines.

 

2.           Inheritable Knowledge: It is a referential knowledge which is made up of objects that             consistof:              Attributes             Corresponding              associated                    values.

 

3.                    Inferential Knowledge: It is a representation knowledge as formal logic. For example:

 

All dogs have tails.

∀x: dog(x) → has a tail(x).

 

4.                    Procedural Knowledge: The basic idea of procedural knowledge is to encode the knowledge in some procedures. These procedures may include small programs that know how to do specific things and how to proceed.

 

Advantages:

 

·                     It sets certain rules which are very strict which can be used to derive more facts. The truth of the new statement can be verified.

·                     It guarantees the correctness.

·                     Many inference procedures available to in implement standard rules of logic. e.g Automated theorem proving.

 

Approaches to Knowledge Representation:

 

A good knowledge representation system should have the following approach to representing the given information so that the reasoning becomes easy. Representational Adequacy is the ability to represent all kinds of knowledge that are needed in a particular domain. This means a good knowledge representation should be able to represent any kind of knowledge in a standard manner.

 

Inferential Adequacy is the ability to manipulate the different facts that are represented in a standard format in such a way that it derives new structured knowledge from an old one. In short, a good knowledge representation system should be able to infer the new facts from the given facts.

 

Inferential Efficiency is the ability to derive the new facts from the given fact in an efficient or optimal manner that is a good knowledge representation should be able to incorporate some additional information which can be used to focus the attention of inference engine in the most promising direction.

 

Acquisitional Adequacy is the ability to acquire new knowledge from the environment in an efficient manner. The types of knowledge are simple relational knowledge, inheritable knowledge, inferential knowledge and procedural knowledge. Simple Relational Knowledge is the simplest way of storing facts by using a relational method where each fact about a set of objects is set out systematically in columns.

 

Inheritable Knowledge is a referential knowledge which is made up of objects that consist of attributes and corresponding associated values. Inferential Knowledge is a representation knowledge as formal logic. The basic idea of procedural knowledge is to encode the knowledge in some procedures. These procedures may include small programs that know how to do specific things and how to proceed.

 

 

 

 

 

Issues in Knowledge Representation:

 

The issues in Knowledge representation are: Are there any attributes of the object which are so basic that they have occurred in almost every problem domain. Are there any important

relationships that exist among the different attributes of objects. At what level should the knowledge is represented and what are the primitives. How should the set of objects be represented? How can the relevant part of the information can be accessed when they are required.

 

Frame Problem:

 

It is a technique that is used for knowledge representation. A semantic network is a graphical representation of knowledge consisting of nodes and arcs where the node is the object and arc are the relations between different objects. The most

commonly used relations are: is a,

has a, member of, belongs to,

inheritance etc.

 

Example1: p: Ram is the father of Shyam.

 

Example2: Ram's height is greater than Shyam's height.

 

 

 

.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Frames:

 

A frame is a collection of attributes which are usually called slots and their associated values which describe the same entity in the real world. We build a frame system as a collection of frames which are connected to each other by virtue of the fact that the value of an attribute of one frame may be another frame. Frames are also an extensive part of knowledge representation and reasoning scheme. Frames were originally derived from the semantic network. and are therefore part of structure based knowledge representation.

 

For example:

 

Person is a: mammal. Cardinality: 6,00,00,000. Adult-male is a: person Cardinality: 2,00,00,000

*height: 6.0".

 

Football-Player is an: Adult-male. Cardinality: 1000

*height: 6.2".

 

Upendra instance: Football-Player. team: MMFC

score: 4

 

height: 6.1".

 

uniform-color: Black.

 

Each friend represents either a class or an instance. In this example, the friends, person, adult-male, football player are classes whereas the frame Upendra is an instance. There are two types of attributes, one is the attributes associated with class and attributes that are to be inherited by each instance of the class. This is called frame.

 

******************Unit 2 Completed******************

Unit 2

one mark questions

1.      Stimulated annealing is the variant of hill climbing. Say True or False

2.      _______________is a successful AI program, which infers the structure of organic compounds using mass spectrum and nuclear magnetic resonance.

3.       Find x                

                                     x   

 

                        (3)              (5)              (7)

     4.    ______________is the ability to represent all of the kinds of knowledge that of that are                needed in that domain.

    5.     ELIZA was originally developed for _______________.

2 Mark questions

1.      Write down any two differences between tree and graph.

2.      Define Best – First Algorithm.

3.      Draw a simple AND – OR graph to acquire a TV set.

4.      Fill the draw table with the robot’s operators

	Push	Carry	Walk	Pick up	Put down	Place
Move object
Move robot

5.      How many state descriptions must be maintained throughout the search process

 

15 mark questions

 

1.      i)          When would be the BFS worse than the simple breadth first algorithm?

i)                    Solve the given 8puzzle using hill climbing algorithm

            Start                            Goal

1	2	3
4	5	6
7	8

           

1	2	3
8	5	6
4	7

               

 

 

 

2.       Explain and Compare A* algorithm with AO* algorithm.

3.      Write the following algorithm i) Generate – and – Test  ii) Hill climbing  iii) Mean End Analysis

4.      How can you get exactly 2 gallons of water in the 4-gallon jug? If you are given two jugs, A 4-gallon one and a 3-gallon one, a pump which has unlimited water which you can use to fill the jug, and the ground on which water may be poured. Neither jug has any measuring markings on it                          

5.      Explain            i) Approaches to Knowledge Representation ii) issues in knowledge representation