Domain-dependent knowledge in answer set planning

ABSTRACT

In this article we consider three different kinds of domain-dependent control knowledge (temporal, procedural and HTN-based) that are useful in planning. Our approach is declarative and relies on the language of logic programming with answer set semantics (AnsProlog*). AnsProlog* is designed to plan without control knowledge. We show how temporal, procedural and HTN-based control knowledge can be incorporated into AnsProlog* by the modular addition of a small number of domain-dependent rules, without the need to modify the planner. We formally prove the correctness of our planner, both in the absence and presence of the control knowledge. Finally, we perform some initial experimentation that demonstrates the potential reduction in planning time that can be achieved when procedural domain knowledge is used to solve planning problems with large plan length.

REFERENCES

• 1: Babovich, Y. and Lifschitz, V. Computing answer sets using program completion.
• 2: Fahiem Bacchus , Froduald Kabanza, Using temporal logics to express search control knowledge for planning, Artificial Intelligence, v.116 n.1-2, p.123-191, Jan. 2000 [doi>10.1016/S0004-3702(99)00071-5]
• 3: Bacchus, F., Kautz, H., Smith, D., Long, D., Geffner, H., and Koehler, J. 2000. AIPS-00 Planning Competition. In proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling Systems.
• 4: Baral, C. 1995. Reasoning about actions:Non-deterministic effects, constraints and qualification. In Proceedings of the 14th International Joint Conference on Artificial Intelligence. Morgan-Kaufmann, San Francisco, CA, 2017--2023.
• 5: Chitta Baral, Knowledge Representation, Reasoning, and Declarative Problem Solving, Cambridge University Press, New York, NY, 2003
• 6: Chitta Baral , Tran Cao Son, Extending ConGolog to Allow Partial Ordering, 6th International Workshop on Intelligent Agents VI, Agent Theories, Architectures, and Languages (ATAL),, p.188-204, July 15-17, 1999
• 7: Avrim L. Blum , Merrick L. Furst, Fast planning through planning graph analysis, Artificial Intelligence, v.90 n.1-2, p.281-300, Feb. 1997 [doi>10.1016/S0004-3702(96)00047-1]
• 8: Blai Bonet , Héctor Geffner, Planning as heuristic search, Artificial Intelligence, v.129 n.1-2, p.5-33, June 2001 [doi>10.1016/S0004-3702(01)00108-4]
• 9: Wolfram Burgard , Armin B. Cremers , Dieter Fox , Dirk Hähnel , Gerhard Lakemeyer , Dirk Schulz , Walter Steiner , Sebastian Thrun, The interactive museum tour-guide robot, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.11-18, July 1998, Madison, Wisconsin, United States
• 10: Tom Bylander, The computational complexity of propositional STRIPS planning, Artificial Intelligence, v.69 n.1-2, p.165-204, Sept. 1994 [doi>10.1016/0004-3702(94)90081-7]
• 11: David Chapman, Planning for conjunctive goals, Artificial Intelligence, v.32 n.3, p.333-377, July 1987 [doi>10.1016/0004-3702(87)90092-0]
• 12: Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001 [doi>10.1145/502807.502810]
• 13: Giuseppe de Giacomo , Yves Lespérance , Hector J. Levesque, ConGolog, a concurrent programming language based on the situation calculus, Artificial Intelligence, v.121 n.1-2, p.109-169, Aug. 2000 [doi>10.1016/S0004-3702(00)00031-X]
• 14: Yannis Dimopoulos , Bernhard Nebel , Jana Koehler, Encoding Planning Problems in Nonmonotonic Logic Programs, Proceedings of the 4th European Conference on Planning: Recent Advances in AI Planning, p.169-181, September 24-26, 1997
• 15: Patrick Doherty , Jonas Kvarnström, TALplanner: An Empirical Investigation of a Temporal Logic-based Forward Chaining Planner, Proceedings of the Sixth International Workshop on Temporal Representation and Reasoning, p.47, May 01-02, 1999
• 16: Thomas Eiter , Wolfgang Faber , Nicola Leone , Gerald Pfeifer , Axel Polleres, Planning under Incomplete Knowledge, Proceedings of the First International Conference on Computational Logic, p.807-821, July 01, 2000
• 17: Eiter, T., Leone, N., Mateis, C., Pfeifer, G., and Scarcello, F. 1998. The KR system dlv: Progress report, comparisons, and benchmarks. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning. 406--417.
• 18: Kutluhan Erol , Dana S. Nau , V. S. Subrahmanian, Complexity, decidability and undecidability results for domain-independent planning, Artificial Intelligence, v.76 n.1-2, p.75-88, July 1995 [doi>10.1016/0004-3702(94)00080-K]
• 19: Fikes, R. and Nilson, N. 1971. STRIPS: A new approach to the application of theorem proving to problem solving. Artif. Intel. 2, 3--4, 189--208.
• 20: Logic programming and knowledge representation-the A-prolog perspective, Artificial Intelligence, v.138 n.1-2, p.3-38, June 2002 [doi>10.1016/S0004-3702(02)00207-2]
• 21: Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming: Proceedings of the 5th International Conference and Symposium, R. Kowalski and K. Bowen, Eds. 1070--1080.
• 22: Gelfond, M. and Lifschitz, V. 1993. Representing actions and change by logic programs. J. Logic Prog. 17, 2,3,4, 301--323.
• 23: Gelfond, M. and Lifschitz, V. 1998. Action languages. ETAI 3, 6.
• 24: Hoffmann, J. and Nebel, B. 2001. The FF planning system: Fast plan generation through heuristic search. J. Artif. Intel. Res. 14, 253--302.
• 25: Yi-Cheng Huang , Bart Selman , Henry Kautz, Control knowledge in planning: benefits and tradeoffs, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.511-517, July 18-22, 1999, Orlando, Florida, United States
• 26: Kautz, H., McAllester, D., and Selman, B. 1994. Encoding plans in propositional logic. In Proceedings of KR 94. 374--384.
• 27: Henry Kautz , Bart Selman, Planning as satisfiability, Proceedings of the 10th European conference on Artificial intelligence, p.359-363, August 1992, Vienna, Austria
• 28: Kautz, H. and Selman, B. 1996. Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96). AAAI Press, 1194--1199.
• 29: Kautz, H. and Selman, B. 1998a. BLACKBOX: A new approach to the application of theorem proving to problem solving. In Workshop Planning as Combinatorial Search, AIPS-98 (Pittsburgh, PA).
• 30: Kautz, H. and Selman, B. 1998b. The role of domain-specific knowledge in the planning as satisfiability framework. In Proceedings of the 4th International Conference on Artificial Intelligence Planning and Scheduling Systems.
• 31: Levesque, H., Reiter, R., Lesperance, Y., Lin, F., and Scherl, R. 1997. GOLOG: A logic programming language for dynamic domains. J. Logic Prog. 31, 1-3 (April-June), 59--84.
• 32: Lifschitz, V. 1999a. Action languages, answer sets and planning. In The Logic Programming Paradigm: a 25-Year Perspective. Springer-Verlag, New York, 357--373.
• 33: Vladimir Lifschitz, Answer set planning, Proceedings of the 1999 international conference on Logic programming, p.23-37, November 1999, Las Cruces, New Mexico, United States
• 34: Answer set programming and plan generation, Artificial Intelligence, v.138 n.1-2, p.39-54, June 2002 [doi>10.1016/S0004-3702(02)00186-8]
• 35: Vladimir Lifschitz , Hudson Turner, Splitting a logic program, Proceedings of the eleventh international conference on Logic programming, p.23-37, August 1994
• 36: Vladimir Lifschitz , Hudson Turner, Representing Transition Systems by Logic Programs, Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning, p.92-106, December 02-04, 1999
• 37: Lin, F. 1995. Embracing causality in specifying the indirect effects of actions. In Proceedings of the 14th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, San Mateo, CA, 1985--1993.
• 38: Fangzhen Lin , Yuting Zhao, ASSAT: computing answer sets of a logic program by SAT solvers, Eighteenth national conference on Artificial intelligence, p.112-117, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 39: Marek, V. and Truszczyński, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: a 25-year Perspective. 375--398.
• 40: McCain, N. and Turner, H. 1995. A causal theory of ramifications and qualifications. In Proceedings of the 14th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, San Mateo, CA, 1978--1984.
• 41: Sheila A. McIlraith, Modeling and Programming Devices and Web Agents, Proceedings of the First International Workshop on Formal Approaches to Agent-Based Systems-Revised Papers, p.63-77, April 05-07, 2000
• 42: Dana S. Nau , Yue Cao , Amnon Lotem , Hector Muñoz-Avila, SHOP: Simple Hierarchical Ordered Planner, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.968-975, July 31-August 06, 1999
• 43: Ilkka Niemelä, Logic programs with stable model semantics as a constraint programming paradigm, Annals of Mathematics and Artificial Intelligence, v.25 n.3-4, p.241-273, 1999 [doi>10.1023/A:1018930122475]
• 44: Ilkka Niemelä , Patrik Simons , Timo Soininen, Stable Model Semantics of Weight Constraint Rules, Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning, p.317-331, December 02-04, 1999
• 45: Reiter, R. 1980. A logic for default reasoning. Artif. Intel. 13, 1,2, 81--132.
• 46: Reiter, R. 2000. On knowledge-based programming with sensing in the situation calculus. In Proceedings of the 2nd International Cognitive Robotics Workshop (Berlin, Germany).
• 47: Sacerdoti, E. D. 1974. Planning in a hierarchy of abstraction spaces. Artif. Intel. 5, 115--135.
• 48: Konstantinos Sagonas , Terrance Swift , David S. Warren, XSB as an efficient deductive database engine, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.442-453, May 24-27, 1994, Minneapolis, Minnesota, United States
• 49: Patrik Simons , Ilkka Niemelá , Timo Soininen, Extending and implementing the stable model semantics, Artificial Intelligence, v.138 n.1-2, p.181-234, June 2002 [doi>10.1016/S0004-3702(02)00187-X]
• 50: Subrahmanian, V. and Zaniolo, C. 1995. Relating stable models and ai planning domains. In Proceedings of the International Conference on Logic Programming. 233--247.
• 51: Tuan, L. and Baral, C. 2001. Effect of knowledge representation on model based planning: Experiments using logic programming encodings. In Proc. of AAAI Spring symposium on “Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning”. 110--115.
• 52: Turner, H. 1997. Representing actions in logic programs and default theories. J. Logic Prog. 31, 1-3, 245--298.
• 53: Hudson Turner, Polynomial-Length Planning Spans the Polynomial Hierarchy, Proceedings of the European Conference on Logics in Artificial Intelligence, p.111-124, September 23-26, 2002
• 54: Wilkins, D. and desJardines, M. Spring 2001. A call for knowledge-based planning. AI Magazine 22, 1, 99--115.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representation languages
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

General Terms:
Languages

Keywords:
Reasoning about actions, answer set planning, control knowledge, planning, procedural knowledge