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.