Lec-2: What is State Space Search | Introduction to Problem Solving in Artificial Intelligence

The video introduces State Space Search as a major application in Artificial Intelligence, focusing on problem-solving. It highlights the historical significance of problem-solving research in the 1960s-70s, particularly for games like Tic-Tac-Toe, Water Jug, 8-Queen, and Chess. The goal is to enable machines to solve problems like humans, making state space searching crucial.

State space refers to all possible states a problem can be in, from a start state to a goal state, including intermediate states. Precise representation of a problem is essential, especially for machines or agents, as verbal instructions are insufficient. Clear representation aids in analyzing how to approach and solve the problem step-by-step.

State space search is defined by a tuple (S, A, Result, Cost). 'S' represents the total number of states, including start, goal, and intermediate states. 'A' denotes the set of all possible actions an agent can take. 'Result' refers to the new state achieved after an action. 'Cost' quantifies the effort or distance to move between states, aiming for optimal solutions with minimum cost.

The 8-puzzle problem is used as an example to illustrate state space search. The problem involves a 3x3 board with 8 numbered tiles and one empty space. The start state is the initial arrangement, and the goal state is a predefined ordered arrangement (e.g., 1-8). Actions in this problem involve moving the empty space (up, down, left, right), generating new intermediate states. Legal and illegal moves must be defined to guide the search.

As actions are taken (e.g., moving the empty space), different branches of states are formed. Each action leads to a resultant state. The video then transitions to discussing search strategies for finding the goal state. These are broadly categorized into uninformed (blind) search and informed search.

Uninformed search (blind search) involves exploring states without any knowledge about the problem domain beyond start and goal states, leading to extensive exploration. Informed search, on the other hand, utilizes heuristic concepts to solve problems more quickly by making locally beneficial decisions. Uninformed search often has exponential time complexity (O(b^d), where 'b' is the branching factor and 'd' is the depth), making it time-consuming for large state spaces (e.g., 3.5 billion states for 8-puzzle), thus favoring informed search for efficiency.