Logical and sub-logicalanalysis

Unedited posts from archives of CSG-L (see INTROCSG.NET):

Date: Thu Oct 14, 1993 9:19 am PST

Subject: Logical and sub-logicalanalysis

[From Bill Powers (931014.0910)] Avery (931014.1530)

> The control system responsible for direction of movement produces anerror signal proportional to the angle between the current direction oflocomotion (the direction the CROWD person is headed) and the direction of thegoal. But there could be another system that ascertains whether motion in thecurrent direction is blocked for the goal ...

In CROWD there is such a second system. However, it ascertains somethingmuch simpler which has the same effect: whether something is too close. Insteadof analyzing the scene and reasoning about it, the person in CROWD simplyavoids, at all times, too much proximity to anything, divided into two classes:total proximity in the left-forwardregion, and ditto in the right-forwardregion. Too much proximity to the left results in a veer to the right, etc, theradius of curvature automatically being inversely related to total proximity.As designed, this system simply overpowers the destination-seekingsystem, but it could have modified the destination-seekingsystem's reference angle to avoid conflict.

In your diagram, a CROWD person would simply head toward the goal until itgot close to the wall, and then veer left or right to avoid collision. It wouldmove along the wall to an opening, and if the sides were far enough apart,through the opening and on toward the goal. The effect is to pick an openingthat is reasonably close to the direction of travel. Not, of course, by theshortest path. The person doesn't actually seek the opening; in effect it justkeeps moving until there is decrease in proximity in a direction toward thedestination, and that reduces the tendency to veer away from thatdirection.

In my original stab at the CROWD program, each person had a 360-degreemap in 6-degreebins, with total proximity recorded in each bin. The idea was to scan the mapand look for minima in total proximity near the direction of the goal, and setthe position of that minimum as the immediate destination. When the person gotto that gap, another scan would take place and a new gap would be sought. Thiswould have resulted in more intelligent behavior in some circumstances, butbecause what lay beyond any given gap was invisible, the result wouldn't havebeen a lot better. And because there were other active people on the field, agap wouldn't necessarily stay put or continue to exist while you were travelingtoward it; in fact the scan would have to be redone on every step, or at leastvery frequently, and a wrong guess about which gap would remain open mightresult in a very unintelligent-lookingpath. Also, as you can guess, by the time I had 10 or 15 active people, allmaking maps, the program was simply CRAWLING along.

I soon saw that I was getting into a complicated logic-levelmodel, and that I still had to solve the collision-avoidanceproblem, so I looked for a simpler way. The simpler way proved to be just toavoid collisions and forget about the map. This method has all sorts ofintelligent-lookingeffects that would require very complicated searching and reasoning toaccomplish by a brute-forcelogical system --for example, getting back out of a cul-de-sac,or deciding that there are no gaps of a large enough size and turning away togo completely around the crowd.

In fact the simpler program does many things that I never would havethought to provide for at the logic level and that would have had to be addedto make the program actually work. Just think of the logical problems when onegroup of five people heading toward one destination crosses the path of anothergroup of five heading toward a different destination, all in the midst of ascattering of stationary obstacles!

One of the most interesting things about CROWD is the way peoplerationalize it after seeing it operate, but without knowing how it works. It'salmost certain that the "explanation" will be at too high a level. "Look," theobserver says, "he's trying to get out of that pocket, looking for theopening." Of course he isn't; he doesn't even know he's in a pocket or thatthere is an opening. All he knows is proximity to left and right, and thedirection and proximity of the destination.

Your proposed rule

Direction D is blocked for goal G if, proceeding in D, you will arrive atan obstacle, such that, when you then head toward D, the obstacle is still inthe way.

is probably an unnecessary complication, a rationalization of somethingthat can be done far more simply at a sub-rationallevel. While the rule can be stated relatively briefly, getting the informationneeded to apply the logic could be extremely complex. For example, to determinewhether the direction of travel will intersect an obstacle, you must projectthe direction of travel to see whether the resulting line crosses the boundaryof some outline; this means testing every point along the line to see if itscoordinates are the same as some coordinate in the boundary of some object.Then you must change the direction of the line infinitesimally and do thecomputation again, until finally a direction is found where the distance to theintersection is sufficiently large. This is the sort of burden of computationthat results from characterizing the problem as one of logic and just trying tocompute your way through it.

If you think in terms of analog perception, it's obvious that if you'regoing to collide with an object, that object will be seen in the middle of theperceptual field, where "straight ahead" always is. In CROWD I assumed somekind of visual perception, with proximity being indicated roughly by the areaof each image, which I could compute as proportional to the inverse square ofthe distance. I could then, knowing the position and orientation of the person,and the positions of all obstacles, easily compute the proximity that would beseen to left and right for all objects --in effect, simulating the environment and the visual equipment.

The result fits your proposed rule, but without applying any logical rule.And the ensuing action doesn't require reasoning, either: you don't need toreason that if you keep going in the same direction, you'll hit the obstacle,and therefore you should institute a turn. You just hook up the perception tothe turning apparatus via a comparator.

I am always amused by "fuzzy logic" programs, which try to solve simpleanalog problems by means of logic-typereasoning. If the inverted pendulum is medium-leftand moving left, apply maximum rightward force; if medium-leftand moving right, apply medium leftward force. And so forth for dozens ofrules. Also, grade the amount of each variable by some distribution around theexact condition, in a "fuzzy" way. So you end up doing something with a high-speedRISC processor that could be accomplished at a sub-rational level with one operational amplifier and a couple of resistors andcapacitors.

If you solve these problems at the lowest level possible, then when thetime comes to consider more complex aspects of the situation, all you need isto decide which analog solution to bring into play. You don't need to carry itout at the logic level: it's already been solved sub-logically.This means that the logic actually required will be quite simple. Let the logiclevel pick the destination (I'm hungry and it's 12:00, so pick the coordinatesof the hot-dogstand as a destination), and the analog systems will get you there withoutbumping into anyone.

Best, Bill P.