From: nakashim@etl.go.jp (Hideyuki Nakashima)
Subject: Summary: Re: class of planners
Organization: Electrotechnical Laboratory
Date: Fri, 14 Aug 1992 02:43:05 GMT

I asked about classes of planners in comp.ai and fj.ai.
Here is a summary of responses I got.

(1) Do not confuse class of planners with class of problems.

From: Robert Baron <robert@cs.ualberta.ca>:
> The classifications as linear/nonlinear hierarchical/nonhierarchical do
> not refer to a type of problem but to how a planner operates; in order
> words they are not classes of planning problems but classes of planners.

> A correctly built (i.e. complete) linear and nonhierarchical planner can
> solve all of the types of problems that you mentionned above (and below).

(2) There are few work on classifying problems.

(3) References

Manuela M. Veloso
"Nonlinear Problme Solving Using Intelligent Casual-Commitment"
CMU-CS-89-210

Naresh Gupta and Dana S. Nau
"Complexity Results for Blocks-World Planning"
AAAI-91, pp.629-633

James Hendler, Austin Tate, and Mark Drummond. 1990.
AI Planning: Systems and Techniques.
AI Magazine (Summer);

David E. Wilkins. 1988.
Pratical Planning -- Extending the Classical AI Planning Paradigm --
Morgan Kaufmann Publishers Inc;

James Allen, James Hendler, and Austin Tate. 1990.
Readings in Planning.
Morgan Kaufmann Publishers Inc.

From: Robert Baron <robert@cs.ualberta.ca>:

    [PLANNER - SHORT SUMMARY]
    Bobrow, D., Raphael, B., "New Programming Languages for Artificial
    Intelligence Research," Association for Computing Machinery Computing
    Surveys, 6, 1974, 153-174.

    [PLANNER]
    Rulifson, J. F., Derksen, J. A., Waldinger, R. J., QA4: A Procedural
    Calculus for Intuitive Reasoning. Technical Note 73, SRI Intern., 1972.

    [PLANNER]
    Hewitt, C., Description and Theoretical Analysis (Using Schemata) of
    PLANNER: A Language for Proving Theorems and Manipulating Models in
    Robots. Report AI-TR-258, Massachusetts Institute of Technology, 1971.

    [PLANNER - MICRO-PLANNER]
    Sussman, G., Winograd, T., Charniak, E., Micro-Planner Reference
    Manual. Memo 203a, Massachusetts Institute of Technology, 1970.

    [PLANNER]
    Hewitt, C., "PLANNER: A Language for Proving Theorems in Robots,"
    Proc. of the First Intern. Joint Conf. on Artificial Intelligence,
    Morgan Kaufmann, 1969, 295-301.

    --------------

    [PLANNING - SURVEY]
    Georgeff, M. P., "Planning," in Annual Review of Computer Science,
    Annual Reviews Inc., 1987, 359-400.

    [PLANNING - LECTURE NOTES]
    Schubert, L. K., "Planning," Personal Communication, 1988.

    [PLANNING - SURVEY]
    Vere, S. A., "Planning," in Encyclopedia of Artificial Intelligence,
    Wiley, 1986, 748-758.

    [PLANNING - EXECUTING]
    "Interleaving Plan formation and execution", Proc. of the Fifth
    National Conf. on Artificial Intelligence, Morgan Kaufmann, 1986,
    58-64.

    [PLANNING - EXECUTING]
    Chien, R. T., Weissman, S., "Planning and Execution in Incompletely
    Specified Environment," Proc. of the Fourth Intern. Joint Conf. on
    Artificial Intelligence, Morgan Kaufmann, 1975, 169-174.

    [PLANNING - PLAN REPRESENTATION]
    Tenenberg, J., "Planning with abstraction," Proc. of the Fifth National
    Conf. on Artificial Intelligence, Morgan Kaufmann, 1986, 76-80.

    [PLANNING - PLAN REPRESENTATION]
    Hayes, P. J., "A Representation for Robot Plans," Proc. of the Fourth
    Intern. Joint Conf. on Artificial Intelligence, Morgan Kaufmann, 1975,
    181-188.

    [PLANNING - EXPERT SYSTEM]
    Crowley, J. L., "Coordination of Action and Perception in a
    Surveillance Robot," Proc. of the Tenth Intern. Joint Conf. on
    Artificial Intelligence, Morgan Kaufmann, 1987, 793-796.

    [PLANNING - EXPERT SYSTEM]
    Crowley, J. L., Coordination of Action and Perception in a Surveillance
    Robot," IEEE Expert, Winter, 1987, 32-43.

    [PLANNING - REPLANNING]
    Alterman, R., "An Adaptive Planner," Proc. of the Fifth National Conf.
    on Artificial Intelligence, Morgan Kaufmann, 1986, 65-69.

    [PLANNING - THEORY]
    Morgenstern, L., "A First Order Theory of Planning, Knowledge, and
    Action," Proc. of the Conf. on Theoretical Aspects of Reasoning about
    Knowledge, Morgan Kaufmann, 1986, 99-114.

    [PLANNING - WORKSHOP REPORT]
    William, S., (ed.), "DARPA Santa Cruz Workshop on Planning," AI
    Magazine, 9(2), 1988, 115-130.

    --------------

    [ROSENSCHEIN - EPISTEMIC MACHINES]
    Rosenschein, S. J., Kaebling, L. P., The Synthesis of Digital Machines
    with Provable Epistemic Properties. Technical Note 412, SRI Intern.,
    1987.

    [ROSENSCHEIN - EPISTEMIC MACHINES]
    Rosenschein, S. J., Kaelbling, L. P., "The Synthesis of Machines with
    Provably Epistemic Properties," Proc. of the Conf. on Theoretical
    Aspects of Reasoning about Knowledge, Morgan Kaufmann, 1986, 83-98.

    [ROSENSCHEIN - EPISTEMIC MACHINES]
    Rosenschein, S. J., "Formal Theories of Knowledge in AI and Robotics,"
    Proc. Workshop on Intelligent Robots: Achievements and Issues, 1984,
    237-252. / * New Generation Computing, 3(4), 1985, 345-357.

    [ROSENSCHEIN - DYNAMIC LOGIC]
    Rosenschein, S. J., "Plan Synthesis: A Logical Perspective," Proc.
    of the Seventh Intern. Joint Conf. on Artificial Intelligence, Morgan
    Kaufmann, 1981, 331-337.

    --------------

    Doyle, R. J., Atkinson, D. J., Doshi, R. S., "Generating Perception
    Requests and Expectations to Verify the Execution of Plans," Proc. of
    the Fifth National Conf. on Artificial Intelligence, Morgan Kaufmann,
    1986, 81-88.
      {Take the approach plan constructor/plan executor.  Use a STRIPS-like
      planner to construct a plan for a goal.  Then, the plan is augmented
      with perception requests to verify the preconditions and postcondi-
      tions of actions.  So actions act with no (or little) feedback.  As
      presented there is no possibility of continuous monitoring as can be
      done by action routines with SHAKEY.  Intend to extend their verifi-
      cation language to incorporate continuous monitoring.  Never tested
      on a real-world robot.  Food for thought, especially the extension
      they propose for the verification language.}

    --------------

    [ROBOT - JASON]
    Coles, S. L., Robb, A. M., Sinclair, P. L., Smith, M. H., Sobek, R. R.,
    "Decision Analysis for an Experimental Robot with Sensors," Proc. of
    the Fourth Intern. Joint Conf. on Artificial Intelligence, Morgan
    Kaufmann, 1975, 749-757.

    --------------

    [PLANNING - ABSTRIPS]
    Sacerdoti, E. D., "Planning in a Hierarchy of Abstraction Spaces,"
    Proc. of the Third Intern. Conf. on Artificial Intelligence, Morgan
    Kaufmann, 1973, 412-422.

    [PLANNING - ABSTRIPS]
    Sacerdoti, E. D., "Planning in a Hierarchy of Abstraction Spaces,"
    Artificial Intelligence, 5, 1974, 115-135.

    --------------

    [PLANNING - CONDITIONAL]
    Manna, Z., Waldinger, R., "A Theory of Plans," in Reasoning about
    Actions and Plans, M. Georgeff and A. Lansky (eds.), Morgan Kaufmann,
    1987, 11-45.

    --------------

    [PLANNING - CONJUNCTIVE GOALS]
    Waldinger, R. J., "Achieving Several Goals Simultaneously," in Machine
    Intelligence 8, E. Elcock, and D. Michie (eds.), Ellis Horwood, 1977,
    94-136.

    --------------

    [PLANNING - DECISION THEORY - NONMONOTICS]
    Langlotz, C., Shortliffe, E. H., "Logical and Decision-Theoretic
    Methods for Planning under Uncertainty," AI Magazine, 10(1), 1989,
    39-47.

    [PLANNING - DECISION THEORY]
    Feldman, J. A., Sproull, R. F., "Decision Theory and Artificial
    Intelligence II: The Hungry Monkey," Cognitive Science 1, 1977,
    158-192.

    [PLANNING - DECISION THEORY]
    Coles, S. L., Robb, A. M., Sinclair, P. L., Smith, M. H., Sobek, R. R.,
    "Decision Analysis for an Experimental Robot with Sensors," Proc. of
    the Fourth Intern. Joint Conf. on Artificial Intelligence, Morgan
    Kaufmann, 1975, 749-757.

    [PLANNING - DECISION THEORY]
    Johnson, D. T., "Decision Theory and Automatic Planning," Tech. Rep.
    TR77-9, Dept. of Computing Science, Univ. of Alberta, Edmomton, 1977.

    [PLANNING - DECISION THEORY]
    Johnson, D. T., Schubert, L. K., "A Planning Control Strategy that
    Allows for the Cost of Planning," Proc. of the Sixth European Meeting
    on Cybernetics and Systems Research, 1982.

    --------------

    [PLANNING - DEVISER]
    Vere, S. A., "Splicing Plans to Achieve Misordered Goals," Proc. of
    the Ninth Intern. Joint Conf. on Artificial Intelligence, Morgan
    Kaufmann, 1985, 1016-1021.

    [PLANNING - DEVISER]
    Vere, S. A., "Planning in Time: Windows and Duration for Activities
    and Goals," IEEE Trans. on Pattern Analysis and Machine Intelligence
    5, 1983, 246-267.

    --------------

    [PLANNING - ELMER]
    McCalla, G. I., Schneider, P. F., "Planning in a Dynamic Microworld,"
    Proc. of the Third Biennial Conf. of the Canadian Society for
    Computational Studies of Intelligence, CIPS National Office, 1980,
    248-255.

    [PLANNING - ELMER]
    McCalla, G. I., Schneider, P. F., "The Execution of Plans in an
    Independent Dynamic Microworld," Proc. of the Sixth Intern. Joint Conf.
    on Artificial Intelligence, Morgan Kaufmann, 1979, 553-555.

    [PLANNING - ELMER]
    McCalla, G. I., Reid, L., Schneider, P. F., "Plan Creation, Plan
    Execution and Knowledge Acquisition in a Dynamic Microworld," Int. J.
    of Man-Machine Studies, 16, 1982, 89-112.

    --------------

    [PLANNING - GREEN]
    Kowalski, R., Logic for Problem Solving. North-Holland, 1979.

    [PLANNING - GREEN]
    Green, C., "Application of Theorem Proving to Problem Solving," Proc.
    of the First Intern. Joint Conf. on Artificial Intelligence, Morgan
    Kaufmann, 1969, 219-239.

    --------------

    [PLANNING - GRIPE]
    Doyle, R. J., Atkinson, D. J., Doshi, R. S., "Generating Perception
    Requests and Expectations to Verify the Execution of Plans," Proc. of
    the Fifth National Conf. on Artificial Intelligence, Morgan Kaufmann,
    1986, 81-88.

    --------------

    [PLANNING - HACKER]
    Sussman, G. J., A Computational Model of Skill Acquisition.
    North-Holland, 1975.

    --------------

    [PLANNING - INTERPLAN]
    Tate, A., "Interacting Goals and Their Use," Proc. of the Fourth
    Intern. Joint Conf. on Artificial Intelligence, Morgan Kaufmann, 1975,
    215-218.

    --------------

    [PLANNING - LAWALY]
    Siklossy, L., Dreussi, J., "An Efficient Robot Planner which Generates
    its own Procedures," Proc. of the Third Intern. Joint Conf. on
    Artificial Intelligence, Morgan Kaufmann, 1973, 423-430.

    --------------

    [PLANNING - MOLGEN]
    Stefik, M., "Planning with Constraints (MOLGEN: Part 1)," Artificial
    Intelligence, 15, 1981, 111-140.

    [PLANNING - MOLGEN]
    Stefik, M., "Planning and Meta-Planning (MOLGEN: Part 2)," Artificial
    Intelligence, 16, 1981, 141-170.

    --------------

    [PLANNING - NASL]
    McDermott, D., "Planning and acting," Cognitive Science, 2, 1978,
    71-109.

    --------------

    [PLANNING - NOAH]
    Sacerdoti, E. D., A Structure for Plans and Behavior. Elsevier, 1977.

    [PLANNING - NOAH]
    Sacerdoti, E. D., The Nonlinear Nature of Plans," Proc. of the Fourth
    Joint Conf. on Artificial Intelligence, Morgan Kaufmann, 1975, 206-214.

    --------------

    [PLANNING - NONLIN - POSSIBLY RELATED]
    Tate, A., "Goal Structure," Proc. of the Sixth European Conf. on
    Artificial Intelligence, 1984, 273-276.

    [PLANNING - NONLIN - RESOURCE CONSUMPTION]
    Tate, A., Whiter, A. M., "Planning with Multiple Resource Constraints
    and an Application to a Naval Planning Problem," Proc. of the First
    Conf. on Applications of Artificial Intelligence, 1984, 410-415.

    [PLANNING - NONLIN]
    Tate, A., "Generating Project Networks," Proc. of the Fifth Intern.
    Joint Conf. on Artificial Intelligence, Morgan Kaufmann, 1977, 888-893.

    [PLANNING - NONLIN]
    Tate, A., Project Planning Using a Hierarchic Non-Linear Planner.
    Research Report 25, Univ. of Edinburgh, 1976.

    --------------

    [PLANNING - PRS]
    Georgeff, M. P., Lansky, A. L., "Reactive Reasoning and Planning,"
    Proc. of the Sixth National Conf. on Artificial Intelligence, Morgan
    Kaufmann, 1987, 677-682.

    [PLANNING - PRS]
    Georgeff, M. P., Lansky, A. L., "Procedural Knowledge," Proc. of the
    IEEE, 74(10), 1986, 1383-1398.

    [PLANNING - PRS]
    Georgeff, M. P., Lansky, A. L., Bessiere, P., "A Procedural Logic,"
    Proc. of the Ninth Intern. Joint Conf. on Artificial Intelligence,
    Morgan Kaufmann, 1985.

    [PLANNING - PRS]
    Georgeff, M. P., Bonollo, U., "Procedural Expert Systems," Proc. of the
    Eighth Intern. Joint Conf. on Artificial Intelligence, Morgan Kaufmann,
    1983, 151.

    --------------

    [PLANNING - RAP]
    Firby, J. R., "An Investigation into Reactive Planning in Complex
    Domains," Proc. of the Sixth National Conf. on Artificial
    Intelligence, Morgan Kaufmann, 1987, 202-206.

    --------------

    [PLANNING - SIPE - POSSIBLY RELATED]
    Wilkins, D. E., "Hierarchical Planning: Definition and Implementation,"
    in Advances in Artificial Intelligence II, B. du Boulay, D. Hogg and L.
    Steels (eds.), Elsevier, 1987, 659-671.

    [PLANNING - SIPE]
    Wilkins, D. E., "Recovering from Execution Errors in SIPE,"
    Computational Intelligence, 1, 1985, 33-45.
      {Takes the approach plan constructor/plan executor.  The paper deals
      with the replanning system.  Was never used to control a real-world
      robot.  Provides a fair analysis of the modifications that need be
      made to a hierarchical plan when the state of the world turns out to
      be not as expected.  The big assumption is that the real state of the
      world is known after executing actions -- intends to develop such a
      system.  In the spirit of SIPE -- ad hoc methods to get efficiency.}

    [PLANNING - SIPE]
    Wilkins, D. E., "Domain-Independent Planning: Representation and Plan
    Generation," Artificial Intelligence, 22, 1984, 269-301.

    [PLANNING - SIPE]
    Wilkins, D. E., "Representation in a Domain-Independent Planner,"
    Proc. of the Eighth Intern. Joint Conf. on Artificial Intelligence,
    Morgan Kaufmann, 1983, 733-740.

    --------------

    [PLANNING - STRIPS]
    Lifschitz, V., "On the Semantics of STRIPS," in Reasoning about Actions
    and Plans, M. Georgeff and A. Lansky (eds.), Morgan Kaufmann, 1986,
    1-9.

    [PLANNING - STRIPS - SHAKEY]
    Nilsson, N. J., Shakey the Robot. Technical Report 323, SRI Intern.,
    1984.

    [PLANNING - STRIPS]
    Nilsson, N. J., Principle of Artificial Intelligence. Morgan Kaufmann,
    1980.

    [PLANNING - STRIPS - MACROP - PLANEX]
    Fikes, R. E., Hart, P. E., Nilsson, N. J., "Learning and Executing
    Generalized Robot Plans," Artificial Intelligence, 3, 1972, 251-288.

    [PLANNING - STRIPS]
    Fikes, R. E. and Nilsson, N. J., "STRIPS: A New Approach to the
    Application of Theorem Proving to Problem Solving," Artificial
    Intelligence, 2, 1971, 189-208.

    [PLANNING - STRIPS - PLANEX]
    Fikes, R. E., "Monitored Execution of Robot Plan Produced by STRIPS,"
    Proc. IFIP Congress 71, 1971.

    [PLANNING - STRIPS - PLANEX - RELATED]
    Munson, J. H., "Robot Planning, Execution, and Monitoring in an
    Uncertain Environment," Proc. of the Second Intern. Joint Conf. on
    Artificial Intelligence, Morgan Kaufmann, 1971, 338-349.

    --------------

    [PLANNING - TEMPORAL]
    Pelavin, R., Allen, J. F. "A Formal Logic of Plans in Temporally Rich
    Domains," Proc. of the IEEE, 74, 1986, 1364-1382.

    --------------

    [PLANNING - TWEAK]
    Chapman, D., "Planning for Conjunctive Goals," Artificial Intelligence,
    32, 1987, 333-377.

    [PLANNING - TWEAK]
    Chapman, D., Planning for Conjunctive Goals. Technical Report 83-85,
    Massachusetts Institute of Technology, 1985.

    --------------

    [PLANNING - UNIVERSAL PLANS]
    Schoppers, M. J., "Universal Plans for Reactive Robots in Unpredictable
    Environments," Proc. of the Tenth Intern. Joint Conf. on Artificial
    Intelligence, Morgan Kaufmann, 1987, 1039-1046.

    --------------

    [PLANNING - WARPLAN-C]
    Warren, D. H. D., "Generating Conditional Plans and Programs," Proc.
    of the Summer Conf. on Artificial Intelligence and Simulation of
    Behavior, Univ. of Edinburgh, 1976, 344-354.

    [PLANNING - WARPLAN]
    Warren, D. H. D., WARPLAN: A System for Generating Plans. Memo 76,
    Univ. of Edinburgh, 1974.

    --------------

                            UNCLASSIFIED REFERENCES

    ---- 1988 ----

    Chang, K.-H., Wee, W. G., "A Planning Model with Problem Analysis and
    Operator Hierarchy," IEEE Trans. on Patterm Analysis and Machine
    Intelligence, 10(5), 1988, 672-675.

    ---- 1987 ----

    Hayes, C., "Using Goal Interactions to Guide Planning," Proc. of the
    Sixth National Conf. on Artificial Intelligence, Morgan Kaufmann, 1987,
    224-228.

    [ROBOT - EXECUTION MONITOR]
    Broverman, C. A., Croft, W. B., "Reasoning About Exceptions During Plan
    Execution Monitoring," Proc. of the Sixth National Conf. on Artificial
    Intelligence, Morgan Kaufmann, 1987, 190-195.

    ---- 1984 ----

    Allen, "General theory of action and time," Artificial Intelligence,
    23, 1984, 123-154.

    Daniel, L., "Planning and Operations Research," in Artificial
    Intelligence: Tools, Techniques, and Applications, T. O'Shea and M.
    Eisenstadt (eds.), Harper & Row, 1984, 423-452.

    Georgeff, M., "A Theory of Action for MultiAgent Planning," Proc. of
    the Fourth National Conf. on Artificial Intelligence, Morgan Kaufmann,
    1984, 121-125.

    Tate, A., "Goal Structure - Capturing the Intent of Plans," Proc.
    European Conf. on Artificial Intelligence, Pisa, Italy, 1984.

    Tate, A., "Planning and Condition Monitoring in a FMS," Conf. on the
    Development of Flexible Manufacturing Systems, London, UK, 1984.

    ---- 1983 ----

    Allen, J., Koomen, J., "Planning Using a Temporal World Model, Proc. of
    the Eighth Intern. Joint Conf. on Artificial Intelligence, Morgan
    Kaufmann, 1983, 741-747.

    Wilenski, R., Planning and understanding, Addison-Wesley, 1983.

    ---- 1982 ----

    Brooks, R. A., "Symbolic Error Analysis and Robot Planning," J.
    Robotics Research, 1(4), 1982, 29-68.

    McDermott, D. A., "A Temporal Logic for Reasoning about Processes and
    Plans," Cognitive Sciences, 6, 1982, 101-155.

    Sridharan, N., Bresina, J., "Plan Formation in Large, Realistic
    Domains," Proc. of the Fifth Biennial Conf. of the Canadian Society for
    Computational Studies of Intelligence, CIPS National Office, 1982,
    12-18.

    ---- 1980 ----

    Moore, R. C., Reasoning about Knowledge and Action. Technical Note 191,
    SRI Intern., 1980.

    Robinson, A. E., Wilkins, D. E., "Representing Knowledge in an
    Interactive Planner," Proc. of the First National Conf. on Artificial
    Intelligence, Morgan Kaufmann, 1980, 148-150.

    Wilensky, R., "Meta-Planning," Proc. of the First National Conf. on
    Artificial Intelligence, Morgan Kaufmann, 1980, 334-336.

    ---- 1979 ----

    Hayes-Roth, B., Hayes-Roth, F., "A Cognitive Model of Planning,"
    Cognitive Sciences, 1979, 275-310.

    Hayes-Roth, B., Hayes-Roth, F., Rosenschein, S. J., Cammarata, S.,
    "Modelling Planning as an Incremental, Opportunistic Process," Proc. of
    the Sixth Intern. Joint Conf. on Artificial Intelligence, Morgan
    Kaufmann, 1979, 375-383.

    Sacerdoti, E. D., "Problem Solving Tactics," Proc. of the Sixth Intern.
    Joint Conf. on Artificial Intelligence, Morgan Kaufmann, 1979,
    1077-1085.

    ---- 1977 ----

    Fikes, R. E., "Knowledge Representation in Automatic Planning Systems,"
    in Perspectives in Computer Science, J. K. Jones (ed.), 1977, 63-75.

    Schank, R. C., Abelson, R. P., Scripts, Plans, Goals and Understanding,
    Erlbaum, 1977.

    Wesson, R. B., "Planning in the World of the Air Traffic Controller,"
    Proc. of the Fifth Intern. Joint Conf. on Artificial Intelligence,
    Morgan Kaufmann, 1977, 473-479.

    ---- 1973 ----

    Lewis, R. A., Bejcsy, A. K., "Planning Consideration for a Roving Robot
    with Arm," Proc. of the Third Joint Intern. Conf. on Artificial
    Intelligence, Morgan Kaufmann, 1973.

    Hendrix, G. G., "Modelling Simultaneous Actions and Continuous
    Processes," Artificial Intelligence, 4, 1973, 145-180.

--
Hideyuki Nakashima
Cooperative Architecture
Electrotechincal Lab.


Newsgroups: comp.ai