Software Engineering

Course Code : CSE3005

Course Credit : 4
Course Type : LTP

Dr. Pranshu Pranjal

(MTech & PhD, IIT (ISM) Dhanbad)
Assistant Professor (AB 125/122)
Division - Artificial Intelligence & Machine Learning,
School of Computing Science and Engineering,
VIT Bhopal University, Bhopal-Indore Highway,
Kothrikalan, Sehore, Madhya Pradesh - 466114
Contact No.: {M} (+91) 8979609032
Email: pranshupranjal@[Link]
Module 1: INTRODUCTION
• Introduction
• Definition
• Future of Artificial Intelligence Characteristics of Intelligent Agents
• Typical Intelligent Agents
• Problem Solving Agents
• Approach to Typical AI problems.
On the Verge of Major Breakthroughs
Artificial Intelligence (AI) has been moving extremely quickly in
the last few years, demonstrating a potential to revolutionize every
aspect of our lives

Work Economy
Medicine
Mobility
What is Artificial Intelligence?

* In today's world, technology is growing very fast, and we are getting in touch with
different new technologies day by day.

* One of the booming technologies of computer science is Artificial Intelligence which

is ready to create a new revolution in the world by making intelligent machines.

* The Artificial Intelligence is now all around us. It is currently working with a variety
of subfields, ranging from general to specific, such as self-driving cars, playing chess,
proving theorems, playing music, etc.
What is Artificial Intelligence?

* AI holds a tendency to cause a machine to work as a human.

* Artificial Intelligence is composed of two words Artificial and Intelligence, where

Artificial defines "man-made," and intelligence defines "thinking power", hence AI
means "a man-made thinking power.”

* we can define AI as:

"It is a branch of computer science by which we can create intelligent machines
which can behave like a human, think like humans, and able to make decisions.“
What is Artificial Intelligence?

* InArtificial Intelligence you do not need to pre-program the machine to do

some work. Instead you have to create a machine with programmed algorithm
which can work with own intelligence.

* Artificial Intelligence exists when a machine can have human based skills such as
learning, reasoning, and solving problems.
Why Artificial Intelligence?

* Before Learning about Artificial Intelligence, we should know that what is the
importance of AI and why should we learn it. Following are some main reasons
to learn about AI:
* With the help of AI, you can create software or devices which can solve real-
world problems very easily and with accuracy such as health issues, marketing,
traffic issues, etc.
* Withthe help of AI, you can create your personal virtual Assistant, such as
Google Assistant, Siri, etc.
Why Artificial Intelligence?
* With the help of AI, you can build such Robots which can work in an
environment where survival of humans can be at risk.
* AI opens a path for other new technologies, new devices, and new
Opportunities.
Applications of AI
But, What is AI ?
AI can be broadly defined as technology that can learn and
produce intelligent behavior

Input Output
An AI
Pixels: Process “Tuberculosis”
But, What is AI ?
AI can be broadly defined as technology that can learn and
produce intelligent behavior

Input Output

An AI Process “Four kids are playing

Pixels:
with a ball”
Applications of AI
AI can be broadly defined as technology that can learn and
produce intelligent behavior

Input Output
Audio Clip: An AI Process “I feel some eye pain”

Speech Recognition
Artificial Intelligence
- Artificial Intelligence is composed of two words Artificial and Intelligence, where Artificial

defines "man-made," and intelligence defines "thinking power", hence AI means "a man-made

thinking power."

- Enables the machine to think and perform task without any human intervention

- Generates / Calculate / Improvise the data to give desired output

- It has an ability to discover, ability to infer, ability to figure things

- Example: (NLP, VISION, TXT-> SPEECH, Motion/Robotics)

- Search based AI

- Statistics based AI

- Using previous history when the computer works -> Machine Learning
 Machine Learning is said as a subset of artificial intelligence that is mainly concerned with the development of algorithms which allow a
computer to learn from the data and past experiences on their own. The term machine learning was first introduced by Arthur
Samuel in 1959. We can define it in a summarized way as:

A machine has the ability to learn if it can improve its performance by gaining more data.

How does Machine Learning work

A Machine Learning system learns from historical data, builds the prediction models, and whenever it receives new data, predicts
the output for it. The accuracy of predicted output depends upon the amount of data, as the huge amount of data helps to build a better
model which predicts the output more accurately.
Steps in Machine Learning process
Classification of Machine Learning
At a broader level, machine learning can be classified into three types:

1. Supervised learning

– Given: training data + desired outputs (labelled)

2. Unsupervised learning

– Given: training data + a few desired outputs (unlabeled)

3. Reinforcement learning

– Rewards from sequence of actions

1) Supervised Learning

• Supervised learning is a type of machine learning method in which we provide sample of labeled data to the machine learning

system in order to train it, and on that basis, it predicts the output.

• The system creates a model using labeled data to understand the datasets and learn about each data, once the training and

processing are done then we test the model by providing a sample data to check whether it is predicting the exact output or not.

• The goal of supervised learning is to map input data with the output data.

• The supervised learning is based on supervision, and it is the same as when a student learns things in the supervision of the

teacher. The example of supervised learning is spam filtering.

Supervised learning can be grouped further in two categories of algorithms:

• Classification
• Regression
Some of the popular supervised learning algorithms are:
1. Linear Regression: It is a simple algorithm used for regression tasks. It models the relationship between the input features and the target
variable using a linear function.
2. Logistic Regression: This algorithm is used for binary classification problems. It models the probability of an input belonging to a certain
class using a logistic function.
3. Decision Trees: Decision trees are versatile algorithms that can be used for both classification and regression tasks. They create a flowchart-
like structure to make decisions based on the input features.
4. Random Forest: Random Forest is an ensemble learning method that combines multiple decision trees to make predictions. It is robust and
can handle high-dimensional data with complex relationships.
5. Support Vector Machines (SVM): SVM is a powerful algorithm for both classification and regression tasks. It finds an optimal hyperplane that
separates different classes in the input space.
6. k-Nearest Neighbors (k-NN): k-NN is a non-parametric algorithm that makes predictions based on the k closest training examples in the
feature space. It can be used for both classification and regression.
7. Neural Networks: Neural networks are a versatile class of algorithms inspired by the human brain. They consist of interconnected nodes
(neurons) organized in layers and can handle complex patterns and large datasets.
2) Unsupervised Learning

• Unsupervised learning is a learning method in which a machine learns without any supervision.

• The training is provided to the machine with the set of data that has not been labeled, classified, or categorized, and the algorithm

needs to act on that data without any supervision.

• The goal of unsupervised learning is to restructure the input data into new features or a group of objects with similar patterns.

• In unsupervised learning, we don't have a predetermined result. The machine tries to find useful insights from the huge amount

of data.

It can be further classifieds into two categories of algorithms:

• Clustering
• Association
Some of the popular unsupervised learning algorithms are:
1. Clustering Algorithms:
1. K-means: It partitions the data into k clusters based on the similarity of the feature vectors.
2. Hierarchical Clustering: It creates a tree-like structure (dendrogram) to represent the relationships between data points, forming
clusters at different levels of the tree.
2. Dimensionality Reduction Algorithms:
1. Principal Component Analysis (PCA): It finds a lower-dimensional representation of the data by identifying the directions of maximum
variance.
2. Auto-encoders: These are neural network architectures that learn to encode and decode the data, effectively reducing its
dimensionality while preserving important features.
3. Anomaly Detection Algorithms:
1. Isolation Forest: It identifies anomalies in the data by isolating instances that are easier to separate from the rest.
2. One-Class SVM: It learns the boundary of normal data points and detects anomalies as data points lying outside. Association Rule
Learning:
3. Apriori Algorithm: It discovers frequent item sets in transactional data and generates association rules based on the presence of these
item sets.
3) Reinforcement Learning

• Reinforcement learning is a feedback-based learning method, in which a learning agent gets a reward for each right action

and gets a penalty for each wrong action.

• The agent learns automatically with these feedbacks and improves its performance. In reinforcement learning, the agent

interacts with the environment and explores it.

• The goal of an agent is to get the most reward points, and hence, it improves its performance.

• The robotic dog, which automatically learns the movement of his arms, is an example of Reinforcement learning.

Other Examples:
– Credit assignment problem
– Game playing
– Robotics
– Balance a pole on your hand
Some of the common reinforcement learning algorithms:

1.Q-Learning: Q-Learning is a model-free RL algorithm that learns an action-value function called Q-function. It uses a table or a function

approximator to estimate the value of taking a particular action in a given state.

[Link] Q-Network (DQN): DQN is an extension of Q-Learning that uses deep neural networks to estimate the Q-function. It can handle high-

dimensional state spaces and has been successfully applied to complex tasks in Atari games.

[Link] Gradient Methods: Policy gradient methods directly learn a parameterized policy that maps states to actions. They use gradient

ascent to update the policy parameters based on the expected cumulative rewards.

[Link] Policy Optimization (PPO): PPO is a policy optimization algorithm that iteratively updates a policy by maximizing a surrogate

objective function. It aims to strike a balance between policy updates and avoiding large policy changes.

[Link] Deterministic Policy Gradient (DDPG): DDPG is an algorithm that combines deep neural networks with deterministic policy gradient

methods. It is primarily used for continuous action spaces.

Why Artificial Intelligence?
Before Learning about Artificial Intelligence, we should know that what is the
importance of AI and why should we learn it. Following are some main reasons to
learn about AI:
 With the help of AI, you can create such software or devices which can solve real-
world problems very easily and with accuracy such as health issues, marketing,
traffic issues, etc.
 With the help of AI, you can create your personal virtual Assistant, such as
Cortana, Google Assistant, Siri, etc.
 With the help of AI, you can build such Robots which can work in an environment
where survival of humans can be at risk.
 AI opens a path for other new technologies, new devices, and new Opportunities.
Goals of Artificial Intelligence
Following are the main goals of Artificial Intelligence:
1. Replicate human intelligence
2. Solve Knowledge-intensive tasks
3. An intelligent connection of perception and action
4. Building a machine which can perform tasks that requires human intelligence such
as:
• Proving a theorem
• Playing chess
• Plan some surgical operation
• Driving a car in traffic
5. Creating some system which can exhibit intelligent behavior, learn new things by
itself, demonstrate, explain, and can advise to its user.
Artificial Intelligence
Artificial Intelligence
Deep Learning (DL)
Machine Learning (ML)
Artificial Intelligence (AI)

Computer Science

Math Physics Chemistry Biology

Complex branch of DL, ex. ChatGPT, DALL-E, Midjourney

GenAI Mimic human brain, biologically inspired, multi layered neural network

AI ML DL Statistical tool to learn from data, like; clustering algo, binary classification etc.
What is AI? (Cont’d)
What’s easy and what’s hard?
• It’s been easier to mechanize many of the high level cognitive tasks we usually
associate with “intelligence” in people
– e. g., symbolic integration, proving theorems, playing chess, some aspect of
medical diagnosis, etc.

• It’s been very hard to mechanize tasks that animals can do easily
– walking around without running into things
– catching prey and avoiding predators
– interpreting complex sensory information (visual, aural, …)
– modeling the internal states of other animals from their behavior
– working as a team (ants, bees)

• Why are some complex problems (e.g., solving differential equations, database
operations) are not subjects of AI?
 History of AI
• AI has roots in a number of scientific disciplines
– computer science and engineering (hardware and software)
– philosophy (rules of reasoning)
– mathematics (logic, algorithms, optimization)
– cognitive science and psychology (modeling high level human/animal thinking)
– neural science (model low level human/animal brain activity)
– linguistics
• The birth of AI (1943 – 1956)
– McCulloch and Pitts (1943): simplified mathematical model of neurons (resting/firing
states) can realize all propositional logic primitives (can compute all Turing computable
functions)
– Alan Turing: Turing machine and Turing test (1950)
– Claude Shannon: information theory; possibility of chess playing computers
– Boole, Aristotle, Euclid (logics, syllogisms)
• Early enthusiasm (1952 – 1969)
– 1956 Dartmouth conference
John McCarthy (Lisp);
Marvin Minsky (first neural network machine);
Alan Newell and Herbert Simon (GPS);
– Emphasis on intelligent general problem solving
GSP (means-ends analysis);
Lisp (AI programming language);
Resolution by John Robinson (basis for automatic theorem proving);
heuristic search (A*, AO*, game tree search)
• Emphasis on knowledge (1966 – 1974)
– domain specific knowledge is the key to overcome existing difficulties
– knowledge representation (KR) paradigms
– declarative vs. procedural representation
• Knowledge-based systems (1969 – 1999)
– DENDRAL: the first knowledge intensive system (determining 3D structures of complex
chemical compounds)
– MYCIN: first rule-based expert system (containing 450 rules for diagnosing blood
infectious diseases)
EMYCIN: an ES shell
– PROSPECTOR: first knowledge-based system that made significant profit (geological
ES for mineral deposits)
• AI became an industry (1980 – 1989)
– wide applications in various domains
– commercially available tools
– AI winter
• Current trends (1990 – present)
– more realistic goals
– more practical (application oriented)
– distributed AI and intelligent software agents
– resurgence of natural computation - neural networks and emergence of genetic
algorithms – many applications
– dominance of machine learning (big apps)
Agents in Artificial Intelligence
An AI system can be defined as the study of the rational agent and its environment. The
agents sense the environment through sensors and act on their environment through actuators.
An AI agent can have mental properties such as knowledge, belief, intention, etc.

What is an Agent?
An agent can be anything that perceives the environment through sensors and act upon that
environment through actuators. An Agent runs in the cycle of perceiving, thinking,
and acting. An agent can be:-
• 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.
Agents in Artificial Intelligence
Sensor: Sensor is a device which detects the change in the environment and
sends the information to other electronic devices. An agent observes its
environment through sensors.
Actuators: Actuators are the component of machines that converts energy
into motion. The actuators are only responsible for moving and controlling a
system. An actuator can be an electric motor, gears, rails, etc.
Agents in Artificial Intelligence

Effectors: Effectors are the devices which affect the environment. Effectors
can be legs, wheels, arms, fingers, wings, fins, and display screen.
Structure of an AI Agent
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: The agent function is used to map a percept to an action.

f:P* → A

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

program executes on the physical architecture to produce function f.
Fundamental in AI and ML 43
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 behavior.
PEAS for self-driving cars:

Let's suppose a self-driving car then PEAS representation will be:

Performance: Safety, time, legal drive, comfort

Environment: Roads, other vehicles, road signs, pedestrian

Actuators: Steering, accelerator, brake, signal, horn

Sensors: Camera, GPS, speedometer, odometer, accelerometer, sonar.

Example of Agents with their PEAS
representation

Performance
Agent Environment Actuator Sensor
Measure
• Healthy
Patient • Hospital • Prescription, • Symptoms
Medical
• Minimized • Doctors Diagnosis, • Patient’s
Diagnosis
Cost • Patients • Scan report response
Example of Agents with their PEAS
representation

Performance
Agent Environment Actuator Sensor
Measure
Classroom,
Subject • Maximize Desk, Chair, Smart displays, Eyes, Ears,
Tutoring scores Board, Staff, Corrections Notebooks
Students
Example of Agents with their PEAS
representation

Performance
Agent Environment Actuator Sensor
Measure
Vacuum • Cleanness • Room • Wheels • Camera
Cleaner • Efficiency • Table • Brushes • Dirt detection
• Battery life • Wood floor • Vacuum sensor
• Security • Carpet Extractor • Cliff sensor
• Various • Bump Sensor
obstacles • Infrared Wall
Sensor
PEAS Examples
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/sense 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.

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
Types of AI Agents
1. Simple Reflex agent:

* The Simple reflex agents are the simplest agents. These agents take decisions based on the
current percepts and ignore the rest of the past 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.
1. Simple Reflex agent:

* 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
* Operating in a fully observable environment.
* Not adaptive to changes in the environment.
2. Model-based reflex agent:

* It works by finding a rule whose condition matches the current situation.

* 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.

* Consider previous input while performing action

* Updating the agent state requires information about:

* How the world evolves

* How the agent's action affects the world

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.

* Expansion of model-based reflex agent

* The agent needs to know its goal which describes 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.

* The goal based agent focuses only on reaching the goal set and hence the decision took
by the agent is based on how far it is currently from their goal of desired state.
3. Goal-based agents:

* Their every action is intended to minimize their distance from the goal.
* This agent is more flexible and the agent develops the decision making skill by
choosing the right from the various option available.

* To reach the Goal state, it require

Searching and Planning

* Example of Supervised Learning

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.

* Example of Reinforcement Learning

Utility-based agents
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
5. Learning Agents

* Hence, learning agents are able to learn, analyze performance, and look for new ways to
improve the performance.
Rational Agents
An agent should strive to "do the right thing", based on what:

• it can perceive and

• the actions it can perform.

The right action is the one that will cause the agent to be most successful

- Performance measure of game-playing agent: win/loss percentage (maximize), robustness,

unpredictability (to “confuse” opponent), etc.

• Rationality is distinct from omniscience (“all knowing”). We can behave rationally even when faced
with incomplete information.

• For each possible percept sequence, a rational agent should select an action that maximizes its
performance measure (in expectation) given the evidence provided by the percept sequence and
whatever built- in knowledge the agent has.
Rational Agents

In AI, rational agents are closely related to intelligent agents or autonomous programs that mimic
human intelligence.
Rational Agents

Performance measure: An objective criterion for success of an agent's behavior.

• Performance measures of a vacuum-cleaner agent: amount of dirt cleaned up, amount of time
taken, amount of electricity consumed, level of noise generated, etc.

• Performance measures self-driving car: time to reach destination (minimize), safety, predictability
of behavior for other agents, reliability, etc.

• Performance measure of game-playing agent: win/loss percentage (maximize), robustness,

unpredictability (to “confuse” opponent), etc.
Environments
1) Fully observable / Partially observable

If an agent’s sensors give it access to the complete state of the environment

needed to choose an action, the environment is fully observable.
(e.g. chess – what about Kriegspiel?)
2) Deterministic / Stochastic

○ An environment is deterministic if the next state of the environment is completely

determined by the current state of the environment and the action of the agent;

○ In a stochastic environment, there are multiple, unpredictable outcomes. (If the

environment is deterministic except for the actions of other agents, then the
environment is strategic).

In a fully observable, deterministic environment, the agent need not deal with uncertainty.
3) Episodic / Sequential

○ In an episodic environment, the agent’s experience is divided into atomic

episodes. Each episode consists of the agent perceiving and then
performing a single action.
○ Subsequent episodes do not depend on what actions occurred in previous
episodes. Choice of action in each episode depends only on the episode
itself. (E.g., classifying images)

○ In a sequential environment, the agent engages in a series of connected

episodes. Current decision can affect future decisions. (E.g., chess and
driving)
4) Static / Dynamic

○ A static environment does not change while the agent is thinking.

○ The passage of time as an agent deliberates is irrelevant.

○ The environment is semi-dynamic if the environment itself does not change
with the passage of time but the agent's performance score does.

5) Discrete / Continuous
○ If the number of distinct percepts and actions is limited, the environment
is discrete, otherwise it is continuous.
6) Single agent / Multi-agent

○ If the environment contains other intelligent agents, the agent needs to be

concerned about strategic, game-theoretic aspects of the environment (for
either cooperative or competitive agents).

○ Most engineering environments don’t have multi-agent properties,

whereas most social and economic systems get their complexity from the
interactions of (more or less) rational agents.
Problem Solving in Artificial Intelligence

• The reflex agent of AI directly maps states into action.

• Whenever these agents fail to operate in an environment where the state of mapping is too large

and not easily performed by the agent, then the stated problem dissolves and sent to a problem-

solving domain which breaks the large stored problem into the smaller storage area and resolves

one by one. The final integrated action will be the desired outcomes.

• The problem-solving agent performs precisely by defining problems and several solutions. So we

can say that problem solving is a part of artificial intelligence that encompasses a number of

techniques such as a tree, B-tree, heuristic algorithms to solve a problem etc.

• We can also say that a problem-solving agent is a result-driven agent and always focuses on

satisfying the goals.

There are basically three types of problem in artificial intelligence:
1. Ignorable: In which solution steps can be ignored.
2. Recoverable: In which solution steps can be undone.
3. Irrecoverable: Solution steps cannot be undo.

Steps problem-solving in AI: The problem of AI is directly associated with the nature of humans and their
activities. So we need a number of finite steps to solve a problem which makes human easy works.

These are the following steps which require to solve a problem :

• Problem definition: Detailed specification of inputs and acceptable system solutions.
• Problem analysis: Analyse the problem thoroughly.
• Knowledge Representation: collect detailed information about the problem and define all possible
techniques.
• Problem-solving: Selection of best techniques.
Components to formulate the associated AI problem:

Initial State: This state requires an initial state for the problem which starts the AI agent towards a

specified goal. In this state new methods also initialize problem domain solving by a specific class.

Action: This stage of problem formulation works with function with a specific class taken from the initial

state and all possible actions done in this stage.

Transition: This stage of problem formulation integrates the actual action done by the previous action

stage and collects the final stage to forward it to their next stage.

Goal test: This stage determines that the specified goal achieved by the integrated transition model or

not, whenever the goal achieves stop the action and forward into the next stage to determines the cost to

achieve the goal.

Path costing: This component of problem-solving numerical assigned what will be the cost to achieve

the goal. It requires all hardware software and human working cost.
Problem Solving -Toy Problem – Vacuum World Problem
• There are two dirty square blocks and we need to clean these dirty square blocks by
using vacuum cleaner. (Agent)

• Percepts : Location (eg, left or right) and content e.g. (Dirty or not)

• Possible actions for Vacuum cleaner

• 1. Move Left (L)

• 2. Move Right (R)

• 3. Suck (S)

• 4. No Operation (NoOp)
Vacuum World Problem…
Initial State:

• Vacuum Agent can be in any states (Left or Right) shown in the picture.

Successor function:

• Successor function generates legal states resulting from applying the three actions {Left, Right, and Suck}

• The states space is shown in the picture, there are 8 world states (23 ) two state and three action.

Goal test:

• Checks whether all squares are clean

Path cost:

• Each step costs 1, so the path cost is the sum of steps in the path from Initial state to goal state.
Path cost is 3 in our problem.
Toy Problem – 8 Puzzle Problem
• It consists of 3 x 3 board with 8 numbered tiles and a blank space.

• A tile adjacent to the blank space can slide into the blank space.

• The objective is to reach the specified goal state.

States:

• Integer location of each tile. (Block position in the board)

Initial State:

• Any state can be initial, (no fixed state for initial state)(Initial state)

Successor Function:

• Generates legal states that result from trying the four actions to move the blank

• Left, Right, Top, Bottom

Goal Test:

• This checks whether the state matches the goal configuration

Path Cost:

• Each step costs 1, so the path cost is the number of steps in the path.
•

•
N-Queens Problem
N - Queens problem is to place n - queens in such a manner on an n x n chessboard that no queens attack
each other by being in the same row, column or diagonal.

It can be seen that for n =1, the problem has a trivial solution, and no solution exists for n =2 and n =3. So
first we will consider the 4 queens problem and then generate it to n - queens problem.

Given a 4 x 4 chessboard and number the rows and column of the chessboard 1 through 4.

Since, we have to place 4 queens such as q1 q2 q3 and q4

on the chessboard, such that no two queens attack each
other. In such a conditional each queen must be placed on
a different row, i.e., we put queen "i" on row "i."
Follow the steps mentioned below to implement the idea:
• Start in the leftmost column
• If all queens are placed return true
• Try all rows in the current column. Do the following for every row.
• If the queen can be placed safely in this row
• Then mark this [row, column] as part of the solution and recursively check if placing queen
here leads to a solution.
• If placing the queen in [row, column] leads to a solution then return true.
• If placing queen doesn’t lead to a solution then unmark this [row, column] then backtrack and
try other rows.
• If all rows have been tried and valid solution is not found return false to trigger backtracking.
Below is the recursive tree of the N Queen problem approach:
Possible solution for 5 queens problem is shown in fig:
One possible solution for 8 queens problem is shown in fig:
Magic Square
• A magic square of order n is an arrangement of n2 numbers, usually distinct integers, in a
square, such that the n numbers in all rows, all columns, and both diagonals sum to the same
constant. A magic square contains the integers from 1 to n2.
• The constant sum in every row, column and diagonal are called the magic constant or magic
sum, M. The magic constant of a normal magic square depends only on n and has the following
value: M = n(n2+1)/2

For normal magic squares of order n = 3, 4, 5, ...,

the magic constants are: 15, 34, 65, 111, 175, 260, ... Magic Square of size 5
----------------------
Magic Square of size 3 9 3 22 16 15
----------------------- 2 21 20 14 8
2 7 6 25 19 13 7 1
9 5 1 18 12 6 5 24
4 3 8 11 10 4 23 17
Sum in each row & each column = 3*(32+1)/2 = 15 Sum in each row & each column
= 5*(52+1)/2 = 65
Magic Square of size 7
----------------------
20 12 4 45 37 29 28
11 3 44 36 35 27 19
2 43 42 34 26 18 10
49 41 33 25 17 9 1
40 32 24 16 8 7 48
31 23 15 14 6 47 39
22 21 13 5 46 38 30
Sum in each row & each column = 7*(72+1)/2 = 175
Three conditions hold:
1. The position of next number is calculated by decrementing row number of the previous
number by 1, and incrementing the column number of the previous number by 1. At any time,
if the calculated row position becomes -1, it will wrap around to n-1. Similarly, if the calculated
column position becomes n, it will wrap around to 0.
2. If the magic square already contains a number at the calculated position, calculated
column position will be decremented by 2, and calculated row position will be incremented by
1.
3. If the calculated row position is -1 & calculated column position is n, the new position would
be: (0, n-2).
Steps:
1. position of number 1 = (3/2, 3-1) = (1, 2)
2. position of number 2 = (1-1, 2+1) = (0, 0)
3. position of number 3 = (0-1, 0+1) = (3-1, 1) = (2, 1)
4. position of number 4 = (2-1, 1+1) = (1, 2)
Since, at this position, 1 is there. So, apply condition 2.
new position=(1+1,2-2)=(2,0)
5. position of number 5=(2-1,0+1)=(1,1)
6. position of number 6=(1-1,1+1)=(0,2)
7. position of number 7 = (0-1, 2+1) = (-1,3) // this is tricky, see condition
new position = (0, 3-2) = (0,1)
8. position of number 8=(0-1,1+1)=(-1,2)=(2,2) //wrap around
9. position of number 9=(2-1,2+1)=(1,3)=(1,0) //wrap around
Thank you!!