Problem-Solving in AI
Lecture no: 4
Problem-Solving
Problem solving is an important aspect of Artificial Intelligence.
A problem can be considered to consist of a goal and a set of actions
that can be taken to lead to the goal.
At any given time, we consider the state of the search space to
represent where we have reached as a result of the actions we have
applied so far.
Classical Problem Solving Approach
Consisted mainly of inference engines used for rule-based systems
Early applications included automating expert knowledge in specific domains mainly in medical
diagnosis and fraud detection.
What is Searching in AI?
Modern AI encloses computational intelligence, primarily biologically-inspired
numeric optimization algorithms like neural networks.
Search is at the heart of problem-solving in AI.
Search in AI is the process of navigating from a starting state to a goal
state by transitioning through intermediate states.
Basic Terms Used in Searching Algorithms
• Search: Searching is a step by step procedure to solve a search-problem in a given
search space. A search problem can have three main factors:
• Search Space: Search space represents a set of possible solutions, which a system may have.
• Start State: It is a state from where agent begins the search.
• Goal test: It is a function which observe the current state and returns whether the goal state
is achieved or not.
• Search tree: A tree representation of search problem is called Search tree. The root
of the search tree is the root node which is corresponding to the initial state.
• 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 which leads from the start node to the goal node.
• Optimal Solution: If a solution has the lowest cost among all solutions.
Properties of Search Algorithms
Following are the four essential properties of search algorithms to compare the efficiency
of these algorithms:
• Completeness: A search algorithm is said to be complete if it guarantees to return a
solution if at least any solution exists for any random input.
• Optimality: If a solution found for an algorithm is guaranteed to be the best solution
(lowest path cost) among all other solutions, then such a solution for is said to be an
optimal solution.
• Time Complexity: Time complexity is a measure of time for an algorithm to complete its
task.
• Space Complexity: It is the maximum storage space required at any point during the
search, as the complexity of the problem.
Data-Driven vs Goal-Driven Search
Data-Driven vs Goal-Driven Search
Generate and Test Approach
Simplest approach to search – also called blind search or brute-force search
Involves generating each node in the search space and testing it to see if it is a goal node.
Must have a suitable Generator, which should satisfy three properties:
1. It must be complete: In other words, it must generate every possible solution; otherwise it
might miss a suitable solution.
2. It must be nonredundant: This means that it should not generate the same solution twice.
3. It must be well-informed: This means that it should only propose suitable solutions and
should not examine possible solutions that do not match the search space.
It is an uninformed search.
Types Of Searching in AI
Uninformed Search
Uninformed search is a type of search algorithm that operated in
brute force way. Uninformed search algorithms are also called as a
blind search algorithm because these do not have any domain-specific
knowledge other than how to traverse a tree.
Informed Search
• Informed search algorithms use domain knowledge.
• In an informed search, problem information is available which can guide the
search.
• An informed search is more efficient than an uninformed search because in
informed search, along with the current state information, some additional
information is also present, which make it easy to reach the goal state.
• Informed search is also called a Heuristic search.
Types Of Search Algorithms
Comparison between Informed and Uninformed Search
Informed Search Un-Informed Search
It uses knowledge for the searching process. It doesn’t use knowledge for searching process.
It finds solution more quickly. It finds solution slow as compared to informed search.
It may or may not be complete. It is always complete.
Cost is low. Cost is high.
It consumes less time. It consumes moderate time.
It provides the direction regarding the solution. No suggestion is given regarding the solution in it.
It is less lengthy while implementation. It is more lengthy while implementation.
Greedy Search, A* Search, Graph Search Depth First Search, Breadth First Search
Problem Abstraction
• Real world is complex and has more details.
• Irrelevant details should be removed from state space and actions, which
is called abstraction.
• What’s the appropriate level of abstraction?
• the abstraction is valid, if we can expand it into a solution in the more
detailed world.
• the abstraction is useful, if carrying out the actions in the solution is
easier than the original problem.
• remove as much detail as possible while retaining validity and usefulness.
Example: Vacuum-Cleaner
States: 8 states
Initial state: any state
Actions: Left, Right, and Suck
Transition model: complete state space, see next page
Goal test: whether both squares are clean
Path cost: each step costs 1
Complete State Space
Example: 8-puzzle
• States: location of each tile and the blank
• Initial state: any, 9!/2
• Actions: blank moves Left, Right, Up or Down
• Transition model: Given a state and action, returns
the resulting state
• Goal test: Goal configuration
• Path cost: Each step costs 1
