3 - uninformed search

Question 1

problem-solving agent

Answer 1

an agent that can figure out the best ocurse of action for a specific situation

Question 2

the problem of designing goal-based agents

Answer 2

Solution: fixed sequence of actions
Search: looking for the sequence of actions that reaches the goal
Agent: can ignore percepts during execution

Question 3

Objectives of a problem solving agent

Answer 3

-formulate appropriate problems as search tasks
-know the fundamental search strategies and algorithms
-evaluate the suitability of a search strategy for a problem

Question 4

Search problem components

Answer 4

♥ Initial state
♥ Goal state
♥ Path cost
♥ Successor Function: result of doing an action in a state
♥ Optimal solution: sequence of actions with the lowest path cost for reaching the goal

Question 5

State Space

Answer 5

The set of all states reachable from initial state by any sequence of actions

Question 6

Tree Search

Answer 6

Begin at the root node (starting state) and expandit by making a list of all possible successor states - keep going until you reach required state

///algorithm outline - upon ititialisation we choose a fringe and expand upon that according to our search strategy;; to avoid repeated states, we keep an explored set every time we expand it, meaning that every time you add a node to the fringe, check whether it already exists in the fringe with a higher path cost, and if yes, replace that node with the new one

Question 7

Uninformed search strategies -

Breadth-first search (BFS)

Answer 7

Expand shallowest unexpanded node, fringeis a FIFO queue, i.e., new successors go at end (so we go by ‘layers’ - first the highest layers, then deeper)

Question 8

Uninformed search strategies -

Depth-first search (DFS)

Answer 8

Expand deepest unexpanded node - like Breadth-first search but we first search the lowest layer, then check the highest ones

Question 9

Uninformed search strategies -

Uniform-cost search (UCS)

Answer 9

Expand least-cost unexpanded node - fringe ordered by path cost (priority queue) * Equivalent to breadth-first if step costs all equal

Question 10

Uninformed search strategies -

Iterative deepening search (IDS)

Answer 10

To keep DFS from wandering down an infinite path
1.Check the root 2.Do a DFS searching for a path of length 1 3.If there is no path of length 1, do a DFS searching for a path of length 2 4.If there is no path of length 2, do a DFS searching for a path of length 3…….

IDDFS calls DFS for different depths starting from an initial value. In every call, DFS is restricted from going beyond given depth. So basically we do DFS in a BFS fashion.

Question 11

Search strategies

Answer 11

picking the order of node expansion based on criteria:
- Completeness
- Optimality
- Time complexity
- Space complexity