Demonstration of various AI search methods using NetLogo
Searching Turtles is a program I developed in NetLogo which demonstrates basic search techniques commonly used in Artificial Intelligence programming. It is developed using NetLogo's native agent-based programming language and utilizes NetLogo's default tools and modelling environment.
The program begins by generating an obstacle filled grid-like environment with a lone agent (or turtle) placed in a random location, or patch. Additionally, a single random patch is colored red, indicating the goal patch. The agent's objective is to search for and move to this goal patch using one of four AI search algorithms:
Random - The agent will move in random directions until it finds the goal patch. Visited patches are not remembered so the agent can visit a patch more than once. This method involves no planning and takes the agent the longest time on average to find the goal compared to the other three search algorithms. Although it is not really considered an AI search method, it is used to demonstrate how search algorithms that involve planning can be more efficient.
The random search is the only search in which the agent attempts to guess where the goal patch is. For the following searches, the agent analyses the environment, remembers the patches it analyzed and plans a path to the goal before it begins to travel to it.
Breadth First Search - The agent begins by searching all of its surrounding patches for the goal. These patches are added to a list of patches pending analysis called an agenda list. If the goal is not found in this list, the agent remembers these patches by adding them to a visited patches list. All unexplored patches that surround the previously searched patches are then added to the agenda list and are evaluated the same way. This continues until the goal is found. Once found, the agent plans a path based on the and begins to travel to the goal.
The breadth first search is programmed to search evenly in every direction since the agent does not have a lead as to where the goal is. Although the search will always find the best possible path from the agent to the goal, there is a high possibility that a large number of patches will be searched in the process. The worst-case scenario occurs when the agent and goal lie on different corners of the environment, in which case, the agent would need to search every node before discovering the goal.
Greedy Search - the greedy search introduces a heuristic, giving the agent a better sense as to where the goal is. The heuristic is:
h(n) = the shorter the distance between the goal patch and a specific patch, n, the greater the value that n has.
As the agent searches for the goal, it assigns patches this value and uses them as a guide as to how to traverse the environment. Since the environment on NetLogo is essentially a grid, the value of a patch n is obtained by using the distance formula, with the goal patch and patch n as the two endpoints.
The search begins by adding the patches that surround the agent to the agenda list, much like the breadth first search. However, of these patches, only the one with the highest heuristic value, that is the shortest distance to the goal based on the distance formula, is added to the visited patches list. The patches that surround that patch are then added to the agenda list and are evaluated the same way. This process repeated until the goal patch is found.
Since the agent now has a sense as to where the goal is due to the heuristic, the search results in a more direct path to the goal, thus visiting less nodes than when implementing the breadth first search.
A* Search - the A* (ay-star) search uses the same heuristic as the greedy search to assign values to patches, while also taking path cost into consideration. The path cost of a patch is calculated by measuring the number of moves or steps it would take the agent to reach that patch from its initial position. For example, if it takes the agent 10 moves to reach a specific patch , n , the path cost of n is 10. The final value of patch n is the sum of 10 and its heuristic value. With the A* search, the agent will analyze patches and search for the goal the same way as it would the greedy search, but while taking path cost into consideration. Although the A* search results in more patches visited than the greedy search, it will always result in the shortest path from the agent to the goal.
I created this program as part of a project for an Artificial Intelligence class I enrolled in while attending Brooklyn College. The objective of the project was to demonstrate and analyze the various AI search techniques.
In addition to the searches mentioned, the program also provides minor features such as patch type visibility, agent positioning and a graph that displays the number of patches visited over time as the program runs. Finally, it contains an information tab containing a more detailed description of the program, as well as statistics calculated by running multiple trials of the different search methods.
