AIspace

Practice Exercise 3.D

1: Background Reading

2: Uninformed Search

Open the graph searching tool. Go to the File menu and select "Load Sample Problem" and select "Vancouver neighbourhood graph."

You'll see the crude Vancouver map you saw in practice exercise 3.A. Click the 'Solve' tab. By default, "Depth First" is selected. Make a prediction about the order in which nodes will be explored and predict which path to the goal will be returned. After you've made a prediction, click "AutoSolve." Alternatively, you can click "Step" if you want to step through the search process more slowly and make a prediction at each step. Were your predictions correct?

Under the "Search Options" menu, select "Breadth First." Repeat the step above, making predictions about which nodes will be explored and which path will be returned. Test your predictions by running the solver again.

Based on your experiments, is one of these search methods better in terms of taking fewer steps to find the goal?

3: Lowest-Cost-First Search

Now under the "View" menu, select "Show Edge Costs." Numbers will now appear on the arcs between the nodes. What could these possibly represent? What might they represent in the cycling planner example?

Under "Search Options," select "Lowest Cost First."

Again, make specific predictions about which nodes will be explored and test them by running the solver. You're encouraged to step through the process to understand how the frontier is being expanded. Notice how the paths in the frontier are sorted.

4: Heuristic Search

Under the "View", select "Show Node Heuristics." Numbers will now appear on each node. After a quick examination of the nodes and their respective costs, you should be able to determine what these heuristic costs represent in this example.

Under "Search Options," select "A*." Again, make a prediction about which nodes will be explored based on what you know about the A* algorithm, using the arc costs and node heuristic costs.

Test your predictions.

5: Cycling

Which of these search methods would you prefer that your cycling planner use? Explain your reasoning.