ArtificialIntelligence Notes

What is Artificial Intelligence?

According to the father of Artificial Intelligence John McCarthy, it is “The science and engineering of making intelligent machines, especially intelligent computer programs”.

Artificial Intelligence is a way of making a computer, a computer-controlled robot, or a software think intelligently, in the similar manner the intelligent humans think.

AI is accomplished by studying how human brain thinks, and how humans learn, decide, and work while trying to solve a problem, and then using the outcomes of this study as a basis of developing intelligent software and systems.

Philosophy of AI

While exploiting the power of the computer systems, the curiosity of human, lead him to wonder, “Can a machine think and behave like humans do?”

Thus, the development of AI started with the intention of creating similar intelligence in machines that we find and regard high in humans.

Goals of AI

·         To Create Expert Systems: The systems which exhibit intelligent behavior, learn, demonstrate, explain, and advice its users.

·         To Implement Human Intelligence in Machines: Creating systems that understand, think, learn, and behave like humans.

What Contributes to AI?

Artificial intelligence is a science and technology based on disciplines such as Computer Science, Biology, Psychology, Linguistics, Mathematics, and Engineering. A major thrust of AI is in the development of computer functions associated with human intelligence, such as reasoning, learning, and problem solving.

Out of the following areas, one or multiple areas can contribute to build an intelligent system.

Programming Without and With AI

The programming without and with AI is different in following ways:

Programming Without AI			Programming With AI
A  computer  program  without	AI	can	A computer program with AI can answer the
answer the specific questions it is meant
			generic questions it is meant to solve.
to solve.
			AI programs can absorb new modifications by
Modification  in  the  program	leads	to	putting   highly   independent   pieces   of
			information together. Hence you can modify
change in its structure.
			even a minute piece of information of program
			without affecting its structure.
Modification is not quick and easy. It may			Quick and Easy program modification.
lead to affecting the program adversely.

What is AI Technique?

In the real world, the knowledge has some unwelcomed properties:

·         Its volume is huge, next to unimaginable.

·         It is not well-organized or well-formatted.

·         It keeps changing constantly.

AI Technique is a manner to organize and use the knowledge efficiently in such a way that:

·         It should be perceivable by the people who provide it.

·         It should be easily modifiable to correct errors.

·         It should be useful in many situations though it is incomplete or inaccurate.

AI techniques elevate the speed of execution of the complex program it is equipped with.

Applications of AI

AI has been dominant in various fields such as:

·         Gaming

AI plays crucial role in strategic games such as chess, poker, tic-tac-toe, etc., where machine can think of large number of possible positions based on heuristic knowledge.

·         Natural Language Processing

It is possible to interact with the computer that understands natural language spoken by humans.

·         Expert Systems

There are some applications which integrate machine, software, and special information to impart reasoning and advising. They provide explanation and advice to the users.

·         Vision Systems

These systems understand, interpret, and comprehend visual input on the computer. For example,

o A spying aeroplane takes photographs which are used to figure out spatial information or map of the areas.

o  Doctors use clinical expert system to diagnose the patient.

o Police use computer software that can recognize the face of criminal with the stored portrait made by forensic artist.

·         Speech Recognition

Some intelligent systems are capable of hearing and comprehending the language in terms of sentences and their meanings while a human talks to it. It can handle different accents, slang words, noise in the background, change in human’s noise due to cold, etc.

·         Handwriting Recognition

The handwriting recognition software reads the text written on paper by a pen or on screen by a stylus. It can recognize the shapes of the letters and convert it into editable text.

·         Intelligent Robots

Robots are able to perform the tasks given by a human. They have sensors to detect physical data from the real world such as light, heat, temperature, movement, sound, bump, and pressure. They have efficient processors, multiple sensors and huge memory, to exhibit intelligence. In addition, they are capable of learning from their mistakes and they can adapt to the new environment.

History of AI

Here is the history of AI during 20^th century:

Year		Milestone / Innovation
1923		Karel Čapek’s play named “Rossum's Universal Robots” (RUR) opens in London,
		first use of the word "robot" in English.
1943		Foundations for neural networks laid.
1945
		Isaac Asimov, a Columbia University alumni, coined the term Robotics.
		Alan Turing introduced Turing Test for evaluation of intelligence and published
1950		Computing  Machinery  and  Intelligence.  Claude Shannon  published  Detailed
		Analysis of Chess Playing as a search.
1956		John McCarthy coined the term Artificial Intelligence. Demonstration of the first
		running AI program at Carnegie Mellon University.
1958		John McCarthy invents LISP programming language for AI.
1964		Danny Bobrow's dissertation at MIT showed that computers can understand
		natural language well enough to solve algebra word problems correctly.
1965		Joseph Weizenbaum at MIT built ELIZA, an interactive problem that carries on
		a dialogue in English.
1969		Scientists at Stanford Research Institute Developed Shakey, a robot, equipped
		with locomotion, perception, and problem solving.

1973	The Assembly Robotics group at Edinburgh University built Freddy, the Famous
	Scottish Robot, capable of using vision to locate and assemble models.
1979	The first computer-controlled autonomous vehicle, Stanford Cart, was built.
1985	Harold Cohen created and demonstrated the drawing program, Aaron.
	Major advances in all areas of AI:
	·  Significant demonstrations in machine learning
	·  Case-based reasoning
	·  Multi-agent planning
1990	·	Scheduling
	·  Data mining, Web Crawler
	·  natural language understanding and translation
	·	Vision, Virtual Reality
	·	Games
1997	The Deep Blue Chess Program beats the then world chess champion, Garry
	Kasparov.
	Interactive robot pets become commercially available. MIT displays Kismet, a
2000	robot with a face that expresses emotions. The robot Nomad explores remote
	regions of Antarctica and locates meteorites.

What is Intelligence?

The ability of a system to calculate, reason, perceive relationships and analogies, learn from experience, store and retrieve information from memory, solve problems, comprehend complex ideas, use natural language fluently, classify, generalize, and adapt new situations.

Types of Intelligence

As described by Howard Gardner, an American developmental psychologist, the Intelligence comes in multifold:

Intelligence	Description		Example
Linguistic	The ability to speak, recognize, and use mechanisms
	of phonology (speech sounds), syntax (grammar),		Narrators, Orators
intelligence
	and semantics (meaning).
	The  ability  to  create,	communicate  with,  and	Musicians,
Musical intelligence	understand meanings made of sound, understanding		Singers,
	of pitch, rhythm.		Composers
Logical-	The ability of use and understand relationships in the		Mathematicians,
mathematical	absence of action or objects. Understanding complex		Scientists
intelligence	and abstract ideas.
	The ability to perceive visual or spatial information,		Map	readers,
Spatial intelligence	change  it,  and  re-create  visual  images  without		Astronauts,
	reference to the objects,	construct 3D images, and
	to move and rotate them.		Physicists
Bodily-Kinesthetic	The ability to use complete or part of the body to
	solve problems or fashion products, control over fine		Players, Dancers
intelligence
	and coarse motor skills, and manipulate the objects.
Intra-personal	The ability to distinguish among one’s own feelings,		Gautam Buddha
intelligence	intentions, and motivations.

Interpersonal	The ability to recognize and make distinctions among	Mass
		Communicators,
intelligence	other people’s feelings, beliefs, and intentions.	Interviewers

You can say a machine or a system is artificially intelligent when it is equipped with at least one and at most all intelligences in it.

chapter -2

                                                                           

Chapter -3

ch-7 Knowledge under Uncertainity

Monotonic learning is when an agent may not learn the knowledge that contradicts with what it already known or exists, it will not replace a statement with its negation. Thus, the knowledge base may only grow with new facts in a monotonic fashion. The advantages of monotonic learning are:

1.greatly simplified truth-maintenance

2.greater choice in learning strategies

Non-monotonic learning is when an agent may learn the new knowledge that contradicts what it already known or existing. So it replaces the old knowledge with new if it believes there is sufficient reason to do so. The advantages of non-monotonic learning are:

1.increased applicability to real domains,

2.greater freedom in the order things are learned in

Implementations: Truth Maintenance Systems

A variety of Truth Maintenance Systems (TMS) have been developed as a means of implementing Non-Monotonic Reasoning Systems.

Basically TMSs:

• all do some form of dependency directed backtracking
• assertions are connected via a network of dependencies.

Justification-Based Truth Maintenance Systems (JTMS)

• This is a simple TMS in that it does not know anything about the structure of the assertions themselves.
• Each supported belief (assertion) in has a justification.
• Each justification has two parts:
  • An IN-List -- which supports beliefs held.
  • An OUT-List -- which supports beliefs not held.

• An assertion is connected to its justification by an arrow.
• One assertion can feed another justification thus creating the network.
• Assertions may be labelled with a belief status.
• An assertion is valid if every assertion in the IN-List is believed and none in the OUT-List are believed.
• An assertion is non-monotonic is the OUT-List is not empty or if any assertion in the IN-List is non-monotonic.

Logic-Based Truth Maintenance Systems (LTMS)
Similar to JTMS except:

• Nodes (assertions) assume no relationships among them except ones explicitly stated in justifications.
• JTMS can represent P and P simultaneously. An LTMS would throw a contradiction here.
• If this happens network has to be reconstructed.
• Assumption-Based Truth Maintenance Systems (ATMS)
  
• JTMS and LTMS pursue a single line of reasoning at a time and backtrack (dependency-directed) when needed -- depth first search.
• ATMS maintain alternative paths in parallel -- breadth-first search
• Backtracking is avoided at the expense of maintaining multiple contexts.
• However as reasoning proceeds contradictions arise and the ATMS can be pruned
• Simply and assertion with no valid justification.
• UNIT-III

• ch-9 Weak SLot and Filler Structure

  Semantic Nets

  The major idea is that:
  

  • The meaning of a concept comes from its relationship to other concepts, and that,
  • The information is stored by interconnecting nodes with labelled arcs.
  These values can also be represented in logic as: isa(person, mammal)
• Partitioned Networks Partitioned Semantic Networks allow for:
  
  
  • propositions to be made without commitment to truth.
  • expressions to be quantified.
  Basic idea: Break network into spaces which consist of groups of nodes and arcs and regard each space as a node.
  Consider the following: Andrew believes that the earth is flat. We can encode the proposition the earth is flat in a space and within it have nodes and arcs

Now consider the quantified expression: Every parent loves their child To represent this we:

• Create a general statement, GS, special class.
• Make node g an instance of GS.
• Every element will have at least 2 attributes:
  • a form that states which relation is being asserted.
  • one or more forall () or exists () connections -- these represent universally quantifiable variables in such statements e.g. x, y in  parent(x) : child(y)  loves(x,y)

Here we have to construct two spaces one for each x,y. NOTE: We can express  variables as existentially qualified variables and express the event of love having an agent p and receiver b for every parent pwhich could simplify the network

Also If we change the sentence to Every parent loves child then the node of the object being acted on (the child) lies outside the form of the general statement. Thus it is not viewed as an existentially qualified variable whose value may depend on the agent. 

Frames

Frames and semantic nets: Frames can be viewed as a structural representation of semantic nets.
Examples: below are four frames for the entities "Mammal", "Elephant", "Clyde", and "Nellie"
(The symbol * means that the value of the feature is typical for the entity, represented by the frame.)

Mammalsubclass: Animalwarm_blooded: yesElephantsubclass: Mammal* color: grey* size: largeClydeinstance: Elephantcolor: pinkowner: FredNellieinstance: Elephantsize: small

Components of a frame entity:

• Name - corresponds to a node in a semantic net

• Attributes (also called slots) filled with particular values

E.G. in the frame for Clyde, instance is the name of a slot, and elephant is the value of the slot.
Names of slots correspond to the links in semantic nets
Values of slots correspond to nodes.
Hence each slot can be another frame.

Person:
is-a: mammal
height:5.8
weight-60

• Necessary attributes

• Typical attributes ("*" used to indicate attributes that are only true of a typical member of the class, and not necessarily every member).

• Type constraints and default values of slots, overriding values.

• Slots and procedures: a slot may have a procedure to compute the value of the slot if needed e.g. object area, given the size

Inheritance
If a slot is not defined for a given frame, we look at the parent-class slot with the same name
Simple if: single parent-class, problems with several parent classes (e.g., Clyde is both an elephant and a circus-animal)
Which parent to inherit from first?
Various mechanisms for making this choice - choosing the most specific parent class to inherit from.
Problems with frames: same as with semantic nets
Useful for:

• classifying new instances of familiar entities (objects/events/places/tasks

• anticipating the attributes of such instances

• inferring the presence and properties of their parts or participants

Ch-10Conceptual Dependency (CD)

Conceptual Dependency originally developed to represent knowledge acquired from natural language input.

The goals of this theory are:

• To help in the drawing of inference from sentences.
• To be independent of the words used in the original input.
• That is to say: For any 2 (or more) sentences that are identical in meaning there should be only one representation of that meaning.

It has been used by many programs that portend to understand English (MARGIE, SAM, PAM). CD developed by Schank et al. as were the previous examples.

CD provides:

• a structure into which nodes representing information can be placed
• a specific set of primitives
• at a given level of granularity.

Sentences are represented as a series of diagrams depicting actions using both abstract and real physical situations.

• The agent and the objects are represented
• The actions are built up from a set of primitive acts which can be modified by tense.

Examples of Primitive Acts are:

ATRANS

-- Transfer of an abstract relationship. e.g. give.

PTRANS

-- Transfer of the physical location of an object. e.g. go.

PROPEL

-- Application of a physical force to an object. e.g. push.

MTRANS

-- Transfer of mental information. e.g. tell.

MBUILD

-- Construct new information from old. e.g. decide.

SPEAK

-- Utter a sound. e.g. say.

ATTEND

-- Focus a sense on a stimulus. e.g. listen, watch.

MOVE

-- Movement of a body part by owner. e.g. punch, kick.

GRASP

-- Actor grasping an object. e.g. clutch.

INGEST

-- Actor ingesting an object. e.g. eat.

EXPEL

-- Actor getting rid of an object from body. e.g. ????.

Six primitive conceptual categories provide building blocks which are the set of allowable dependencies in the concepts in a sentence:

PP

-- Real world objects.

ACT

-- Real world actions.

PA

-- Attributes of objects.

AA

-- Attributes of actions.

T

-- Times.

LOC

-- Locations.

How do we connect these things together?

Consider the example:

John gives Mary a book

• Arrows indicate the direction of dependency. Letters above indicate certain relationships:

  o

  -- object.

  R

  -- recipient-donor.

  I

  -- instrument e.g. eat with a spoon.

  D

  -- destination e.g. going home.

• Double arrows () indicate two-way links between the actor (PP) and action (ACT).
• The actions are built from the set of primitive acts (see above).
  • These can be modified by tense etc.The use of tense and mood in describing events is extremely important and schank introduced the following modifiers:
    
    

    p

    -- past

    f

    -- future

    t

    -- transition

    

    -- start transition

    

    -- finished transition

    k

    -- continuing

    ?

    -- interrogative

    /

    -- negative

    delta

    -- timeless

    c

    -- conditional

    the absence of any modifier implies the present tense.

So the past tense of the above example:

John gave Mary a book becomes:

he  has an object (actor), PP and action, ACT. I.e. PP  ACT. The triplearrow () is also a two link but between an object, PP, and its attribute, PA. I.e. PP  PA.

It represents isa type dependencies. E.g

Dave  lecturerDave is a lecturer.

Primitive states are used to describe many state descriptions such as height, health, mental state, physical state.

There are many more physical states than primitive actions. They use a numeric scale.

E.g. John  height(+10) John is the tallest John  height(< average) John is short Frank Zappa  health(-10) Frank Zappa is dead Dave  mental_state(-10) Dave is sad Vase physical_state(-10) The vase is broken

You can also specify things like the time of occurrence in the relation ship.

For Example: John gave Mary the book yesterday

Now let us consider a more complex sentence: Since smoking can kill you, I stopped Lets look at how we represent the inference that smoking can kill:

• Use the notion of one to apply the knowledge to.
• Use the primitive act of INGESTing smoke from a cigarette to one.
• Killing is a transition from being alive to dead. We use triple arrows to indicate a transition from one state to another.
• Have a conditional, c causality link. The triple arrow indicates dependency of one concept on another.

To add the fact that I stopped smoking

• Use similar rules to imply that I smoke cigarettes.
• The qualification  attached to this dependency indicates that the instance INGESTing smoke has stopped.

Advantages of CD:

• Using these primitives involves fewer inference rules.
• Many inference rules are already represented in CD structure.
• The holes in the initial structure help to focus on the points still to be established.

Disadvantages of CD:

• Knowledge must be decomposed into fairly low level primitives.
• Impossible or difficult to find correct set of primitives.
• A lot of inference may still be required.
• Representations can be complex even for relatively simple actions. Consider:Dave bet Frank five pounds that Wales would win the Rugby World Cup.
  Complex representations require a lot of storage

Applications of CD:

MARGIE

(Meaning Analysis, Response Generation and Inference on English) -- model natural language understanding.

SAM

(Script Applier Mechanism) -- Scripts to understand stories. See next section.

PAM

(Plan Applier Mechanism) -- Scripts to understand stories.

Scripts

A script is a structure that prescribes a set of circumstances which could be expected to follow on from one another.

It is similar to a thought sequence or a chain of situations which could be anticipated.

It could be considered to consist of a number of slots or frames but with more specialised roles.

Scripts are beneficial because:

• Events tend to occur in known runs or patterns.
• Causal relationships between events exist.
• Entry conditions exist which allow an event to take place
• Prerequisites exist upon events taking place. E.g. when a student progresses through a degree scheme or when a purchaser buys a house.

The components of a script include:

Entry Conditions

-- these must be satisfied before events in the script can occur.

Results

-- Conditions that will be true after events in script occur.

Props

-- Slots representing objects involved in events.

Roles

-- Persons involved in the events.

Track

-- Variations on the script. Different tracks may share components of the same script.

Scenes

-- The sequence of events that occur. Events are represented in conceptual dependency form.

Scripts are useful in describing certain situations such as robbing a bank. This might involve:

• Getting a gun.
• Hold up a bank.
• Escape with the money.

Here the Props might be

• Gun, G.
• Loot, L.
• Bag, B
• Get away car, C.

The Roles might be:

• Robber, S.
• Cashier, M.
• Bank Manager, O.
• Policeman, P.

The Entry Conditions might be:

• S is poor.
• S is destitute.

The Results might be:

• S has more money.
• O is angry.
• M is in a state of shock.
• P is shot.

• If a particular script is to be applied it must be activated and the activating depends on its significance.
• If a topic is mentioned in passing then a pointer to that script could be held.
• If the topic is important then the script should be opened.
• The danger lies in having too many active scripts much as one might have too many windows open on the screen or too many recursive calls in a program.
• Provided events follow a known trail we can use scripts to represent the actions involved and use them to answer detailed questions.
• Different trails may be allowed for different outcomes of Scripts ( e.g. The bank robbery goes wrong).

Advantages of Scripts:

• Ability to predict events.
• A single coherent interpretation may be build up from a collection of observations.

Disadvantages:

• Less general than frames.
• May not be suitable to represent all kinds of knowledge.
  
  
  
  
  
  
  
  
  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

Planning System Components

Simple problem solving tasks basically involve the following tasks:

1. Choose the best rule based upon heuristics.
2. Apply this rule to create a new state.
3. Detect when a solution is found.
4. Detect dead ends so that they can be avoided.

Rule application

• Previously rules could be applied without any difficulty as complete systems were specified and rules enabled the system to progress from one state to the next.
• Now we must be able to handle rules which only cover parts of systems.
• A number of approaches to this task have been used.

Green's Approach (1969)
Basically this states that we note the changes to a state produced by the application of a rule.
Consider the problem of having two blocks A and B stacked on each other (A on top).
Then we may have an initial state  which could be described as:

    ON(

   ONTABLE(

   CLEAR( 

If we now wish to UNSTACK(A, B). We express the operation as follows:

 [CLEAR(x,s)  ON(x, y, s)] 

   [HOLDING(x, DO(UNSTACK(x,y),s)) 



    CLEAR(y,DO(UNSTACK(x,y),s))]




STRIPS (1971 ff.)

STIPS proposed another approach:



Basically each operator has three lists of predicates associated with it:

a list of things that become TRUE called ADD.
a list of things that become FALSE called DELETE.
a set of prerequisites that must be true before the operator can be applied.


Anything not in these lists is assumed to be unaffected by the operation.
This method initial implementation of STRIPS -- has been extended to include other forms of reasoning/planning (e.g. Nonmonotonic methods, Goal Stack Planning and even Nonlinear planning -- see later)


Consider the following example in the Blocks World and the fundamental operations:



STACK
-- requires the arm to be holding a block A and the other block B to be clear. Afterwards the block A is on block B and the arm is empty and these are true -- ADD; The arm is not holding a block and block B is not clear; predicates that are false DELETE;
UNSTACK
-- requires that the block A is on block B; that the arm is empty and that block A is clear. Afterwards block B is clear and the arm is holding block A - ADD; The arm is not empty and the block A is not on block B -- DELETE;

See Exercises for more examples.

We have now greatly reduced the information that needs to be held. If a new attribute is introduced we do not need to add new axioms for existing operators. Unlike in Green's method we remove the state indicator and use a database of predicates to indicate the current state

Thus if the last state was:

ONTABLE(B)  ON(A,B)  CLEAR(A)

after the unstack operation the new state is

ONTABLE(B)  CLEAR(B)  HOLDING(A)  CLEAR(A)



Goal Stack Planning

Basic Idea to handle interactive compound goals uses goal stacks, Here the stack contains :

goals,
operators -- ADD, DELETE and PREREQUISITE lists
a database maintaining the current situation for each operator used.


Consider the following where wish to proceed from the start to goal state.



Fig. 24 Goal Stack Planning Example

We can describe the start state:

ON(B, A)  ONTABLE(A)  ONTABLE(C)  ONTABLE(D)  ARMEMPTY

and goal state:

ON(C, A)  ON(B,D)  ONTABLE(A)  ONTABLE(D)



Initially the goal stack is the goal state.
We then split the problem into four subproblems
Two are solved as they already are true in the initial state -- ONTABLE(A), ONTABLE(D).




With the other two -- there are two ways to proceed:

    ON(C,A)

   ON(B,D)



   ON(C,A)   ON(B,D)



       ONTABLE(A)  
ONTABLE(D)



    ON(B,D)

   ON(C,A)



   ON(C,A)   ON(B,D)



       ONTABLE(A)  
ONTABLE(D)







The method is to

Investigate the first node on the stack ie the top goal.
If a sequence of operators is found that satisfies this goal it is removed and the next goal is attempted.
This continues until the goal state is empty.


Consider alternative 1 above further:

The first goal ON(C,A) is not true and the only operator that would make it true is STACK (C,A) which replaces ON(C,A) giving:

    B<>STACK (C,A)

   ON(B,D)



   ON(C,A)   ON(B,D)



       ONTABLE(A)  
ONTABLE(D)







STACK has prerequisites that must be met which means that block A is clear and the arm is holding block C. So we must do:

    B<>CLEAR(A)

   HOLDING(C)



   CLEAR(A)  HOLDING(C)



   STACK (C,A)



   ON(B,D)



   ON(C,A)   ON(B,D)



       ONTABLE(A)  
ONTABLE(D)







Now top goal is false and can only be made true by unstacking B. This leads to:

    B<>ON(B,A)

   CLEAR(B) 



   ARMEMPTY 



   ON(B,A)   CLEAR(B)



       ARMEMPTY



   UNSTACK(B,A)



   HOLDING(C)



   CLEAR(A)  HOLDING(C)

    


Now the first goal is true, the second is universally true, and the arm is empty. Thus all top three goals are true means that we can apply the operator UNSTACK(B,A) as all prerequisites are met. This gives us the first node in databaseONTABLE(A)  ONTABLE(C)  ONTABLE(D)  HOLDING(C)  CLEAR(A)






Note as a future reference of the use of UNSTACK(B,A) that HOLDING(B) is true as well as CLEAR(A)
The goal stack becomes
    HOLDING(C)

    CLEAR(A)  HOLDING(C)



   STACK (C,A)



   ON(B,D)



   ON(C,A)   ON(B,D)   ONTABLE(A)



       ONTABLE(D)







There are two ways we can achieve HOLDING(C) by using the operators PICKUP(C) or UNSTACK(C,x) where x is an unspecified block. This leads to two alternative paths:


 ON(C, x)

 CLEAR(C)



ARMEMPTY



ON(C, x)  CLEAR(C)



     ARMEMPTY



UNSTACK(C,x)



 CLEAR(A)  HOLDING(C)



 STACK (C,A)



 ON(B,D)



 ON(C,A)   ON(B,D)   ONTABLE(A)



    
ONTABLE(D)










1
 ONTABLE(C)

 CLEAR(C)



ARMEMPTY



ONTABLE(C)  CLEAR(C)



     ARMEMPTY



PICKUP(C)



 CLEAR(A)  HOLDING(C)



 STACK (C,A)



 ON(B,D)



 ON(C,A)   ON(B,D)   ONTABLE(A)



    
ONTABLE(D)






In this first route we can see three references to some block, x and these must refer to the same block, although in the search it is conceivable several blocks will become temporarily attached. Hence the binding of variables to blocks must be recorded. Investigating further we need to satisfy the first goal and this requires stacking C on some block which is clear.
    CLEAR(x)

   HOLDING(C)



   CLEAR(x)  HOLDING(C)



   STACK (C, x)



   CLEAR(C)



   ARMEMPTY

    


We now notice that one of the goals created is HOLDING(C) which was the goal we were trying to achieve by applying UNSTACK(C, some block) in this case and PICKUP(C) in the other approach. So it would appear that we have added new goals and not made progress and in terms of the A* algorithm it seems best to try the other approach.

So looking at the second approach

We can see that the first goal is achieved block C is on the table.
The second goal is also achieved block C is clear.
Remember that HOLDING(B) is still true which means that the arm is not empty. This can be achieved by placing B on the table or planting it on block D if it is clear.
Lookahead could be used here to compare the ADD lists of the competing operators with the goals in the goal stack and there is a match with ON(B,D) which is satisfied by STACK (B,D). This also binds some block to block D.
Applying STACK (B,D) generates extra goals CLEAR(D) and HOLDING(B)


The new goal stack becomes;
    CLEAR(D)

   HOLDING(B)



    CLEAR(D)   HOLDING(B)



   STACK (B, D)



   ONTABLE(C)  CLEAR(C)  ARMEMPTY



    PICKUP(C)

    




At this point the top goal is true and the next and thus the combined goal leading to the application of STACK (B,D), which means that the world model becomesONTABLE(A)  ONTABLE(C)  ONTABLE(D)  ON(B,D)  ARMEMPTY
This means that we can perform PICKUP(C) and then STACK (C,A)
Now coming to the goal ON(B,D) we realise that this has already been achieved and checking the final goal we derive the following plan


UNSTACK(B,A)
STACK (B,D)
PICKUP(C)
STACK (C,A)




This method produces a plan using good Artificial Intelligence techniques such as heuristics to find matching goals and the A* algorithm to detect unpromising paths which can be discarded.

UNIT-IV

ch-15Natural language processing

Natural Language Processing (NLP) refers to AI method of communicating with an intelligent systems using a natural language such as English.

Processing of Natural Language is required when you want an intelligent system like robot to perform as per your instructions, when you want to hear decision from a dialogue based clinical expert system, etc.

The field of NLP involves making computers to perform useful tasks with the natural languages humans use. The input and output of an NLP system can be −

• Speech
• Written Text

Components of NLP

There are two components of NLP as given −

Natural Language Understanding (NLU)

Understanding involves the following tasks −

• Mapping the given input in natural language into useful 
• representations.
• Analyzing different aspects of the language.

Natural Language Generation (NLG)

It is the process of producing meaningful phrases and sentences in the form of natural language from some internal representation.
It involves −
• Text planning − It includes retrieving the relevant content from knowledge base.
• Sentence planning − It includes choosing required words, forming meaningful phrases, setting tone of the sentence.
• Text Realization − It is mapping sentence plan into sentence structure.
The NLU is harder than NLG.

Difficulties in NLU

NL has an extremely rich form and structure.
It is very ambiguous. There can be different levels of ambiguity −
• Lexical ambiguity − It is at very primitive level such as word-level.
• For example, treating the word “board” as noun or verb?
• Syntax Level ambiguity − A sentence can be parsed in different ways.
• For example, “He lifted the beetle with red cap.” − Did he use cap to lift the beetle or he lifted a beetle that had red cap?
• Referential ambiguity − Referring to something using pronouns. For example, Rima went to Gauri. She said, “I am tired.” − Exactly who is tired?
• One input can mean different meanings.
• Many inputs can mean the same thing.

• Steps in NLP

  There are general five steps −
  • Lexical Analysis − It involves identifying and analyzing the structure of words. Lexicon of a language means the collection of words and phrases in a language. Lexical analysis is dividing the whole chunk of txt into paragraphs, sentences, and words.
  • Syntactic Analysis (Parsing) − It involves analysis of words in the sentence for grammar and arranging words in a manner that shows the relationship among the words. The sentence such as “The school goes to boy” is rejected by English syntactic analyzer.

• Semantic Analysis − It draws the exact meaning or the dictionary meaning from the text. The text is checked for meaningfulness. It is done by mapping syntactic structures and objects in the task domain. The semantic analyzer disregards sentence such as “hot ice-cream”.
• Discourse Integration − The meaning of any sentence depends upon the meaning of the sentence just before it. In addition, it also brings about the meaning of immediately succeeding sentence.
• Pragmatic Analysis − During this, what was said is re-interpreted on what it actually meant. It involves deriving those aspects of language which require real world knowledge.

Implementation Aspects of Syntactic Analysis

There are a number of algorithms researchers have developed for syntactic analysis, but we consider only the following simple methods −

• Context-Free Grammar
• Top-Down Parser

Let us see them in detail −

Context-Free Grammar

It is the grammar that consists rules with a single symbol on the left-hand side of the rewrite rules. Let us create grammar to parse a sentence −

“The bird pecks the grains”

Articles (DET) − a | an | the

Nouns − bird | birds | grain | grains

Noun Phrase (NP) − Article + Noun | Article + Adjective + Noun

= DET N | DET ADJ N

Verbs − pecks | pecking | pecked

Verb Phrase (VP) − NP V | V NP

Adjectives (ADJ) − beautiful | small | chirpin

These rules say that a certain symbol may be expanded in the tree by a sequence of other symbols. According to first order logic rule, if there are two strings Noun Phrase (NP) and Verb Phrase (VP), then the string combined by NP followed by VP is a sentence. The rewrite rules for the sentence are as follows −

S → NP VP

NP → DET N | DET ADJ N

VP → V NP

Lexocon −

DET → a | the

ADJ → beautiful | perching

N → bird | birds | grain | grains

V → peck | pecks | pecking

The parse tree can be created as shown −

Top-Down Parser

Here, the parser starts with the S symbol and attempts to rewrite it into a sequence of terminal symbols that matches the classes of the words in the input sentence until it consists entirely of terminal symbols.

These are then checked with the input sentence to see if it matched. If not, the process is started over again with a different set of rules. This is repeated until a specific rule is found which describes the structure of the sentence.

Merit − It is simple to implement.

Demerits −

• It is inefficient, as the search process has to be repeated if an error occurs.
• Slow speed of working.

ch-19 Common Sense Reasoning

What is Common Sense ?

• Common sense is the mental skills that most people share.

•   Common Sense is ability to analyze a situation based on its context, using millions of integrated pieces of common knowledge.

• John	McCarthy	was	the first	to talk about commonsense reasoning	in
his	paper  in	1959,	explains	that  a  program  has  commonsense	if

it automatically deduces for itself sufficiently wide class of immediate consequences of any thing

•       Time

The most basic notion of time is events. Events occur during intervals over continuous spaces of time. An interval has a start and end point and a duration between them.

Intervals can be related to one another as :

is-before,   is-after,   meets,	is-met-by, starts, is-started-by,
during,  contains,   ends,	is-ended-by and equals.
We can build a axioms with intervals	to describe events in	time.

Space

	The  Blocks  World  is  a  simple  example  of  what  we  can  model  and
	describe space. However common sense notions such as :
	place object  x  near  object  y
	are  not  accommodated. Objects  have  a  spatial extent  while  events  have  a temporal extent. We  may  try  to  extend of  common  sense  theory  of time.  But, space is  3D  and  has  many  more  relationships  than  those for  time so it  is not a good idea.                           Another  approach  is  view  objects  and  space  at  various  levels  of abstraction.  For  example,   we  can  view  most  printed  circuit  boards as  being a 2D object. Choosing  a  representation  means  selecting  relevant  properties  at particular  levels  of  granularity.  For  instance  we  can  define  relations over spaces such as inside, adjacent etc. We can also define relations for curves, lines, surfaces, planes and volumes. e.g. along, across, perpendicular etc. Materials The  Liquids provide  many  interesting  points,  such as,  the  space occupied by them. Thus we can define their properties such as: ‡ Capacity - a bound to an amount of liquid. ‡ Amount - volume occupied by a liquid. ‡ Full - if amount equals capacity. Other properties that materials can posses include: ‡ Free - if a space is not wholly contained inside another object. ‡ Surround - if enclosed by a very thin free space.                                               ‡    Rigid ‡    Flexible Particulate - e.g. sand 5. Memory Organization is  central to  common  sense  behavior  and  also  the  basis  for Memory learning. Human memory is   still   not   fully   understood   however psychologists have proposed several ideas.

■      Short term memory (STM) :

Only a few items at a time can be held here;

perceptual information are stored directly here.

■      Long term memory (LTM) :

Capacity for storage is very large and fairly permanent; LTM is often divided further as :

‡    Episodic memory :

Contains information about personal experiences.

‡    Semantic memory :

General facts with no personal meaning, e.g. Birds fly; useful in natural language understanding.

ch-20Expert Systems

Expert systems (ES) are one of the prominent research domains of AI. It is introduced by the researchers at Stanford University, Computer Science Department.

What are Expert Systems?

The expert systems are the computer applications developed to solve complex problems in a particular domain, at the level of extra-ordinary human intelligence and expertise.

Characteristics of Expert Systems

• High performance
• Understandable
• Reliable
• Highly responsive
• Components of Expert Systems

The components of ES include −

• Knowledge Base
• Inference Engine
• User Interface

Knowledge Base

It contains domain-specific and high-quality knowledge.

Knowledge is required to exhibit intelligence. The success of any ES majorly depends upon the collection of highly accurate and precise knowledge.

What is Knowledge?

The data is collection of facts. The information is organized as data and facts about the task domain. Data, information, andpast experience combined together are termed as knowledge.

Components of Knowledge Base

The knowledge base of an ES is a store of both, factual and heuristic knowledge.

• Factual Knowledge − It is the information widely accepted by the Knowledge Engineers and scholars in the task domain.
• Heuristic Knowledge − It is about practice, accurate judgement, one’s ability of evaluation, and guessing.

Knowledge representation

It is the method used to organize and formalize the knowledge in the knowledge base. It is in the form of IF-THEN-ELSE rules.

Knowledge Acquisition

The success of any expert system majorly depends on the quality, completeness, and accuracy of the information stored in the knowledge base.

The knowledge base is formed by readings from various experts, scholars, and the Knowledge Engineers. The knowledge engineer is a person with the qualities of empathy, quick learning, and case analyzing skills.

He acquires information from subject expert by recording, interviewing, and observing him at work, etc. He then categorizes and organizes the information in a meaningful way, in the form of IF-THEN-ELSE rules, to be used by interference machine. The knowledge engineer also monitors the development of the ES.

Inference Engine

Use of efficient procedures and rules by the Inference Engine is essential in deducting a correct, flawless solution.

In case of knowledge-based ES, the Inference Engine acquires and manipulates the knowledge from the knowledge base to arrive at a particular solution.

In case of rule based ES, it −

• Applies rules repeatedly to the facts, which are obtained from earlier rule application.
• Adds new knowledge into the knowledge base if required.
• Resolves rules conflict when multiple rules are applicable to a particular case.

To recommend a solution, the Inference Engine uses the following strategies −

• Forward Chaining
• Backward Chaining

Forward Chaining

It is a strategy of an expert system to answer the question,“What can happen next?”

Here, the Inference Engine follows the chain of conditions and derivations and finally deduces the outcome. It considers all the facts and rules, and sorts them before concluding to a solution.

This strategy is followed for working on conclusion, result, or effect. For example, prediction of share market status as an effect of changes in interest rates.

Backward Chaining

With this strategy, an expert system finds out the answer to the question, “Why this happened?”

On the basis of what has already happened, the Inference Engine tries to find out which conditions could have happened in the past for this result. This strategy is followed for finding out cause or reason. For example, diagnosis of blood cancer in humans.

User Interface

User interface provides interaction between user of the ES and the ES itself. It is generally Natural Language Processing so as to be used by the user who is well-versed in the task domain. The user of the ES need not be necessarily an expert in Artificial Intelligence.

It explains how the ES has arrived at a particular recommendation. The explanation may appear in the following forms −

• Natural language displayed on screen.
• Verbal narrations in natural language.
• Listing of rule numbers displayed on the screen.

The user interface makes it easy to trace the credibility of the deductions.

Requirements of Efficient ES User Interface

• It should help users to accomplish their goals in shortest possible way.
• It should be designed to work for user’s existing or desired work practices.
• Its technology should be adaptable to user’s requirements; not the other way round.
• It should make efficient use of user input.

Expert Systems Limitations

No technology can offer easy and complete solution. Large systems are costly, require significant development time, and computer resources. ESs have their limitations which include −

• Limitations of the technology
• Difficult knowledge acquisition
• ES are difficult to maintain
• High development costs

Applications of Expert System

The following table shows where ES can be applied.

Application	Description
Design Domain	Camera lens design, automobile design.
Medical Domain	Diagnosis Systems to deduce cause of disease from observed data, conduction medical operations on humans.
Monitoring Systems	Comparing data continuously with observed system or with prescribed behavior such as leakage monitoring in long petroleum pipeline.
Process Control Systems	Controlling a physical process based on monitoring.
Knowledge Domain	Finding out faults in vehicles, computers.
Finance/Commerce	Detection of possible fraud, suspicious transactions, stock market trading, Airline scheduling, cargo scheduling.

Expert System Technology

There are several levels of ES technologies available. Expert systems technologies include −

• Expert System Development Environment − The ES development environment includes hardware and tools. They are −
  • Workstations, minicomputers, mainframes.
  • High level Symbolic Programming Languages such as LISt Programming (LISP) andPROgrammation en LOGique (PROLOG).
  • Large databases.
• Tools − They reduce the effort and cost involved in developing an expert system to large extent.
  • Powerful editors and debugging tools with multi-windows.
  • They provide rapid prototyping
  • Have Inbuilt definitions of model, knowledge representation, and inference design.
• Shells − A shell is nothing but an expert system without knowledge base. A shell provides the developers with knowledge acquisition, inference engine, user interface, and explanation facility. For example, few shells are given below −
  • Java Expert System Shell (JESS) that provides fully developed Java API for creating an expert system.
  • Vidwan, a shell developed at the National Centre for Software Technology, Mumbai in 1993. It enables knowledge encoding in the form of IF-THEN rules.

Development of Expert Systems: General Steps

The process of ES development is iterative. Steps in developing the ES include −

Identify Problem Domain

• The problem must be suitable for an expert system to solve it.
• Find the experts in task domain for the ES project.
• Establish cost-effectiveness of the system.

Design the System

• Identify the ES Technology
• Know and establish the degree of integration with the other systems and databases.
• Realize how the concepts can represent the domain knowledge best.

Develop the Prototype

From Knowledge Base: The knowledge engineer works to −

• Acquire domain knowledge from the expert.
• Represent it in the form of If-THEN-ELSE rules.

Test and Refine the Prototype

• The knowledge engineer uses sample cases to test the prototype for any deficiencies in performance.
• End users test the prototypes of the ES.

Develop and Complete the ES

• Test and ensure the interaction of the ES with all elements of its environment, including end users, databases, and other information systems.
• Document the ES project well.
• Train the user to use ES.

Maintain the System

• Keep the knowledge base up-to-date by regular review and update.
• Cater for new interfaces with other information systems, as those systems evolve.

Benefits of Expert Systems

• Availability − They are easily available due to mass production of software.
• Less Production Cost − Production cost is reasonable. This makes them affordable.
• Speed − They offer great speed. They reduce the amount of work an individual puts in.
• Less Error Rate − Error rate is low as compared to human errors.
• Reducing Risk − They can work in the environment dangerous to humans.
• Steady response − They work steadily without getting motional, tensed or fatigued.

Expert System Shells

Expert system shells provide methods of building expert systems without extensive knowledge of programming through mechanisms that

•  input the decisions, questions and rules that are followed 
•  construct a knowledge database that can be manipulated by subsequent parts of the system 
•  verifies possible violations of surface validity and 
•  operates the "inference engine" that operates on the rules, poses the questions to the users, and  determines whether a particular decision is valid. 

Most expert systems also allow the user to halt the processing at any time to 

query the system why aquestion was asked, or how a decision was reached Most 

expert system shells can now run easily onmost current micro-computers and are 

able to handle the manipulation of a relatively large number of rules and 

associated questions. Expert system shells a re expert system development tools 

consisting essentially of the expertsystem without the knowledge base, 

embodying the inference engine, working memory, and the user interface (Sener, 

1991). An example of the inference engine part of an expert system that deduces 

new conclusions from known facts is illustrated below

IF liquid limit=known

AND plastic limit=known

AND plastic limit>liquid limit

THEN soil=non plastic

Expert systems give advice or solve problems by drawing upon this knowledge 

stored in the IF/THEN rules.