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

(Written by Dr. Robert Goldstone, Department of Psychology,
Indiana University. http://cognitrn.psych.indiana.edu/. Email: rgoldsto@indiana.edu)

This simulation shows how close-to-optimal paths can be found around obstacles with a decentralized system. In traditional Artificial Intelligence, the search for a good solution is typically viewed as a process of adding steps to a solution and backtracking when dead-ends are found. The alternative method pursued here is to have simple agents locally influence each others position. They globally form a path even though no agent by itself represents an entire solution.

The method used here for creating good solutions is called "simulated annealing." In actual annealing, strong metal structures are formed by gradually cooling the metal. At high temperatures, the molecules of the metal move freely with respect to one another. If the metal is cooled slowly, thermal mobility is lost. The atoms are often able to line themselves up and form a pure crystal that is completely ordered, hence increasing the strength of the structure. The analogy in "simulated annealing" is gradually reduce the randomess in a system. Early on, randomness helps the system sample different candidate solutions. later on, stability helps the system settle down to a single strong solution. In computational applications of simulated annealing, the probability that a system will move from a state with goodness/energy E1 to a state with goodness E2 is set to exp[-(E2-E1)/kT], where a low E value means a BETTER solution (low energy is good), k is a constant, and T is the temperature or randomness in the system. As such, if temperature if very low, then the system will almost always move in the direction of lower E. However, if T is high, then the system may move toward the state with a higher E. Although it may seem counter-productive to increase the energy of the system if one wants to have the least energy possible, it helps the system in avoiding LOCAL MINIMA. Local minima are states such that the current E value is lower than all E values that are obtained by neighboring states, yet E is not the lowest possible value that the system could obtain. In order to find global rather than local minima, it is often necessary that the energy in the system momentarily increases. As an analogy, if a dog want to get a bone on the other side of a fence, he may actually have to walk further away from the bone (momentarily) so as to walk around the fence in order to eventually be close to the bone. The local minimum in this case would be the dog salivating right at the fence with the bone a mere two feet away on the other side. It is a local minimum because the dog cannot move without increasing his distance from the bone. However, there is a global minimum that would have the dog right at the bone, but this could only be found if the dog jostles himself out of the local minima. High values of T allow this to happen.

The individual agents (dots) in this simulation follow the following simple rules:

1. Each dot is assigned two neighbors, making a set of dots arranged from first to last. One of the fixed blue dots is the neighbor of the first dot. The other blue dot is the neighbor of the last dot.

2. Each dot will move toward the average position of its two neighbors, and will also move with a bit of randomness.

3. If the location that a dot would move to is painted green, then it does not move.

HOW TO USE IT

The dots will always try to form a path between the two blue dots on the top and bottom of the screen.

Click the SET UP button to erase the screen, and create a number of dots stipulated by the num_dots slider.

Click the RANDOMIZE button to preserve the green obstacles but place the dots in new locations.

The NOISE slider sets the amount of randomness in the movements of the dots. A high value of noise corresponds to a high temperature T.

The MOVEMENT-RATE slider sets the amount of movement that each dot makes on every step.

To try out a simulated annealing strategy for your problem, click SIMULATED-ANNEALING. The program will start off with a high level of noise and gradually reduce it with time. How quickly gradually noise is reduced is set by the SPEED-FOR-SIMULATED-ANNEALING slider.

Click DRAW and ERASE to draw and erase the green obstacle on the screen. If you are drawing, simply click the mouse on the area where you would like an obstacle. The size of your obstacle will be defined by the slider PEN-SIZE.

THINGS TO NOTICE

Draw a single medium-sized obstacle in the middle of the screen. If NOISE is set to zero, then a good path is not created by the dots between the two blue points. In this case, each dot will always move closer to their neighboring dots whenever possible, and thus they will easily fall into local minima where no dot can move without falling on a green patch.

If NOISE is set very high, then a good path is also not found. In this case, the dots randomly move around without settling on any path.

Setting NOISE to a small value often suffices to find a good solution, but notice that the dots still jiggle around. Also, this solution will not work if the obstacles are fairly complex. In these cases, you may be able to find paths using simulated annealing (gradually reducing the noise) that you would not be able to find otherwise.

EXPLORATIONS

Experiment with different ways of adjusting the amount of randomness and amount of movement of the balls. What technique does the best job of usually finding good pathways? According to formula for simulated annealing mentioned above, how should you gradually reduce the noise in the system?

What is the best number of balls for a maze? Why? Does the best number of balls depend on the maze?

What kinds of mazes can and cannot usually be solved?

If the balls have trouble finding a pathway, what can you do to help them?

How can you improve the simulated annealing schedule for reducing noise that is used here?

Is there a better method than simulated annealing for efficiently finding pathways?