Home

A01: 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:

Organic pathfinding

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.

Organic pathfinding

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:

Aldrich Park

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:

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.

Recall from our uninformed search and informed search notes 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)$.

On londo, you’ll find the files search.py, paths.py, and some images in the /home/jeckroth/csci431/assignments/A01 directory. Copy these files to your own directory (and create a git repository as usual, i.e., csci431-A01). You will modify paths.py only. Refer to the file for details.

When you run paths.py on londo, 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).


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).

Desire path with tree and sidewalks

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

Deliverables

Copy all files from /home/jeckroth/csci431/assignments/A01 to your own directory. You only need to modify paths.py. See the file for instructions about what to modify. Be sure at least paths.py is committed in your git repository.

Grading rubric

Out of 5 points:

CSCI 431 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.