Overview
Summary
JOHN is a programming language for automated planning (like STRIPS, a pioneer planning program).
It is an object oriented model of microworlds which uses situation calculus, possible worlds models, and first order logic to reason about past and future states of the objects. The system uses search of possible worlds along with the aid of heuristics and optimizations to find a rather optimum path to a goal of an object in the microworld.
The programming language has two main objectives:
- 1) to be useful as an educational programming tool for children and non-programmers
- The syntax aims to read like natural language and mathematics. It follows the belief that if the statements fairly resemble sentences of a natural language, a normal person can understand the system by reading the program itself. The most valuable learning aspect for children would likely be how they can "model" a specific domain problem as a microworld in the most natural way.
- 2) to offer a higher level of intelligence to everyday programs by bringing traditionally AI techniques such as search, heuristics, and planning to everyday programming
- We can add a higher level of control and readability to everyday programs if the procedures do not run by themselves, but a higher level agent chooses which combination of procedures to run and when. The agent can use the aid of heuristics and optimizations to decide the most relevant set of procedures to run, as well as search for exploring multiple possibilities. The goal driven methodology offers more coherent, readable, and manageable programs by separating the meanings and invariants of problems (i.e. what it is they're trying to accomplish) from procedures and optimizations (i.e. how they accomplish that). The agent can determine when the task is accomplished by asking the meaning part of the program.
Motivation
It seems natural that our knowledge in this world can be broken down to particular microworlds , within each the knowledge is expressed in terms of classes and their properties . Such an indication in John McCarthy 's Advice Taker inspires us to to think knowledge representation should naturally be in terms of classes and their properties, better known as Object Oriented programming in computer science.
SHRDLU was a 1970 program by Terry Winograd at the M.I.T. capable of reasoning about a simple blocks world in the form of natural language. It involved a robot arm and several lego blocks. The user would input a command or question in English, the system understood quite complex English sentences regarding this microworld and was able to reason about it also expressed in English in a quite intelligent way. This was a promising prototype. However, the extent of knowledge of this machine could not go beyond this simple blocks world, and thus was not particularly useful. The problem was that this knowledge was hard-coded in the program, so no one could extend and modify it but the original programmer or someone patient enough to look into its MacLisp source code. Can we have a system that can be taught and be smart about anything. As mentioned above, we can use Prolog to program the knowledge of anything, but implementing SHRDLU just with a set of prolog rules does not make sense. We seem to need a knowledge presentation language easily expressed and understood by humans, able to teach the machine about anything, expect it to reason about it, and allow it to easily grow its knowledge about arbitrary microworlds. This paper will present JOHN knowledge presentation language, which aims to accomplish this task.
Basics
JOHN is a programming language to build and reason about microworld s, potentially allowing for ever expanding knowledge of readily accessible infinite number of microworlds.
Describing a microworld comprises definition of classes and their properties. Qualifications or dynamic properties are defined to assign attribute to objects depended on the status of the microworld. Relative Qualifications are names of relations we attribute between two objects also based on the status of the microworld. Actions that can bring change in the state of the microworld, and rules are defined to indicate the governing rules of such actions. Goals can be defined to indicate a desired state of the microworld for a particular class, and finally heuristics help the class to get closer to their goal states when search trees are too large to be solved entirely.
Lets pretend we like to teach a machine about the game of chess. When teaching a child about the game, one would first introduce the pieces, then the moves, before getting into discussing strategy. Similarly here, we first tell the machine about the classes involved in the chess microworld, which possibly include the board, squares, rows, columns, pieces, and players. A board object possibly has properties such as squares. square object has a piece property to identify the piece currently on it, the piece object may have color and position properties, and so on. Next the machine needs to learn about the specific instances of these objects that we like to deal with. For instance, we need to have two players, one with color property of white, other black. We go on to make instances of all pieces such as the white queen etc, with correct initial positions. By now the machine knows about the start state of the chess world, yet has no idea how to start the game. The following step involves teaching the machine how pieces can move about and what rules restrict the possibilities.
Sample Microworlds
There are a few Sample Programs that demonstrate how JOHN language can be used to store common sense knowledge of arbitrary subjects.