Artificial Intelligence
Dr. Eftekhari
Homework 2
Chapter 3 (Part I)
Spring 2025
1- Maze Navigation and State Space Abstraction (10 Points)
A robot starts at the center of a maze facing north. It can turn to face north, east, south, or
west, and it can move forward until hitting a wall.
a. Formulate this problem precisely in terms of:
i. State representation
ii. Initial state
iii. Goal state
iv. Goal test
v. Possible actions
vi. Transition model
vii. Path cost
How Large is the state space?
b. Reformulate the problem by observing that the robot only needs to turn at
intersections of two or more corridors.
What is the new state representation?
How Large is the state space?
c. Further simplify: at each location, the robot can move in any direction until it
reaches the next turning point. How does this change the action set?
Do you still need to track orientation?
d. List three real-world details that were abstracted away in this formulation.
2- Missionaries and Cannibals Problem (10 Points)
Three missionaries and three cannibals are on one side of a river with a boat that can
carry one or two people. At no point can missionaries be outnumbered by cannibals on
either side.
a. Formulate this problem as a search problem, defining:
i. State representation
ii. Initial state
iii. Goal state
iv. Goal test
v. Legal actions
vi. Transition model
vii. Path cost
What are the Constraints to avoid invalid states?
b. Draw or describe the complete state space, highlighting valid and invalid states.
c. Describe how uninformed search algorithms such as BFS or DFS would solve this
problem.
Which would be more suitable? Why?
Should repeated states be checked? Justify your answer.
3- The Water Jug Problem (10 Points)
You have three jugs measuring 12, 8, and 3 gallons. You can fill the jugs from a faucet,
pour water from one to another, or empty them. Your goal is to measure exactly 1 gallon.
a. Formulate this problem as a search problem:
i. State representation
ii. Initial state
iii. Goal state
iv. Goal Test
v. Actions
vi. Transition model
vii. Path cost
b. Use a search tree to describe the first few levels of the state space (a diagram is
optional but encouraged)
c. Which uninformed search strategy would be most effective here? Discuss tradeoffs
in terms of:
i. Completeness
ii. Optimality
iii. Space complexity
iv. Time complexity
4- Does a finite state space always lead to a finite search tree? How about a finite state space
that is a tree? Can you be more precise about what types of state spaces always lead to
finite search trees? (10 Points)
5- Uninformed Search (60 Points)
Using the provided graph image, execute different uninformed search algorithms (both
Tree Search and Graph Search version) to find a path from node H to node G.
a. Searches include:
i. Breadth-First Search (BFS)
ii. Depth-First Search (DFS)
iii. Iterative Deepening Search (IDS)
iv. Uniform Cost Search (UCS)
b. For each algorithm, write down:
i. The search tree
ii. The frontier list
iii. The explored/extended list (for Graph Search)
iv. The final path from H to G
v. The total path cost
Note: For Tree Search: If the search doesn't converge after 2-3 levels, you may stop
and explain why.
Important: When multiple nodes have the same priority in the frontier, expand
nodes in alphabetical order.
6- (Optional Question) (15 Points)
Prove that under certain conditions, the optimal meeting point for bidirectional search is
not necessarily the midpoint of the solution path. Consider a state space where the
branching factor b₁ in the forward direction differs from the branching factor b₂ in the
backward direction. Derive a mathematical expression for the optimal meeting depth d*
as a function of b₁, b₂, and the solution depth d, that minimizes the total number of nodes
generated. Demonstrate how this optimal meeting point changes as the ratio b₁/b₂ varies.
Submission Guidelines
• The format for submitting files should only be in PDF format, handwritten,
and in Persian language.
• Use clear section headings for each problem.
• Cite sources if you refer to external materials.
• PDF name format: FirstNameLastName_StudentID_HW2
(e.g. JhonDoe_123401234_HW2)
• Total Points: 100
Good Luck!