Planner (often seen in publications as "PLANNER" although it is not an acronym) is a
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
designed by
Carl Hewitt
Carl Eddie Hewitt () is an American computer scientist who designed the Planner programming language for automated planningCarl Hewitt''PLANNER: A Language for Proving Theorems in Robots''IJCAI. 1969. and the actor model of concurrent computing, ...
at
MIT
The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the m ...
, and first published in 1969. First, subsets such as Micro-Planner and Pico-Planner were implemented, and then essentially the whole language was implemented as ''Popler'' by Julian Davies at the
University of Edinburgh
The University of Edinburgh ( sco, University o Edinburgh, gd, Oilthigh Dhùn Èideann; abbreviated as ''Edin.'' in post-nominals) is a public research university based in Edinburgh, Scotland. Granted a royal charter by King James VI in 15 ...
in the
POP-2
POP-2 (also referred to as POP2) is a programming language developed around 1970 from the earlier language POP-1 (developed by Robin Popplestone in 1968, originally named COWSEL) by Robin Popplestone and Rod Burstall at the University of Edin ...
programming language.
[Carl Hewitt Middle History of Logic Programming: Resolution, Planner, Prolog and the Japanese Fifth Generation Project ArXiv 2009. ] Derivations such as QA4, Conniver, QLISP and Ether (see
scientific community metaphor
In computer science, the scientific community metaphor is a metaphor used to aid understanding scientific communities. The first publications on the scientific community metaphor in 1981 and 1982 involved the development of a programming langu ...
) were important tools in
artificial intelligence
Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
research in the 1970s, which influenced commercial developments such as
Knowledge Engineering Environment
Knowledge Engineering Environment (KEE) is a Frame language, frame-based development tool for expert systems. It was developed and sold by IntelliCorp (software), IntelliCorp, and first released in 1983. It ran on Lisp machines, and was later port ...
(KEE) and
Automated Reasoning Tool (ART).
Procedural approach versus logical approach
The two major paradigms for constructing semantic software systems were
procedural and
logical
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
. The procedural paradigm was epitomized by
Lisp
A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech.
Types
* A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lisping ...
cCarthy ''et al.'' 1962which featured recursive procedures that operated on list structures.
The logical paradigm was epitomized by uniform proof procedure
resolution-based derivation (proof) finders obinson 1965 According to the logical paradigm it was “cheating” to incorporate procedural knowledge
reen 1969
Procedural embedding of knowledge
Planner was invented for the purposes of the procedural embedding of knowledge
ewitt 1971and was a rejection of the
resolution
Resolution(s) may refer to:
Common meanings
* Resolution (debate), the statement which is debated in policy debate
* Resolution (law), a written motion adopted by a deliberative body
* New Year's resolution, a commitment that an individual mak ...
uniform proof procedure paradigm
obinson 1965 which
#''Converted everything to clausal form.'' Converting all information to
clausal form is problematic because it hides the underlying structure of the information.
#''Then used resolution to attempt to obtain a proof by contradiction by adding the clausal form of the negation of the theorem to be proved.'' Using only resolution as the rule of inference is problematical because it hides the underlying structure of proofs. Also, using proof by contradiction is problematical because the axiomatizations of all practical domains of knowledge are inconsistent in practice.
Planner was a kind of hybrid between the procedural and logical paradigms because it combined programmability with logical reasoning. Planner featured a procedural interpretation of logical sentences where an implication of the form can be procedurally interpreted in the following ways using pattern-directed invocation:
#
Forward chaining
Forward chaining (or forward reasoning) is one of the two main methods of reasoning when using an inference engine and can be described logically as repeated application of ''modus ponens''. Forward chaining is a popular implementation strategy fo ...
(antecedently):
#:
#:
#
Backward chaining
Backward chaining (or backward reasoning) is an inference method described colloquially as working backward from the goal. It is used in automated theorem provers, inference engines, proof assistants, and other artificial intelligence application ...
(consequently)
#:
#:
In this respect, the development of Planner was influenced by
natural deductive logical system
A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system.
A form ...
s (especially the one by
Frederic Fitch
Frederic Brenton Fitch (September 9, 1908, Greenwich, Connecticut – September 18, 1987, New Haven, Connecticut) was an American logician, a Sterling Professor at Yale University.
Education and career
At Yale, Fitch earned his B.A in 1931 and ...
952
Year 952 ( CMLII) was a leap year starting on Thursday (link will display the full calendar) of the Julian calendar.
Events
By place Europe
* Summer – At the Reichstag in Augsburg (assembled by King Otto I), joined by German nob ...
.
Micro-planner implementation
A subset called Micro-Planner was implemented by
Gerry Sussman,
Eugene Charniak
Eugene Charniak is a professor of computer Science and cognitive Science at Brown University. He holds an A.B. in Physics from the University of Chicago and a Ph.D. from M.I.T. in Computer Science. His research has always been in the area of l ...
and
Terry Winograd
Terry Allen Winograd (born February 24, 1946) is an American professor of computer science at Stanford University, and co-director of the Stanford Human–Computer Interaction Group. He is known within the philosophy of mind and artificial intell ...
ussman, Charniak, and Winograd 1971and was used in Winograd's natural-language understanding program
SHRDLU
SHRDLU was an early natural-language understanding computer program, developed by Terry Winograd at MIT in 1968–1970. In the program, the user carries on a conversation with the computer, moving objects, naming collections and querying the st ...
, Eugene Charniak's story understanding work, Thorne McCarty's work on legal reasoning, and some other projects. This generated a great deal of excitement in the field of AI. It also generated controversy because it proposed an alternative to the logic approach that had been one of the mainstay paradigms for AI.
At
SRI International
SRI International (SRI) is an American nonprofit scientific research institute and organization headquartered in Menlo Park, California. The trustees of Stanford University established SRI in 1946 as a center of innovation to support economic d ...
, Jeff Rulifson, Jan Derksen, and
Richard Waldinger
Richard Jay Waldinger is a computer science researcher at SRI International's Artificial Intelligence Center (where he has worked since 1969) whose interests focus on the application of automated deductive reasoning to problems in software enginee ...
developed
QA4 which built on the constructs in Planner and introduced a context mechanism to provide modularity for expressions in the database. Earl Sacerdoti and Rene Reboh developed QLISP, an extension of QA4 embedded in
INTERLISP
Interlisp (also seen with a variety of capitalizations) is a programming environment built around a version of the programming language Lisp. Interlisp development began in 1966 at Bolt, Beranek and Newman (renamed BBN Technologies) in Cambridge, ...
, providing Planner-like reasoning embedded in a procedural language and developed in its rich programming environment. QLISP was used by
Richard Waldinger
Richard Jay Waldinger is a computer science researcher at SRI International's Artificial Intelligence Center (where he has worked since 1969) whose interests focus on the application of automated deductive reasoning to problems in software enginee ...
and Karl Levitt for program verification, by Earl Sacerdoti for planning and execution monitoring, by
Jean-Claude Latombe
Jean-Claude Latombe (born May 14, 1947) is a French- American roboticist and the Kumagai Professor Emeritus in the School of Engineering at Stanford University. Latombe is a researcher in robot motion planning, and has authored one of the most ...
for computer-aided design, by Richard Fikes for deductive retrieval, and by Steven Coles for an early expert system that guided use of an econometric model.
Computers were expensive. They had only a single slow processor and their memories were very small by comparison with today. So Planner adopted some efficiency expedients including the following:
*Backtracking
olomb and Baumert 1965was adopted to economize on the use of time and storage by working on and storing only one possibility at a time in exploring alternatives.
*A unique name assumption was adopted to save space and time by assuming that different names referred to different objects. For example, names like Peking (previous PRC capital name) and Beijing (current PRC capital transliteration) were assumed to refer to different objects.
*A
closed-world assumption The closed-world assumption (CWA), in a formal system of logic used for knowledge representation, is the presumption that a statement that is true is also known to be true. Therefore, conversely, what is not currently known to be true, is false. Th ...
could be implemented by conditionally testing whether an attempt to prove a goal exhaustively failed. Later this capability was given the misleading name "
negation as failure Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive \mathrm~p (i.e. that ~p is assumed not to hold) from failure to derive ~p. Note that \mathrm ~p can be different from the statement \neg p ...
" because for a goal it was possible to say: "if attempting to achieve exhaustively fails then assert ."
The genesis of Prolog
Gerry Sussman,
Eugene Charniak
Eugene Charniak is a professor of computer Science and cognitive Science at Brown University. He holds an A.B. in Physics from the University of Chicago and a Ph.D. from M.I.T. in Computer Science. His research has always been in the area of l ...
,
Seymour Papert
Seymour Aubrey Papert (; 29 February 1928 – 31 July 2016) was a South African-born American mathematician, computer scientist, and educator, who spent most of his career teaching and researching at MIT. He was one of the pioneers of artificial ...
and
Terry Winograd
Terry Allen Winograd (born February 24, 1946) is an American professor of computer science at Stanford University, and co-director of the Stanford Human–Computer Interaction Group. He is known within the philosophy of mind and artificial intell ...
visited the University of
Edinburgh
Edinburgh ( ; gd, Dùn Èideann ) is the capital city of Scotland and one of its 32 Council areas of Scotland, council areas. Historically part of the county of Midlothian (interchangeably Edinburghshire before 1921), it is located in Lothian ...
in 1971, spreading the news about Micro-Planner and
SHRDLU
SHRDLU was an early natural-language understanding computer program, developed by Terry Winograd at MIT in 1968–1970. In the program, the user carries on a conversation with the computer, moving objects, naming collections and querying the st ...
and casting doubt on the resolution uniform proof procedure approach that had been the mainstay of the Edinburgh Logicists. At the University of Edinburgh, Bruce Anderson implemented a subset of Micro-Planner called PICO-PLANNER (Anderson 1972) and Julian Davies (1973) implemented essentially all of Planner.
According to Donald MacKenzie,
Pat Hayes
Patrick John Hayes FAAAI (born 21 August 1944) is a British computer scientist who lives and works in the United States. , he is a Senior Research Scientist at the Institute for Human and Machine Cognition in Pensacola, Florida.
Education
Hay ...
recalled the impact of a visit from Papert to Edinburgh, which had become the "heart of
artificial intelligence
Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
's Logicland," according to Papert's MIT colleague, Carl Hewitt. Papert eloquently voiced his critique of the resolution approach dominant at Edinburgh "…and at least one person upped sticks and left because of Papert."
acKenzie 2001 p 82.
The above developments generated tension among the Logicists at Edinburgh. These tensions were exacerbated when the UK Science Research Council commissioned Sir James Lighthill to write a report on the AI research situation in the UK. The
resulting report James_Lighthill">Lighthill_1973;_John_McCarthy_(computer_scientist).html" ;"title="James_Lighthill.html" ;"title="/nowiki> Lighthill_1973;_John_McCarthy_(computer_scientist)">McCarthy_1973.html" ;"title="James Lighthill">Lighthill 1973; John McCarthy (computer scientist)">McCarthy 1973">James Lighthill">Lighthill 1973; John McCarthy (computer scientist)">McCarthy 1973was highly critical although SHRDLU
SHRDLU was an early natural-language understanding computer program, developed by Terry Winograd at MIT in 1968–1970. In the program, the user carries on a conversation with the computer, moving objects, naming collections and querying the st ...
was favorably mentioned.
Pat Hayes visited Stanford where he learned about Planner. When he returned to Edinburgh, he tried to influence his friend Bob Kowalski to take Planner into account in their joint work on automated theorem proving. "Resolution theorem-proving was demoted from a hot topic to a relic of the misguided past. Bob Kowalski
Robert Anthony Kowalski (born 15 May 1941) is an American-British logician and computer scientist, whose research is concerned with developing both human-oriented models of computing and computational models of human thinking. He has spent mo ...
doggedly stuck to his faith in the potential of resolution theorem proving. He carefully studied Planner.” according to Bruynooghe, Pereira, Siekmann, and van Emden 004 Kowalski 988states "I can recall trying to convince Hewitt that Planner was similar to SL-resolution." But Planner was invented for the purposes of the procedural embedding of knowledge and was a rejection of the resolution uniform proof procedure paradigm. Colmerauer and Roussel recalled their reaction to learning about Planner in the following way:
"While attending an IJCAI convention in September ‘71 with Jean Trudel, we met Robert Kowalski
Robert Anthony Kowalski (born 15 May 1941) is an American-British logician and computer scientist, whose research is concerned with developing both human-oriented models of computing and computational models of human thinking. He has spent mo ...
again and heard a lecture by Terry Winograd on natural language processing. The fact that he did not use a unified formalism left us puzzled. It was at this time that we learned of the existence of Carl Hewitt’s programming language, Planner ewitt, 1969 The lack of formalization of this language, our ignorance of Lisp and, above all, the fact that we were absolutely devoted to logic meant that this work had little influence on our later research." Alain_Colmerauer">Colmerauer_and_Roussel_1996.html" ;"title="Alain_Colmerauer.html" ;"title="/nowiki> Colmerauer_and_Roussel_1996">Alain_Colmerauer.html"_;"title="/nowiki>Alain_Colmerauer">Colmerauer_and_Roussel_1996
In_the_fall_of_1972,_Philippe_Roussel.html" ;"title="Alain Colmerauer">Colmerauer and Roussel 1996">Alain_Colmerauer.html" ;"title="/nowiki>Alain Colmerauer">Colmerauer and Roussel 1996
In the fall of 1972, Philippe Roussel">Alain Colmerauer">Colmerauer and Roussel 1996">Alain_Colmerauer.html" ;"title="/nowiki>Alain Colmerauer">Colmerauer and Roussel 1996
In the fall of 1972, Philippe Roussel implemented a language called Prolog (an abbreviation for PROgrammation en LOGique – French for "programming in logic"). Prolog programs are generically of the following form (which is a special case of the backward-chaining in Planner):
:
Prolog duplicated the following aspects of Micro-Planner:
*Pattern directed invocation of procedures from goals (''i.e.'' backward chaining
Backward chaining (or backward reasoning) is an inference method described colloquially as working backward from the goal. It is used in automated theorem provers, inference engines, proof assistants, and other artificial intelligence application ...
)
*An indexed data base of pattern-directed procedures and ground sentences.
*Giving up on the completeness paradigm that had characterized previous work on theorem proving and replacing it with the programming language procedural embedding of knowledge paradigm.
Prolog also duplicated the following capabilities of Micro-Planner which were pragmatically useful for the computers of the era because they saved space and time:
*Backtracking control structure
*Unique Name Assumption by which different names are assumed to refer to distinct entities, ''e.g.'', Peking and Beijing are assumed to be different.
*Reification of Failure. The way that Planner established that something was provable was to successfully attempt it as a goal and the way that it establish that something was unprovable was to attempt it as a goal and explicitly fail. Of course the other possibility is that the attempt to prove the goal runs forever and never returns any value. Planner also had a construct which succeeded if failed, which gave rise to the “Negation as Failure Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive \mathrm~p (i.e. that ~p is assumed not to hold) from failure to derive ~p. Note that \mathrm ~p can be different from the statement \neg p ...
” terminology in Planner.
Use of the Unique Name Assumption and Negation as Failure became more questionable when attention turned to Open Systems ewitt and de Jong 1983, Hewitt 1985, Hewitt and Inman 1991
The following capabilities of Micro-Planner were omitted from Prolog:
*Pattern-directed invocation of procedural plans from assertions (''i.e''., forward chaining
Forward chaining (or forward reasoning) is one of the two main methods of reasoning when using an inference engine and can be described logically as repeated application of ''modus ponens''. Forward chaining is a popular implementation strategy fo ...
)
*Logical negation, ''e.g.'', .
Prolog did not include negation in part because it raises implementation issues. Consider for example if negation were included in the following Prolog program:
:
:
The above program would be unable to prove even though it follows by the rules of mathematical logic. This is an illustration of the fact that Prolog (like Planner) is intended to be a programming language and so does not (by itself) prove many of the logical consequence
Logical consequence (also entailment) is a fundamental concept in logic, which describes the relationship between statements that hold true when one statement logically ''follows from'' one or more statements. A valid logical argument is on ...
s that follow from a declarative reading of its programs.
The work on Prolog was valuable in that it was much simpler than Planner. However, as the need arose for greater expressive power in the language, Prolog began to include many of the capabilities of Planner that were left out of the original version of Prolog.
References
Bibliography
*Bruce Anderson. Documentation for LIB PICO-PLANNER School of Artificial Intelligence, Edinburgh University. 1972
*Bruce Baumgart. Micro-Planner Alternate Reference Manual Stanford AI Lab Operating Note No. 67, April 1972.
* .
* .
* .
* .
*
* .
*Carl Hewitt. "The Challenge of Open Systems" Byte Magazine. April 1985
*Carl Hewitt and Jeff Inman. "DAI Betwixt and Between: From ‘Intelligent Agents’ to Open Systems Science" IEEE Transactions on Systems, Man, and Cybernetics. Nov/Dec 1991.
*Carl Hewitt and Gul Agha. "Guarded Horn clause languages: are they deductive and Logical?" International Conference on Fifth Generation Computer Systems, Ohmsha 1988. Tokyo. Also in ''Artificial Intelligence at MIT'', Vol. 2. MIT Press 1991.
* .
*William Kornfeld and Carl Hewitt
The Scientific Community Metaphor
MIT AI Memo 641. January 1981.
*Bill Kornfeld and Carl Hewitt. "The Scientific Community Metaphor" IEEE Transactions on Systems, Man, and Cybernetics. January 1981.
*Bill Kornfeld. "The Use of Parallelism to Implement a Heuristic Search" IJCAI 1981.
*Bill Kornfeld. "Parallelism in Problem Solving" MIT EECS Doctoral Dissertation. August 1981.
*Bill Kornfeld. "Combinatorially Implosive Algorithms" CACM. 1982
*Robert Kowalski
"The Limitations of Logic"
Proceedings of the 1986 ACM fourteenth annual conference on Computer science.
*Robert Kowalski
"The Early Years of Logic Programming"
CACM January 1988.
* .
* .
* .
*Gerry Sussman and Terry Winograd
Micro-planner Reference Manual
AI Memo No, 203, MIT Project MAC, July 1970.
*Terry Winograd
Procedures as a Representation for Data in a Computer Program for Understanding Natural Language
MIT AI TR-235. January 1971.
*Gerry Sussman, Terry Winograd and Eugene Charniak
Micro-Planner Reference Manual (Update)
AI Memo 203A, MIT AI Lab, December 1971.
*Carl Hewitt
Description and Theoretical Analysis (Using Schemata) of Planner, A Language for Proving Theorems and Manipulating Models in a Robot
AI Memo No. 251, MIT Project MAC, April 1972.
*Eugene Charniak.
Toward a Model of Children's Story Comprehension
MIT AI TR-266. December 1972.
*Julian Davies. Popler 1.6 Reference Manual University of Edinburgh, TPU Report No. 1, May 1973.
*Jeff Rulifson, Jan Derksen, and Richard Waldinger. "QA4, A Procedural Calculus for Intuitive Reasoning" SRI AI Center Technical Note 73, November 1973.
*Scott Fahlman. "A Planning System for Robot Construction Tasks" MIT AI TR-283. June 1973
*James Lighthill. "Artificial Intelligence: A General Survey Artificial Intelligence: a paper symposium." UK Science Research Council. 1973.
*John McCarthy. "Review of ‘Artificial Intelligence: A General Survey Artificial Intelligence: a paper symposium." UK Science Research Council. 1973.
*Robert Kowalsk
"Predicate Logic as Programming Language"
Memo 70, Department of Artificial Intelligence, Edinburgh University. 1973
*Pat Hayes. Computation and Deduction Mathematical Foundations of Computer Science: Proceedings of Symposium and Summer School, Štrbské Pleso, High Tatras, Czechoslovakia, September 3–8, 1973.
*Carl Hewitt, Peter Bishop and Richard Steiger. "A Universal Modular Actor Formalism for Artificial Intelligence" IJCAI 1973.
*L. Thorne McCarty. "Reflections on TAXMAN: An Experiment on Artificial Intelligence and Legal Reasoning" Harvard Law Review. Vol. 90, No. 5, March 1977
*Drew McDermott and Gerry Sussman
The Conniver Reference Manual
MIT AI Memo 259A. January 1974.
*Earl Sacerdoti, et al., "QLISP A Language for the Interactive Development of Complex Systems" AFIPS. 1976
* .
* .
External links
*{{webarchive , url=https://web.archive.org/web/20030727192519/http://www.lim.univ-mrs.fr/~colmer/ArchivesPublications/HistoireProlog/19november92.pdf , archive-url=https://web.archive.org/web/20030727192519/http://www.lim.univ-mrs.fr/~colmer/ArchivesPublications/HistoireProlog/19november92.pdf , archive-date=2003-07-27 , url-status=live , date=July 27, 2003 , title=Alain Colmerauer's and Philippe Roussel's 1992 account of the birth of Prolog
History of artificial intelligence
Automated planning and scheduling
Logic programming languages
Robot programming languages
Theorem proving software systems
Programming languages created in 1969