WHAT IS IT?

This model demonstrates an agent-based technique for plotting the curve of an equation. While this is not a typical StarLogo application (or even a typical agent-based application), it serves as an example of how turtles with very simple behaviors can participate in a complicated math-based model, with minimal control by observer code. More specifically, this model demonstrates a simple, non-calculus-based approach to goal-seeking (e.g. optimization or root-finding) with turtles: here, the turtles are trying to minimize their absolute deviation from a specified function value.

HOW IT WORKS

In the traditional, procedural method for plotting graphs that is usually taught to students, we iterate across some set of X values, compute the Y value for each X, plot each (X, Y) pair on a grid, and draw a more or less smooth curve connecting the plotted points. In contrast, this model uses agents that wander around, in a semi-directed fashion, until their coordinates satisfy the specified equation (within a given tolerance); when this happens, the turtle marks the patch on which it is standing, and then dies. The procedural approach works well when it is easy to isolate one variable on one side of the equation; when this is not possible, a declarative approach (like the one used in this model) can be simpler - even if it requires more steps.

Perhaps the best way to understand the mechanism used by the model is to imagine performing an analogous exercise with a group of students - in fact, such an exercise might be a useful activity for a first- or second-year Algebra class.

Assume you have a gymnasium, playground, parking lot, or playing field, marked out as a cartesian grid. The origin (0, 0) is at the center of the space, and each unit in the X or Y direction is a meter or yard (or a foot, in a pinch) in the playing space.

To begin, instruct the students to find a random spot on the playing space, and face a random direction. At the same time, display (on a whiteboard, flip chart, etc.) the equation the students will be "plotting". (If you are doing this with first-year Algebra students - whether in reality or in StarLogo - it makes sense to start with a linear equation, e.g. y = 2x - 4.) It is not crucial for all students to be able to see the equation clearly at all times; the instructor (and/or any assistants) will be communicating the necessary information to the students. Moving forward, the task is for the students to wander, until their locations on the grid fit the curve of the equation.

Each student's position on the grid is used to determine how close he or she is to the curve; this distance is given by the absolute value of how "unbalanced" the equation is. For example, if our equation is y = 2x - 4, and a student is located at (3.5, 8), then the left side evaluates to 8, and the right side evaluates to 3; the absolute difference between these two is 5, and that is the value the student must remember until the next step. (This is not a rectilinear or euclidean distance, but is simply a measure that will be used for comparison at the next step, so that the student can tell if he or she is closer to, or further away from, the curve.)

From this point on, the following steps are performed at each iteration:

1. Each student takes one step (or a couple of steps, depending on the size of the space, and on the student's distance from the desired value) in the direction they are facing.

2. Each student is told (by the instructor or an assistant) his new distance from the curve (as described above).

3. If the new distance is greater than the previous distance, the student should turn 180 degrees, to face the opposite direction.

4. If the new distance is less than a predetermined tolerance, the student is considered to be on the curve; he or she stops, and takes no more steps.

5. All students who are not yet on the curve should pick a new direction - mostly going in the direction they are currently facing, but possibly turning a bit to the left or right (whether to turn, and how much, is completely up to the student - however, the student should turn no more than 90 degrees to the right or the left).

We can see that these steps are essentially the classic "wiggle" motion, with two critical refinements: if the student finds he or she is getting further from the curve, he or she must turn in the opposite direction, before continuing to wiggle; if the student is on the curve (based on having a distance from the curve that is within the predetermined tolerance), he or she stops, and does not continue to wiggle. As an option which would be useful for a small class, a student who has stopped could mark the spot (e.g. by marking with chalk on a playground or parking lot) and then begin again - finding a new random spot in the space, and commencin' to wiggle.

When all students have stopped, they are all on the curve. If the number of students is reasonably large, they will trace out the shape of the curve; even with a small number, simple curves (esp. those of linear functions) should be quite apparent from the students' positions.

The StarLogo model functions almost identically to the description above, with a couple of variations:

- The turtles know enough to compute their functional value (and thus, the absolute distance from the desired functional value) at each step; no observer code is involved in doing this.

- The function (which can be a second order polynomial in X and Y) is expressed with all variables on one side of the equation, and the constant term on the other. For example, the equation used above (y = 2x - 4) would be expressed as 2x + y = -4; thus, the slider corresponding to the X coefficient would be set to -2, the slider corresponding to the Y coefficient to 1, the slider corresponding to the constant term to -4, and all other coefficient sliders would be set to 0.

- Before evaluating the desired function, and each turtle's distance from the curve of the function, the X and Y coordinates of the turtles are multiplied by a scaling factor. This factor is based on the "Plot Scale" slider: 10 is raised to the value taken from the slider, to compute the scaling factor. Thus, the scaling factor can range from 0.001 (Plot Scale = -3) to 1000 (Plot Scale = 3). This scaling allows for a greater range of equations that can be plotted.

- The step size and maximum wiggle angle at each iteration are partially determined by the distance from the curve.

- When a turtle is within a specified tolerance from the curve, it sets the color of the underlying patch (to a shade of green, based on the distance to the curve), and dies. This setting of the patch color is essentially plotting a point on the curve.

- When all turtles are dead, it means that the curve is as fully plotted as it will be in this run of the model, and execution stops.

HOW TO USE IT

Use the first group of sliders to specify the coefficient and constant values in the equation ax^2 + bx + cy^2 + dy + exy = k (from here on out, this equation will be referred to as f(x, y) = k).

Use the "Number of Plotting Turtles" slider to specify the number of turtles to be used in plotting the equation. Using more turtles will generally result in a more filled-in line, but each iteration (especially at the start) will take longer if there are more turtles. 500 or 1000 turtles is a pretty good starting point.

Use the "Plot Tolerance" slider to specify how close the turtles must come to the desired constant value k, when evaluating the function f(x, y) at a specific point, in order to be considered "on the curve". The actual tolerance is computed by raising 10 to the power specified with this slider - for example, a value of 0 means that a turtle will mark its spot and die when its computed function value is in the range (k - 1, k + 1); a value of -2 means that a turtle will not stop seeking the curve until its computed function value is in the range (k - 0.01, k + 0.01).

Use the "Plot Scale" slider to zoom in or out. A value of 0 means that the plotted X values are in the range [-screen-half-width - 0.5, screen-half-width + 0.5), while the plotted Y values are in the range [-screen-half-height - 0.5, screen-half-height + 0.5). Changing this value multiplies the X and Y ranges by the corresponding power of 10 - for example, a value of -1 divides these ranges by 10, while a value of 2 multiples the ranges by 100. (Monitors below and to the right of the canvas indicate the current effective scaled height and width of the canvas.)

Use the "Plot" button to start the plotting process. As the process advances, the "Step #" monitor will indicate how many iterations have been performed, and the "Turtles" monitor will indicate the number of turtles which are still wandering around, looking to find the curve.

If any of the sliders are modified while plotting is in process, the process will automatically restart with the new parameter values. To stop the plotting process at any time, simply re-press the "Plot" button, so that it is in the up position.

The "Reset" button can be used to re-scramble the turtles (creating new turtles as necessary) and reset the plotting process to its initial state. This button is useful for plotting the same curve multiple times, to point out different features to students.

THINGS TO NOTICE

In some non-linear curves, turtles tend to end up more in some regions than in others; also, in some cases, turtles will wander around (before finally landing on the curve) longer in some regions than others. For example, in plotting the equation -x^2 + y = 0, more turtles will wander around in the neighborhood just below (i.e. in the negative Y direction) the origin than anywhere else; for most hyperbolas (e.g. x^2 - y^2 = 1), more turtles gather in the neighborhood directly between the centers of the two branches of the hyperbola, vs. around the extremities of the branches - however, a few turtles will take a very long time to settle in, in the extremities. If we were to make a three-dimensional plot, with z = |f(x, y) - k|, we would see that the relative flatness or steepness of different sections of the resulting terrain corresponds to the different covergence behavior seen in the model. Since our distance metric and step size are based on the difference in height between the current point and the target contour, the slope of the terrain close to the target contour has a lot of influence on the convergence behavior.

In general, the best results (in terms of performance, and display quality of the plot) are obtained when the values of "Plot Scale" and "Plot Tolerance" are similar or equal. Setting the tolerance much larger than the scale will generally result in wide banding in sections of the plotted curve. Also, note that with such banding, turtles will often reach the edge of the tolerance band and stop, leaving the outer edges of the band well-marked (with darker-green spots), while the core of the band (where the actual curve of the function lies) remains relatively sparsely filled with light-green dots. On the other hand, setting the tolerance much smaller than the scale will result in the turtles congregating in the neighborhood of the curve, but taking a very long time to settle down and plot the curve.

Depending on the type of function being plotted, and the coefficient and constant values, some functions cannot be plotted without zooming out (increasing the plot scale); other functions (e.g. x^2 + y^2 = 1) will not be plotted in sufficient detail, without zooming in; finally, some functions (e.g. x^2 + y^2 = -1) cannot be plotted at all in the plane of real numbers (the locus of points which satisfy the equation lies entirely in the complex plane). If you attempt to plot a function which cannot be displayed in the plotting canvas - either because the displayed scale is too small, or because f(x, y) = k has no real-valued solutions - the turtles will just wander around, without plotting points on the curve. (In some cases, they may appear to converge, but they never stop moving.) This non-terminating behavior can be detected easily: the monitor showing the number of turtles left alive will never show a decrease.

When a curve extends beyond the edge of the canvas, some turtles converging on that part of the curve will wrap around to other side, and may end up converging on a completely different portion of the curve.

THINGS TO TRY

Experiment with different kinds of equations. Which equations require the fewest iterations to draw the curve satisfactorily? Which require the most?

Experiment with different numbers of turtles, and with different kinds of equations. Which equations require the fewest turtles to draw the curve satisfactorily? Which require the most?

Experiment with setting different plot tolerance values, and with different kinds of equations. Which equations require the tightest tolerance (or the most iterations)?

After experimenting with different coefficient and constant values, and observing the results, try to anticipate how new coefficient and constant values will affect the resulting curve. What changes in coefficient and constant values will require a change of scale? Are there some types of equations, and some sets of coefficient and constant values, which - while having real-values solutions - result in the plot being completely off the canvas, regardless of the scale selected (from the range available)?

After discussing traditional methods for plotting curves (e.g. iterating over a subset of the domain of X values, then solving for and plotting the corresponding Y values), compare the relative scomplexity of the procedural (traditional) method, vs. that of the declarative method used in this model. Also, compare the time required for the different methods. Do the comparisons change for different types of equations?

EXTENDING THE MODEL

The current model supports a very general 2nd-degree polynomial function in X and Y. Useful "downgrades" of the model could be constructed, restricted to simpler types of equations (e.g. straight lines, Y as a quadratic function of X, etc.). Alternatively, the user interface could simply be rearranged, hiding sliders which are not appropriate for the target users.

The model could be extended (or probably more usefully, a new version created) to support trigonometric functions, e.g. y = a*sin(b*x + c) + d*cos(e*x + f). It could also be extended to support equations in polar notation: r = a*sin(theta) + b*cos(theta) + c*theta, etc. This latter change would require a bit more work, since each turtle would have to use the "distance" and "towards" commands at each iteration, to get the current r and theta values. (Also, I suggest, to anyone wants to try making a new version that supports polar coordinates, that the result of the "towards" command be transformed into standard mathematical angular measurements - i.e. theta measured in radians, with theta = 0 along the positive X axis, and with theta increasing in the counter-clockwise direction. This would make the polar notation used in the model match the usual trigonometric conventions.) Of course, the r value would have to be scaled, just as the x and y coordinates of the turtles are scaled in the current model.

For use as a visualization tool in a college-level course, it could be very useful to scrap the wiggle-based movement, and use a differential-based method (e.g. Newton-Raphson) to determine the direction and distance the turtle should move. As an additional option, useful in root-finding and optimization of very complex functions, a Simulated Annealing-based model could be used to control the maximum step size. (One of the difficulties in doing the latter would be in finding functions suitable for demonstrating on the StarLogo canvas, which would also be complex enough to warrant using the Simulated Annealing approach.)

The model could be made to perform somewhat more efficiently, by having the "Plot" button call the turtle procedure "iterate" directly, rather than calling the observer procedure "plotGraph". This would simplify the Java thread management performed by StarLogo, making the model run faster; however, the "Step #" monitor would no longer have any meaning, and the facility to restart the plotting process automatically when parameter values change would require the use of an additional "forever" button (which could be pressed programmatically), calling an observer procedure which monitors the sliders. (Even if the plot were not restarted when the sliders changed, there would need to be a way to insulate the turtles from changes in the parameters, while plotting is underway.)

On-the-fly rescaling (i.e. without restarting the plotting process) could be implemented by having turtles which are on the curve stay alive, lighting up according to their distance (instead of setting the patch color, as in the current model). Then, when rescaling is needed, an "ask-turtles" command could be used to move the turtles towards or away from the center, according to the new scaling factor. However, turtles would have to reverify their on-the-curve status after zooming in, since this could result in sections of the curve, which were previously within the boundaries of the canvas, being scaled off the canvas; any turtles marking those sections would wrap around, and would almost certainly not be on the curve anymore.

In some cases, and with enough memory dedicated to the Java VM, it might be more efficient to skip using turtles altogether, and just use patch logic. To do this, you would use an "ask-patches" command, and instruct the patches to scale their color using the same logic used (by turtles that have landed on the curve) to mark the patches in the current model. With that approach, patches outside the effective tolerance value would be colored black, and those within would be colored with shades of green; thus, the result would look very similar to what the current model produces. This "ask-patches" logic would only need to happen once; there would be no need for iteration. (While this is still a declarative, rather than procedural, approach, it isn't really agent-based.) This change would result in a model with very little code, but it could take a great deal of execution time - and if there were too many patches, it would run for a while, and then stop, without seeming to do anything. (StarLogo v2.2 seems to be less robust in this respect than v2.1 was.) However, assuming that it ran, it could be a useful experiment - especially in a CS class - to have students assess the tradeoffs between having each of (screen-width * screen-height) patches evaluate the function once, vs. having a much smaller number of turtles evaluating the function dozens or hundreds of times each. (In this comparison, it might be useful to look at the model with the speed slider turned down, so that the convergence behavior - i.e. do the turtles converge in a uniform fashion, or do most converge quickly, with a few taking much more time - is more apparent. Also, the thread-management overhead for each case would have to be included in the comparison.)

STARLOGO FEATURES

This model uses sliders for controlling almost all aspects of execution (with the exception of the values controlling the step size and maximum wiggle angle at each iteration; those values - and the step-size & direction control scheme itself - could use some further experimentation and tuning).

Monitors are used to display the current iteration (step) number, and the number of turtles still searching for the curve. Since these values are also used in the main observer iteration procedure ("plotGraph"), they are maintained in globals by that procedure, and those globals are accessed by the monitors.

The "scale-pc" command is used by the turtle "reorient" procedure to modify the color of the patch on which a turtle resides, when the turtle detects that it has reached the curve.

The "jump" turtle command is used instead of "forward", in order to reduce the runtime impact of having hundreds or thousands of turtles moving around the screen at once.

The "no-display"/"display" command pair is used when setting up the screen, in an attempt to minimize the drawing time required, and minimize screen "chatter" while creating the axes and the turtles; however, the benefit of doing this in this model is only seen with a very large number of turtles (i.e. thousands). In fact, a previous version of the model wrapped each iteration of the process in these commands, but that degraded performance significantly (especially when the plot was mostly filled in, and the number of turtles was low).

Global variables are used to maintain internal copies of all of the slider values. At the start of each iteration, these copies are compared to the current slider values, to see if the user has moved the sliders while the model is running; if that is indeed the case, the internal copies are updated, and the model is restarted with the new values. (The code involved in doing this makes up the bulk of the observer code.)

Additional global variables are used for most of the constants used in the model. This allows for modifying these values without having to search for them in the code; instead, a few lines in the "setConstants" procedure can be modified as necessary.

Simple iteration (based on the "dotimes" command) is used to draw the axes. A previous version of the model used "ask-patches-with"; however, with the number of patches in the model (approximately 90,000), this ran very slowly in StarLogo v2.1x, and not at all in StarLogo v2.2x (in other words, v2.2 made it painfully obvious that "ask-patches-with" probably isn't a good idea, for cases where there are very many patches, but where only a few satisfy the specified condition).

Since the main "forever" button which runs the process calls an observer procedure, the same procedure checks the turtle count, and stops all procedures and monitors (after a short delay, to allow the monitors to perform a final upate) if there aren't any turtles left. (If the "forever" button were calling a turtle procedure, this check would not be necessary: the button would automatically stop when there were no turtles left.)

In generating a reasonably detailed plot, this model benefits from a very small patch size. Also, for flexibility in the different types of equations that can be plotted, and to handle different function coefficients and constant values, a fairly large canvas is required. Thus, unless a very large monitor is being used, I don't recommend using a patch size larger than 2.

CREDITS AND REFERENCES

This model was developed by Nick Bennett (nickbenn@g-r-c.com) of Grass Roots Consulting (http://www.g-r-c.com), in response to the concern (expressed repeatedly by some Adventures in Modeling participants) that StarLogo does not seem to be useful in teaching Mathematics. Nick's sincere desire is that this model will help change a few minds.