• 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 to protect a network in Death First Search - Episode 1.

An agent is moving through the network towards one of several gateways. In each turn, your program must remove one connection to stop the agent from escaping.

Begin with a simple working strategy. Then make it smarter: Which gateway poses the greatest immediate risk? Which path is the agent likely to follow? Should you cut the final connection to a gateway or intervene earlier? Can a locally sensible decision create a worse situation in the next turn?

Use graph search to guide these decisions, and consider situations in which a simple greedy strategy may fail.

Start the challenge during the lab and continue it as part of the self-study regarding classes. Groups that complete Episode 1 may continue with Death First Search — Episode 2. Selected groups may share their strategies at the next lab, and effective solutions may receive bonus points.

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