INTRODUCTIONTO ARTIFICIAL INTELLIGENCE

Introduction – Defintion – Future of Artificial Intelligence Characteristics of intelligent

agents – AI Problems – AI Techniques..

1.1 INTRODUCTION
Artificial Intelligence is one of the booming technologies of computer science, which is ready to
create a new revolution in the world by making intelligent machines. AI 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, painting etc. AI holds a tendency to cause a machine to
work as a human.

INTELLIGENCE ARTIFICIAL INTELLIGENCE

It is a natural process. It is programmed by humans.
It is actually hereditary. It is not hereditary.
Knowledge is required for intelligence. KB and electricity are required to generate
output.
No human is an expert. We may get better Expert systems are made which aggregate
solutions from other humans. many person’s experience and ideas.

Why Artificial Intelligence?

• With the help of AI, we 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, we can create your personal virtual Assistant, such as Cortana, Google Assistant etc.

• With the help of AI, we 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
1
 • Plan some surgical operation

5. Driving a car in trafficCreating some system which can exhibit intelligent behavior, learn new things by
itself, demonstrate, explain, and can advise to its user.

INTELLIGENT SYSTEMS

AI is the combination of computer science, physiology and philosophy.

AI is a broad topic consisting of different fields from Machine vision to expert systems. John McCarthy was
one of the founders of AI field who stated that “AI is the science and engineering of making intelligent
machines, especially intelligent computer programs”.

Components of an Intelligent System

1. Knowledge Base:

o Contains facts and rules about the system’s domain.

o Example: A medical expert system’s knowledge base stores symptoms and diseases.

2. Inference Engine:

o The brain of the system that applies logical reasoning to the knowledge base to draw conclusions.

o Example: If “fever” and “cough” are symptoms, it concludes “flu”.

3. Sensors (Input):

o Detect changes or gather data from the environment.

o Example: Cameras, microphones, temperature sensors.

4. Actuators (Output):

o Devices that perform actions based on decisions.

o Example: Motors, displays, robotic arms.

5. Learning Module:

o Helps the system improve over time using past experiences.

o Example: A recommendation system learns user preferences.

Other Definitions of AI:

1. AI is the study of mental faculties through the use computational models.

 This definition focuses on understanding the human mind and reproducing it using computers.

2
  It tries to model how humans think, learn, remember, and decide using computer programs.

 Example: A memory model in AI that mimics how humans recall past experiences.

2. The art of creating machines that performs functions which require intelligence when performed by
people.

 This means AI enables machines to perform intelligent tasks that normally require human
thinking.

 Example: Playing chess, understanding language, driving a car, or recognizing faces.

3. AI is a field of study that seeks to explain & emulate intelligent behavior in terms of computational
processes.

 Here, AI tries to explain how intelligent behavior happens and then reproduce it using
algorithms.
 “Emulate” means to imitate or copy.
 Example: A chatbot that imitates human conversation.

4. AI is the study of how to make computers do things at which, at the moment, people are better.

 This shows that AI’s goal is to make computers perform human-like tasks, such as reasoning,
planning, or learning.

 Example: A translation software that can translate languages almost as well as humans.

5. AI is the study of the computations that make it possible to perceive reason & act.

 This definition highlights the three key abilities of an intelligent system:

 Perceive – understand the environment (e.g., see or hear).

 Reason – think and decide logically.

 Act – take action based on reasoning.

 Example: A self-driving car perceives the road, reasons which path is safe, and acts by steering accordingly.

6. AI is the branch of computer science that is concerned with the automation of intelligent behavior

 This emphasizes that AI is a sub-field of computer science.

 Its purpose is to automate intelligent actions — in other words, to make computers do tasks that
seem “smart.”

3
  Example: A virtual assistant that automatically schedules meetings or answers questions.

1.2 DEFINITION

The study of how to make computers do things at which at the moment, people are better.
“Artificial Intelligence is the ability of a computer to act like a human being”.

 Systems that think like humans

 Systems that act like humans
 Systems that think rationally. Systems that act rationally.

Figure 1.1 Some definitions of artificial intelligence, organized into four categories
(a) Intelligence - Ability to apply knowledge in order to perform better in an environment.
(b) Artificial Intelligence - Study and construction of agent programs that perform well
in a given environment, for a given agent architecture.
(c) Agent - An entity that takes action in response to precepts from an environment.
(d) Rationality - property of a system which does the “right thing” given what it knows.
(e) Logical Reasoning - A process of deriving new sentences from old, such that the new
sentences are necessarily true if the old ones are true.

Four Approaches of Artificial Intelligence:

 Acting humanly: The Turing test approach.
 Thinking humanly: The cognitive modelling approach.
 Thinking rationally: The laws of thought approach.
 Acting rationally: The rational agent approach.

4
 1.3 FUTURE OF ARTIFICIAL INTELLIGENCE CHARACTERISTICS OF INTELLIGENT
AGENTS

The future of Artificial Intelligence (AI) is very bright and promising.

AI is continuously evolving and will become a key part of almost every industry — from business
and education to healthcare and transportation.
Future AI systems will be more powerful, more human-like, and more integrated into our
daily lives.

 Transportation: Although it could take a decade or more to perfect them,

autonomous cars will one day ferry us from place to place.

 Manufacturing: AI powered robots work alongside humans to perform a limited

range of tasks like assembly and stacking, and predictive analysis sensors keep
equipment running smoothly.

 Healthcare: In the comparatively AI-nascent field of healthcare, diseases are more

quickly and accurately diagnosed, drug discovery is sped up and streamlined, virtual
nursing assistants monitor patients and big data analysis helps to create a more
personalized patient experience.

 Education: Textbooks are digitized with the help of AI, early-stage virtual tutors
assist human instructors and facial analysis gauges the emotions of students to help
determine who’s struggling or bored and better tailor the experience to their
individual needs.

 Media: Journalism is harnessing AI, too, and will continue to benefit from it.
Bloomberg uses Cyborg technology to help make quick sense of complex financial
reports. The Associated Press employs the natural language abilities of Automated
Insights to produce 3,700 earning reports stories per year — nearly four times more
than in the recent past

 Customer Service: Last but hardly least, Google is working on an AI assistant that
can place human-like calls to make appointments at, say, your neighborhood hair
salon. In addition to words, the system understands context and nuance.

AI will not only make machines think and act intelligently but will also help humans make better
decisions, increase productivity, and improve quality of life.

Key Areas Shaping the Future of AI

1. Automation and Robotics

o AI will automate repetitive and dangerous tasks.
o Robots will work alongside humans in factories, offices, and homes.
o Example: Delivery robots, warehouse automation, and service robots.
2. Healthcare Revolution
o AI will help in early disease detection, drug discovery, and robotic surgery.
o Personalized treatment plans will be designed using patient data.

5
 o Example: AI tools that detect cancer or heart disease early.
3. Education and Learning
o AI-powered systems will create personalized learning paths for students.
o Virtual tutors and chatbots will help in doubt solving and assessments.
4. Smart Cities and Transportation
o AI will help in traffic control, waste management, and energy efficiency.
o Self-driving cars and AI-controlled public transport will improve safety.
5. Business and Economy
o AI will support data-driven decision making, financial analysis, and fraud detection.
o Many businesses will use AI for marketing, forecasting, and customer care.
6. Cybersecurity
o AI will detect and prevent online threats faster than humans.
o It can identify unusual activities and protect systems from hacking.
7. Human–AI Collaboration
o Instead of replacing humans, AI will assist them.
o Humans will focus on creative and strategic work, while AI handles data-intensive tasks.
8. Ethical and Responsible AI
o The future will focus on developing safe, fair, and transparent AI systems.
o Rules and laws will be created to ensure AI is used for good purposes.

1.4 CHARACTERISTICS OF INTELLIGENT AGENTS

An Intelligent Agent is a system (software or machine) that can perceive its environment, reason
about it, and act intelligently to achieve specific goals.

In simple words, an intelligent agent is something that acts on behalf of a user or makes decisions
automatically based on the situation.

Examples:

 Chatbots like Siri, Alexa, or Google Assistant.

 Self-driving cars that sense surroundings and make driving decisions.
 Recommendation systems like those used by Netflix or Amazon.

Situatedness

The agent receives some form of sensory input from its environment, and it performs
some action that changes its environment in some way.

Examples of environments: the physical world and the Internet.

 Autonomy

The agent can act without direct intervention by humans or other agents and that it has
control over its own actions and internal state.

 Adaptivity

The agent is capable of

(1) reacting flexibly to changes in its environment;

6
 (2) taking goal-directed initiative (i.e., is pro-active), when appropriate; and
(3) Learning from its own experience, its environment, and interactions with others.
 Sociability

The agent is capable of interacting in a peer-to-peer manner with other agents or humans

1.3.1 AGENTS AND ITS TYPES

Figure 1.3 Agent types

An agent is anything that can be viewed as perceiving its environment through

sensors and acting upon that environment through actuators.

 Human Sensors:
 Eyes, ears, and other organs for sensors.
 Human Actuators:
 Hands, legs, mouth, and other body parts.
 Robotic Sensors:
 Mic, cameras and infrared range finders for sensors
 Robotic Actuators:
 Motors, Display, speakers etc 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.

Hence the world around us is full of agents such as thermostat, cell phone, camera,
and even we are also agents. Before moving forward, we should first know about sensors,
effectors, and actuators.

Sensor: Sensor is a device which detects the change in the environment and sends the
7
information to other electronic devices. An agent observes its environment through sensors.

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

Effectors: Effectors are the devices which affect the environment. Effectors can be
legs, wheels, arms, fingers, wings, fins, and display screen.

Figure 1.3.1 Effectors

1.5 AI PROBLEMS:

Artificial Intelligence (AI) deals with creating systems that can think, learn, and act intelligently.
To achieve this, AI must solve different kinds of problems that usually require human
intelligence.

An AI Problem is any task where a computer needs to make decisions, find solutions, or achieve goals in
a way that resembles human reasoning or behavior.

Main Characteristics of AI Problems

1. Clearly Defined Initial State

o The starting point of the problem must be known.
o Example: Starting position of a chessboard.
2. Well-Defined Goal State
o The goal or final state must be clear.
o Example: Reaching the destination in a navigation app.
3. Set of Possible Actions (Operators)
o The actions that can be performed to move from one state to another.
o Example: Moving left, right, up, or down in a maze.
4. Path and Cost of Solution
o The way to move from the initial state to the goal state, possibly minimizing cost (time, distance, etc.).

9
 AI problems can be broadly categorized into:
1. Search problems: Finding a path or solution in a large space (e.g., chess, maze solving).

 Involve finding a path or sequence of actions that leads from a start state to a goal state.
 The computer explores possible solutions step by step.
 Examples:
 Solving a maze
 Playing chess or tic-tac-toe
 Navigating routes in Google Maps

2. Constraint satisfaction problems: Assigning values to variables under constraints (e.g., scheduling).
 The system must assign values to variables while satisfying specific rules or conditions.
 Used when multiple conditions must be met simultaneously.
 Examples:
 Scheduling exams without time conflicts
 Sudoku puzzles
 Map coloring (neighboring regions cannot have the same color)

3. Optimization problems: Finding the best solution according to a criterion (e.g., route planning).

 The goal is to find the best possible solution from many alternatives, usually by minimizing cost
or maximizing efficiency.
 Examples:

 Route planning for delivery vehicles

 Portfolio optimization in finance
 Energy-efficient resource allocation

4. Classification problems: Assigning categories based on data (e.g., spam detection).

 The system assigns data into categories or groups based on patterns learned from past examples.
 Examples:

 Spam vs. non-spam email detection

 Disease diagnosis (healthy/sick)
 Customer segmentation in marketing

5. Prediction problems: Forecasting future outcomes based on past data.

 The system predicts future outcomes based on past data and trends.
 Uses statistical and machine learning models.
 Examples:
 Stock price forecasting
10
  Weather prediction
 Sales and demand forecasting

6. Planning problems: Generating sequences of actions to achieve goals.

 The system creates a sequence of actions to achieve specific goals under given conditions.
 Often used in robotics and logistics.
 Examples:
 Robot path planning
 Task scheduling in factories
 Travel itinerary generation

7. Natural Language Processing problems: Understanding and generating human language.

 Focuses on understanding, interpreting, and generating human language.
 Allows machines to communicate naturally with humans.
 Examples:
 Chatbots (e.g., ChatGPT, Alexa, Siri)
 Machine translation (English ↔ Tamil)
 Sentiment analysis of reviews

Steps to Solve an AI Problem

1. Define the Problem Clearly – Identify the start, goal, and possible actions.
2. Represent the Problem – Use suitable data structures or models.
3. Choose the Technique – Select the right algorithm (search, reasoning, learning, etc.).
4. Implement the Solution – Apply the method using programming or AI tools.
5. Evaluate the Output – Check efficiency, accuracy, and performance.

Challenges in Solving AI Problems

1. Incomplete or Uncertain Data – Lack of complete information.

2. Complex Search Spaces – Too many possible options.
3. Computation Cost – Some problems take too much time or memory.
4. Dynamic Environments – Conditions may change over time.
5. Ethical Issues – Decision-making in sensitive areas like healthcare or law.

11
 1.6 AI TECHNIQUES:
Artificial Intelligence (AI) refers to developing computer systems for performing tasks requiring
human intelligence. These systems assess large amounts of data to identify patterns and make logical
decisions based on the collected information. The ultimate goal of AI is to create machines to carry out
diverse tasks.

Artificial Intelligence techniques refer to a set of methods and algorithms used to develop intelligent
systems that can perform tasks requiring human-like intelligence. Some of the widely used ones
are:
 Machine Learning.
 Natural Language Processing.
 Computer Vision.
 Deep Learning
 Data Mining
 Robotics.
Machine Learning:

This approach involves the building of algorithms to learn patterns in data and make predictions based on it.
1. Unsupervised machine learning -AI systems analyse unlabelled data, where no predefined outcomes
are provided. The objective is to uncover inherent structures or patterns within the data without
any prior knowledge. For instance, it can group similar customer behaviour data to identify
customer segments for targeted marketing strategies.
2. Supervised learning - A combination of an input data set and the intended output is inferred from the
12
 training data. AI systems learn from a labelled dataset, where each data point is associated with a
known outcome. For instance, it enables email spam filters to distinguish between spam and
legitimate emails based on learned patterns.
3. Semi-supervised learning - It is a method that uses a small amount of labelled data and a large
amount of unlabelled data to train a model. The goal of semi-supervised learning is to learn a
function that can accurately predict the output variable based on the input variables, similar to
supervised learning. However, unlike supervised learning, the algorithm is trained on a dataset
that contains both labelled and unlabelled data.
4. Reinforcement learning - In RL, the data is accumulated from machine learning systems that use a
trial-and-error method to learn from outcomes and decide which action to take next. After each
action, the algorithm receives feedback that helps it determine whether the choice it made was
correct, neutral or incorrect. It performs actions with the aim of maximizing rewards, or in other
words, it is learning by doing in order to achieve the best outcomes.
Natural Language Processing:
Natural Language Processing involves programming computers to process human languages to facilitate
interactions between humans and computers.
However, the nature of human languages makes Natural Language Processing difficult because of the
rules involved in passing information using natural language. NLP leverages algorithms to
recognize and abstract the rules of natural languages, converting unstructured human language
data into a computer-understandable format.

Applications of Natural Language Processing can be found in IVR systems and applications used in call
centres, language translation applications like Google Translate, and word processors such as
Microsoft Word to check the accuracy of grammar in text.
This AI technique has paved the way for virtual assistants, chatbots, and language translation tools,
making communication between humans and machines more seamless than ever.
Some of the common variants of NLP are:
1. Lexical integration - Lexical analysis is the process of converting a sequence of characters into a
sequence of tokens. A lexer is generally combined with a parser, which together analyses the
syntax of programming languages, web pages, and so forth. Lexers and parsers are most often
used for compilers. The text or sound waves are segmented into words and other units.
13
 2. Syntactic integration - Syntactic analysis is the process of analysing a string of symbols, either in
natural language, computer languages, or data structures, conforming to the rules of formal
grammar. It is used in the analysis of computer languages, to facilitate the writing of compilers
and interpreters. Grammatical rules are applied to categories and groups of words, not individual
words. It is a crucial part of NLP.
3. Semantic integration - Semantic Analysis attempts to understand the meaning of the human language.
It captures the meaning of the given text while considering context, logical structuring of
sentences, and grammar roles.
2 parts of Semantic Analysis are:
 Lexical Semantic Analysis
 Compositional Semantics Analysis.
4. Pragmatic integration - Pragmatic Analysis is part of the process of extracting information from text.
It focuses on taking a structured set of text and figuring out the actual meaning of the text. It also
focuses on the meaning of the words of the time and context.
Effects on interpretation can be measured using PA by understanding the communicative and social
content from the given text.
5. Disclosure integration - Discourse analysis is used to uncover the motivation behind a text and is
useful for studying the underlying meaning of a spoken or written text as it considers the social
and historical contexts of it. Discourse analysis is a process of performing text or language
analysis, that involves text interpretation and an understanding of social interactions and customs.
Computer Vision:
Computer Vision equips machines with the ability to interpret visual information from the world. This
technique has revolutionized industries like healthcare, automotive, and robotics, enabling tasks
such as facial recognition, object detection, and autonomous driving. The extent to which it can
discriminate between objects is an essential component of machine vision.
Sensitivity in computer vision is an AI application’s ability to pick out small details in visual information.
A low-sensitivity system may not pick up subtle clues in images or fail to work well in low
lighting. However, high sensitivity might be able to look at an image’s fine details and pick up on
information other systems might miss.
Sensitivity in computer vision is an AI application’s ability to pick out small details in visual
information. A low-sensitivity system may not pick up subtle clues in images or fail to work well
in low lighting. However, high sensitivity might be able to look at an image’s fine details and pick
up on information other systems might miss. A common example is Surveillance systems.
Resolution is the level of detail a computer vision system can capture and process.

14
Deep Learning:
Deep learning is the branch of machine learning which is based on artificial neural network architecture.
An artificial neural network or ANN uses layers of interconnected nodes called neurons that work
together to process and learn from the input data.

In a fully connected Deep neural network, there is an input layer and one or more hidden layers
connected one after the other. Each neuron receives input from the previous layer neurons or the
input layer. The output of one neuron becomes the input to other neurons in the next layer of the
network, and this process continues until the final layer produces the output of the network. The
layers of the neural network transform the input data through a series of nonlinear
transformations, allowing the network to learn complex representations of the input data.
The main applications of deep learning can be divided into computer vision, natural language processing
(NLP), and reinforcement learning.
In computer vision, Deep learning models can enable machines to identify and understand visual data.
Some of the main applications include the identification and locating of objects within images and
videos.
In NLP, the Deep learning model can enable machines to understand and generate human language.
Some of the main applications include the generation of essays, translating languages, and
sentiment analysis
In reinforcement learning, deep learning works as training agents to take action in an environment to
maximize a reward. Some of the main applications of deep learning in reinforcement learning
include the training of robots to perform complex tasks such as grasping objects, navigation, and
manipulation.
Data Mining:
Data mining is the process of extracting knowledge or insights from large amounts of data using various
15
 statistical and computational techniques. The data can be structured, semi-structured, or
unstructured, and can be stored in various forms such as databases, data warehouses, and data
lakes.
The primary goal of data mining is to discover hidden patterns and relationships in the data that can be
used to make informed decisions or predictions. This involves exploring the data using various
techniques such as clustering, classification, regression analysis, association rule mining, and
anomaly detection.
Data mining has a wide range of applications across various industries, including marketing, finance,
healthcare, and telecommunications. For example, in marketing, data mining can be used to
identify customer segments and target marketing campaigns, while in healthcare, it can be used to
identify risk factors for diseases and develop personalized treatment plans.
However, data mining also raises ethical and privacy concerns, particularly when it involves personal or
sensitive data. It’s important to ensure that data mining is conducted ethically and with
appropriate safeguards in place to protect the privacy of individuals and prevent misuse of their
data.
Robotics & Automation:
Automation aims to enable machines to perform boring, repetitive jobs, increasing productivity and
delivering more effective, efficient, and affordable results. To automate processes, many
businesses employ machine learning, artificial neural, and graphs.
By leveraging the CAPTCHA technique, this automation can avoid fraud problems during online
payments.
Robotic process automation is designed to carry out high-volume, repetitive jobs while being capable of
adapting to changing conditions.

16
 UNIT 2

Problem solving Methods – Search Strategies- Uninformed – Informed – Heuristics – Local

Search Algorithms and Optimization Problems - Searching with Partial Observations –
Constraint Satisfaction Problems – Constraint Propagation - Backtracking Search – Game
Playing – Optimal Decisions in Games – Alpha – Beta Pruning – Stochastic Games

2.1 PROBLEM SOLVING METHOD

An important aspect of intelligence is goal-based problem solving.

The solution of many problems can be described by finding a sequence of actions

that lead to a desirable goal. Each action changes the state and the aim is to find the sequence
of actions and states that lead from the initial (start) state to a final (goal) state.

A well-defined problem can be described

by: Initial state

 Operator or successor function - for any state x returns s(x), the set of states
reachable from x with one action

 State space - all states reachable from initial by any sequence of actions

 Path - sequence through state space

 Path cost - function that assigns a cost to a path. Cost of a path is the sum of costs
of individual actions along the path

 Goal test - test to determine if at goal state

What is Search?

Search is the systematic examination of states to find path from the start/root state
to the goal state.

The set of possible states, together with operators defining their connectivity
constitute the search space.

The output of a search algorithm is a solution, that is, a path from the initial state to a
state that satisfies the goal test.

Problem-solving agents

A Problem solving agent is a goal-based agent. It decide what to do by finding

sequence of actions that lead to desirable states. The agent can adopt a goal and aim at
satisfying it.

To illustrate the agent’s behavior, let us take an example where our agent is in the city
17
of Arad, which is in Romania. The agent has to adopt a goal of getting to Bucharest.

18
 Goal formulation, based on the current situation and the agent’s performance
measure, is the first step in problem solving.

The agent’s task is to find out which sequence of actions will get to a goal state.

Problem formulation is the process of deciding what actions and states to consider
given a goal.

Example: Route finding problem Referring to

figure
On holiday in Romania : currently in Arad. Flight leaves tomorrow from Bucharest
Formulate goal: be in Bucharest
Formulate problem: states: various cities
actions: drive between cities
Find solution:
sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest

Problem formulation
A problem is defined by four items:
initial state e.g., “at Arad"
successor function S(x) = set of action-state pairs e.g., S(Arad) = {[Arad -
>Zerind;Zerind],….} goal test, can be
explicit, e.g., x = at Bucharest" implicit, e.g., NoDirt(x)
path cost (additive)
e.g., sum of distances, number of actions executed, etc. c(x; a; y) is the step cost,
assumed to be >= 0
A solution is a sequence of actions leading from the initial state to a goal state.
Goal formulation and problem formulation

2.2 EXAMPLE PROBLEMS

The problem solving approach has been applied to a vast array of task environments.
Some best known problems are summarized below. They are distinguished as toy or real-
world problems

A toy problem is intended to illustrate various problem solving methods. It can be

easily used by different researchers to compare the performance of algorithms.

A real world problem is one whose solutions people actually care about.

19
2.3 TOY PROBLEMS

Vacuum World Example

o States: The agent is in one of two locations, each of which might or might not contain
dirt. Thus there are 2 x 22 = 8 possible world states.

o Initial state: Any state can be designated as initial state.

o Successor function: This generates the legal states that results from trying the three
actions (left, right, suck). The complete state space is shown in figure

o Goal Test: This tests whether all the squares are clean.

o Path test: Each step costs one, so that the path cost is the number of steps in the path.

Vacuum World State Space

Figure 2.1 The state space for the vacuum world.

Arcs denote actions: L = Left, R = Right

The 8-puzzle

An 8-puzzle consists of a 3x3 board with eight numbered tiles and a blank space. A
tile adjacent to the balank space can slide into the space. The object is to reach the goal state,
as shown in Figure 2.4

Example: The 8-puzzle

20
 Figure 2.2 A typical instance of 8-puzzle

The problem formulation is as follows:

o States : A state description specifies the location of each of the eight tiles and the
blank in one of the nine squares.
o Initial state : Any state can be designated as the initial state. It can be noted that any
given goal can be reached from exactly half of the possible initial states.
o Successor function : This generates the legal states that result from trying the four
actions(blank moves Left, Right, Up or down).
o Goal Test : This checks whether the state matches the goal configuration shown in
Figure(Other goal configurations are possible)
o Path cost : Each step costs 1,so the path cost is the number of steps in the path.

The 8-puzzle belongs to the family of sliding-block puzzles, which are often used as
test problems for new search algorithms in AI. This general class is known as NP-complete.
The 8-puzzle has 9!/2 = 181,440 reachable states and is easily solved.

The 15 puzzle ( 4 x 4 board ) has around 1.3 trillion states, an the random instances
can be solved optimally in few milli seconds by the best search algorithms.

The 24-puzzle (on a 5 x 5 board) has around 1025 states and random instances are still
quite difficult to solve optimally with current machines and algorithms.

8-Queens problem

The goal of 8-queens problem is to place 8 queens on the chessboard such that no
queen attacks any other.(A queen attacks any piece in the same row, column or diagonal).

Figure 2.3 shows an attempted solution that fails: the queen in the right most column
is attacked by the queen at the top left.

An Incremental formulation involves operators that augments the state description,

starting with an empty state. For 8-queens problem, this means each action adds a queen to
the state. A complete-state formulation starts with all 8 queens on the board and move them
around. In either case the path cost is of no interest because only the final state counts.

21
 Figure 2.3 8-queens problem

The first incremental formulation one might try is the following:

o States: Any arrangement of 0 to 8 queens on board is a state.

o Initial state: No queen on the board.
o Successor function: Add a queen to any empty square.
o Goal Test: 8 queens are on the board, none attacked.

In this formulation, we have 64.63…57 = 3 x 1014 possible sequences to investigate.

A better formulation would prohibit placing a queen in any square that is already
attacked.

o States : Arrangements of n queens ( 0 <= n < = 8 ),one per column in the left most
columns, with no queen attacking another are states.

o Successor function : Add a queen to any square in the left most empty column
such that it is not attacked by any other queen.

This formulation reduces the 8-queen state space from 3 x 1014 to just 2057,and
solutions are easy to find.

For the 100 queens the initial formulation has roughly 10400 states whereas the
improved formulation has about 1052 states. This is a huge reduction, but the improved state
space is still too big for the algorithms to handle.

2.4 REAL-WORLD PROBLEMS

ROUTE-FINDING PROBLEM

Route-finding problem is defined in terms of specified locations and transitions along

links between them. Route-finding algorithms are used in a variety of applications, such as
routing in computer networks, military operations planning, and airline travel planning
systems.

22
2.5 AIRLINE TRAVEL PROBLEM

The airline travel problem is specifies as follows:

o States: Each is represented by a location (e.g., an airport) and the current time.

o Initial state: This is specified by the problem.

o Successor function: This returns the states resulting from taking any scheduled flight
(further specified by seat class and location),leaving later than the current time plus
the within-airport transit time, from the current airport to another.

o Goal Test: Are we at the destination by some prespecified time?

o Path cost: This depends upon the monetary cost, waiting time, flight time, customs
and immigration procedures, seat quality, time of date, type of air plane, frequent-
flyer mileage awards, and so on.

2.6 TOURING PROBLEMS

Touring problems are closely related to route-finding problems, but with an

important difference. Consider for example, the problem, “Visit every city at least once” as
shown in Romania map.

As with route-finding the actions correspond to trips between adjacent cities. The state
space, however, is quite different.

The initial state would be “In Bucharest; visited{Bucharest}”.

A typical intermediate state would be “In Vaslui;visited {Bucharest,

Urziceni,Vaslui}”. The goal test would check whether the agent is in Bucharest and

all 20 cities have been

visited.

2.7 THE TRAVELLING SALESPERSON PROBLEM(TSP)

Is a touring problem in which each city must be visited exactly once. The aim is to
find the shortest tour. The problem is known to be NP-hard. Enormous efforts have been
expended to improve the capabilities of TSP algorithms. These algorithms are also used in
tasks such as planning movements of automatic circuit-board drills and of stocking
machines on shop floors.

VLSI layout

A VLSI layout problem requires positioning millions of components and connections

on a chip to minimize area, minimize circuit delays, minimize stray capacitances, and
maximize manufacturing yield. The layout problem is split into two parts: cell layout and
channel routing.

23
 ROBOT navigation

ROBOT navigation is a generalization of the route-finding problem. Rather than a

discrete set of routes, a robot can move in a continuous space with an infinite set of possible
actions and states. For a circular Robot moving on a flat surface, the space is essentially two-
dimensional. When the robot has arms and legs or wheels that also must be controlled, the
search space becomes multi-dimensional. Advanced techniques are required to make the
search space finite.

2.8 AUTOMATIC ASSEMBLY SEQUENCING

The example includes assembly of intricate objects such as electric motors. The aim in
assembly problems is to find the order in which to assemble the parts of some objects. If the
wrong order is choosen, there will be no way to add some part later without undoing some
work already done. Another important assembly problem is protein design, in which the goal
is to find a sequence of Amino acids that will be fold into a three-dimensional protein with
the right properties to cure some disease.

2.9 INTERNET SEARCHING

In recent years there has been increased demand for software robots that perform
Internet searching, looking for answers to questions, for related information, or for shopping
deals. The searching techniques consider internet as a graph of nodes(pages) connected by
links.

Different Search Algorithm

Figure 2.4 Different Search Algorithms

24
2.10 UNINFORMED SEARCH STRATGES

Uninformed Search Strategies have no additional information about states beyond

that provided in the problem definition.

Strategies that know whether one non goal state is “more promising” than another are
called

Informed search or heuristic search strategies.

There are five uninformed search strategies as given below.

o Breadth-first search
o Uniform-cost search
o Depth-first search
o Depth-limited search
o Iterative deepening search

Breadth-first search

o Breadth-first search is a simple strategy in which the root node is expanded first, then
all successors of the root node are expanded next, then their successors, and so on. In
general, all the nodes are expanded at a given depth in the search tree before any
nodes at the next level are expanded.

o Breath-first-search is implemented by calling TREE-SEARCH with an empty fringe

that is a first-in-first-out (FIFO) queue, assuring that the nodes that are visited first
will be expanded first. In otherwards, calling TREE-SEARCH (problem, FIFO-
QUEUE()) results in breadth-first-search. The FIFO queue puts all newly generated
successors at the end of the queue, which means that Shallow nodes are expanded
before deeper nodes.

Figure 2.5 Breadth-first search on a simple binary tree. At each stage, the node to be
expanded next is indicated by a marker.

25
Properties of breadth-first-search

Figure 2.6 Breadth-first-search properties

Time complexity for BFS

Assume every state has b successors. The root of the search tree generates b nodes at
the first level, each of which generates b more nodes, for a total of b2 at the second level.
Each of these generates b more nodes, yielding b3 nodes at the third level, and so on. Now
suppose, that the solution is at depth d. In the worst case, we would expand all but the last
node at level d, generating bd+1 - b nodes at level d+1.

Then the total number of nodes generated is b + b2 + b3 + …+ bd + ( bd+1 + b) = O(bd+1).

Every node that is generated must remain in memory, because it is either part of the
fringe or is an ancestor of a fringe node. The space compleity is, therefore, the same as the
time complexity

2.11 UNIFORM-COST SEARCH

Instead of expanding the shallowest node, uniform-cost search expands the node n
with the lowest path cost. Uniform-cost search does not care about the number of steps a path
has, but only about their total cost.

26
 2.12 DEPTH-FIRST-SEARCH

Depth-first-search always expands the deepest node in the current fringe of the search
tree. The progress of the search is illustrated in Figure 1.31. The search proceeds immediately
to the deepest level of the search tree, where the nodes have no successors. As those nodes
are expanded, they are dropped from the fringe, so then the search “backs up” to the next
shallowest node that still has unexplored successors.

Figure 2.7 Depth-first-search on a binary tree. Nodes that have been expanded and have node
scendants in the fringe can be removed from the memory; these are shown in black.
Nodes at depth 3 are assumed to have no successors and M is the only goal node.

This strategy can be implemented by TREE-SEARCH with a last-in-first-out (LIFO)

queue, also known as a stack.

Depth-first-search has very modest memory requirements. It needs to store only a

single path from the root to a leaf node, along with the remaining unexpanded sibling nodes
for each node on the path. Once the node has been expanded, it can be removed from the
memory, as soon as its descendants have been fully explored (Refer Figure 2.7).

For a state space with a branching factor b and maximum depth m, depth-first-search
requires storage of only bm + 1 nodes.

Using the same assumptions as Figure, and assuming that nodes at the same depth as
the goal node have no successors, we find the depth-first-search would require 118 kilobytes
instead of 10 petabytes, a factor of 10 billion times less space.

27
Drawback of Depth-first-search

The drawback of depth-first-search is that it can make a wrong choice and get stuck
going down very long(or even infinite) path when a different choice would lead to solution
near the root of the search tree. For example, depth-first-search will explore the entire left
subtree even if node C is a goal node.

2.12 BACKTRACKING SEARCH

A variant of depth-first search called backtracking search uses less memory and only
one successor is generated at a time rather than all successors.; Only O(m) memory is needed
rather than O(bm)

DEPTH-LIMITED-SEARCH

Figure 2.8 Depth-limited-search

The problem of unbounded trees can be alleviated by supplying depth-first-search

with a pre- determined depth limit l. That is, nodes at depth l are treated as if they have no
successors. This approach is called depth-limited-search. The depth limit soves the infinite
path problem.

Depth limited search will be nonoptimal if we choose l > d. Its time complexity is
l
O(b ) and its space complete is O(bl). Depth-first-search can be viewed as a special case of
depth- limited search with l = oo Sometimes, depth limits can be based on knowledge of the
problem. For, example, on the map of Romania there are 20 cities. Therefore, we know that if
there is a solution, it must be of length 19 at the longest, So l = 10 is a possible choice.
However, it can be shown that any city can be reached from any other city in at most 9 steps.
This number known as the diameter of the state space, gives us a better depth limit.

28
 Depth-limited-search can be implemented as a simple modification to the general
tree- search algorithm or to the recursive depth-first-search algorithm. The pseudocode for
recursive depth- limited-search is shown in Figure.

It can be noted that the above algorithm can terminate with two kinds of failure : the
standard failure value indicates no solution; the cutoffvalue indicates no solution within the
depth limit. Depth-limited search = depth-first search with depth limit l,returns cut off if any
path is cut off by depth limit

function Depth-Limited-Search( problem, limit) returns a solution/fail/cutoff return

Recursive-DLS(Make-Node(Initial-State[problem]), problem, limit) function Recursive-
DLS(node, problem, limit) returns solution/fail/cutoff cutoff-occurred? false
Goal-Test(problem,State[node]) then return Solution(node)
if Depth[node] = limit then return cutoff
for each successor in Expand(node, problem) do result
Recursive-DLS(successor, problem, limit) if result = cutoff then cutoff_occurred?true
if result not = failure then return result
cutoff_occurred? then return cutoff else return failure
Figure 2.9 Recursive implementation of Depth-limited-search

2.13 ITERATIVE DEEPENING DEPTH-FIRST SEARCH

Iterative deepening search (or iterative-deepening-depth-first-search) is a general

strategy often used in combination with depth-first-search, that finds the better depth limit. It
does this by gradually increasing the limit – first 0,then 1,then 2, and so on – until a goal is
found. This will occur when the depth limit reaches d, the depth of the shallowest goal node.
The algorithm is shown in Figure.

Iterative deepening combines the benefits of depth-first and breadth-first-search Like

depth-first-search, its memory requirements are modest; O(bd) to be precise.

Like Breadth-first-search, it is complete when the branching factor is finite and

optimal when the path cost is a non decreasing function of the depth of the node.

Figure shows the four iterations of ITERATIVE-DEEPENING_SEARCH on a binary

search tree, where the solution is found on the fourth iteration.

29
 Figure 2.10 The iterative deepening search algorithm, which repeatedly applies
depth-limited- search with increasing limits. It terminates when a solution is found or
if the depth limited search returns failure, meaning that no solution exists.

Figure 2.11 Four iterations of iterative deepening search on a binary tree

Iterative search is not as wasteful as it might seem

30
 Figure 2.12 Iterative search is not as wasteful as it might seem
Properties of iterative deepening search

Figure 2.13 Properties of iterative deepening search

31
Bidirectional Search

The idea behind bidirectional search is to run two simultaneous searches – one
forward from the initial state and the other backward from the goal, stopping when the two
searches meet in the middle

The motivation is that bd/2 + bd/2 much less than, or in the figure, the area of the two
small circles is less than the area of one big circle centered on the start and reaching to the
goal.

Figure 2.14 A schematic view of a bidirectional search that is about to succeed, when
a Branch from the Start node meets a Branch from the goal node.

• Before moving into bidirectional search let’s first understand a few terms.

• Forward Search: Looking in-front of the end from start.

• Backward Search: Looking from end to the start back-wards.

• So Bidirectional Search as the name suggests is a combination of forwarding and

backward search. Basically, if the average branching factor going out of node / fan-
out, if fan-out is less, prefer forward search. Else if the average branching factor is
going into a node/fan in is less (i.e. fan-out is more), prefer backward search.

• We must traverse the tree from the start node and the goal node and wherever they
meet the path from the start node to the goal through the intersection is the optimal
solution. The BS Algorithm is applicable when generating predecessors is easy in
both forward and backward directions and there exist only 1 or fewer goal states.

32
 Figure 2.15 Comparing Uninformed Search Strategies

Figure 2.16 Evaluation of search strategies, b is the branching factor; d is the depth of the
shallowest solution; m is the maximum depth of the search tree; l is the depth limit.
Superscript caveats are as follows: a complete if b is finite; b complete if step costs >=
E for positive E; c optimal if step costs are all identical; d if both directions use
breadth-first search.

2.14 SEARCHING WITH PARTIAL INFORMATION

o Different types of incompleteness lead to three distinct problem types:

o Sensorless problems (conformant): If the agent has no sensors at all
o Contingency problem: if the environment if partially observable or if action are
uncertain (adversarial)
o Exploration problems: When the states and actions of the environment are unknown.

33
o No sensor
o Initial State(1,2,3,4,5,6,7,8)
o After action [Right] the state (2,4,6,8)
o After action [Suck] the state (4, 8)
o After action [Left] the state (3,7)
o After action [Suck] the state (8)
o Answer : [Right, Suck, Left, Suck] coerce the world into state 7 without any sensor
o Belief State: Such state that agent belief to be

there Partial knowledge of states and actions:

– sensorless or conformant problem

– Agent may have no idea where it is; solution (if any) is a sequence.
– contingency problem
– Percepts provide new information about current state; solution is a tree or policy;
often interleave search and execution.
– If uncertainty is caused by actions of another agent: adversarial problem
– exploration problem
– When states and actions of the environment are unknown.

Figure 2.17 states and actions of the

environment are unknown

34
 Figure 2.18 states and actions

Contingency, start in {1,3}.

Murphy’s law, Suck can dirty a clean carpet. Local sensing: dirt, location only.
– Percept = [L,Dirty] ={1,3}
– [Suck] = {5,7}
– [Right] ={6,8}
– [Suck] in {6}={8} (Success)
– BUT [Suck] in {8} = failure Solution??
– Belief-state: no fixed action sequence guarantees solution
Relax requirement:
– [Suck, Right, if [R,dirty] then Suck]
– Select actions based on contingencies arising during execution.

Time and space complexity are always considered with respect to some measure of
the problem difficulty. In theoretical computer science, the typical measure is the size of the
state space.
In AI, where the graph is represented implicitly by the initial state and successor
function, the complexity is expressed in terms of three quantities:
b, the branching factor or maximum number of successors of any node;
d, the depth of the shallowest goal node; and

35
 m, the maximum length of any path in the state space.
Search-cost - typically depends upon the time complexity but can also include the
term for memory usage.
Total–cost – It combines the search-cost and the path cost of the solution found.
2.15 INFORMED SEARCH AND EXPLORATION
Informed (Heuristic) Search Strategies
Informed search strategy is one that uses problem-specific knowledge beyond the
definition of the problem itself. It can find solutions more efficiently than uninformed
strategy.
Best-first search
Best-first search is an instance of general TREE-SEARCH or GRAPH-SEARCH
algorithm in which a node is selected for expansion based on an evaluation function f(n).
The node with lowest evaluation is selected for expansion, because the evaluation measures
the distance to the goal.
This can be implemented using a priority-queue, a data structure that will maintain the
fringe in ascending order of f-values.
2.16 HEURISTIC FUNCTIONS
A heuristic function or simply a heuristic is a function that ranks alternatives in
various search algorithms at each branching step basing on an available information in order
to make a decision which branch is to be followed during a search.
The key component of Best-first search algorithm is a heuristic function, denoted by
h(n): h(n) = estimated cost of the cheapest path from node n to a goal node.
For example, in Romania, one might estimate the cost of the cheapest path from Arad
to Bucharest via a straight-line distance from Arad to Bucharest (Figure 2.19).
Heuristic function are the most common form in which additional knowledge is
imparted to the search algorithm.
Greedy Best-first search
Greedy best-first search tries to expand the node that is closest to the goal, on the
grounds that this is likely to a solution quickly.
It evaluates the nodes by using the heuristic function f(n) = h(n).
Taking the example of Route-finding problems in Romania, the goal is to reach
Bucharest starting from the city Arad. We need to know the straight-line distances to
Bucharest from various cities as shown in Figure. For example, the initial state is
In(Arad),and the straight line distance heuristic hSLD (In(Arad)) is found to be 366.
Using the straight-line distance heuristic hSLD, the goal state can be reached faster.

36
Figure 2.19 Values of hSLD - straight line distances to Bucharest

Figure 2.20 progress of greedy best-first search

37
 Figure shows the progress of greedy best-first search using hSLD to find a path from
Arad to Bucharest. The first node to be expanded from Arad will be Sibiu, because it is closer
to Bucharest than either Zerind or Timisoara. The next node to be expanded will be Fagaras,
because it is closest. Fagaras in turn generates Bucharest, which is the goal.

Properties of greedy search

o Complete: No–can get stuck in loops, e.g., Iasi !Neamt !Iasi !Neamt !
Complete in finite space with repeated-state checking
o Time: O(bm), but a good heuristic can give dramatic improvement
o Space: O(bm) - keeps all nodes in memory
o Optimal: No

Greedy best-first search is not optimal, and it is incomplete.

The worst-case time and space complexity is O(bm),where m is the maximum depth of
the search space.

A* SEARCH

A* Search is the most widely used form of best-first search. The evaluation function
f(n) is obtained by combining

(1) g(n) = the cost to reach the node, and

(2) h(n) = the cost to get from the node to the goal :
f(n) = g(n) + h(n).

A* Search is both optimal and complete. A* is optimal if h(n) is an admissible

heuristic. The obvious example of admissible heuristic is the straight-line distance hSLD. It
cannot be an overestimate.

A* Search is optimal if h(n) is an admissible heuristic – that is, provided that h(n)
never overestimates the cost to reach the goal.

An obvious example of an admissible heuristic is the straight-line distance hSLD that

we used in getting to Bucharest. The progress of an A * tree search for Bucharest is shown in
Figure

The values of ‘g ‘ are computed from the step costs shown in the Romania map(figure).
Also the values of hSLD are given in Figure

38
 Figure 2.21 A* Search

Figure 2.22 Example A* Search

2.17 LOCAL SEARCH ALGORITHMS AND OPTIMIZATION PROBLEMS

o In many optimization problems, the path to the goal is irrelevant; the goal state itself
is the solution

o For example, in the 8-queens problem, what matters is the final configuration of
queens, not the order in which they are added.

o In such cases, we can use local search algorithms. They operate using a single
current state (rather than multiple paths) and generally move only to neighbors of
that state.

39
o The important applications of these class of problems are (a) integrated-circuit design,
(b) Factory-floor layout, (c) job-shop scheduling, (d) automatic programming, (e)
telecommunications network optimization, (f) Vehicle routing, and (g) portfolio
management.
Key advantages of Local Search Algorithms
(1) They use very little memory – usually a constant amount; and
(2) they can often find reasonable solutions in large or infinite(continuous) state spaces
for which systematic algorithms are unsuitable.
2.18 OPTIMIZATION PROBLEMS
In addition to finding goals, local search algorithms are useful for solving pure
optimization problems, in which the aim is to find the best state according to an objective
function.
State Space Landscape
To understand local search, it is better explained using state space landscape as
shown in Figure.
A landscape has both “location” (defined by the state) and “elevation” (defined by
the value of the heuristic cost function or objective function).
If elevation corresponds to cost, then the aim is to find the lowest valley – a global
minimum; if elevation corresponds to an objective function, then the aim is to find the
highest peak – a global maximum.
Local search algorithms explore this landscape. A complete local search algorithm
always finds a goal if one exists; an optimal algorithm always finds a global
minimum/maximum.

Figure 2.23 A one dimensional state space landscape in which elevation

corresponds to the objective function. The aim is to find the global
maximum. Hill climbing search modifies the current state to try to improve
it, as shown by the arrow. The various topographic features are defined in
the text

40
 Hill-climbing search

The hill-climbing search algorithm as shown in figure, is simply a loop that

continually moves in the direction of increasing value – that is, uphill. It terminates when it
reaches a “peak” where no neighbor has a higher value.

function HILL-CLIMBING( problem) return a state that is a local maximum

input: problem, a problem
local variables: current, a
node.
neighbor, a node.

current ←MAKE-NODE(INITIAL-STATE[problem])
loop do
neighbor ← a highest valued successor of current
if VALUE [neighbor] ≤ VALUE[current] then return STATE[current]
current ←neighbor
Figure 2.24 The hill-climbing search algorithm (steepest ascent version), which is
the most basic local search technique. At each step the current node is replaced
by the best neighbor; the neighbor with the highest VALUE. If the heuristic cost
estimate h is used, we could find the neighbor with the lowest h.

Hill-climbing is sometimes called greedy local search because it grabs a good

neighbor state without thinking ahead about where to go next. Greedy algorithms often
perform quite well. Problems with hill-climbing

Hill-climbing often gets stuck for the following reasons :

 Local maxima: a local maximum is a peak that is higher than each of its neighboring
states, but lower than the global maximum. Hill-climbing algorithms that reach the
vicinity of a local maximum will be drawn upwards towards the peak, but will then be
stuck with nowhere else to go

 Ridges: A ridge is shown in Figure 2.10. Ridges results in a sequence of local

maxima that is very difficult for greedy algorithms to navigate.

 Plateaux: A plateau is an area of the state space landscape where the evaluation
function is flat. It can be a flat local maximum, from which no uphill exit exists, or a
shoulder, from which it is possible to make progress.

41
 Figure 2.25 Illustration of why ridges cause difficulties for hill-climbing. The grid
of states(dark circles) is superimposed on a ridge rising from left to right, creating
a sequence of local maxima that are not directly connected to each other. From
each local maximum, all the available options point downhill.

Hill-climbing variations

 Stochastic hill-climbing
o Random selection among the uphill moves.
o The selection probability can vary with the steepness of the uphill move.
 First-choice hill-climbing
o cfr. stochastic hill climbing by generating successors randomly until a better
one is found.
 Random-restart hill-climbing
o Tries to avoid getting stuck in local maxima.

Simulated annealing search

A hill-climbing algorithm that never makes “downhill” moves towards states with
lower value (or higher cost) is guaranteed to be incomplete, because it can stuck on a local
maximum. In contrast, a purely random walk –that is, moving to a successor choosen
uniformly at random from the set of successors – is complete, but extremely inefficient.

Simulated annealing is an algorithm that combines hill-climbing with a random walk

in someway that yields both efficiency and completeness.

Figure shows simulated annealing algorithm. It is quite similar to hill climbing.

Instead of picking the best move, however, it picks the random move. If the move improves
the situation, it is always accepted. Otherwise, the algorithm accepts the move with some
probability less than 1. The probability decreases exponentially with the “badness” of the
move – the amount E by which the evaluation is worsened.

42
Simulated annealing was first used extensively to solve VLSI layout problems in the early
1980s. It has been applied widely to factory scheduling and other large-scale optimization
tasks.

Figure 2.26 The simulated annealing search algorithm, a version of stochastic

hill climbing where some downhill moves are allowed.

Genetic algorithms

A Genetic algorithm (or GA) is a variant of stochastic beam search in which successor
states are generated by combining two parent states, rather than by modifying a single state

Like beam search, Gas begin with a set of k randomly generated states, called the
population. Each state, or individual, is represented as a string over a finite alphabet – most
commonly, a string of 0s and 1s. For example, an 8 8-quuens state must specify the positions
of 8 queens, each in a column of 8 squares, and so requires 8 x log2 8 = 24 bits.

Figure 2.27 Genetic algorithm

43
 Figure shows a population of four 8-digit strings representing 8-queen states. The
production of the next generation of states is shown in Figure

In (b) each state is rated by the evaluation function or the fitness function.

In (c),a random choice of two pairs is selected for reproduction, in accordance with
the probabilities in (b).

Figure describes the algorithm that implements all these steps.

function GENETIC_ALGORITHM( population, FITNESS-FN) return an individual

input: population, a set of individuals
FITNESS-FN, a function which determines the quality of the individual
repeat
new_population←empty set
loop for ifrom 1 to SIZE(population) do
x ←RANDOM_SELECTION(population, FITNESS_FN)
y ←RANDOM_SELECTION(population,
FITNESS_FN)
child ←REPRODUCE(x,y)
if (small random probability) then child
MUTATE(child ) add child to
new_population population ←new_population
until some individual is fit enough or enough time has elapsed
return the best individual
Figure 2.28 A genetic algorithm.

2.29 CONSTRAINT SATISFACTION PROBLEMS(CSP)

A Constraint Satisfaction Problem(or CSP) is defined by a set of variables,X1,X2,

….Xn, and a set of constraints C1,C2,…,Cm. Each variable Xi has a nonempty domain D,of
possible values.

Each constraint Ci involves some subset of variables and specifies the allowable
combinations of values for that subset.

A State of the problem is defined by an assignment of values to some or all of the

variables,{Xi = vi,Xj = vj,…}. An assignment that does not violate any constraints is called a
consistent or legal assignment. A complete assignment is one in which every variable is
mentioned, and a solution to a CSP is a complete assignment that satisfies all the constraints.

Some CSPs also require a solution that maximizes an objective function.

44
Example for Constraint Satisfaction Problem

Figure shows the map of Australia showing each of its states and territories. We are
given the task of coloring each region either red, green, or blue in such a way that the
neighboring regions have the same color. To formulate this as CSP, we define the variable to
be the regions

:WA,NT,Q,NSW,V,SA, and T. The domain of each variable is the set

{red,green,blue}.The constraints require neighboring regions to have distinct colors; for
example, the allowable combinations for WA and NT are the pairs

{(red,green),(red,blue),(green,red),(green,blue),(blue,red),(blue,green)}.

The constraint can also be represented more succinctly as the inequality WA not =
NT, provided the constraint satisfaction algorithm has some way to evaluate such
expressions.) There are many possible solutions such as

{ WA = red, NT = green, Q = red, NSW = green, V = red,SA = blue,T = red}.

It is helpful to visualize a CSP as a constraint graph, as shown in Figure 2.29. The

nodes of the graph corresponds to variables of the problem and the arcs correspond to
constraints.

Figure 2.29 Principle states and territories of Australia. Coloring this map can be
viewed as a constraint satisfaction problem. The goal is to assign colors to each
region so that no neighboring regions have the same color.

45
 Figure 2.30 Mapping Problem

CSP can be viewed as a standard search problem as follows:

 Initial state: the empty assignment {},in which all variables are unassigned.
 Successor function: a value can be assigned to any unassigned variable, provided that
it does not conflict with previously assigned variables.
 Goal test: the current assignment is complete.
 Path cost: a constant cost(E.g.,1) for every step.

Every solution must be a complete assignment and therefore appears at depth n if

there are n variables.

Depth first search algorithms are popular for CSPs

Varieties of CSPs
(i) Discrete variables Finite domains

The simplest kind of CSP involves variables that are discrete and have finite
domains. Map coloring problems are of this kind. The 8-queens problem can also be viewed
as finite- domain

CSP, where the variables Q1,Q2,…..Q8 are the positions each queen in columns 1,
….8 and each variable has the domain {1,2,3,4,5,6,7,8}. If the maximum domain size
of any
46
variable in a CSP is d, then the number of possible complete assignments is O(d n) – that is,
exponential in the number of variables. Finite domain CSPs include Boolean CSPs, whose
variables can be either true or false. Infinite domains

Discrete variables can also have infinite domains – for example, the set of integers or
the set of strings. With infinite domains, it is no longer possible to describe constraints by
enumerating all allowed combination of values. Instead a constraint language of algebric
inequalities such as Startjob1 + 5 <= Startjob3.

(ii) CSPs with continuous domains

CSPs with continuous domains are very common in real world. For example in
operation research field, the scheduling of experiments on the Hubble Telescope requires
very precise timing of observations; the start and finish of each observation and manoeuvre
are continuous-valued variables that must obey a variety of astronomical, precedence and
power constraints. The best known category of continuous-domain CSPs is that of linear
programming problems, where the constraints must be linear inequalities forming a convex
region. Linear programming problems can be solved in time polynomial in the number of
variables.

Varieties of constraints

(i) unary constraints involve a single variable.

Example : SA # green
(ii) Binary constraints involve paris of variables.
Example : SA # WA
(iii) Higher order constraints involve 3 or more variables. Example :cryptarithmetic puzzles.

S
Figure 2.31 cryptarithmetic puzzles.

47
 Figure 2.32 Cryptarithmetic puzzles-Solution

Figure 2.33 Numerical Solution

Backtracking Search for CSPs

The term backtracking search is used for depth-first search that chooses values for
one variable at a time and backtracks when a variable has no legal values left to assign. The
algorithm is shown in figure

48
Figure 2.34 A simple backtracking algorithm for constraint satisfaction problem. The
algorithm is modeled on the recursive depth-first search

Figure 2.34 Part of the search tree generated by simple backtracking for the map-
coloring problem

Figure 2.35 Part of search tree generated by simple backtracking for the map
coloring problem.

49
Forward checking

One way to make better use of constraints during search is called forward checking.
Whenever a variable X is assigned, the forward checking process looks at each unassigned
variable Y that is connected to X by a constraint and deletes from Y ’s domain any value that
is inconsistent with the value chosen for X. Figure 5.6 shows the progress of a map-coloring
search with forward checking.

Figure 2.36 The progress of a map-coloring search with forward checking. WA = red
is assigned first; then forward checking deletes red from the domains of the
neighboring variables NT and SA. After Q = green, green is deleted from the domain
of NT, SA, and NSW. After V = blue, blue, is deleted from the domains of NSW and
SA, leaving SA with no legal values.

Constraint propagation

Although forward checking detects many inconsistencies, it does not detect all of them.

Constraint propagation is the general term for propagating the implications of a

constraint on one variable onto other variables.

Arc Consistency

Figure 2.37 Arc Consistency

50
 Figure 2.38 Arc Consistency –CSP

k-Consistency

Local Search for CSPs

The Structure of Problems Problem Structure

Independent Subproblems

Figure 2.39 Independent Subproblems

51
 Tree-Structured CSPs

Figure 2.40 Tree-Structured CSPs

2.30 ADVERSARIAL SEARCH

Competitive environments, in which the agent’s goals are in conflict, give rise to
adversarial search problems – often known as games.

Games

Mathematical Game Theory, a branch of economics, views any multiagent

environment as a game provided that the impact of each agent on the other is “significant”,
regardless of whether the agents are cooperative or competitive. In, AI, “games” are
deterministic, turn-taking, two-player, zero-sum games of perfect information. This means
deterministic, fully observable environments in which there are two agents whose actions
must alternate and in which the utility values at the end of the game are always equal and
opposite. For example, if one player wins the game of chess(+1),the other player necessarily
loses(-1). It is this opposition between the agents’ utility functions that makes the situation
adversarial.

Formal Definition of Game

We will consider games with two players, whom we will call MAX and MIN. MAX
moves first, and then they take turns moving until the game is over. At the end of the game,
points are awarded to the winning player and penalties are given to the loser. A game can be
formally defined as a search problem with the following components:

o The initial state, which includes the board position and identifies the player to move.

o A successor function, which returns a list of (move, state) pairs, each indicating a
legal move and the resulting state.

52
 o A terminal test, which describes when the game is over. States where the game has
ended are called terminal states.

o A utility function (also called an objective function or payoff function), which give a
numeric value for the terminal states. In chess, the outcome is a win, loss, or draw,
with values+1,-1, or 0. he payoffs in backgammon range from +192 to -192.

Game Tree

The initial state and legal moves for each side define the game tree for the game.
Figure 2.18 shows the part of the game tree for tic-tac-toe (noughts and crosses). From the
initial state, MAX has nine possible moves. Play alternates between MAX’s placing an X and
MIN’s placing a 0 until we reach leaf nodes corresponding to the terminal states such that one
player has three in a row or all the squares are filled. He number on each leaf node indicates
the utility value of the terminal state from the point of view of MAX; high values are
assumed to be good for MAX and bad for MIN. It is the MAX’s job to use the search tree
(particularly the utility of terminal states) to determine the best move.

Figure 2.41 A partial search tree. The top node is the initial state, and MAX
move first, placing an X in an empty square.

Optimal Decisions in Games

In normal search problem, the optimal solution would be a sequence of move leading
to a goal state – a terminal state that is a win. In a game, on the other hand, MIN has
something
53
to say about it, MAX therefore must find a contingent strategy, which specifies MAX’s
move in the initial state, then MAX’s moves in the states resulting from every possible
response by MIN, then MAX’s moves in the states resulting from every possible response by
MIN those moves, and so on. An optimal strategy leads to outcomes at least as good as any
other strategy when one is playing an infallible opponent.

Figure 2.42 Optimal Decisions in Games

Figure 2.43 MAX-VALUE and MIN-VALUE

54
 Figure 2.44 An algorithm for calculating minimax decisions. It returns the action
corresponding to the best possible move, that is, the move that leads to the outcome
with the best utility, under the assumption that the opponent plays to minimize
utility. The functions MAX-VALUE and MIN-VALUE go through the whole game
tree, all the way to the leaves, to determine the backed-up value of a state.

The minimax Algorithm

The minimax algorithm computes the minimax decision from the current state. It uses
a simple recursive computation of the minimax values of each successor state, directly
implementing the defining equations. The recursion proceeds all the way down to the leaves
of the tree, and then the minimax values are backed up through the tree as the recursion
unwinds. For example in Figure 2.19,the algorithm first recourses down to the three bottom
left nodes, and uses the utility function on them to discover that their values are 3, 12, and 8
respectively. Then it takes the minimum of these values, 3, and returns it as the backed-up
value of node B. A similar process gives the backed up values of 2 for C and 2 for D. Finally,
we take the maximum of 3, 2, and 2 to get the backed-up value of 3 at the root node. The
minimax algorithm performs a complete depth-first exploration of the game tree. If the
maximum depth of the tree is m, and there are b legal moves at each point, then the time
complexity of the minimax algorithm is O(bm). The space complexity is O(bm) for an
algorithm that generates successors at once.

Alpha-Beta Pruning

The problem with minimax search is that the number of game states it has to examine
is exponential in the number of moves. Unfortunately, we can’t eliminate the exponent, but

55
we can effectively cut it in half. By performing pruning, we can eliminate large part of the
tree from consideration. We can apply the technique known as alpha beta pruning, when
applied to a minimax tree, it returns the same move as minimax would, but prunes away
branches that cannot possibly influence the final decision.

Alpha Beta pruning gets its name from the following two parameters that describe
bounds on the backed-up values that appear anywhere along the path:

o α : the value of the best (i.e., highest-value) choice we have found so far at any
choice point along the path of MAX.

o β: the value of best (i.e., lowest-value) choice we have found so far at any choice
point along the path of MIN.

Alpha Beta search updates the values of α and β as it goes along and prunes the
remaining branches at anode(i.e., terminates the recursive call) as soon as the value of the
current node is known to be worse than the current α and β value for MAX and MIN,
respectively. The complete algorithm is given in Figure. The effectiveness of alpha-beta
pruning is highly dependent on the order in which the successors are examined. It might be
worthwhile to try to examine first the successors that are likely to be the best. In such case, it
turns out that alpha-beta needs to examine only O(bd/2) nodes to pick the best move, instead of
O(bd) for minimax. This means that the effective branching factor becomes sqrt(b) instead of
b – for chess,6 instead of 35. Put an other way alpha-beta cab look ahead roughly twice as far
as minimax in the same amount of time.

56
Figure 2.45 The alpha beta search algorithm. These routines are the same as the minimax
routines in figure 2.20,except for the two lines in each of MIN-VALUE and MAX-
VALUE that maintain α and β

Key points in Alpha-beta Pruning

 Alpha: Alpha is the best choice or the highest value that we have found at any
instance along the path of Maximizer. The initial value for alpha is – ∞.

 Beta: Beta is the best choice or the lowest value that we have found at any instance
along the path of Minimizer. The initial value for alpha is + ∞.

 The condition for Alpha-beta Pruning is that α >= β.

 Each node has to keep track of its alpha and beta values. Alpha can be updated only
when it’s MAX’s turn and, similarly, beta can be updated only when it’s MIN’s
chance.

 MAX will update only alpha values and MIN player will update only beta values.

 The node values will be passed to upper nodes instead of values of alpha and beta
during go into reverse of tree.

 Alpha and Beta values only be passed to child nodes.

Working of Alpha-beta Pruning

1. We will first start with the initial move. We will initially define the alpha and beta
values as the worst case i.e. α = -∞ and β= +∞. We will prune the node only when
alpha becomes greater than or equal to beta.

57
 Figure 2.46 Step 1 Alpha-beta Pruning

2. Since the initial value of alpha is less than beta so we didn’t prune it. Now it’s turn for
MAX. So, at node D, value of alpha will be calculated. The value of alpha at node D
will be max (2, 3). So, value of alpha at node D will be 3.

3. Now the next move will be on node B and its turn for MIN now. So, at node B, the
value of alpha beta will be min (3, ∞). So, at node B values will be alpha= – ∞ and
beta will be 3.

Figure 2.47 Step 2 Alpha-beta Pruning

In the next step, algorithms traverse the next successor of Node B which is node E,
and the values of α= -∞, and β= 3 will also be passed.

58
4. Now it’s turn for MAX. So, at node E we will look for MAX. The current value of
alpha at E is – ∞ and it will be compared with 5. So, MAX (- ∞, 5) will be 5. So, at
node E, alpha = 5, Beta = 5. Now as we can see that alpha is greater than beta which
is satisfying the pruning condition so we can prune the right successor of node E and
algorithm will not be traversed and the value at node E will be 5.

Figure 2.48 Step 3 Alpha-beta Pruning

6. In the next step the algorithm again comes to node A from node B. At node A alpha
will be changed to maximum value as MAX (- ∞, 3). So now the value of alpha and
beta at node A will be (3, + ∞) respectively and will be transferred to node C. These
same values will be transferred to node F.

7. At node F the value of alpha will be compared to the left branch which is 0. So, MAX
(0, 3) will be 3 and then compared with the right child which is 1, and MAX (3,1) = 3
still α remains 3, but the node value of F will become 1.

Figure 2.49 Step 4 Alpha-beta Pruning

59
8. Now node F will return the node value 1 to C and will compare to beta value at C.
Now its turn for MIN. So, MIN (+ ∞, 1) will be 1. Now at node C, α= 3, and β= 1 and
alpha is greater than beta which again satisfies the pruning condition. So, the next
successor of node C i.e. G will be pruned and the algorithm didn’t compute the entire
subtree G.

Figure 2.50 Step 5 Alpha-beta Pruning

Now, C will return the node value to A and the best value of A will be MAX (1, 3)
will be 3.

Figure 2.51 Step 6 Alpha-beta Pruning

The above represented tree is the final tree which is showing the nodes which are
computed and the nodes which are not computed. So, for this example the optimal value of
the maximizer will be 3.

60
61