Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-24T07:52:31.809Z Has data issue: false hasContentIssue false
  • English
  • Français

A Review of knowledge-based planning techniques

Published online by Cambridge University Press:  07 July 2009

Austin Tate
Austin Tate
Affiliation:
Knowledge-based Planning Group, Artificial Intelligence Applications Institute, University of Edinburgh
Get access Rights & Permissions [Opens in a new window]

Summary

Planning systems have been an active research topic within Artificial Intelligence for over two decades. There have been a number of techniques developed during that period which still form an essential part of many of today's planners. This paper introduces the techniques, attempts to classify some of the important research themes in AI planning and describes their historical development.

Type
Research Article
Information
The Knowledge Engineering Review , Volume 1 , Issue 2 , June 1984 , pp. 4 - 17
Copyright
Copyright © Cambridge University Press 1984

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

9. PLANNING BIBLIOGRAPHY

Where names of planning systems and other AI softwares are described in the paper, the bibliography is annotated with the name of the system in brackets.

[1]Allen, J.F. and Koomen, J.A. (1983) “Planning Using a Temporal World Model”, IJCAI-83, pp 741–747, Karlsruhe, West Germany. (TIMELOGIC)Google Scholar
[2]Appelt, D.E. (1985) “Planning English Referring Expressions”, Artificial Intelligence, 26, pp 1–33. (KAMP)CrossRefGoogle Scholar
[3]Bell, C.E. and Tate, A. (1985) “Using Temporal Constraints to Restrict Search in a Planner” Proceedings of the Third Workshop of the Alvey IKBS Programme Planning Special Interest Group, Sunningdale, Oxfordshire, UK, April 1985. Available through the Institute of Electrical Engineers, London, UK (O-PLAN)Google Scholar
[4]Bresina, J.L. (1981) “An Interactive Planner that Creates a Structured Annotated Trace of its Operation”, Rutgers University, Computer Science Research Laboratory, Report CBM-TR-123. (PLANX-10)Google Scholar
[5]Corkill, D.D. (1979) “Hierarchical Planning in a Distributed Environment”, IJCAI-79, pp 168–756, Tokyo, Japan.Google Scholar
[6]Corkill, D.D. and Lesser, V.R. (1983) “The Use of Meta-level Control for Coordination in a Distributed Problem Solving Network”, IJCAI-83, pp 748–756, Karlsruhe, West Germany.Google Scholar
[7]Daniel, L. (1983). “Planning and Operations Research”, in “Artificial Intelligence: Tools, Techniques and Applications”, Harper and Row, New York. (NONLIN)Google Scholar
[8]Davis, R. and Smith, R. (1983) “Negotiation as a Metaphor for distributed problem solving”, Artificial Intelligence, 20, pp 63–109.CrossRefGoogle Scholar
[9]Davis, P.R. and Chien, R.T. (1977) “Using and Re-using Partial Plans”, IJCAI-77, Cambridge, Mass., USA.Google Scholar
[10]Dean, T. (1985) “Temporal Reasoning Involving Counterfactuals and Disjunctions”, IJCAI-85, Los Angeles, Calif. (TNMS)Google Scholar
[11]Dershowitz, N. “Synthetic programming”, Artificial Intelligence, 25, pp 323–373.CrossRefGoogle Scholar
[12]Doran, J.E. and Michie, D. (1966) “Experiments with the Graph Traverser Program” Proceedings of the Royal Society, A, pp 235–259. (GRAPH TRAVERSER)CrossRefGoogle Scholar
[13]Doran, J.E. and Trayner, C. (1985) “Distributed planning and Execution — Teamwork 1”, Computer Science Technical Report, University of Essex, UK (TEAMWORK)Google Scholar
[14]Doyle, J. (1979) “A Truth maintenance System” Artificial Intelligence, 12, pp 231–272.CrossRefGoogle Scholar
[15]Drummond, M.E. (1985) “Refining and Extending the Procedural Net” IJCAI-85, Los Angeles, Calif.Google Scholar
[16]Duffay, P. and Latombe, J-C (1983) “An Approach to Automatic Robot Programming Based on Inductive Learning” IMAG, Grenoble, France. (TROPIC)Google Scholar
[17]Erman, L.D., Hayes-Roth, F., Lesser, V.R. and Reddy, D.R. (1980) “The HEARSAY-II speech-understanding system: Integrating Knowledge to Resolve Uncertainty” ACM Computing Surveys, 12, No. 2.CrossRefGoogle Scholar
[18]Fahlman, S.E. (1974) “A Planning System for Robot Construction Tasks” Artificial Intelligence, 5, pp 1–49.CrossRefGoogle Scholar
[19]Faletti, J. (1982) “PANDORA — A Program for Doing Commonsense Reasoning Planning in Complex Situations” AAAI-82, Pittsburgh, Pa., USA, 08, 1982. (PANDORA)Google Scholar
[20]Fikes, R.E. (1970) “REF-ARF: A System for solving problems stated as Procedures” Artificial Intelligence”, 1, pp 27–120.CrossRefGoogle Scholar
[21]Fikes, R.E. (1982) “A Commitment-based Framework for Describing Informal Cooperative Work”, Cognitive Science, 6, pp 331–347.Google Scholar
[22]Fikes, R.E. and Nilsson, N.J. (1971) “STRIPS: a New Approach to the Application of Theorem Proving to Problem Solving”, Artificial Intelligence, 2, pp 189–208. (STRIPS)CrossRefGoogle Scholar
[23]Fikes, R.E., Hart, P.E. and Nilsson, N.J. (1972a) “Learning and Executing Generalised Robot Plans”, Artificial Intelligence, 3. (STRIPS/PLANEX)CrossRefGoogle Scholar
[24]Fikes, R.E., Hart, P.E. and Nilsson, N.J. (1972b) “Some New Directions in Robot Problem Solving”, in “Machine Intelligence 7”, Meltzer, B. and Michie, D., eds., Edinburgh University Press. (STRIPS)Google Scholar
[25]Fox, M.S., Allen, B. and Strohm, G. (1981) “Job Shop Scheduling: an Investigation in Constraint-based Reasoning”, IJCAI-81, Vancouver, British Columbia, Canada, 08 1981. (ISIS.II)Google Scholar
[26]Georgeff, M. (1982) “Communication and Interaction in Multiagent Planning Systems”, AAAI-3.Google Scholar
[27]Georgeff, M. and Lansky, A. (1985) “A Procedural Logic”, IJCAI-85, Los Angeles, Calif., 08 1985.Google Scholar
[28]Green, C.C. (1969) “Theorem Proving by Resolution as basis for Question Answering” in Machine Intelligence, 4, eds. Meltzer, B. and Michie, D., Edinburgh University Press.Google Scholar
[29]Hayes, P.J. (1975) “A Representation for Robot Plans”, Advance papers of IJCAI-75, Tbilisi, USSR.Google Scholar
[30]Hayes-Roth, B. and Hayes-Roth, F. (1979) “A Cognitive Model of Planning”, Cognitive Science, pp 275–310. (OPM)CrossRefGoogle Scholar
[31]Hayes-Roth, B. (1983a) “The Blackboard Architecture: A General Framework for Problem Solving?”, Heuristic Programming Project Report No. HPP-83–30. Stanford University. 05 1983.Google Scholar
[32]Hayes-Roth, B. (1983b) “A Blackboard Model of Control”, Heuristic Programming Project Report No. HPP-83–38. Stanford University. 06 1983. (OPM)Google Scholar
[33]Hendrix, G. (1973) “Modelling Simultaneous Actions and Continuous Processes”, Artificial Intelligence, 4, pp 145–180.CrossRefGoogle Scholar
[34]Kahn, K. and Gorry, G.A. (1977) “Mechanizing Temporal Knowledge” Artificial Intelligence, 9, pp 87–108.CrossRefGoogle Scholar
[35]Konolige, K. (1983) “A Deductive Model of belief”, IJCAI-83, pp 377–381, Karlsruhe, West Germany, 08 1983.Google Scholar
[36]Konolige, K. and Nilsson, N.J. (1980) “Multi-agent Planning Systems”, AAAI-1, pp 38–142, Stanford, Ca., USA.Google Scholar
[37]Kornfeld, W.A. (1979) “ETHER: a Parallel Problem Solving System” IJCAI-79 pp 490–492, Tokyo, Japan.Google Scholar
[38]Lansky, A. (1985) “Behavioral Planning for Multi-Agent Plans”, SRI AI Center Report.Google Scholar
[39]Latombe, J-C. (1976) “Artificial Intelligence in Computer-aided Design — The TROPIC System”, Stanford Research Institute AI Center Technical Note 125, Menlo Park, Ca., USA.Google Scholar
[40]Lermat, D.B. (1975) “BEINGS: Knowledge as Interacting Experts”, IJCAI-75, pp 126–133, Tbilisi, USSR.Google Scholar
[41]London, P. (1977) “A Dependency-based Modelling Mechanism for problem solving”, Dept of Computer Science, University of Maryland, Memo. TR-589.Google Scholar
[42]Luckham, D.C. and Buchanan, J.R. (1974) “Automatic Generation of Programs Containing Conditional Statements”, AISB Summer Conference, University of Sussex, UK, pp 102–126, 07 1974.Google Scholar
[43]Masui, S., McDermott, J. and Sobel, A. (1983) “Decision-making in Time Critical Situations”, IJCAI-83, pp 233–235, Karlsruhe, West Germany, 08, 1983. (AIRPLAN)Google Scholar
[44]McCarthy, J. and Hayes, P.J. (1969) “Some Philosophical Problems from the standpoint of Artificial Intelligence”, in Machine Intelligence 4, ed. Meltzer, B. and Michie, D., Edinburgh University Press.Google Scholar
[45]McDermott, D.V. (1978) “Planning and Acting”, Cognitive Science, 2.CrossRefGoogle Scholar
[46]McDermott, D.V. (1982) “A Temporal Logic for Reasoning about Processes and plans”, Cognitive Science, 6, pp 101–155.Google Scholar
[47]McDermott, D.V. and Doyle, J. (1979) “An Introduction to Nonmonotonic Logic”, IJCAI-79 pp 562–567, Tokyo, Japan.Google Scholar
[48]Mellish, C.S. (1984) “Towards Top-down Generation of Multi-paragraph Text”, Proceedings of the Sixth European Conference on Artificial Intelligence, pp 229, Pisa,Italy, 09 1984.Google Scholar
[49]Moore, R. (1980) “Reasoning about Knowledge and Action”, SRI AI Center Report No. 191.Google Scholar
[50]Mostow, D.J. (1983) “A Problem Solver for Making Advice Operational”, Proc. AAAI 3, pp 179–283Google Scholar
[51]Newell, A. and Simon, H.A. (1963) “GPS: a Program that Simulates Human Thought”, in Feigenbaum, E.A. and Feldman, J. eds Comuters and Thought (McGraw-Hill, New York, 1963). (GPS)Google Scholar
[52]Reiger, C. and London, P. (1977) “Subgoal Protection and Unravelling During Plan Synthesis”, IJCAI-77, Cambridge, Mass., USA.Google Scholar
[53]Rich, C. (1981) “A Formal Representation for Plans in the Programmer's Apprentice”, IJCAI-81 pp 1044–1052, Vancouver, British Columbia, Canada.Google Scholar
[54]Rich, C., Shrobe, H.E. and Waters, R.C. (1979) “Overview of the Programmer's Apprentice”, IJCAI-79, pp 827–828, Tokyo, Japan.Google Scholar
[55]Rosenschein, S.J. (1980) “Synchronisation of Multi-agent Plans”, AAAI-2.Google Scholar
[56]Rosenschein, S.J. (1981) “Plan Synthesis; A Logical Perspective”, IJCAI-81, Vancouver, British Columbia, Canada.Google Scholar
[57]Sacerdoti, E.D. (1973) “Planning in a Hierarchy of Abstraction Spaces”, Advance papers of IJCAI-73, Palo Alto, Ca., USA. (ABSTRIPS)Google Scholar
[58]Sacerdoti, E.D. (1975) “The Non-linear Nature of Plans”, Advance papers of IJCAI-75, Tbilisi, USSR. (NOAH)Google Scholar
[59]Sacerdoti, E.D. (1977) “A Structure for plans and Behaviour”, Elsevier-North Holland. (NOAH)Google Scholar
[60]Sacerdoti, E.D. (1979) “Problem solving Tactics”, IJCAI-79, Tokyo, Japan.CrossRefGoogle Scholar
[61]Sathi, A., Fox, M.S. and Greenberg, M. (1985) “Representation of Activity Knowledge for Project Management” IEEE Special Issue of Transactions on Pattern Analysis and Machine Intelligence, 07, 1985. (CALLISTO)Google Scholar
[62]Schank, R.C. and Abelson, R.P. (1977) “Scripts, Plans, Goals and Understanding”, Lawrence Erlbaum Press, Hillsdale, New Jersey, USA.Google Scholar
[63]Siklossy, L. and Roach, J. (1973) “Proving the Impossible is Impossible is Possible: Disproofs based on Hereditary Partitions”, IJCAI-73, Palo Alto, Calif. (DISPROVER/LAWALY)Google Scholar
[64]Siklossy, L. and Dreussi, J. (1975) “An Efficient Robot Planner that Generates its own Procedures”, IJCAI-73 Palo Alto, Ca., USA. (LAWALY)Google Scholar
[65]Smith, R.G. (1977) “The Contract Net: a Formalism for the Control of Distributed Problem Solving”, IJCAI-77 pp 472 Cambridge, Mass, USA.Google Scholar
[66]Smith, R.G. (1979) “A Framework for Distributed Problem Solving”, IJCAI-79, Tokyo, Japan.Google Scholar
[67]Stallman, R.M. and Sussman, G.J. (1977) “Forward Reasoning and Dependency Directed Backtracking”, Artificial Intelligence, 9, pp 135–196.CrossRefGoogle Scholar
[68]Steele, G.L. and Sussman, G.J. (1978) “Constraints”, MIT AI Lab Memo 502.Google Scholar
[69]Stefik, M.J. (1981a) “Planning with Constraints”, Artificial Intelligence, 16, pp 111–140. (MOLGEN)CrossRefGoogle Scholar
[70]Stefik, M.J. (1981b) “Planning and Meta-planning”, Artificial Intelligence, 16, pp 141–169. (MOLGEN)CrossRefGoogle Scholar
[71]Sussman, G.A. (1973) “A Computational Model of Skill Acquisition”, M.I.T. AI Lab. memo no. AI-TR-297. (HACKER)Google Scholar
[72]Tate, A. (1975) “Interacting Goals and Their Use”, IJCAI-75, pp 215–218, Tbilisi, USSR. (INTERPLAN)Google Scholar
[73]Tate, A. (1976) “Project Planning Using a Hierarchical Non-linear Planner”, Dept. of Artificial Intelligence Report 25, Edinburgh University. (NONLIN)Google Scholar
[74]Tate, A. (1977) “Generating Project Networks”, IJCAI-77, Boston, Ma., USA. (NONLIN)Google Scholar
[75]Tate, A. (1984a) “Planning and Condition Monitoring in a FMS”, International Conference on Flexible Automation Systems”,Institute of Electrical Engineers,London, UKJuly 1984. (NONLIN)Google Scholar
[76]Tate, A. (1984b) “Goal Stucture: Capturing the Intent of Plans”, European Conference on Artificial Intelligence,Pisa,Italy,September 1984. (NONLIN)Google Scholar
[77]Tate, A. and Whiter, A.M. (1984) “Planning with Multiple Resource Constraints and an Application to a Naval Planning Problem”, First Conference on the Applications of Artificial Intelligence,Denver,Colorado, USA.December 1984. (NONLIN)Google Scholar
[78]Vere, S. (1983) “Planning in Time: Windows and Durations for Activities and Goals”, IEEE Trans. on Pattern Analysis and Machine Intelligence, PAMI-5, No. 3, pp. 246–267, 05 1983. (DEVISER)CrossRefGoogle Scholar
[79]Vilain, M.B. (1980) “A System for Reasoning about Time”, AAAI-2.Google Scholar
[80]Waldinger, R. (1975) “Achieving Several Goals Simultaneously”, SRI AI Center Technical Note 107, SRI, Menlo Park, Ca., USA.Google Scholar
[81]Warren, D.H.D. (1974) “WARPLAN: a System for Generating Plans”, Dept. of Computational Logic Memo 76. Artificial Intelligence, Edinburgh University. (WARPLAN)Google Scholar
[82]Warren, D.H.D. (1976) “Generating conditional plans and programs”, Proceedings of the AISB Summer Conference, pp 344–354, University of Edinburgh,UK,July 1976. (WARPLAN-C)Google Scholar
[83]Wilensky, R. (1978) “Understanding Goal-based Stories”, Dept. of Computer Science, Yale Unviersity, Research Report No. 140.Google Scholar
[84]Wilensky, R. (1981a) “Meta-planning: Representing and Using Knowledge about planning in Problem Solving and Natural Language understanding”, Cognitive Science, 5, pp 197–233.Google Scholar
[85]Wilensky, R. (1981b) “A Model for Planning in Complex Situations”, Electronics Research Lab. Memo. No. UCB/ERL M81/49, University of California, Berkeley, Ca., USA.Google Scholar
[86]Wilensky, R. (1983) “Planning and Understanding”, Addison-Wesley, Reading, Mass.Google Scholar
[87]Wilkins, D.E. and Robinson, A.E. (1981) “An Interactive Planning System”, SRI Technical Note 245. (SIPE)Google Scholar
[88]Wilkins, D.E. (1983) “Representation in a Domain-Independent Planner”, IJCAI-83, pp 733–740, Karlsruhe, West Germany. (SIPE)Google Scholar

10. BIBLIOGRAPHY ON SUPPORT LANGUAGE, DATABASES AND BACKGROUND

[89]Barrow, H.G. (1975) “HBASE: a Fast Clean Efficient Data Dase System”, D.A.I. POP-2 library documentatin. Edinburgh University., (HBASE)Google Scholar
[90]Bobrow, D.G. and Stefik, M.J. (1983) “The LOOPS Reference Manual”, Xerox Palo Alto Research Center, Ca. USA. (LOOPS)Google Scholar
[91]Bobrow, D.G. and Winograd, T. (1976) “An Overview of KRL — a Knowledge Representation Language”, Xerox PARC Repport CSL-76–4. Xerox Palo Alto Research Center, Ca. USA. (KEL)Google Scholar
[92]Carnegie Group Inc. “Knowledge Craft”, Commerce Court at station square, Pittsburgh, PA 15219, USA. (Knowledge Craft, SRL+)Google Scholar
[93]Clocksin, W. and Mellish, C. (1981) “Programming in PROLOG”, Springer-Verlag. (PROLOG)Google Scholar
[94]Davies, D.J.M. (1973) “POPLER 1.5 Reference Manual”, D.A.I. Theoretical Psychology Unit Report no.l, Edinburgh university. (POPLER)Google Scholar
[95]Deering, M., Faletti, J. and Wilensky, R. (1981) “PEARL: An Efficient Language for Artificial Intelligence Programming”, IJCAI-81, Vancouver, British Columbia, Canada, Aug, 1981. (PEARL)Google Scholar
[96]Elcock, E.W., Foster, J.M., Gray, P.M.D., McGregor, J.J. and Murrry, A.M. (1971) “ABSET, a programming Language based on sets: Motivation and Examples”, in Meltzer, B. and Michie, D.Machine Intelligence, 6, (Edinburgh University Press). (ABSET)Google Scholar
[97]Fahlman, S.E. (1979) “NETL: a System for Representing Real World Knowledge”, MIT Press, Cambridge, Mass. USA. (NETL)CrossRefGoogle Scholar
[98]Fox, M. (1983) “SRL user's Manual”, Technical Report, Robotics Institute, Carnegie-Mellon University, Pittsburgh, Pa., USA. (SRL)Google Scholar
[99]Hendrix, G. (1975) “Expanding the Utility of Semantic Networks through Partitioning”, IJCAI-75, Tbilisi, USSR.CrossRefGoogle Scholar
[100]Hewitt, C. (1972) “Description and Theoretical Analysis (using Schemata) of PLANNER”, MIT AI Lab. Memo no. MAC-TR-256. (PLANNER)Google Scholar
[101]Hillis, (1981) “The Connection Machine” MIT AI Lab Memo 640.Google Scholar
[102]Inference Corporation (1985), “ART Manual”, 5300 West Century Blvd, 5th Floor, Los Angeles, CA 90045. (ART)Google Scholar
[103]Intellicorp (1985), “KEE System Manual” 707 Laurel Street, Menlo Park, CA 94025–3445. (KEE)Google Scholar
[104]Jiang, Y. J. and Lavington, S.H. (1985) “The Qualified Binary Relationship Model of Information”, University of Manchester, Department of Computer Science, Internal Report IFS/2/85.Google Scholar
[105]McDermott, D.V. and Sussman, G.J. (1972) “The CONNIVER Reference Manual”, M.I.T. AI Lab. Memo no. 259. (CONNIVER)Google Scholar
[106]McGregor, D.R. and Malone, J.R. (1981). “The FACT Database: A System using Generic Associative Networks”, Research Report No. 2/80, Department of Computer Science, Univ. of Strathclyde, UK. (FACT)Google Scholar
[107]Nii, H.P. and Aiello, N. (1979) “AGE (Attempt to Generalize): A Knowledge-based Program for Building Knowledge-based programs”, IJCAI-79, Tokyo, Japan. (AGE)Google Scholar
[108]Rulifson, J.F., Derkson, J.A. and Waldinger, R.J. (1972) “QA4: A Procedural Calculus for Intuitive Reasoing”, Technical Note 73, SRI International Menlo Part, Ca., USA, (QA4)Google Scholar
[109]Sacerdoti, E.D., Fikes, R.E., Reboh, R., Saglowicz, D. and Waldinger, R.J. (1976) “QLISP: a Language for the Interactive Development of Complex Systems”, SRI International, AI Center, (QLISP) Stanford, Ca. USA.CrossRefGoogle Scholar
[110]Sloman, A. (1983) (POPLOG — a Multi-purpose, Multi-language Program Development Environment” Cognitive Studies Programme, University of Sussex, UK. (POPLOG)Google Scholar
[111]Stefik, M.J. (1979) “an Examination of a Frame-structured Representation system”, IJCAI-79, pp 845–852 Tokyo, Japan, (UNITS)Google Scholar
[112]Sussman, G.A. and McDermott, D.V. (1972) “Why conniving is Better than Planning”, MIT AI Lab. Memo 255A. (CONNIVER)Google Scholar

11. RECOMMENDED READING

A good and reasonably up-to-date account of AI planning techniques and systems is given in Charniak and McDermott's Introduction to Artificial Intelligence textbook (114). In particular, chapter 9 and sections of chapters 5 and 7 are relevant.

Somewhat earlier material is provided in Elaine Rich's Artificial Intelligence textbook (116). Nilsson's book on the Principles of Artificial Intelligence (115) provides a uniform treatment of planning techniques available up to the time it was published. There are several useful summaries of early AI planning work in the Handbook of Artificial Intelligence (113) Volume I section II.D and Volume III sections XI.B, XI.Cf and XV.

[113]Barr, A. and Feigenbaum, E.A. (1981) “The Handbook of Artificial Intelligence” William Kaufmann, Los Angeles, Calif.Google Scholar
[114]Charniak, E. and McDermott, D.V. (1985) “Introduction to Artificial Intelligence”, Addison-Wesley.Google Scholar
[115]Nisson, N.J. (1980) “Principles of Artificial Intelligence”, Tioga Press, Palo Alto, Calif.Google Scholar
[116]Rich, E. (1983) “Artificial Intelligence”, McGraw-Hill, New York.Google Scholar