CASAP: A Testbed for Program Flexibility
Proceedings of the Third International Joint Conference on Artificial Intelligence. General Problem Solving. Pages 601-604.
© 1973 International Joint Conferences on Artificial Intelligence
Abstract
CASAP attempts to create a more flexible knowledge-based system for performing actions. It is based on the combination of a procedural representation of actions. and an information retrieval subsystem used to dynamically obtain all information required to perform an action. It is argued that such a combination eases the specification of new actions and increases their ability to obtain. from a wide variety of possible environments. the information they require.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
Introduction
The effort to build Intelligent programs has received a great deal of Interest for a number of years. The early attempts were of the theorem proving type characterized by the Logic Theori~t [1·]. which attempted to · Imp-lement the ru 1 es of propG.S-1 tiona 1 ca leu 1 us. Using these rules the system attempted to move from a stated set of axioms to a theorem to be proved by a generalized search technique. This system was the genesis for the later General Problem Solver (GPS) [2]. GPS applied a series of user specl.fied operators to move from the initial state to the goal state as determined by rules of applicability of those operators and as directed by a difference table to eliminate differences between the current situation and the goal state.
Both systems are essentially table driven and represent an attempt to build a single general purpose problem solver capable of accepting valid operations in a wide variety of domains and using them to move from initial to goal states. The problem with such attempts has been that the general mechanisms contained within them for deciding in what order to apply the operators to make progress towards the goal have not been adequate for the problems under investigation. Also. specific knowledge about how to proceed in a particular domain has been difficult to state Jn a general form for such systems.
This research is supported b.y the Advanced Research Pro.jects Agency under Contract No. OAHCIS 72 C 0308. ARPA Order No. 222311. Program Code _No. 3030 and 3Pl0.
CASAP: A TESTBED FOR PROGRAM FLEXIBILITY
Robert M. Balzer
USC Information Sciences Institute 4676 Admiralty Way Marina del Rey. California 90291
These difficulties with general problem solvers led to a second approach centered around the incorporation of specific knowledge about how best to operate in a particular domain. Since this knowledge was not well codified. these systems represented it in the most general way known: i.e., in terms of programs. Experience with systems of this type led to the development of PLANNER [3] as a way of systematizing some common aspects of this approach. These common aspects include provisions for backtracking, provisions for the dynamic update and maintenance of a data base, and pattern directed Invocation (i.e., routines are invoked not by name, but by the results they promise to deliver. The promise is pattern matched against the current subgoal and is invoked if the match is satisfied) - the procedural analog of the difference table
In GPS.
These systems have traded Increased operational power for loss of awareness. Because the knowledge Is represented procedurally. the system is less capable of using it deductively or In determining what the consequence of particular actions may be.
CASAP represents a combination of these two approaches: the procedural representation of knowledge together with the general mechanism for assembling the information required for actions or inferences.
There are two main problems with the procedural approach. The first is the concurrent transfer of both control and data between routines. Typically, when a routine is invoked. the data that it is to process is also passed to it as part of the invocation. Thus, the caller needs to know what data is required by the called routine. Such an organization is much too rigid. All that the caller should know about the called program is the result that lt promises to deliver. Since routines are to be invoked on the basis of the result that they promise to deliver. if for one reason or another they are inapplicable in a given situation, then they wi 11 inform the caller of this and alternative action can be taken. It should therefore be the responsibility of the called program to obtain the information it requires.
Towards this end, some systems keep the data In a common global data base which is directly accessible by all routines. Hence. any routine can get at whatever data it requires. This, too, is an unacceptable
solution; for It requires too wide a distribution of the knowledge of how and where to fln.d Information, and unnecessarily comp ll cates .each of the rout l nes in such a system.
We propose instead, in CASAP, to place a single information retrieval routine between any routine requiring data and the global dat~ base itself. Thus, all each routine requires is the knowledge that it needs a certain piece of information which it then requests from the information retrieval package. Knowledge about the data base Is thus centralized in a single routine.
The second major prob I em wi -th the procedural approach is the pointwise applicability of procedures. Either one procedure or another Is active, but not both. This greatly limits the ability for two or more procedures to perform actions in a coerdl nated way. The closest thl ng ·We have to a solution fo~ this problem are the demons which exist in various systems. These demons watch for certain events, in either the control or data spaces, and when such events oacur, invoke an associated routine which then gets control. This allows for more dispersed and low level interactions between various routines toward a coordinated goal, but does not, in fact, lead to coordinated actions~
If viewed in this manner, CASAP does not address this issue at all. However, from a different standpoint, what we desire is the ability for one routi-ne to influence the behavior of another rout~ne, that is, to set up constraints or suggestions which are dynamically used to modify the behavior of the invoked routines as directed.
CASAP, in a limit ed way, performs such modifications by utilizing a context which is established and maintained by the information retriever, and used whenever information is required. Thus, the information obt~lned at any point, in response to a question, is dependent upon the context that has been previously set up. Through this mechanism an invoking routine can establish the context in which the request for. informatlon from invoked ¥outines will be answered and thus changes the perceived state .of the world for that routine.
This mechanism is, however, .quite ll.mited from two standpoints. first, it only deals with information that the invoked routine requires in a particular situation. Information which is not . needed by the invoked routine has no way of Influencing the behavior of such a rout l.ne. Second] y.. l t l s an information-based context and not an action-based one. Hence, it only plays a part when information is required and not when actions are being performed. With these restrictions in mind, however, it is a step in the direction of a system which utilizes context for the lnterpretion of actions and information dynamically required.
It is our belief that moving from essentially macro based languages to languages that are essentially context dependent for the Interpretation of both actions and data Is the next major needed advance in programming languages.
System Organization
CASAP represents our attempt to test these ideas in an operational way and has demonstrated, in a very limited way, the feasibility, if not the practicality, of such an approach.
Organizationally, CASAP was predicated on the principle that there would be no subroutines in CASAP programs (the system Itself was Implemented by standard technique); that there would be no hard, well-defined Interfaces between the specifications of actions to be accomplished; and that Information would flow among the processing components as required by the particular example, rather than as preplanned. Thus, both the decision of what actions to Initiate, and how and where the information for those actions is obtained, Is dynamically determined while the system is in operation.
The system logically consists of three parts: an Interpreter responsible for carrying out initiated actions; an Information retrieval part responsible for obtaining and putting Into usable form the Information required by initiated ·actions and/or the user; and finally, a modification component responsible for altering an action to fit it into a dynamic context. Currently the modification component is null and the system has been constructed so as not to invoke this
function.
As part of this experiment we wanted to investigate the bul ld-up and use of commonly used concepts in a natural way. Hence, we have decided to use English as the way of specifying the actions, the concepts, and the information Input to the system. However, to avoid concentration on parsing of natural language, all input to the system was pre-parsed by the author, although it still contained the original English words.
Each input by the user was examined to see whether it was a concept or fact to be added to the data base, or the initiation of an action. In the former case the concept or information was merely stored in the data base in the input form. Commands, however, caused the system to determine which action should be invoked. This is done by pattern directed invocation centered around the verbs. That Is, the system first determines what actions It knows about in the data base that correspond, either directly or by inference second level of applicability check is made to see if the action is appropriate for the
with the specified command word (verb). A current situation.
If any such actions are appropriate, the system selects one and applies its definition. This process Is repeated until one of the primitives of the system is applied. These primitives consist of the set manipulating routines of insert, remove, create, and destroy which enable the system to add, delete or modify attributes and/or their values to objects In such sets. As the specifications of the operations are being applied, contexts are being built up, which enable the Information retriever to locate the relevant data for the operations to be performed.
System Operation
Let-s consider some examples from the protocol In the appendix. All the examples In this paper wl II be drawn from the domain of card games, and particularly from the game of Hearts. The system knows nothing about either cards, card games, or the game of Hearts initially but merely the idea of ordered sets and the manipulations previously indicated as being primitive.
We begin by telling the system that a hand is a set of cards ordered by suit and card value and then tell it the ordering ~elatlonshlp both for suits and for the card values by explicitly naming the values of each of these attributes In order. Then we tell the system that all players have a hand, and ask It to create a player which we are going -to ca I I PI ayer I. The system creates such a player, notices that all players have a hand, and therefore, constructs with that created player, a set which Is to be its hand, which the system knows will be composed of cards. We similarly then create two other players named Player 2 and Player 3. Then we create five cards. Having now primed the system, we are ready to start investigating its behavior in carrying out a series of actions. We begin with the command "insert card 1 in the hand of Player 1°. The "insert" primitive action is applied and obtains both the object it Is to Insert and the set in which it is supposed to do the insertion by asking questions of the Information retriever. In this case, the required Information Is Immediately aval lable; and no problems are encountered In this execution. However, when we ask the system to then Insert card 2 In the hand of Player 1, the system first finds out which card and in which set the object Is supposed to be Inserted. Then, In the process of doing the Insertion, It discovers that this set is ordered. It determines that the primary ordering relationship Is suit. Since there already Is a card In that set., It must discover the relative ordering between those .two cards on the basis of the suit attribute. .Therefore, it attempts to fl nd out the suit of .the car.d It Is now Inserting. An I nterna I question Is formed for the information retriever, which looks through the current .context and the data base, but can-t dl scover the value of this attribute, and so~ asks the user. The user responds that It-s a heart. The system then continues operation of the I-nsert primitive, but sees that it must also find the suit o.f the already .Inserted card so that a compariso.n may be made. Again a question is formed, and again the Information retriever asks the user. The user responds that the suit of card 1 is a diamond. Because the two suits are different, the system can order them properly; and card 2 Is correctly Inserted in the hand of Player 1.
Notice that we routine twice. In information that it have invoked the same the first case, the only needed was the primary objects that were manipulated - - the object to be Inserted and the object In which the Insertion was to be done. In the second c ase, those same pieces of information were needed; and, In addition, two other pieces of Information were r equired: the suits of the two cards that were being inserted, so that the ordering could be properly maintained.
Thus, the amount of Information required by this routine- or, In fact, any routine, - Is context dependent. This is one of the main reasons why we want such information to be dynamically obtained through the information retriever package, rather than being passed down or discovered by Individual examination
of a global data base.
To belabor the point even further, suppose we now insert another card, and when the system asks us what the suit of that card is, we tell it that it Is also a heart. Since there is already a card, which is a heart, in the hand, it must obtain further information to resolve the conflict. By exam1n1ng the ordering relationship specified with hands, it finds that this relationship is the card value. Th~ Insert routine must then discover the card value of both the new card being Inserted, and the old card with which there is a partial conflict.
Skipping ahead in the protocol, after putting the players around in a circle by means of a relation called "to the left of", we reach an interesting command "each player passes the highest heart". (For ease of explanation we wi 11 now deviate slightly from the protocol In the appendix.)
Once the system has obtained the relevant actIons, of which there might be sever a 1, it sees which of them are applicable to the given situation on the basis of their applicability to the objects described. In the current example, the system had available a description of how to pass a card. To test the applicability of this action, an internal question was generated as to whether the highest heart was a card. The Information retriever examined the data base, and found that heart was the value of the suit attribute of the object card. Therefore, it assumed that highest heart was a descriptive term being used for card which is the highest heart. Hence the description of how to pass a
card was i nvoked.
The interpreter retrieved the previously specified definition of "pass a card," which is: uremove It from your hand and place it face down on the table In front of the player to your left" ("in front of" was taken to be a specific location on the table for each player). The interpreter then invoked the remove operation by pattern directed · invocation. This operation is one of the primitives of the system consisting of all the set manipulation operations. To perform the remove operation, the objects which "remove" manipulates must be available. It obtains these through the information retrieval package, but first forms a question to discover from which set the objects are being removed. The information retriever discovers that it is "your hand" and that there exist many hands in the data base. Thus "your" is used to determine which one is being specified. "Hand" is looked up In the data base and is found to be o~ned by "player." Thus "your" refers to a particular player. Since it Is not further specified, the Information retriever assumes that the particular player is the one who is in context, that is, the one selected earlier by the interpreter as part of the iteration of the "each player ··· " command. Thus, the Information retriever returns to the interpreter the specific set that has been referenced. Next, a question is formulated ~ithin the remove package to discover which object from that set is to be removed. Again the question Is formulated and the information retriever, working through the context stack, finds that the object is the card being passed, and that the card being passed is the highest heart. At this point the information retriever computes which is the highest heart within the context of the previously selected set, i.e., the highest heart is computed on the basis of the hand in question and not the highest heart in the deck.
As one can see, the success of the interpretation of this particular example is critically dependent upon the order In ~hich the questions ~ere asked; but the knowledge that they should be asked In this particular order, namely, finding the set first and then the object within the set is part of the intelligence of the remove package. not part of the general intelligence of the system itself.
However, the remove routine is actually a little bit more general than indicated. Had the information retrieval package not been able to find a specific set for the remove operation, then the question would have been asked as to whether the object being specified was a named object or a computed object. If it was a named object, then the question of which set ~ould have been re-asked in the context of those sets that contain the specific object in question. In the current example the object ~as a computed one; and hence, the strategy would have failed.
Conclusion
It is important to note at this point the flexibility that has been demonstrated by this admittedly simple example. The correct interpretation of the command ~as accomplished by the combination of the follo~ing: information in the data base ~hich allowed us to de.termi ne that the highest heart was an instance of card; the context set up by a definition of one of the operatons used in carrying out that command, namely, the context established by the set specification in the definition; and the intelligence incorporated In the system at the lowest level in the order in ~hich the remove package dynamically obtained its parameters. The combination of these elements in an environment that dynamically obtains information as required has produced an instance of the flexibility that people seem to have in locating and utilizing Information as opposed to the rigidity displayed by most computer systems.
Appendix
Sys: CASAP Initialized
User: Hand is set(card, ordered-by suit and card-value)
Sys: Input accepted
User: Value-set(of suit, is clubs, and and diamonds, and hearts, and spades)
Sys: Input accepted
User: Value-set(of card-value, Is ten, and Jack, and Queen, and King and Ace)
Sys: Input accepted
User: Player(which all, has hand)
Sys: Input accepted
User: Create object player named Playerl
Sys: Input accepted
User:
Sys:
Create object player named Player2
Input accepted
User: Sys: Create object player named Player3 Input accepted
User: Create object card named Cardl
Sys: Input accepted
User: Create object card named Card2
Sys: Input accepted
User: Create object card named Card3
User: Input accepted
User: Create object card named Card4
Sys:
Input accepted
User: Create object card named CardS
sys: Input accepted
User: Insert(object cardl, in hand of PI ayer 1)
Sys: Input accepted
User: Insert(object card2, in hand of Playerl)
Sys: What is the suit of Card21
User: Hearts
Sys: What Is the suit of Cardl?
User: Diamonds
Sys: Input accepted
User: Insert(object Card3, in hand of Playerl)
Sys: What Is the suit of Card31
User: Spades
Sys: Input accepted
User: Insert(object card4,in hand of Player!)
Sys: What is the suit of Card41
User: Hearts
Sys: What Is the card-value of Card41
User: Jack
Sys: What is the card-value of Card21
User: Queen
Sys: Input accepted
User: Insert(object CardS, in hand of Playerl)
Sys: What Is the suit of CardS?
User: Hearts
Sys: What Is the card-value of CardS?
User: King
Sys: Input accepted
User: Remove(object hearts which hlghest,from hand of Playerl)
Sys: What Is the means of highest?
User: Sys: Highest means card-value most large Input accepted
User: To-the-left(of Playerl,ls Player2)
Sys:
Input accepted
User: To-the-left(of Player2,ls Player3)
Sys: Input accepted
User: To-the-left(of Player3,1s Playerl)
Sys: Input accepted
- User: Pass(who player which each,object card(suit hearts, which lowest))
What is the means of pass?
- Pass(object card:*1,means remove(object *1,from hand which your,then Insert (object *1,in hand of player which-is to-the-left of player)))
Sys: What is the means of lowest?
User: Lowest means card-value most small
Sys:
User:
Input accepted
Stop
@inproceedings{ijcai1973p74,
title = {CASAP: A Testbed for Program Flexibility},
author = {Balzer, Robert},
booktitle = {Proceedings of the Third International Joint Conference on
Artificial Intelligence, {IJCAI-73}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Nils J. Nilsson},
pages = {601--604},
year = {1973},
month = {8},
note = {General Problem Solving},
url = {https://ijcai.org/proceedings/1973/74},
}
TY - CPAPER TI - CASAP: A Testbed for Program Flexibility AU - Balzer, Robert T2 - Proceedings of the Third International Joint Conference on Artificial Intelligence, IJCAI-73 PB - International Joint Conferences on Artificial Intelligence PY - 1973 SP - 601 EP - 604 UR - https://ijcai.org/proceedings/1973/74 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: