Lesson 3 - State Space Search (Part 2) PDF

CMPSC 162: Artificial Intelligence Lesson 3 State Space Search (Part 2) WILBEN CHRISTIE R. PAGTACONAN Faculty Mariano Marcos State University College of Computing and Informati...

CMPSC 162: Artificial Intelligence Lesson 3 State Space Search (Part 2) WILBEN CHRISTIE R. PAGTACONAN Faculty Mariano Marcos State University College of Computing and Information Sciences Search Searching through a state space involves the following: A set of states Operators and their costs Start state A test to check for goal state The basic search algorithm Let L be a list containing the initial state (L= the fringe) Loop if L is empty return failure Node ← select (L) if Node is a goal then return Node (the path from initial state to Node) else generate all successors of Node, and merge the newly generated states into L End Loop Search algorithm: Key issues ✓ The search tree may be unbounded. ✓ Should we return a path or a node? ✓ The search graph may be weighted or unweighted. Evaluating Search strategies Completeness: Is the strategy guaranteed to find a solution if one exists? Evaluating Search strategies Optimality: Does the solution have low cost or the minimal cost? Evaluating Search strategies What is the search cost associated with the time and memory required to find a solution? ✓ Time complexity: Time taken (number of nodes expanded) (worst or average case) to find a solution. ✓ Space complexity: Space used by the algorithm measured in terms of the maximum size of fringe Search Tree – Terminology Root Node: The node from which the search starts. Leaf Node: A node in the search tree having no children. Search Tree – Terminology Ancestor/Descendant: X is an ancestor of Y is either X is Y’s parent or X is an ancestor of the parent of Y. If X is an ancestor of Y, Y is said to be a descendant of X. Search Tree – Terminology Branching factor: the maximum number of children of a non-leaf node in the search tree Path: A path in the search tree is a complete path if it begins with the start node and ends with a goal node. Otherwise it is a partial path. Node data structure ✓ A state description ✓ A pointer to the parent of the node ✓ Depth of the node ✓ The operator that generated this node ✓ Cost of this path (sum of operator costs) from the start state Graph vs Search Tree State space graph Graph vs Search Tree Search Tree Uninformed Search Strategies The strategy gives the order in which the search space is searched Breadth first Depth first Depth limited search Iterative deepening Uniform cost Breadth First Search breadth-first search (BFS) is a search algorithm that begins at the root node and explores all the neighbouring nodes. Breadth First Search Let fringe be a list containing the initial state Loop if fringe is empty return failure Node ← remove-first (fringe) if Node is a goal then return the path from initial state to Node else generate all successors of Node, and (merge the newly generated nodes into fringe) add generated nodes to the back of fringe End Loop Breadth First Search Step 1: Initially fringe contains only one node corresponding to the source state A. FRINGE(Open List): A Closed List: [] Breadth First Search Step 2: A is removed from fringe. The node is expanded, and its children B and C are generated. They are placed at the back of fringe. FRINGE(Open List): B C Closed List: A Breadth First Search Step 3: Node B is removed from fringe and is expanded. Its children D, E are generated and put at the back of fringe. FRINGE(Open List): C DE Closed List: AB Breadth First Search Step 4: Node C is removed from fringe and is expanded. Its children D and G are added to the back of fringe. FRINGE(Open List): D EDG Closed List: ABC Breadth First Search Step 5: Node D is removed from fringe. Its children C and F are generated and added to the back of fringe. FRINGE(Open List): EDGCF Closed List: A B C D Breadth First Search Step 6: Node E is removed from fringe. It has no children. FRINGE(Open List): DGCF Closed List: A B C D E Breadth First Search Step 7: D is expanded, B and F are put in OPEN. FRINGE(Open List): GCFBF Closed List: A B C D E D Breadth First Search Step 8: G is selected for expansion. It is found to be a goal node. So the algorithm returns the path A - C - G by following the parent pointers of the node corresponding to G. The algorithm terminates. FRINGE(Open List): GCFBF Closed List: A B C D E D Properties of Breadth-First Search Complete. The algorithm is optimal (i.e., admissible) if all operators have the same cost. Otherwise, breadth first search finds a solution with the shortest path length. Properties of Breadth-First Search The algorithm has exponential time and space complexity O(bd). A complete search tree of depth d where each non-leaf node has b children, has a total nodes of: 1 + b + b2 +... + b(d-1) = (bd - 1)/(b-1) Advantage of Breadth First Search Finds the path of minimal length to the goal. Disadvantage of Breadth First Search Requires the generation and storage of a tree whose size is exponential the depth of the shallowest goal node. Breadth First Search Example (1) Home (2) Room1 (3) Room2 (4) Room3 (5) Desk (6) Toilet (7) Desk (8) Toilet (9) Bed (10) Chair END OF LESSON 3 (Part 2)