Chapter 2 - Search

2.1 Solving Problems by Searching

• To solve problem, we first formulate the problem or find the model of the problem. Then, we find the solutions from the model. Basically, each obtained solution is a solution in terms of the model. We have more confidence in the solution when our model accurately represents the problem.

2.2 Problem Solving Agents

• Given a model of a problem, a problem solving agent finds a sequence of actions that lead from an initial state to the goal. The sequence is also called a solution which can be executed later by the agent.
• Search is a basic technique to find a solution of problem. It is performed by trying all possible actions iteratively in order to get to the goal.

Example 2.1: Water Jug Problem

Problem: We have a 3-liter jug, a 5-liter jug, and a water faucet. How can we measure exactly 4 liters in the 5-liter jug?

• Initial state: [0, 0] (both jugs empty)
• Goal state: [x, 4] (4 liters in 5-liter jug) where $0\le x \le 3$

Problem Definition

• State representation:
  • A tuple of two numbers representing the amount of water in each jug
  • Example: [0, 0] means both jugs are empty
• Goal state:
  • A state where the amount of water in the 5-liter jug is 4 liters
• Available actions:
  • Fill up one of the jugs
  • Empty one of the jugs
  • Pour water from one jug to another jug
  • Example: Apply 'pour water from 3-liter jug to 5-liter jug' to state [3, 0] → get new state [0, 3]

State Space

We can draw a directed graph showing the changes of amount of water after applying actions:

เวลาเขียนต้องให้เป็น Valid state ด้วย

• Each node is a state
• Each edge shows an action transforming a state to another state
• The graph is called 'state space'

Example solution path: [0,0] → [0,5] → [3,2] → [0,2] → [2,0] → [2,5] → [3,4]

2.2.1 Search Formulation

Here are what we need to determine as the model of a search problem:

Key Components

State:

• Represents a situation of problem
• Contains all necessary information to identify a situation of problem
• Transformed to another state by applying an action

Initial state:

• The state that the system starts in

Goal test:

• ก็เหมือน $[x,4]$ เมื่อกี้ ไม่ได้เป็น Goal state เลยนะ!
• Condition to determine whether a given state is a goal state
• In real-world problems, more than one state can be considered a goal
• Usually a function that takes a state and returns true/false

Actions:

• Set of transitions between states
• Different states may have different sets of possible actions
• A successor function takes a state and returns a set of its possible actions

State space:

• Graph connecting all possible states with actions
• Usually difficult to explicitly define in real-world problems

Path cost:

• Represents the cost of a solution, since actions may have different costs
• Often computed as the sum of the step costs along the path
• Step cost is the cost of an action
• Formula: $$\text{Path Cost}=\sum_i\text{Step Cost}_i$$

Example 2.2: Water Jug Problem Formulation

• State: Tuple [x,y] where x, y show the amount of water in 3- and 5-liter jugs respectively
• Initial state: State [0,0]
• Goal test: Any state [x,4] where $0 ≤ x ≤ 3$
• Actions:
  • Empty one of the jugs
  • Fill up one of the jugs
  • Pour water from one jug to the other jug
• Step cost: Amount of water changed

  ==Optimal solution = Solution with minimum path cost==

Example 2.3: Successors of State [3,1]

2.2.2 Implementing the Problem Formulation

To develop a problem-solving agent, we implement the formulation including:

1. State representation
2. Goal test
3. Successor function

See problem_formulation.ipynb for an implementation of the Water Jug Problem.

Problem Examples

Example 2.4: 8-Puzzle

Problem: Sliding puzzle with the objective to order the tiles in order by making sliding moves.

Search Formulation: 

See problem_formulation.ipynb for an implementation of the 8-puzzle problem.

Example 2.5: 8-Queens

Problem: Place eight queens on an 8×8 chess board so that no two queens attack each other.

Example 2.6: Alternative 8-Queens Formulation

State representation:

• 8-tuple representing the row number that a queen is placed in each column
• 0 means no queen in that column
• No attacking between any pair of queens is allowed

Examples:

• [1, 7, 4, 0, 0, 0, 0, 0] - 3 queens placed

• [2, 4, 6, 8, 3, 1, 7, 5] - Complete solution
  
  Search components:

• Initial state: Empty chess board i.e. []

• Goal test: Board with 8 queens on the board

• Actions: Add a queen to any row in the leftmost empty column (new queen must not attack any other queen)

Formulation Impact on Performance

Different formulations affect the number of possible states:

• 1st formulation: $64 \times 63 \times 62 \times 61 \times 60 \times 59 \times 58 \times 57 \approx 1.8 \times 10^{14}$ possible states
• 2nd formulation: Only 2,057 states

💡 Tip: Try to formulate the problem in a way that minimizes the number of possible states by incorporating as many constraints as possible into the state.

See problem_formulation.ipynb for an implementation of the 8-queens problem.

Example 2.7: Route Finding Problem

Problem: Find a drive route from Arad to Bucharest using the Romania map.

Search Formulation: 

See problem_formulation.ipynb for an implementation of the route-finding problem.

Example 2.8: Two-Friend Meeting Problem

Problem: Two friends live in different cities in Romania and want to meet. They take turns moving, and on each turn both friends simultaneously travel to a neighboring city. The travel time from city i to adjacent city j equals road distance d(i,j). If one friend arrives before the other, that friend must wait by phone until the other arrives before the next turn begins. One friend starts from Arad, the other from Bucharest. Goal is for them to meet in the same city.

Exercise: Formulate this search problem by defining:

1. State representation
2. Initial state
3. Goal test
4. Actions
5. Step cost