M. Eng. Thesis Proposal

Push Singh

February 1997

For my masters thesis, I propose to write a program that can do limited planning in common sense domains. My approach to building the system will be drawn from Marvin Minsky’s "Society of Mind" theory of intelligence (Minsky, 85). I will develop Minsky’s paranome idea, a scheme where a diversity of specialized problem solving mechanisms, or "agencies", operate on parallel arrays of frames. This approach is motivated by the apparent diversity of common sense domains, which suggests that no planner with a single representation and problem solving strategy can efficiently solve problems in all of these realms. Accepting that to be true, systems that plan in common sense domains must use a diversity of mechanisms.   The paranome idea lets us bring multiple viewpoints to bear on a single problem, as it allows for different agencies to focus on the same thing in different ways, where a "thing" could be an object, an event, a difference, a cause – really anything at all. If a particular agency gets stuck while solving a problem, it can call for help from other agencies. These other agencies can look at the stuck agency’s problem in their own way, and perhaps see a solution that was not visible from the stuck agency’s restricted perspective.

I plan to explore these ideas by building three agencies and coordinating them to solve several planning problems in the context of a simple children’s story about a birthday party. I plan to use the Cyc knowledgebase to provide the background knowledge necessary to solve these problems. Cyc’s knowledge is organized into microtheories, consistent collections of knowledge related to some area of concern, like "people" or "space". These different microtheories can provide the background knowledge for different agencies. I will compare my multi-agency planner with current single agency planners.

What’s wrong with current planners?

The main inadequacy of current planners with respect to solving problems in common sense domains is that they almost all use a single representation scheme. There are two general categories of planners, rule-based and case-based (see footnote 1). Rule-based planners operate by searching through the space of possible plans, using control rules and evaluation functions to decide which actions to consider next during search. Case-based planners operate by matching and adapting existing plans to the current problem. But in either case, the representation of the problem is chosen in advance, and fixed throughout the planning process. A planner must choose a representation language that lets it express the differences between its current situation and its goals, such that those differences can be reduced by available actions. Given the enormous range of situations and goals, and hence differences, that arise in common sense problem solving, a common sense planner must have an extremely rich and diverse representation language. The language of Cyc, the only existing system that can express a wide range of common sense knowledge, has many thousands of terms.

The trouble begins when the planner must choose how to describe the current situation or difference in its representation language. Initially it will describe the situation in terms of those aspects that differ from its goals, but if at some point during the planning process it encounters a problem for which no solution is at hand, it must resort to searching an enormous space of possible descriptions to find a viewpoint that renders the solution obvious. Consider that even in the simplest situations the range of possible descriptions is enormous. In a typical act of giving, such as "Mary gave John a present", I can focus on Mary’s hair color, John’s appreciation of the present, the physical motion of the present as it changed hands, the transfer in ownership of the present, and a vast range of other possibilities. Current planners get around this problem either by expressing everything about the situation in a single undifferentiated union of possible descriptions, which can be done if the problem is simple enough, or they choose a particular description building strategy that restricts the descriptions to a certain narrow type. Clearly, neither of these solutions is adequate for common sense planning.

How can we add multiple representations?

In the multiple agency system I will build, each agency sees the world through the filter of a particular limited understanding of reality. One agency may know how to solve problems in social realms, where things are described in terms of who-knows-who and hierarchies of power; another may knows about physical realms, where things are described in terms of their shape, substance, and strength; another about economic realms, where things are described in terms of their value, their expected change in value as time passes, etc. What are the benefits of this approach, as compared to single agency systems?

• Individual agencies live in "microworlds" in which problem solving is relatively easy. Because any particular agency has a simplifed view of reality, it can be implemented as one of the existing "single viewpoint" planners. In fact, it a general heuristic in designing such systems could be that if an agency’s world ever grows more complicated than what one would consider a microworld, that agency should be divided into separate simpler agencies.
   
• Very different representations can be used by different agencies. One implication of this is that very different difference reduction mechanisms can be used in different realms. A spatial agency may have a planner that exploits the dimensional structure of space in finding a plan to move from point A to point B. A syntax agency may have representations that resemble grammars. A social agency may have special representations for expressing hierarchies of power, and special machinery for computing social relationships between entities. The only constraint is that the different representations share frame terminals, so that different agencies can look in on each others problems.
   
• When an agency gets stuck, it can harness other agencies. An agency that gets stuck can call upon other agencies to help it. A difference that seems impassable from the perspective of one agency may be easily crossed from the point of view of another. In fact, the other agency may suggest that the stuck agency abandon its current goal altogether since the other agency has already found a plan that will achieve that goal during the course of its own problem solving. Another idea is that a stuck agency can continue planning by "skipping" a difference that it expects another agency can probably fill in. In fact, it may start in the "middle" of a plan, and the different agencies may coordinate to fill in the plan at intermediate points until the whole structure resolves itself. The possible interactions between agencies in this manner are largely unexplored.
   
• This idea provides a natural way to separate conflicting models of reality. Different agencies may have very different ideas about the way the world works, and while this requires explicit arbitration machinery to arbitrate between agencies that generate conflicting plans (perhaps using "manager" agencies), it is still an improvement over single agency planners, in which it is not clear at all how to incorporate conflicting world models.

Footnote 1. I do not include connectionist approaches to planning because they are typically variants of rule-based or case-based planners that either use activation spreading instead of systematic search, or use threshold units in matching instead of symbolic structures.

Push Singh
push@mit.edu

Some Self-Criticisms

To someone who is trying to develop an idea, nothing is more valuable than a set of well-stated criticisms. Here are some that I came up with while working on these ideas (some are a bit "straw man".)

• I find the evidence that the brain performs many computations in parallel convincing, but this does not lead me to conclude that the brain must divide its representation of the world into "mental realms". It may be that the brain has a single stream of operation, but exploits parallelism in much the same way as a modern superscalar microprocessor – while it only performs a single operation at a time, this operation is performed in parallel, like a parallel pattern match or following many search paths simultaneously. According to this view, the brain is a parallel-ized implementation of a traditional "single viewpoint" problem solver.
   
• Most inventions are the product of a single mind, and not a team of people. Surely a society of agencies is bound to be less creative than a single agent that can connect any two ideas as easily as any other two.
   
• The amount of insulation introduced by the society of agents view makes sharing knowledge among different agencies more difficult than it is in single viewpoint systems, where the knowledge is represented in a single, uniform manner and stored in a globally accessible database. Since sharing knowledge is important, both so that agencies can share problem solving strategies and so that they can make analogies between their respective models. Furthermore, it delays the notice of goals interacting negatively. Different agencies generate conflicting plans because they are unaware of the goals of other agencies.
   
• Problem solving systems in which knowledge is represented in a single, uniform way, and where that knowledge is manipulated by a simple, easy-to-understand mechanism, are clearly easier to build than the kinds of complex, multi-agent systems that you propose. Many exist, such as Prodigy and Soar, and they have been tested successfully on a wide variety of simple problems. We have not yet shown that such single viewpoint machines cannot reason about the complex domains of common sense. Surely you ought to try getting such systems to work first, say by gluing Cyc to Prodigy, before embarking on a more complicated theory!
   
• Perhaps all we need to do to make single perspective systems scale up is to add new ways to organize their knowledge, using mechanisms like "contexts" or "microtheories".

Push Singh
push@mit.edu