NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

WHAT IS IT?

This model simulates an implementation of the A* path finding algorithm, for finding a path from the source patch to the destination patch. The heuristic function used (h(n)) always gives the exact distance from an intermediate patch to the destination patch by employing the NetLogo primitive "distance". This exact heuristic replaces the admissible heuristic in the standard A* which drives path finding exactly in the direction of the destination. This takes place by choosing the next patches (nodes) for exploration which are not yet explored and have the least cost i.e. the smallest distance to the destination as compared to other patches that have not yet been explored. This enables the algorithm to always find an optimal path (least cost path) to the destination, if one exists.

THE INTERFACE

The elements of the user interface from top to bottom along with their functions are as follows:

-> Setup (button): Clicking this button resets the simulation. This clears the view and places the source and destination patches at two random locations in the view.

-> Select-element (chooser): This is used to select a particular maze element that can then be drawn on to the view of the model using the Draw elements button and the mouse. The different maze elements are:
+> source: Select this to place the source patch at a different location in the
view.

+> destination: Select this to place the destination patch at a different
location in the view.

+> obstacles: Select this to place obstacles in the view. This can be used to
design a maze in the view, which can then be navigated using A* to
find a path between the source patch and the destination patch.

+> erase obstacles: Select this to erase existing obstacles in the view. This can be used to remove an unneeded obstacle from the view, and can also be used in designing a maze in the view.

-> Draw elements (button): This is used to draw the maze element that is selected in the Select-element chooser on to the view. This can be done by clicking (activating) this button once and then using the mouse to draw the element onto the view. Once the elements have been drawn this button can again be clicked (deactivated) to stop drawing the maze elements on to the view.

-> Find an optimal path (button): Clicking this button will execute the A* path finding algorithm, for finding a path between the source patch and the destination patch. This will result in drawing the shortest path between the source and the destination, if one exists or notifying that such a path does not exist.

-> Clear View (button): Clicking this button clears the view but keeps the source and destination patches at their original locations.

-> Save this maze (button): Clicking this button saves the maze as a ".png" (Portable Network Graphics) image file at a user defined location in the file system.

-> Load a maze (button): Clicking this button loads a maze (Portable Network Graphics) image file from the user defined location in the file system to the view, with the precondition that it should be a valid maze. An image is a valid maze if it has exactly one source patch and destination patch.

-> The notes to the right of the view define what the different colors of the patches mean. For example: White colored patches are obstacles, the blue and green patches are the source and destination respectively, etc.

-> The output text box: Displays the "shortest path length" after clicking the find an optimal path in terms of number of patches that had to be covered to reach the destination via the optimal path.

HOW IT WORKS

The maze elements are drawn on the view by placing them at the X and Y coordinates of the mouse pointer once it is clicked and is inside the view.

The Path finding uses the A* algorithm to calculate the shortest path between the source and the destination patch, by avoiding obstacles, as a list of patches and storing it as a variable named "path" with the path finding agent (turtle 0). Once the path is found it is traced by the agent to reach to the destination patch. As A* path finding is used the concept of "open" and "closed" lists are used, these lists contain unexplored and explored patches (nodes) respectively.

With each step a patch is removed ("explored") from the open list (unexplored patches) and placed in the closed list (explored patches) with a precondition that the value of its knowledge plus heuristic cost function f(), is minimum. After this the parent patch (predecessor-node), g() (knowledge cost function), h() (heuristic cost function) and f() = g() + h() knowledge plus heuristic cost function) values of the removed patch's neighbors are updated accordingly, and these neighboring patches are added to the open list, if they are not already a part of the open list.

Once the destination patch is reached (a node neighboring to the destination patch is explored) the search process ends. Search path is calculated by traversing through the parent patch of the neighbor of the destination which triggered the end of the search, all the way till the source patch. This path forms a list of patches, which is stored in the path variable of the agent.

If a path does not exist from the source to the destination, ultimately all patches (reachable from the source) end up in the explored (close list) and the open list becomes empty. In which case we conclude that a path from the source to the destination does not exist.

The save maze operation saves a copy of the view as a ".png" image to the filesystem and load maze operation loads (imports) and existing maze ".png" image on the file system into the view.

HOW TO USE IT

Press the setup button, choose elements from the Select-element chooser, click on the Draw elements button and design your own maze on the view using your mouse and clicking wherever you wish to place the selected element.

Click on the "Find an optimal path" button to compute the shortest path from the source patch to the destination patch through your designed maze, once this is done the agent will navigate through this path from the source patch to the destination patch.

Use "Save this maze" and "Load a maze" to export and import mazes to and from the file system respectively.

WHAT IS ITS PURPOSE?

The purpose of this model is to show how the A* path finding algorithm works when we can accurately guide the search towards the goal by using an exact heuristic function, instead of an approximate (admissible) heuristic function used in the standard A* search specification.

THINGS TO TRY

Design different mazes and test the path finding on them.
Change the locations of the source and destination patches for a maze and see its effect on the computed search path.
There can be more than one optimal paths for reaching the destination, try making a maze in which this happens and observe the behavior of the algorithm in that case.

EXTENDING THE MODEL

Change/modify the path finding algorithm used (the "find-a-path" procedure) and see how the model behaves while navigating through various mazes.

NETLOGO FEATURES

mouse-inside?, mouse-xcor, mouse-ycor, mouse-down? are used to track the mouse pointer motions in the view.

sort-by was used to sort the "open" list of patches by their f() (knowledge plus heuristic cost function) values for selecting the one with the minimum value of f().

neighbors4 was used to access the "Von Neumann" neighbors of the patch being explored.

user-message, user-file, user-new-file were used for displaying user message as a dialog box, and loading and saving maze image files from and to the file system by interacting with the user.

import-pcolors, export-view were the NetLogo primitives used to import and export maze image files to and from the view of the simulation.

CREDITS AND REFERENCES

Russell, S. J.; Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall. pp. 97–104. ISBN 0-13-790395-2

http://en.wikipedia.org/wiki/A*_search_algorithm