• 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 does the Romania route-finding problem make about the map, road costs, and the effects of travelling along a road? Which real-world changes would require replanning?
2. 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 (Work 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.

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*