The Map-Search Module

FLAIR's Map-Search module is designed to demonstrate how different search methods can be applied to find a path between two points on a map, or to find the shortest path between two points on a map. The default search space used in this demonstration is a set of cities in Massachusetts and the distances between them on major highways. The search methods demonstrated are depth-first, breadth-first, uniform-cost, hill-climbing, best-first and A* search.

The user can select the start city, the goal city and the search method to apply to this problem. The module will then run that algorithm on the map search space. The module displays the path between the two cities that the algorithm discovered, the number of cities that were examined by the search algorithm to find this path, and the length of the path.

The module environment includes a main display window, a message window, a list animation window, and a map editor. The display window shows the search map and the nodes and paths examined during search. It also allows the user to specify the search conditions, including the heuristic and algorithm used, and to modify the speed and other features of the module display. The Module Message Window is a scrolling text window which maintains a history of the user's actions and of algorithm results.

The user may explore the algorithms in more detail using the (optional) Generalized List Animation Tool (GLAT) feature. The GLAT window allows the user to see the city nodes 'explored by' the algorithm (the'closed' list nodes plus the 'selected' node) at each step. The GLAT display is run concurrently with the map-search display. While running the GLAT window, the user may display the F-values currently associated with cities included on the OPEN and CLOSED lists by left-clicking on the list names (OPEN and/or CLOSED) in the GLAT window.

The user may replace the current map at any time. Map datasets may be loaded from files or generated using a map editor.


Information is available on how to access and use the Search Module.