Navigation by searching a graph

Preparation

Read the description and/or the tutorials for the graph searching applet from page: \hrefhttp://www.aispace.org/search/index.shtml

Download the applet (search.jnlp), run it by the Web Start interface (javaws program).

Note: depending on the Java security settings on your computer, the Java applet may run or may refuse to. In the latter case, run the jcontrol program and in the Web Settings tab add the http://www.aispace.org location to the allowed sites.

Load a sample predefined graph build into the applet and learn about solving it using different search algorithms and options.

Exercise 1 [5 points]

In particular, try the Cyclic Graph Example. Which algorithms can solve the problem, and which cannot, without changing any options? Try to understand why. When you are ready to explain, report to the instructor.

Exercise 2 [5 points]

In turn, try the Misleading Heuristic Demo graph and the Best First algorithm. Why cannot the program find the solution? How can you solve the problem, to allow the Best First algorithm find the solution?

Report to the instructor when you have answered these questions.

Exercise 3 [10 points]

Subsequently, create a graph for your own terrain navigation problem. This can be roads connecting several cities in a country of your choice, or a network of important points in some city with paths connecting them, a map of rooms, doors, and hallways, for a mobile robot navigation, or something similar. Be realistic, use some real-life data for graph nodes and the weights of their connecting edges, representing the actual distances. Make an effort to reflect the geographic proximity of the actual landmarks by the graph geometry.

Practice finding paths in your graph by setting the start and goal nodes. Try to identify the most effective navigation algorithms. Show examples of wrong or inefficient navigation.

Report to the instructor during class, or describe the results in your written report.