Organic pathfinding

This assignment helps you practice with variations of uninformed and informed search. Although all search algorithms, even informed search like A*, can be effective for many problem solving tasks, a common use is pathfinding. The problem of pathfinding is to find a series of actions or steps from a starting point to a goal point. In most cases, we prefer the shortest path or the most efficient.

Humans and other animals engage in pathfinding every day. However, we do not necessarily always follow the most efficient path, nor do we seem to entirely plan the path in our minds before making the first step (particularly if we cannot see around an obstruction). How do we find paths? Perhaps we can discover some insights into this question by finding a model or replication of the kinds of paths that humans make.

Background

Organic paths have been documented extensively, often by architects. For example, consider the following set of photos, published in Klaus Humpert’s Lauf-Spuren (“running tracks”) from 2007:

Humpert observes which individuals choose to walk through the garden and compares them to individuals who chose the longer, paved route. For our purposes, it is interesting to observe that a path through the garden was forged in spite of the paved walkway. Clearly, the reason is that the direct path is faster, and the garden was not a sufficient barrier to prevent people from trudging through it and forging a new path.

Humpert shows several examples of one or more paths being formed around an obstacle or muddy terrain. For our purposes, it is interesting that only a small number (1 or 2) alternate paths are formed rather than a new path for every individual. This indicates people and other animals prefer established paths before making their own. Note also that one person does not make a path; rather, many people must follow a similar path before it is forged and an attractor to future individuals.

Organic paths have also been the subject of a curious urban legend about university planning. I have found several references to a story like the following, although the university in question often changes:

At the University of California at Irvine, when they first built its campus, they just planted grass. Then they waited a year and looked at where people had made paths in the grass and built the sidewalks there. – Larry Wall, creator of Perl

The design of paths in Aldrich Park (at UCI) seems to support Larry Wall’s story:

The legend has been realized recently on Virginia Tech’s campus. Even so, the veracity of the story is not as interesting as its tedency to be believed. The story seems like it could be true. It seems that the “optimal” paths to cover in concrete are those that people formed organically. As an analogy, the story suggests that careful design before user testing will never be as good as getting honest feedback from actual users and modifying plans accordingly.

In fact, the phenomenon of organic pathfinding goes by another name: desire paths. There is a small fanbase online, as evidenced by this Flickr group and this podcast episode.

According to my research, nobody has ever tried to reproduce so-called desire paths in software. This assignment asks you to do just that.

Task

Your task is to modify some Python code to perform different kinds of pathfinding searches on some given maps. You will be required to produce each of these searches:

• A* search
• Best-first search
• Beam search
• “Human” search

Recall that we can reproduce many variations of search algorithms by just modifying the “action cost” g(s) and “heuristic” h(s) functions of the generic search algorithm. “Human” search can be programmed by figuring out the right variations of g(s) and h(s). Breadth-first search is shown in the examples below, but it is too slow and produces paths that look nothing like organic paths. It has been disabled in the code.

You will modify paths.py only. The map is represented as a two-dimensional array of integers; each integer in this array represents the cost of moving on that position in the map (high cost means slower movement). Possible actions are north, south, east, west, northeast, southeast, northwest, southwest. Some actions may not be allowed from a particular position if there is a barrier nearby (red in the map, value -1 in the 2D array of cost values). Refer to the file for details.

When you run paths.py, using command python paths.py, it will produce images like the ones below. When you have the strategies implemented correctly, the runtime should be about three minutes.

The images below show the various paths forged across many iterations. The starting and ending points are indicated by blue (starting) and green (ending) pixels. Red pixels are impassible terrain (e.g., trees). The grayscale colors represent action cost, i.e., ease of walking on that pixel: darker is easier, so black represents pavement (more or less) and white represents bushes. As simulated people follow their own paths, each pixel they follow gets slightly darker since they are wearing down the path.

Examples

Garden

Consider this map, representing the garden with surrounding sidewalk documented by Humpert. Recall that blue pixels represent possible starting points (a starting point is randomly chosen on each iteration) and green represent possible ending points. Each map is actually 50x50 pixels, but shown here enlarged.

The starting map and each final map after 500 simulated people are shown in the table. The search algorithm is indicated below each image. Notice that the beam and “human” strategies perform most human-like in the garden example. Although it’s difficult to see, best-first search never follows the round sidewalk (which is not human-like). Also notice that A* indeed follows the lowest-cost path, which happens to be along the round sidewalk rather than directly through the grass.

Starting map	Breadth-first search	Best-first search
A* search	Beam search	"Human" search

Tree obstacle

In this example, also following Humpert’s observations, we have a tree in the middle of the map. The red pixels cannot be traversed.

Starting map	Breadth-first search	Best-first search
A* search	Beam search	"Human" search

Notice that only the “human” search correctly walks around the tree.

Tree with sidewalks

Consider the “desire path” formed below (image borrowed from the Flickr group).

Notice how only the “human” algorithm correctly simulates human behavior.

Starting map	Breadth-first search	Best-first search
A* search	Beam search	"Human" search

Aldrich Park

Finally, consider Larry Wall’s story about UC Irvine. I pointed out that Aldrich Park seems to consist of paved organic paths. The map below tries to recreate the initial design of the park with the circular sidewalk. We see that some curvy paths are formed across the park with beam and “human” searches.

Starting map	Breadth-first search	Best-first search
A* search	Beam search	"Human" search

Grading rubric

Out of 5 points:

• 5 pts: Your modifications produce images very similar to the ones shown above (note, you do not need to reproduce breadth-first search). You do not need to exactly match the images, but “qualitatively” do so, e.g., your “human” strategy should curve around the tree in one case and cut through the garden in another case.
• 4 pts: Your modifications produce the above images except the “human” search. In this case, you should be able to nearly exactly produce the above images.
• 3 pts: Your modifications produce 2 of the 4 images (among best-first, A*, beam, and “human”).
• 2 pts: Your modifications produce 1 of the above images (among best-first, A*, beam, and “human”).
• 1 pts: Regardless of the quality of your improvements, the code does not run to completion.
• 0 pts: No submission.