Organic pathfinding

Summary Students implement action cost and heuristic cost functions in order to specialize a generic search function to realize breadth-first search, best-first search, beam search, A* search, and a novel "human" search technique. The specifications of the "human" search technique are left open-ended, but students are asked to recreate "organic" paths (also known as "desire paths") as found in natural and urban environments. A typical organic path is one that cuts across a grass field even though a sidewalk or road is nearby but less direct. Sometimes, organic paths are less efficient, due to humans' tendency to avoid walking close to obstacles such as buildings and trees, so they are clearly distinct from A*. Organic paths are also visually distinct from breadth-first and best-first search. Students are encouraged to examine example organic paths and reflect on their own behavior to develop the "human" search technique. A Python script is provided that simulates a student's search techniques and produces images of the resulting paths. In the assignment description and example code, the search process is run through many iterations (500 by default). After each path is found, the "cost" of each step along the path is reduced in order to simulate humans walking along and forging the path. This dynamic update of the environment may influence pathfinding in the next iteration, depending on the search technique.
Topics search, pathfinding, A* search, breadth-first search, best-first search, beam search, heuristic search
Audience Introductory Artificial Intelligence (AI) students
Difficulty Students are not asked to implement a search algorithm. They are only asked to implement different versions of the action cost and heuristic functions used by a generic search algorithm. These functions are relatively simple, involving conditionals and some simple math such as Euclidean distance. This assignment may be the first assignment in an introductory AI course, after discussing heuristic search.
Strengths Students learn that the various search techniques (e.g., A*, best-first, breadth-first, depth-first, beam search, etc.) are all minor variations of the same generic search algorithm. This lesson reinforces the idea that search is a generally useful procedure in AI and may be specialized for different kinds of use cases. This assignment also gives students a taste of the complexity of human behavior and encourages them to study real life examples and engage in self-reflection, both common practices by researchers developing new AI techniques.
Weaknesses Because students are not asked to implement the search algorithm from scratch, they might not acquire a solid understanding of how it works. However, the assignment can be modified to ask students to implement the search algorithm, perhaps with novel variations suited for organic paths. Another weakness is that organic paths are a case of pathfinding, which is a common application of search techniques like A*, but not the only useful or interesting application of search. Students should also be aware that search may be used for many different kinds of problems.
Dependencies Students must be aware of the generic search algorithm (e.g., from Russell & Norvig's Artificial Intelligence: A Modern Approach) as well as the differences between A* search, best-first search, etc. Students must also be able to write simple functions in the Python language.
Variants Instructors may choose to require that students implement search algorithms from scratch. Instructors may also ask students to implement more variations of search and explain the usefulness of each in terms of pathfinding. The assignment may be modified so that only a single path is found (i.e., a single iteration). Other kinds of paths may be examined, such as most scenic, quickest to goal, and least destructive (stay on sidewalks).

Links: