Fundamentals of Artificial Intelligence

Soft. Eng. Extension Program

April 2024

04/21/2024
 Chapter 3
Problem-Solving

04/21/2024 2
Outline
▪ Problem solving

▪ Search algorithms in Artificial Intelligence

▪ Problem-solving agents

▪ Searching strategies

▪ Uninformed search and

▪ Informed search

04/21/2024 3
Discussion Question

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

04/21/2024 4
Problem-Solving
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.

04/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. 04/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.

04/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.

04/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).

04/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. 04/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.

04/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.
▪ 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.
04/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.

04/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.

04/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. 04/21/2024 15

Cont.
Constraint Satisfaction Problems (CSP): Reading Assignment.

04/21/2024 16
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.
04/21/2024 17
Cont.
▪ Search techniques are universal problem-solving methods. These search techniques 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.
04/21/2024 18
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.
04/21/2024 19
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.

04/21/2024 20
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. Three basic variables 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 observes 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.

04/21/2024 21
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.

04/21/2024 22
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.

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

search) and informed (Heuristic search) algorithms.

04/21/2024 24
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.
04/21/2024 25
Cont.
It can be divided into five main types:

▪ Breadth-first search

▪ Depth-first search

▪ Uniform cost search

▪ Bidirectional Search

04/21/2024 26
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. 04/21/2024 27

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.

04/21/2024 28
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.

▪ Backtracking is a recursive algorithm strategy for

identifying all possible answers

04/21/2024 29
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.

04/21/2024 30
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.

04/21/2024 31
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.

04/21/2024 32
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.
04/21/2024 33
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.

04/21/2024 34
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, 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. 04/21/2024 35
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.
04/21/2024 36
Cont.
A* Search

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

both the cost of reaching a state and an estimate of the cost to reach the goal from that state.

▪ 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
and an estimate of the remaining distance to the destination for each potential route. It prioritizes
paths that have lower total estimated costs, leading to more efficient exploration of the search space.
04/21/2024 37
End of Chapter 3

04/21/2024 38
 Assignment 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.

04/21/2024 39