ARTIFICIAL INTELLIGENCE

CO1: Enumerate the history & Foundation of AI (Understand-L2)

​

CO2: Apply the Searching algorithms for AI in problem solving (Apply-L3)

CO3: Choose the appropriate representation of knowledge (Apply-L3)

​

CO4: Choose the appropriate logic concepts (Apply-L3)

​

CO5: Understand the Expert systems techniques in AI (Understand-L2)

Course Outcomes: At the end of this course

UNIT-I: Introduction:

• AI problems,
• Foundation of AI
• History of AI
• Intelligent agents: agents and environments,
• The concept of rationality,
• The nature of environments,
• Structure of agents,
• Problem solving agents,
• Problem formulation.

INTRODUCTION

• Artificial Intelligence is composed of two words Artificial and Intelligence

​

• Artificial defines "man- made,"

​

• intelligence defines "thinking power“

​

• AI means "a man-made thinking power."

​

WHAT IS ARTIFICIAL INTELLIGENCE?�

• It is a branch of Computer Science that pursues creating the computers or machines as intelligent as human beings.

​

• It is the science and engineering of making intelligent machines, especially intelligent computer programs.

​

• It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable

​

Definition of AI:

• Artificial Intelligence is the study of how to make computers do things, which, at the moment, people do better.

​

• 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,
• a software think intelligently, in the similar manner the intelligent humans think.

​

FOUNDATIONS OF AI

1. PHILOSOPHY
2. MATHEMATICS
3. ECONOMICS
4. NEUROSCIENCE
5. PSYCHOLOGY
6. COMPUTER ENGINEERING
7. CONTROL THEORY
8. LINGUISTICS

​

​

​

PHILOSOPHY

• Philosophical inquiries about the mind and reasoning groundwork for AI's theoretical frameworks. 
• Can formal rules be used to draw valid conclusions?
• How does the mind arise from a physical brain?
• Where does knowledge come from?
• How does knowledge lead to action?

Aristotle (384–322 B.C.), was the first to formulate a precise set of laws governing the rational part of the mind. He developed an informal system of syllogisms for proper reasoning, which in principle allowed one to generate conclusions mechanically, given initial premises.

Example: All dogs are animals and all animals have 4 legs .

-i.e All doges have 4 legs.

​

HISTORY OF ARTIFICIAL INTELLIGENCE

​

HISTORY OF ARTIFICIAL INTELLIGENCE

​

Maturation of Artificial Intelligence (1943-1952)

​

• Year 1943 : The first work which is now recognized as AI was done by Warren McCulloch and Walter pits in 1943. They proposed a model of artificial neurons.

​

• Year 1949: Donald Hebb demonstrated an updating rule for modifying the connection strength between neurons. His rule is now called Hebbian learning.

​

• Year 1950: The Alan Turing who was an English mathematician and pioneered Machine learning in 1950. Alan Turing publishes "Computing Machinery and Intelligence" in which he proposed a test. The test can check the machine's ability to exhibit intelligent behavior equivalent to human intelligence, called a Turing test.

​

The birth of Artificial Intelligence (1952-1956)

• Year 1955: An Allen Newell and Herbert A. Simon created the "first artificial intelligence program"Which was named as "Logic Theorist". This program had proved 38 of 52 Mathematics theorems, and find new and more elegant proofs for some theorems.
• Year 1956: The word "Artificial Intelligence" first adopted by American Computer scientist John McCarthy at the Dartmouth Conference. For the first time, AI coined as an academic field.

At that time high-level computer languages such as FORTRAN, LISP, or COBOL were invented. And the enthusiasm for AI was very high at that time.

​

The golden years-Early enthusiasm (1956-1974)

​

• Year 1966: The researchers emphasized developing algorithms which can solve mathematical problems. Joseph Weizenbaum created the first chatbot in 1966, which was named as ELIZA.

​

• Year 1972: The first intelligent humanoid robot was built in Japan which was named as WABOT-1.

​

The first AI winter (1974-1980)

​

• The duration between years 1974 to 1980 was the first AI winter duration. AI winter refers to the time period where computer scientist dealt with a severe shortage of funding from government for AI researches.

​

• During AI winters, an interest of publicity on artificial intelligence was decreased.

​

A boom of AI (1980-1987):-

​

• Year 1980: After AI winter duration, AI came back with "Expert System". Expert systems were programmed that emulate the decision-making ability of a human expert
• In the Year 1980, the first national conference of the American Association of Artificial Intelligence was held at Stanford University.

​

​

The second AI winter (1987-1993)

• The duration between the years 1987 to 1993 was the second AI Winter duration.Again Investors and government stopped in funding for AI research as due to high cost but not efficient result. The expert system such as XCON was very cost effective.

​

The emergence of intelligent agents (1993-2011)

​

• Year 1997: In the year 1997, IBM Deep Blue beats world chess champion, Gary Kasparov, and became the first computer to beat a world chess champion.

​

• Year 2002: for the first time, AI entered the home in the form of Roomba, a vacuum cleaner.

​

• Year 2006: AI came in the Business world till the year 2006. Companies like Facebook, Twitter, and Netflix also started using AI.

​

Deep learning, big data and artificial general intelligence (2011-present)

​

• Year 2011: In the year 2011, IBM's Watson won jeopardy, a quiz show, where it had to solve the complex questions as well as riddles. Watson had proved that it could understand natural language and can solve tricky questions quickly.

​

• Year 2012: Google has launched an Android app feature "Google now", which was able to provide information to the user as a prediction.

​

• Year 2014: In the year 2014, Chatbot "Eugene Goost man" won a competition in the infamous "Turing test."

​

• Year 2018: The "Project Debater" from IBM debated on complex topics with two master debaters and also performed extremely well.

​

• Google has demonstrated an AI program "Duplex" which was a virtual assistant and which had taken hairdresser appointment on call, and lady on other side didn't notice that she was talking with the machine.

​

APPLICATION OF AI

AGENTS

AND

ENVIRONMENTS

​

​

AGENT is a particular thing or particular equipment.

Environment what is able to see?

​

• Agent sense the Environment.
• Agent can react with environment by sensors.

Through Sensors and act on their environment.

Through Actuators is a machine to operate.

​

Definition of Agent:-

An Agent can be anything that perceive environment through sensors and act upon that environment through actuators.

​

Types of Agents:-

​

HUMAN-AGENT: A human agent has eyes, ears, and other organs which work for sensors and hand, legs, vocal tract work for actuators.

​

ROBOTIC AGENT: A robotic agent can have cameras, infrared range finder, NLP for sensors and various motors for actuators.

​

SOFTWARE AGENT: Software agent can have keystrokes, file contents as sensory input and act on those inputs and display output on the screen.

​

EXAMPLE FOR AGENT AND ENVIRONMENTS?

HOW DOES THE AGENT INTERACT WITH THE ENVIRONMENT?

The agents interact with the environment in two ways:

1.PERCEPTION

Perception is a passive interaction, where the agent gains information about the environment without changing the environment. The sensors of the robot help it to gain information about the surroundings without affecting the surrounding. Hence, gaining information through sensors is called perception.

2.ACTION

Action is an active interaction where the environment is changed. When the robot moves an obstacle using its arm, it is called an action as the environment is changed. The arm of the robot is called an “Effector” as it performs the action.

​

CONSIDER A VACUUM CLEANER WORLD

Imagine that our intelligent agent is a robot vacuum cleaner.

​

Let's suppose that the world has just two rooms. The robot can be in either room and there can be dirt in zero, one, or two rooms.

MEASURING PERFORMANCE

With any intelligent agent, we want it to find a (good) solution and not spend forever doing it.

The interesting quantities are, therefore,

THE SEARCH COST--how long the agent takes to come up with the solution to the problem,

and

THE PATH COST--how expensive the actions in the solution are.

The total cost of the solution is the sum of the above two quantities.

​

THE CONCEPT OF RATIONALITY

​

INTELLIGENT AGENTS:

An intelligent agent is an autonomous entity which act upon an environment using sensors and actuators for achieving goals. An intelligent agent may learn from the environment to achieve their goals. A thermostat is an example of an intelligent agent.

Following are the main four rules for an AI agent:

ØRule 1: An AI agent must have the ability to perceive the environment.

​

ØRule 2: The observation must be used to make decisions.

​

ØRule 3: Decision should result in an action.

​

ØRule 4: The action taken by an AI agent must be a rational action.

​

RATIONAL AGENT:

A rational agent is an agent which has clear preference, models uncertainty, and acts in a way to maximize its performance measure with all possible actions.

A rational agent is said to perform the right things. AI is about creating rational agents to use for game theory and decision theory for various real- world scenarios.

For an AI agent, the rational action is most important because in AI reinforcement learning algorithm, for each best possible action, agent gets the positive reward and for each wrong action, an agent gets a negative reward.

NOTE: Rational agents in AI are very similar to intelligent agents.

​

Essentially, all rational agents are intelligent agents, but not all intelligent agents are rational. While an intelligent agent can learn and adapt, a rational agent focuses on making the most logical and optimal choices based on information and goals.

RATIONALITY:

The rationality of an agent is measured by its performance measure. Rationality can be judged on the basis of following points:

• Performance measure which defines the success criterion.
• Agent prior knowledge of its environment.
• Best possible actions that an agent can perform.
• The actions that the agent can perform.
• The agent’s percept sequence to date.

​

NOTE: Rationality differs from Omniscience because an Omniscient agent knows the actual outcome of its action and act accordingly, which is not possible in reality.

​

To design a rational agent we need to specify a task environment

A problem specification for which the agent is a solution

PEAS Representation

PEAS is a type of model on which an AI agent works upon. When we define an AI agent or rational agent, then we can group its properties under PEAS representation model. It is made up of four words:

P: Performance measure

E: Environment

A: Actuators

S: Sensors

Here performance measure is the objective for the success of an agent's behaviour.

​

Performance measure: ? Environment: ?

Actuators: ? Sensors: ?

Performance measure:

safe, fast, legal, comfortable, maximize profits

​

Environment:

roads, other traffic, pedestrians, customers

​

Actuators:

steering, accelerator, brake, signal, horn

​

Sensors:

cameras, sonar, speedometer, GPS

PEAS: SPECIFYING AN AUTOMATED TAXI DRIVER

PEAS: SPECIFYING AN AUTOMATED TAXI DRIVER

PERFORMANCE MEASURE: Healthy patient, minimize costs, lawsuits

​

ENVIRONMENT: Patient, hospital, staff

​

ACTUATORS: Screen display (form including: questions, tests, diagnoses, treatments,

referrals)

​

SENSORS: Keyboard (entry of symptoms, findings, patient's answers)

​

Example of Agents with their PEAS representation

THE NATURE OF ENVIRONMENTS

• An environment in artificial intelligence is the surrounding of the agent. The agent takes

input from the environment through sensors and delivers the output to the environment through actuators.

• An environment is everything in the world which surrounds the agent, but it is not a part of an agent itself. An environment can be described as a situation in which an agent is present.
• The environment is where agent lives, operate and provide the agent with something to sense and act upon it. An environment is mostly said to be non-feministic.

FEATURES OF ENVIRONMENT

As per Russell and Norvig, an environment can have various features from the point of view of an agent:

1. Fully observable vs Partially Observable
2. Static vs Dynamic
3. Discrete vs Continuous
4. Deterministic vs Stochastic
5. Single-agent vs Multi-agent
6. Episodic vs sequential
7. Known vs Unknown
8. Accessible vs Inaccessible

1. FULLY OBSERVABLE VS PARTIALLY OBSERVABLE:
• If an agent sensor can sense or access the complete state of an environment at each point of time

then it is a fully observable environment, else it is partially observable.

• A fully observable environment is easy as there is no need to maintain the internal state to keep track history of the world.
• An agent with no sensors in all environments then such an environment is called as unobservable.

​

2. DETERMINISTIC VS STOCHASTIC:
• If an agent's current state and selected action can completely determine the next state of the environment, then such environment is called a deterministic environment.
• A stochastic environment is random in nature and cannot be determined completely by an agent.
• In a deterministic, fully observable environment, agent does not need to worry about uncertainty.

3. EPISODIC VS SEQUENTIAL:
• In an episodic environment, there is a series of one-shot actions, and only the current percept is

required for the action.

• However, in Sequential environment, an agent requires memory of past actions to determine the next best actions.

and operating by itself then such an

4. SINGLE-AGENT VS MULTI-AGENT
• If only one agent is involved in an environment, environment is called single agent environment.

• However, if multiple agents are operating in an environment, then such an environment is called

a multi-agent environment.

• The agent design problems in the multi-agent environment are different from single agent environment.

5. STATIC VS DYNAMIC:
• If the environment can change itself while an agent is deliberating then such environment is

called a dynamic environment else it is called a static environment.

• Static environments are easy to deal because an agent does not need to continue looking at the world while deciding for an action.
• However for dynamic environment, agents need to keep looking at the world at each action.
• Taxi driving is an example of a dynamic environment whereas Crossword puzzles are an example of a static environment.

6. DISCRETE VS CONTINUOUS:
• If in an environment there are a finite number of percepts and actions that can be performed within it, then such an environment is called a discrete environment else it is called continuous environment.
• A chess game comes under discrete environment as there is a finite number of moves that can be performed.
• A self-driving car is an example of a continuous environment.

7. ACCESSIBLE VS INACCESSIBLE

• If an agent can obtain complete and accurate information about the state's environment, then such

an environment is called an Accessible environment else it is called inaccessible.

• An empty room whose state can be defined by its temperature is an example of an accessible environment.

8. KNOWN VS UNKNOWN

• Known and unknown are not actually a feature of an environment, but it is an agent's state of

​

knowledge to perform an action.

​

• In a known environment, the results for all actions are known to the agent. While in unknown

​

environment, agent needs to learn how it works in order to perform an action.

• It is quite possible that a known environment to be partially observable and an Unknown environment to be fully observable.

THE STRUCTURE OF

AGENTS

THE STRUCTURE OF AGENTS

The task of AI is to design an agent program which implements the agent function. The structure of an intelligent agent is a combination of architecture and agent program. It can be viewed as:

​

Agent = Architecture + Agent program

​

Architecture: Architecture is machinery that an AI agent executes on. Agent Function: Agent function is used to map a percept to an action. f:P* → A

Agent program: Agent program is an implementation of agent function. An agent

program executes on the physical architecture to produce function f.

TYPES OF AI AGENTS

Agents can be grouped into five classes based on their degree of perceived intelligence and

capability. All these agents can improve their performance and generate better action over the time. These are given below:

• Simple Reflex Agent

​

• Model-based reflex agent

​

• Goal-based agents

​

• Utility-based agent

​

• Learning agent

1. SIMPLE REFLEX AGENT:
• The Simple reflex agents are the simplest agents. These agents take decisions on the basis of the current percepts and ignore the rest of the percept history.
• These agents only succeed in the fully observable environment.
• The Simple reflex agent does not consider any part of percepts history during their decision and action process.
• The Simple reflex agent works on Condition-action rule, which means it maps the current state to

action. Such as a Room Cleaner agent, it works only if there is dirt in the room.

• Problems for the simple reflex agent design approach:
• They have very limited intelligence
• They do not have knowledge of non-perceptual parts of the current state
• Mostly too big to generate and to store.
• Not adaptive to changes in the environment.

Schematic diagram of a simple reflex agent.

2. MODEL-BASED REFLEX AGENT
• The Model-based agent can work in a partially observable environment, and track the situation.
• A model-based agent has two important factors:
• Model: It is knowledge about "how things happen in the world," so it is called a Model-based agent.
• Internal State: It is a representation of the current state based on percept history.
• These agents have the model, "which is knowledge of the world" and based on the model

they perform actions.

• Updating the agent state requires information about:
• How the world evolves
• How the agent's action affects the world.

A model-based reflex agent.

3. GOAL-BASED AGENTS

• The knowledge of the current state environment is not always sufficient to decide for an

​

agent to what to do.

​

• The agent needs to know its goal which describes desirable situations.

​

• Goal-based agents expand the capabilities of the model-based agent by having the "goal"

​

information.

​

• They choose an action, so that they can achieve the goal.

​

• These agents may have to consider a long sequence of possible actions before deciding

​

whether the goal is achieved or not. Such considerations of different scenario are called

​

searching and planning, which makes an agent proactive.

4. UTILITY-BASED AGENTS

• These agents are similar to the goal-based agent but provide an extra component of utility

​

measurement which makes them different by providing a measure of success at a given

​

state.

​

• Utility-based agent act based not only goals but also the best way to achieve the goal.

​

• The Utility-based agent is useful when there are multiple possible alternatives, and an

​

agent has to choose in order to perform the best action.

​

• The utility function maps each state to a real number to check how efficiently each action

​

achieves the goals.

5. LEARNING AGENTS

• A learning agent in AI is the type of agent which can learn from its past experiences, or it has

learning capabilities.

• It starts to act with basic knowledge and then able to act and adapt automatically through learning.
• A learning agent has mainly four conceptual components, which are:
• Learning element: It is responsible for making improvements by learning from environment
• Critic: Learning element takes feedback from critic which describes that how well the agent is

doing with respect to a fixed performance standard.

• Performance element: It is responsible for selecting external action
• Problem generator: This component is responsible for suggesting actions that will lead to new and informative experiences.
• Hence, learning agents are able to learn, analyze performance, and look for new ways to improve the performance.

A general learning agent.

PROBLEM-SOLVING AGENT

PROBLEM-SOLVING AGENT

The problem-solving agent performs precisely by defining problems and its several solutions.

• According to psychology, “a problem-solving refers to a state where we wish to reach to a

definite goal from a present state or condition.”

• According to computer science, a problem-solving is a part of artificial intelligence which

encompasses a number of techniques such as algorithms, heuristics to solve a problem.

​

STEPS PERFORMED BY PROBLEM-SOLVING AGENT

​

Goal Formulation: It is the first and simplest step in problem-solving.

• It organizes the steps/sequence required to formulate one goal out of multiple goals as well as actions to achieve that goal.
• Goal formulation is based on the current situation and the agent’s performance measure

(discussed below).

Problem Formulation: It is the most important step of problem-solving which decides what actions should be taken to achieve the formulated goal.

​

There are following five components involved in problem formulation:

​

• Initial State: It is the starting state or initial step of the agent towards its goal.

​

• Actions: It is the description of the possible actions available to the agent.

​

• Transition Model: It describes what each action does.

​

• Goal Test: It determines if the given state is a goal state.
• Path cost: It assigns a numeric cost to each path that follows the goal. The problem-solving agent selects a cost function, which reflects its performance measure. Remember, an optimal solution has the lowest path cost among all the solutions.

• Search: It identifies all the best possible sequence of actions to reach the goal state from the current

​

state. It takes a problem as an input and returns solution as its output.

• Solution: It finds the best algorithm out of various algorithms, which may be proven as the best optimal solution.
• Execution: It executes the best optimal solution from the searching algorithms to reach the goal state from the current state.

NOTE: Initial state, actions, and transition model together define the state-space of the problem implicitly. State-space of a problem is a set of all states which can be reached from the initial state followed by any sequence of actions. The state-space forms a directed map or graph where nodes are the states, links between the nodes are actions, and the path is a sequence of states connected by the sequence of actions.

EXAMPLE PROBLEMS

Basically, there are two types of problem approaches:

• Toy Problem: It is a concise and exact description of the problem which is used by the researchers to compare the performance of algorithms.
• Real-world Problem: It is real-world based problems which require solutions. Unlike a toy problem, it does not depend on descriptions, but we can have a general formulation of the

problem.

SOME TOY PROBLEMS

8 Puzzle Problem: Here, we have a 3×3 matrix with movable tiles numbered from 1 to 8 with a blank space. The tile adjacent to the blank space can slide into that space. The objective is to reach a specified goal state similar to the goal state, as shown in the below figure.

SOME TOY PROBLEMS

THE PROBLEM FORMULATION IS AS FOLLOWS:

• States: It describes the location of each numbered tiles and the blank tile.
• Initial State: We can start from any state as the initial state.
• Actions: Here, actions of the blank space is defined, i.e., either left, right, up or down
• Transition Model: It returns the resulting state as per the given state and actions.
• Goal test: It identifies whether we have reached the correct goal-state.
• Path cost: The path cost is the number of steps in the path where the cost of each step is 1.

EIGHT PUZZLE PROBLEM

• We also know the eight-puzzle problem by the name of N puzzle problem or sliding puzzle problem.
• N-puzzle that consists of N tiles (N+1 titles with an empty tile) where N can be 8, 15, 24 and so on.
• In our example N = 8. (that is square root of (8+1) = 3 rows and 3 columns).
• In the same way, if we have N = 15, 24 in this way, then they have Row and columns as

follow (square root of (N+1) rows and square root of (N+1) columns).

• That is if N=15 than number of rows and columns= 4, and if N= 24 number of rows and columns= 5.
• So, basically in these types of problems we have given a initial state or initial configuration (Start state) and a Goal state or Goal Configuration.

Here We are solving a problem of 8 puzzle that is a 3x3 matrix.

The puzzle can be solved by moving the tiles one by one in the single empty space and thus achieving the Goal state.

Rules of solving puzzle

Instead of moving the tiles in the empty space we can visualize moving the empty space in place

of the tile.

The empty space can only move in four directions (Movement of empty space) Up Down Right or Left

The empty space cannot move diagonally and can take only one step at a time.

You are given with 2 Jugs, 4 Gallon and a 3 Gallon one. Neither of the jugs has any Measuring marks on it. There is a pump that can be used to fill the jugs with water. How can we get exactly 2 Gallons of water in 4 Gallon Jug?

​

start state : (0,0)

goal state : (2,n) where n = any value