Fundamentals of Artificial Intelligence

3rd Yr. Soft. Eng.

Feb 2024

02/21/2024
 Chapter 3
Problem-Solving by Searching

02/21/2024 2
Outline
▪ Problem solving

▪ Search algorithms in Artificial Intelligence

▪ Problem-solving agents

▪ Searching strategies

▪ Uninformed search and

▪ Informed search

02/21/2024 3
Discussion Question

1. Why was AI invented? What is its main purpose?

02/21/2024 4
Problem-Solving
What is problem?

▪ In AI, a problem refers to a task or challenge that an AI system is designed to solve or address.

▪ These problems can be diverse in nature and can arise in various domains and contexts. Essentially,

a problem in AI defines a goal or objective that the AI system is intended to achieve through its

computational processes.

▪ Problems in AI can range from simple and well-defined tasks, such as classifying images or

predicting numeric values, to complex and open-ended challenges, such as understanding natural

language or making decisions in uncertain environments.

▪ Two types of problems: Toy problems and real-world problems.

02/21/2024 5
Cont.
1. Toy problems: Toy problems are simplified, abstracted versions of real-world problems. They are
often used in AI research and education as simplified models to demonstrate or study specific
algorithms, techniques, or concepts.

Examples:
▪ The 8-Puzzle, where the objective is to rearrange numbered tiles on a grid to reach a goal
configuration.
▪ The Traveling Salesman Problem with a small number of cities, aiming to find the shortest route
visiting each city exactly once.

Toy problems serve as testbeds for evaluating algorithms, understanding their properties, and
comparing their performance under controlled conditions. They provide a starting point for
exploring more complex real-world applications. 02/21/2024 6
Cont.
2. Real world problems: are problems that have much greater commercial/economic impact if
solved.
✓ Real-world problems are typically complex, with multiple interacting variables, uncertainties, and

constraints.

▪ Examples

✓Autonomous driving, where AI systems must navigate real-world roadways, interact with other

vehicles, pedestrians, and traffic signals, and make decisions in real time.

✓Healthcare diagnosis and treatment planning, involving the analysis of medical data, patient

history, and symptoms to recommend appropriate interventions.

02/21/2024 7
Cont.
▪ Real-world problems represent the ultimate goal of AI research and application, aiming to

develop intelligent systems that can effectively address complex challenges in diverse domains.

▪ Solutions to real-world problems often require a combination of AI techniques, domain expertise,

and interdisciplinary collaboration.

02/21/2024 8
Steps for addressing problems
Example: 8-Puzzle - Toy problems
Problem Identification and Definition
▪ The 8-Puzzle is a classic toy problem where you have a 3x3 grid with 8 numbered tiles and one

empty space. The goal is to rearrange the tiles into a target configuration by sliding them one at a
time into the empty space.
▪ Formally define the initial state, goal state, actions (possible moves), and transition model (how

moves change the state).

02/21/2024 9
Cont.
Selecting a Representation

▪ Each state of the 8-Puzzle can be represented as a 3x3 grid, where each tile is labeled with a number (1-8) or

represented as an empty space. This representation allows us to model the state space and apply search
algorithms.

Choosing a Search or Problem-Solving Algorithm

▪ For the 8-Puzzle, we might use a search algorithm like A* search or breadth-first search to find the optimal

sequence of moves from the initial state to the goal state.

Implementing and Testing the Solution

▪ Develop code to represent the problem, apply the selected algorithm, and find a solution to the 8-Puzzle.

▪ Test the solution with different initial configurations of the puzzle to ensure it finds the correct solution

efficiently. 02/21/2024 10
Cont.
Evaluation and Iteration

▪ Measure the performance of the solution in terms of solution quality (optimality) and

computational efficiency.

▪ Refine the solution or explore alternative algorithms to improve performance if necessary.

02/21/2024 11
Example: Real-world problem - Autonomous driving
Problem Identification and Definition
▪ Autonomous driving involves developing vehicles capable of navigating roads safely without human

intervention.
▪ We define the problem by specifying the initial state (current position of the vehicle), goal state

(destination), actions (steering, accelerating, braking), and transition model (how actions affect the
vehicle's position and surroundings).
Selecting a Representation

▪ In autonomous driving, the state of the vehicle and its surroundings can be represented using

sensor data such as lidar, camera images, and GPS coordinates. This data is processed and
represented in a format suitable for decision-making algorithms.
02/21/2024 12
Cont.
Choosing a Search or Problem-Solving Algorithm

▪ Algorithm Autonomous driving systems may use a combination of techniques including path

planning algorithms (e.g., A* search), machine learning models for perception and decision-making,
and control algorithms for vehicle dynamics.

Implementing and Testing the Solution

▪ Implement the autonomous driving system using appropriate software and hardware components.

▪ Conduct extensive testing in simulated and real-world environments to ensure the system

operates safely and reliably under various conditions.

02/21/2024 13
Cont.
Evaluation and Iteration

▪ Evaluate the performance of the autonomous driving system in terms of safety, efficiency, and

compliance with regulations.

▪ Continuously improve the system based on feedback, new data, and advances in AI technology.

02/21/2024 14
Types of problem-solving in AI
The two common types are searching and constraint satisfaction problems (CSP).

Searching is a fundamental problem-solving technique in AI that involves exploring a space of

possible solutions to find a goal state or optimal solution. It's widely used in various domains such as
pathfinding, scheduling, planning, and optimization.

▪ Searching in AI is like exploring a maze to find the way out. It looks at different paths step by step

until it finds the best one.

▪ How it works: We use special algorithms to look through all the possible options until we find the

right answer. It's like trying different keys until one unlocks the door.

▪ Example: Imagine finding the shortest route on a map. Searching helps us explore different roads

until we find the quickest way to our destination. 02/21/2024 15

Cont.
Constraint Satisfaction Problems (CSP) involve finding solutions to problems where variables have certain
constraints on their values. It is common in various fields including scheduling, planning, resource allocation, and
decision making.

▪ Variables: Start by explaining what variables are. Variables are placeholders for values that we want to find. For

example, in a Sudoku puzzle, each square can be a variable.

▪ Domains: Introduce the concept of domains. Domains are the set of possible values that each variable can take. In

Sudoku, the domain for each square is typically the numbers 1 through 9.

▪ Constraints: Explain what constraints are. Constraints are rules that limit the possible combinations of values for

variables. In Sudoku, the constraints are that each row, column, and 3x3 subgrid must contain unique values.

▪ Solution: The goal of solving a CSP is to find a combination of values for variables that satisfy all the constraints. In

Sudoku, this means finding a number for each square so that no row, column, or subgrid contains the same number
02/21/2024 16
twice.
Cont.
The goal of Constraint Satisfaction Problems is to find a solution where all constraints are satisfied.

Example

▪ Variables: These are the entities that need to be assigned values. For example, in a scheduling problem,

variables could represent different tasks to be scheduled.

▪ Domains: Each variable has a domain, which is the set of possible values that a variable can take. For

example, in a scheduling problem, the domain for each task could be the set of possible time slots.

▪ Constraints: These define the rules that the variables must follow. Constraints restrict the possible

combinations of values that can be assigned to variables. For example, in a scheduling problem, a constraint
might be that two tasks cannot be scheduled at the same time.

▪ Solution: The goal of solving a CSP is to find a combination of values for variables that satisfy all the
02/21/2024 17
constraints.
Search algorithms in Artificial Intelligence
▪ In artificial intelligence, search algorithms are methods used to find a solution to a problem within a

predefined search space. These algorithms are crucial in various AI applications, including problem-
solving, planning, optimization, and decision-making.

▪ By evaluating scenarios and alternatives, search algorithms in artificial intelligence assist AI agents in

achieving the objective state.

▪ AI agents make artificial intelligence easy. These agents carry out tasks to achieve a specific

objective and plan actions that can lead to the intended outcome. The combination of these actions
completes the given task.

▪ The AI agents discover the best solution by considering all alternatives or solutions. Search

algorithms in artificial intelligence are used to find the best possible solutions for AI agents.
02/21/2024 18
Cont.
▪ Search techniques are universal problem-solving methods in Artificial Intelligence.

▪ These search strategies or algorithms were generally employed by rational agents or problem-

solving agents in AI to solve a given problem and provide the best outcome.

▪ Rational agents in AI are designed to achieve specific goals or objectives. These goals can vary

depending on the problem domain, but the agent's primary objective is to find a sequence of
actions that leads to the attainment of these goals.

▪ Before employing search algorithms, the problem must be represented in a formal manner. This

involves defining:
✓Initial state: The starting configuration or situation of the problem.

✓Actions: The set of possible actions or moves that the agent can take. 02/21/2024 19
Cont.
✓Transition model: The rules that dictate how actions change the state of the problem.

✓Goal test: The condition that determines whether a particular state is a solution to the problem.

▪ Depending on the problem characteristics, different search algorithms or strategies may be employed.

Such as uninformed search algorithms, and informed search algorithms.

▪ Once a search algorithm is applied, the agent evaluates the solutions generated and compares them

based on various criteria, such as Completeness: Whether the algorithm guarantees to find a solution if
one exists, Optimality, Time and Space Complexity.

▪ After finding a solution through the search process, the agent executes the sequence of actions

determined by the algorithm to achieve the desired outcome. The actions taken by the agent are based
on the solution path found during the search.
02/21/2024 20
Cont.
▪ Generally, search strategies or algorithms are essential components of rational agents in AI, enabling

them to systematically explore and navigate complex problem spaces to find optimal or satisfactory
solutions.

▪ By employing these algorithms, agents can effectively address a wide range of problems in various

domains.

02/21/2024 21
Cont.
Search Algorithm Terminologies:

▪ Search: Searching is a method of solving a search problem in a given search space by following a

set of steps. There are three basic variables that can contribute to a search problem:
▪ Search Space: Search space represents a set of possible solutions, which a system may have.

▪ Start State: It is a state from where the agent begins the search.

▪ Goal test: It is a function that observe the current state and returns whether the goal state is

achieved or not.

▪ Search tree: A tree representation of a search problem. The root node, which corresponds to the

initial state, is at the top of the search tree.

02/21/2024 22
Cont.
▪ Actions: It gives the description of all the available actions to the agent.

▪ Transition model: A description of what each action do, can be represented as a transition

model.

▪ Path Cost: It is a function which assigns a numeric cost to each path.

▪ Solution: It is an action sequence that connects the start node and the goal node.

▪ Optimal Solution: If a solution has the lowest cost of all the solutions, it is said to be the optimal

solution.

02/21/2024 23
Cont.
Properties of Search Algorithms:

The four most important properties of search algorithms to compare their efficiency are as follows:

▪ Completeness: If a search method guarantees to return a solution if at least one solution exists

for any random input, it is said to be complete.

▪ Optimality: A solution obtained for an algorithm is considered to be optimal if it is guaranteed to

be the best solution (lowest route cost) among all other solutions.

▪ Time Complexity: It is a measurement of how long it takes an algorithm to finish a task.

▪ Space Complexity: The maximum storage capacity required at any time during the search, as

measured by the problem's complexity.

02/21/2024 24
Types of search algorithm
▪ Based on the search issues search algorithms in artificial intelligence divide into uninformed (Blind

search) and informed (Heuristic search) algorithms.

02/21/2024 25
Cont.
Uninformed Search

▪ Is a type of search algorithm used in artificial intelligence where the search strategy does not have

any additional information about the problem beyond what is given in the problem definition.

▪ It's like searching blindly without any prior knowledge or hints about the direction of the goal.

▪ Imagine you're trying to find your way through a maze with no prior knowledge of its layout or any

clues about which path might lead you to the exit.

▪ Uninformed search algorithms operate similarly; they systematically explore the search space

without any insight into the structure of the problem.

02/21/2024 26
Cont.
It can be divided into five main types:

▪ Breadth-first search

▪ Depth-first search

▪ Uniform cost search

▪ Iterative deepening depth-first search

▪ Bidirectional Search

02/21/2024 27
Cont.
Breadth-First Search (BFS)

▪ The most frequent search approach for traversing a tree or

graph is breadth-first search. Breadth-first search is the
name given to an algorithm that searches a tree or graph in
a breadth-first manner.

▪ Before going on to nodes of the next level, the BFS

algorithm starts searching from the tree's root node and
extends all successor nodes at the current level.

▪ A general-graph search algorithm like the breadth-first

search algorithm is an example.

▪ A FIFO queue data structure was used to implement a

breadth-first search. 02/21/2024 28
Cont.
Advantages

▪ If a solution is available, BFS will provide it.

▪ If there are multiple answers to a problem, BFS will present the simplest solution with the fewest

steps.

Disadvantages

▪ It necessitates a large amount of memory since each level of the tree must be saved into memory

before moving on to the next.

▪ If the solution is located far from the root node, BFS will take a long time.

02/21/2024 29
Cont.
Example:

▪ For example you are exploring a social network graph to find the shortest connection

between two users. Breadth-First Search would start by exploring all the immediate friends of
the starting user before moving on to friends of friends, and so on. It systematically searches
through the network, ensuring that it finds the shortest path.

02/21/2024 30
Cont.
Depth-First Search (DFS)

▪ A recursive approach for traversing a tree or graph data

structure is a depth-first search.

▪ The depth-first search is named after the fact that it begins at

the root node and follows each path to its greatest depth
node before going on to the next path.

▪ DFS is implemented using a stack data structure.

Note: Backtracking is a recursive algorithm strategy for

identifying all possible answers

02/21/2024 31
Cont.
Advantages

▪ Because DFS only needs to store a stack of nodes on the path from the root node to the current

node, it uses extremely little memory.

▪ It takes less time to reach the goal node than the BFS method (if it traverses in the correct

order).

Disadvantages

▪ The DFS algorithm performs deep searching and may occasionally enter an infinite cycle.

02/21/2024 32
Cont.
Example:

▪ For example you are navigating through a maze, trying to find a path from the entrance to the

exit. Depth-First Search would explore one corridor of the maze as far as possible before
backtracking and trying another corridor. It continues this process until it either finds the exit
or exhausts all possible paths.

02/21/2024 33
Cont.
Uniform cost search(UCS) –

▪ Uniform Cost Search (UCS) is a method for finding the

lowest-cost path from a starting point to a goal point in a

graph.

▪ It explores nodes in order of their total cost from the start

node, ensuring that it always selects the cheapest option

available.

▪ It is similar to the breadth-first search if each transition's

cost is the same.

02/21/2024 34
Cont.
Advantages

▪ Because the path with the lowest cost is chosen at each state, uniform cost search is the best

option.

Disadvantages

▪ UCS may consume a lot of memory, especially if the search space is large, as it needs to store

information about all visited nodes and their associated costs.

02/21/2024 35
Cont.
Example:

▪ For example you are trying to find the cheapest route from your home to a friend's house

through a city map with different roads having various tolls. UCS would help you find the path
with the lowest total toll cost, ensuring you reach your friend's house spending the least
amount of money possible.

02/21/2024 36
Cont.
Bidirectional Search

▪ Bidirectional Search is a search algorithm that

simultaneously explores the search space from both the
start and goal nodes, meeting in the middle when they
intersect.

▪ It aims to reduce the search space by exploring from

both ends towards each other, potentially resulting in a

faster search compared to traditional search algorithms
like breadth-first search or depth-first search.

02/21/2024 37
Cont.
Advantages

▪ Bidirectional Search can be more efficient than traditional search algorithms, especially in large search spaces,

as it explores from both ends simultaneously, potentially reducing the search space.

Disadvantages

▪ The bidirectional search tree is difficult to implement.

▪ Bidirectional Search may require additional memory to store information about nodes visited from both ends,

which can be a concern in memory-constrained environments.

02/21/2024 38
Cont.
Example:

▪ For example you are trying to find the shortest path between two locations in a city using a map.

Bidirectional Search would start exploring from both your current location and your destination
simultaneously, searching for the shortest path from both ends. When the search from both ends
meets at an intersection, you've found the shortest path.

02/21/2024 39
Cont.
Informed Search

▪ Domain knowledge is used by informed search algorithms, the problem information is available which can

guide the search. Informed search tactics are more likely to find a solution than uninformed search strategies.

▪ Informed search, also known as heuristic search, is a type of search algorithm that uses additional information

about the problem domain to guide the search process.

▪ This extra information, called a heuristic, helps the algorithm make better decisions about which paths to

explore to reach the goal more efficiently.

▪ Informed search can solve a lot of complicated problems that can't be solved any other way.

▪ The two types of informed search are:

✓ Greedy Search and A* Search 02/21/2024 40

Cont.
Greedy Search:

▪ Greedy search is a simple informed search algorithm that always chooses the path that appears to

be the best at the current moment, without considering the long-term consequences.

▪ It makes decisions based solely on the information available at each step, aiming to get closer to the

goal as quickly as possible.

Example: Imagine you're trying to find the shortest route to a destination on a map. With greedy
search, you would always choose the path that looks shortest from your current location, without
considering if it might lead to a dead-end or a longer route in the future.

02/21/2024 41
Cont.
Advantages and Disadvantages

▪ Greedy search is fast and straightforward, but it may not always find the optimal solution.

▪ It can get stuck in local optimal solutions and may overlook better paths that require initially

sacrificing short-term gains for long-term benefits.

02/21/2024 42
Cont.
A* Search

▪ A* search is a more sophisticated informed search algorithm that combines information about both

the cost of reaching a state (known as g-value) and an estimate of the cost to reach the goal from that
state (known as h-value).

▪ It evaluates each possible path by considering both the current cost and the estimated remaining

cost, aiming to find the most promising path.

Example: Continuing with the map example, A* search considers both the distance traveled so far (g-
value) and an estimate of the remaining distance to the destination (h-value) for each potential route.
It prioritizes paths that have lower total estimated costs, leading to more efficient exploration of the
search space. 02/21/2024 43
Cont.
Advantages and Disadvantages

▪ A* search is often more efficient than a greedy search and can find optimal solutions when used

with an admissible heuristic (one that never overestimates the true cost to reach the goal).

▪ However, finding an appropriate heuristic can be challenging, and A* search may still require

significant computational resources for large search spaces.

02/21/2024 44
Applications
Search algorithms find applications across various domains within artificial intelligence. Here are some common
applications:

▪ Problem Solving: Search algorithms are extensively used to find solutions to problems in various domains such
as puzzles, games (e.g., chess, Sudoku), route planning (e.g., GPS navigation), and logistics optimization.

▪ Natural Language Processing (NLP): In NLP, search algorithms are applied in tasks such as machine
translation, speech recognition, and information retrieval. For instance, beam search is used in machine translation
to generate the most likely sequence of words given an input sentence.

▪ Robotics and Path Planning: Search algorithms play a crucial role in robotic path planning tasks, where robots
need to navigate through environments to reach their goals safely and efficiently. Algorithms like A* search and
Dijkstra's algorithm are commonly used for pathfinding.

▪ Machine Learning: Search algorithms are employed in various machine learning techniques, such as feature
selection, hyperparameter tuning, and model selection. For example, grid search and randomized search are used
for hyperparameter optimization in machine learning algorithms. 02/21/2024 45
Cont.
▪ Game Playing: Search algorithms are fundamental in creating AI agents for playing board games like chess, Go, and

checkers. These algorithms enable the AI to explore possible moves and choose the best action based on a search
strategy.

▪ Automated Planning and Scheduling: Search algorithms are used to generate plans or schedules that satisfy

given goals or objectives while adhering to constraints. Applications include automated assembly line scheduling,
project management, and logistics planning.

▪ Computer Vision: Search algorithms can be applied in computer vision tasks such as object detection, image

segmentation, and image recognition. For example, search-based optimization techniques may be used to find
optimal parameters for image processing algorithms.

▪ Optimization Problems: Search algorithms are widely used to solve optimization problems in various fields,

including engineering, finance, and operations research. These problems involve finding the best solution from a set
of feasible options, such as minimizing costs, maximizing efficiency, or optimizing resource allocation. 02/21/2024 46
End

02/21/2024 47
Assignment 1
1. In your opinion, which artificial intelligence technologies pose the greatest
concerns in terms of both security and ethics? Please elaborate on the potential
risks and implications associated with these technologies from both perspectives.
Provide examples and discuss possible strategies to address these concerns
effectively.

02/21/2024 48