Question

3.1 Bratko states that iterative deepening combines the best properties of breadth-first search and depth-first search and is therefore, in practice, often the best choice
amongst the basic search methods. Discuss this statement.

3.2 Discuss the concept of the ‘locality’ of the effects of actions in the context of planning problems.

Answer 1

3.1) Iterative deepening is the best choice among the basic search methods. As Iterative deepening combines both the best properties of depth first search and breadth first search.

The current statement stated by Bratko that Iterative deepening combines the best properties of breadth first search and depth first search and therefore in practice often it's the best choice. If we closely monitor that depth first search property we will see that dfs first Traverse node goes through one by one by the root then the next adjacent one. The basic problem in dfs is that if there is a node close to root but not in few subtress traversed by DFS. Then dfs arrived at that particular leaf node very late so it is not considered as the shortest path to find a node in term number of edges in depth first search.

On the other hand if we talk about Breadth first search, it goes level by level but it requires more space. The space needed by DFS is O(d) where d the depth of the tree but space required by BFS is O(n) where n is a number of nodes or leaves in the tree.In BFS we need to traverse every level one by one in a queue. So both the ways are having advantages and disadvantages that's why Iterative deepening is another approach that we can use to combine the best properties of both of them. In short we do DFS in a BFS manner in this Iterative deepening.

In iterative deepening search , the child nodes on the bottom level are expanded once then next to bottom level expanded twice and upto root node till the expansion reaches upto d+1 times. So, the total number of expansions in iterative deepening search is O(b^d).

Iterative deepening combines the best property of breadth first searchs fast search and best property of depth first search as its space efficiency. In this way both the overheads of these searching ways are overcome and we get a best technique for basic search methods in the name of Iterative deepening.

3.2) The planning problem in artificial intelligence is about the decision making that is taken by the virtual intelligent machines used by artificial intelligence as human robots or computer programs. When they are set to perform some specific goal they are set to involve a sequence of actions that will perform step by step in order to perform this specific task for which the virtual machine has been made.

So these planning problems are of various categories. Some of the planning problems are restriction to one agent into the deterministic environment. If a machine is under uncertainty for which it hasn't been prepared, it shows the effect of action over itself and therefore we don't have any prediction to predict the results of a plan with certainty.

Hence the concept of locality of effect of actions has been raised in such a scenario in which the locality under which the decision has been unpredictable and it's suitable actions are not programmed in the machine. It itself shows the locality in which it's showing problems and force to make uncertainty decisions.

In this way the locality in which the effects of action have arising can be easily programmed in future by the machine programmer.