Uninformed search strategies

Introduction

Search strategies determine which node is selected from the frontier. How we choose the frontier is what changes from a uninformed search strategy to another. Uninformed search strategies also called blind search because they use only the information contained in the problem formulation.

The frontier is the set of node that we could expand. Deciding which node to consider first is the essence of search. We say that any state that has had a node generated for it has been reached (whether or not that node has been expanded). Note that we distinguish between:

• tree-search: no elimination of redundant states

• graph-search: with elimination of reduntant states

Some notes on terminology:

• Generating a node means adding that node to the frontier

• Extracting a node means selecting a node for expansion from the frontier. This is where most search algorithm differ.

• Expanding a node means generating it's child nodes, which means adding them to the frontier

Pseudocode of tree-search algorithm:

LOOP DO
	IF there are no more nodes candidate for expansion
		RETURN failure
	select a node not yet expanded
	IF the node corresponds to a goal state 
		RETURN the corresponding solution
	ELSE
		expand the chosen node, adding the resulting nodes to the tree

#### Property list

1. Completeness - does it always find a solution when there is one?

2. Optimality - minimum cost solution?

3. Complexity - $T(n)$, $S(n)$

Parameters list

1. $b$, branching factor of the search tree (it is the number of children at each node, the outdegree. If this value is not uniform, an average branching factor can be calculated.)

2. $d$, depth of the shallowest goal node

3. $m$, maximum depth of the search tree

4. $l$, depth limit

We have the following types of uninformed search algorithms:

1. BFS

2. Uniform cost search

3. DFS

4. Depth limited search

5. Iterative deepening search

6. Bidirectional search

Breadth First Search (BFS)

BFS first chooses the root, then all the successors of the root, then all their successors, and so on. It chooses the shallowest node (the node with minimum depth). All nodes at level $k$ of the search tree must be chosen before choosing any node at level $k+1$. It is implented by using a FIFO queue:

image-20211005115214356

Note that from <3, 4, 5> it goes to <4, 5, 6, 7> because it expands the shallowest node, which is 3.

Properties

• complete (assuming $b$ finite)

• optimal when step costs are all equal (e.g., they are unitary)

• $S(n) = T(n) = O(b^{d+1})$

Node extraction/expansion

Given the frontier, and given the node selected by following the algorithm's policy:

1. Is the extracted node a goal node? If yes -> we're done, and we can stop extracting nodes. Otherwise -> add it to the frontier.

2. Expansion of nodes added to the frontier (successor generation). We can apply goal test at each successor generation during node expansion (only is BFS)

BFS with elimination of repeated states

We have a difference in node extraction: we first check if the extracted node is in the closed list. If it is not, we add it to the closed list, and then we expand it. Closed list: set of states.

Notes

• Node that while expanding successors (adding them to the frontier) we proceed in lexographical order.

• Goal test at node extraction is done only for BFS.

Depth First Search (DFS)

Depth-first search chooses first the root node, then one of its successors, then one of its successors, and so on. It chooses the deepest node. When depth-first search reaches a node without successors, it “backtracks” and chooses one of the deepest nodes not yet chosen.

Example:

image-20211005125514916

#### Properties

• not complete, since it can follow paths with infinite length. This means that if a solution exists, DFS is not guaranteed to find it. It is complete only for acyclic states

• not optimal, because the solution can be found at any level of the tree

• $S(n) = O(bm)$

• $T(n) = O(b^{m})$

  • $m$ is the maximum depth of the search tree (it could be $m=\infin$). Of course $m \ge d$ (often $m >> d$).

  • At each step of the search, only a single path (from the root to a leaf node) must be stored in memory. Also the nodes not yet expanded at each level should be stored.

Node extraction/expansion

1. Node generation: add node to frontier

2. Node extraction: is it goal? Yes -> stop. Otherwise -> expand.

Node extraction/expansion with elimination of repeated states (backtracking)

1. Node generation: add node to frontier

2. Node extraction: is it goal? Yes -> stop. Otherwise ->

   ​ Is it in the closed list? Yes -> skip it. Otherwise -> add it to closed list and expand it.

Notes

• The fact that goal test is execute at extraction time means that the goal node could be found quite some time after it was added to the frontier.

Uniform Cost Search (UCS)

Uniform-cost search is a search strategy that generalizes BFS: it sorts the frontier according to their increasing path cost from the root, it does not necessarily choose the shallowest node.

#### Properties

1. complete, assuming $b$ finite and step costs are larger than a small positive (strictly positive)

2. optimal

3. $T(n) = S(n) = O(b^{1+[C*/e]})$, where $C*$ is the cost of the optimal solution

Node extraction/expansion

1. Node generation: add node to frontier

2. Node extraction: is it goal? Yes -> stop. Otherwise -> expand

Notes

• Increasing path cost means that at each step the cost between the node we're expanding is the sum of all the path costs from the initial state to it.

• Like BFS, it can be implemented w/out or with elimination of repeated states. In the latter the node extraction/generation algorithm is the following:

  1. Node generation: add node to frontier

  2. Node extraction: is it a goal node? Yes -> stop. Otherwise:

     Is it in the closed list? Yes -> skip. Otherwise -> add to closed list, expand.

Depth-limited search

Depth-limited search is a DFS with a predetermined depth limit $l$. Nodes at level $l$ are assumed to have no successors.

#### Properties

• complete if $l>=d$, but $d$ is xoften unknown

• not optimal

• $S(n) = O(bl)$

• $T(n) = O(b^{l})$

Iterative deepening search

Iterative deepening search performs repeated depth-limited searches, increasing the depth limit $l$: $l=0$, $l=1$, $l=2$, $...$.

Properties

• complete, if $b$ is finite

• optimal, if steps costs are all equal

• $S(n) = O(bd)$

• $T(n) = O(b^{d})$

Best compromise between BFS and DFS.

Bidirectional search

Bidirectional search performs two parallel searches:

• a “forward” search: from the initial state to a goal state

• a “backward” search: from a goal state to the initial state

Using the search strategies previously discussed, many nodes (in the search tree) corresponding to the same state (in the state space) can be generated.

How do we manage repetitions?

Such “repeated states” (revisited states) can generate infinite search trees even if the state space is finite: search is inefficient.

To avoid repeated states, we need to be able to compare the states corresponding to nodes. We use a closed list that contains the states corresponding to nodes that have been already chosen from the frontier:

• When a node is chosen for expansion, the corresponding state is checked against those in the closed list.

• When a node is expanded, the corresponding state is added to the closed list.

$T(n), S(n)$ recap

XmiuMbYqOydAcutI-image-1640610009896