As was mentioned in the introduction of this tutorial, the Workspace is similar to a construction site, in the sense that there are many agents working locally and in parallel to build the structures that you have seen. The workers in the Workspace are called Codelets, as each has a specified job to do (like workers) that is defined by the piece of programming code that they are executing. This section introduces Copycat’s search strategy, the parallel terraced scan, and discusses how the Coderack is used to implement it. Furthermore, it discusses how Codelets choose the objects in Workspace to work from, and details the types of Codelets that are used in the formation of a solution.
The Parallel Terraced Scan
Many traditional AI models of analogy making, such as the ACME and SME models, apply an exhaustive search of the problem domain in order to find the best possible solution. However, according to Hofstadter (1995, p286), such a strategy is "both computationally infeasible and psychologically implausible in any realistic situation."
Instead of using an exhaustive search strategy, Copycat uses a "parallel terraced scan" in which many options are considered in parallel, but to varying degrees. This strategy, as stated by Mitchell (1993, p33), is analogous to how people find partners. That is, when looking for romance, instead of giving each individual you meet equal consideration, many possibilities are considered concurrently, with some being easily dismissed (based on some early criteria, such as physical appearance), and others receiving further levels of evaluation. Even when a match has been found, other alternatives can still be considered to various degrees, with the potential of breaking up the initial match depending on its strength.
Similarly, in Copycat, many possible solutions are explored in parallel to various degrees. This has been achieved by breaking down each task (e.g. building a specific bond), into a series of steps, with each step being a higher level of evaluation. As Copycat was written to run on serial computers, a form of parallelism is achieved by assigning each step to a different Codelet and choosing which Codelet to run probabilistically. This allows the steps of many different processes to be interleaved.
Exercise 1. From the Visible pulldown menu, select the "Show Proposed Structures" item. This will make visible the intermediate steps that are being taken to build structure in the Workspace. These "Proposed Structures" are shown in green, with the darkness corresponding to the level of completion, with black corresponding to fully built structures.
Make sure the Workspace is Maximised and run the problem abc-abd, ijk-?, using a random seed value of 25. You should see several possible avenues being explored in parallel, with the proposed structures not straying too far from the structures that are built. This is similar to a column of ants, in which the ants at the front branch out in all directions, with the most promising pathway being taken by the colony.
Describe some of the alternatives that were explored.
Urgency Values
Each Codelet when created is assigned an urgency value (which describes the estimated importance of its potential action in the formation of a solution) and is placed in a pool of Codelets called the Coderack. The name "Coderack" was designed to conjure up the image of a coat-rack, in which there limited space, an ever changing population (i.e. new clothes are bought, and old ones are thrown away), with only one item being selected at a time from any potential position in the rack to be worn.
From the Coderack, Codelets are chosen probabilistically one at a time to run, based on their urgency values. The urgency values themselves are calculated on a number of factors, including the activation of corresponding nodes in the Slipnet, and how well the structure fits into the existing structures in the Workspace. For example, Codelets that are seeking instances of a Slipnet Concept that is weakly activated in the Slipnet, will have a low urgency value and will have to wait a long time before being selected to run. In contrast, a Codelet that is seeking an instance of a highly active node will have a high urgency value and will be run soon after it is created.
As the choice of which Codelet to run is a probabilistic decision based on urgency, the Coderack cannot be thought of as a priority queue, where the highest priority tasks are run first. Rather, the urgency value dictates the relative speed at which a process is running.
CHECKLIST
By the end of this section of the tutorial you should:
- have an understanding of what a parallel terraced scan is, and how it is implemented in Copycat
- know how urgency values are assigned to Codelets, and the role that they play in the selection of Codelets from the Coderack
