# Searching and Problem Solving in AI

# 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?