• Reading:
  • AIMA: Chapter 3 - Solving Problems by Searching. Focus on problem formulation, graph-search concepts, the main uninformed and informed search strategies, and the assumptions behind their completeness and cost optimality.
• Technical preparation:
  • Open today's notebook and run all setup cells and the first code cell in Segment 1 to verify that the notebook works in your environment. You should obtain a simplified visualization of the Romania map.

1. What assumptions make a fixed sequence of actions an adequate solution? What would change if the environment were nondeterministic or partially observable?
2. Consider route finding. Which details should be included in the state, and which should be abstracted away? When would “current city” cease to be a sufficient state representation?
3. Why does BFS permit an early goal test, while UCS normally tests for a goal only when a node is removed from the frontier?
4. What makes a heuristic useful? How can a more aggressive heuristic reduce search effort while weakening theoretical guarantees?

Notebook: HCAI_Lab_Search.ipynb (Open in Google Colab or download the .ipynb file to local environment)

Work in groups of 2-4. Every group member must be able to explain the results. Running the cells alone is not sufficient for checkpoint credit.

Work in groups of 2–4 on Death First Search - Episode 1.

Your program must represent a changing network as a graph and remove one edge in each turn to prevent the moving agent from reaching a gateway.

Start by implementing a valid baseline strategy. Then improve it using BFS or another suitable graph-search algorithm. Pay particular attention to:

1. representing and updating the graph;
2. selecting a gateway or path to defend;
3. choosing which edge to remove;
4. identifying situations in which a locally reasonable strategy may fail.

The challenge is intended to be started during the lab and completed as part of the self-study regarding classes.

Groups that complete Episode 1 may continue with Death First Search — Episode 2. Selected groups may briefly present their strategies and results at the beginning of the next lab. Particularly effective solutions may receive bonus points.

• Introduction to the A* Algorithm from Red Blob Games – an interactive comparison of BFS, UCS/Dijkstra, and A*