Computational Perspectives I

Searching For Optimal Paths

Note: in order to run the simulation referred to in this slide, go here, to the Java Applet version. You will be directed to download the latest version of the Java plug-in.

You may imagine the simulation's eight circles as different end results that an value-producing individual could possibly reach. In terms of the previous slide's example, they represent different utensils that the apprentice might make: spoons, forks, knives, chopsticks, etc. Initially, she only knows how to reach state 0. The state may correspond, for instance, to the production of little wooden blocks that aren't very useful for food consumption. For now, she is utterly unaware of the other states' existence.

Click "Go" once to see her learn a way to reach state 6. Perhaps, she finds a way to make something reminiscent of a spoon out of the "state 0" wooden block. At the next click of the button, she analyzes her newly found option, and decides that the utensil represented by state 6 is worth the wood-carving effort. As a result, both state 0 and 6 light up in red, marking the individual's optimal behavior given her current knowledge. You should also see an upward jump in the value of the currently chosen path in the graph below.

Next two simulation steps teach her of how to reach state 7, but the state's payoff turns out not to be worth the path's cost - at time 4, the optimal path remains the same. You may keep clicking the "Go" button to see the apprentice's progress, as she learns new behavioral options and analyzes them to adopt the best one. Step 28 marks her learning the last useful piece of information - the formation of a direct path from state 0 to state 4.

In mathematical terms, our learner performs a depth-first search on the graph that represents her knowledge base, and finds the path with the greatest Net Value - i.e. the value of its final state minus the cost of travel from state 0. State values are shown as the sizes of corresponding circles, and the cost function is simply the Euclidean distance between their centers.