Searching in Problem Solving
A search problem is defined by:
• A search space: – The set of objects among which we search for the solution
Examples: routes between cities,
or n-queens configuration
• A goal condition – Characteristics of the object we want to find in the search space.
Examples: Path between cities A and B
Non-attacking n-queen configuration
Four general steps in problem solving:
Goal formulation
deciding on what the goal states are
based on current situation and agent’s performance measure
What are the successful world states
Problem formulation
how can we get to the goal
What actions and states to consider given the goal
state the problem in such a way that we can make efficient progress toward a goal state.
Search
Determine the possible sequence of actions that lead to the states of known values and then choose the best sequence.
Search algorithms – input is a problem, output is a solution (action sequence)
Execute
Given the solution, perform the actions.
Search problems can be often represented using graphs
Typical example: Route finding – Map corresponds to the graph, nodes to cities, links valid moves via available connections.
Goal: find a route (sequence of moves) in the graph from S to T
Puzzle 8.
Find a sequence of moves from the initial configuration to the goal configuration.
- nodes corresponds to states of the game,
- links to valid moves made by the player
N-queens
Some problems are easy to convert to the graph search problems
But some problems are harder and less intuitive
Take e.g. N-queens problem.
Problem:
- We look for a configuration, not a sequence of moves
- No distinguished initial state, no operators (moves)
Problem Solving Agent
Special Type of Goal Based Agent
- Problem solving agent is a goal-based agent that decides what to do by finding sequences of actions that lead to desirable states
- Intelligent agents are supposed to maximize their performance measure
- This can be simplified if the agent can adopt a goal and aim at satisfying it
- Goals help organize behavior by limiting the objectives that the agent is trying to achieve
Ex. Vacuum cleaner world
- two locations – which may or may not contain dirt
- Vacuum is in one of the locations
- Actions – move left
- move right
- suck
Agent first formulates goal and problem, then determines an action sequence, after which it executes the sequence.
Uninformed search methods
Search techniques that rely only on the information available in the problem definition
- Breadth first search
- Depth first search
- Iterative deepening
- Bi-directional search
Properties of search methods :
Completeness.
Does the method find the solution if it exists?
Optimality.
Is the solution returned by the algorithm optimal? Does it give a minimum length path?
Space and time complexity.
How much time it takes to find the solution?
How much memory is needed to do this?
