×

zbMATH — the first resource for mathematics

Using temporal logics to express search control knowledge for planning. (English) Zbl 0939.68827
Summary: Over the years increasingly sophisticated planning algorithms have been developed. These have made for more efficient planners, but unfortunately these planners still suffer from combinatorial complexity even in simple domains. Theoretical results demonstrate that planning is in the worst case intractable. Nevertheless, planning in particular domains can often be made tractable by utilizing additional domain structure. In fact, it has long been acknowledged that domain-independent planners need domain-dependent information to help them plan effectively. In this work we present an approach for representing and utilizing domain-specific control knowledge. In particular, we show how domain-dependent search control knowledge can be represented in a temporal logic, and then utilized to effectively control a forward-chaining planner. There are a number of advantages to our approach, including a declarative semantics for the search control knowledge; a high degree of modularity (new search control knowledge can be added without affecting previous control knowledge); and an independence of this knowledge from the details of the planning algorithm. We have implemented our ideas in the TLplan system, and have been able to demonstrate its remarkable effectiveness in a wide range of planning domains.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
UCPOP; Prodigy; Graphplan
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] AIPS98, Artificial Intelligence Planning Systems 1998 planning competition. http://ftp.cs.yale.edu/pub/mcdermott/aipscomp-results.html, 1998
[2] Bacchus, F.; Kabanza, F., Planning for temporally extended goals, (), 1215-1222 · Zbl 1034.68549
[3] Bacchus, F.; Kabanza, F., Using temporal logic to control search in a forward chaining planner, (), 141-153
[4] Bacchus, F.; Kabanza, F., Planning for temporally extended goals, Ann. math. artificial intelligence, 22, 5-27, (1998) · Zbl 1034.68549
[5] Bacchus, F.; Petrick, R., Modeling and Agent’s incomplete knowledge during planning and execution, (), 432-443
[6] Barbeau, M.; Kabanza, F.; St-Denis, R., Synthesizing plant controllers using real-time goals, (), 791-798
[7] Barrett, A.; Golden, K.; Penberthy, J.S.; Weld, D., UCPOP User’s manual (version 2.0), (1993), University of Washington Department of Computer Science and Engineering, (ftp://cs.washington.edu/pub/ai/)
[8] Barrett, A.; Weld, D., Task-decomposition via plan parsing, (), 1117-1122
[9] Barrett, A.; Weld, D.S., Partial-order planning: evaluating possible efficiency gains, Artificial intelligence, 67, 1, 71-112, (1994) · Zbl 0807.68080
[10] Bauer, M.; Biundo, S.; Dengler, D.; Hecking, M.; Koehler, J.; Merziger, G., Integrated plan generation and recognition—A logic-based approach, (1991), DFKI, Technical Report RR-91-26
[11] Biundo, S.; Stephan, W., Modeling planning domains systematically, (), 599-603
[12] Biundo, S.; Stephan, W., System assistance in structured domain model development, (), 1240-1245
[13] Blum, A.; Furst, M., Fast planning through planning graph analysis, Artificial intelligence, 90, 281-300, (1997) · Zbl 1017.68533
[14] Bonet, B.; Loerincs, G.; Geffner, H., A robust and fast action selection mechanism for planning, (), 714-719
[15] Boutilier, C.; Dearden, R., Using abstractions for decision-theoretic planning with time constraints, (), 1016-1022
[16] Carbonell, J.G.; Blythe, J.; Etzioni, O.; Gil, Y.; Joseph, R.; Khan, D.; Knoblock, C.; Minton, S.; Pérez, A.; Reilly, S.; Veloso, M.; Wang, X., Prodigy 4.0: the manual and turorial, (1992), School of Computer Science, Carnegie Mellon University Pittsburgh, PA, Technical Report CMU-CS-92-150
[17] Currie, K.; Tate, A., O-plan: the open planning architecture, Artificial intelligence, 52, 49-86, (1991)
[18] Dean, T.; Kaelbling, L.P.; Kerman, J.; Nicholson, A., Planning with deadlines in stochastic domains, (), 574-579
[19] Emerson, E.A., Temporal and modal logic, (), 997-1072 · Zbl 0900.03030
[20] Erol, K.; Nau, D.S.; Subrahmanian, V.S., On the complexity of domain-independent planning, (), 381-386
[21] Erol, K., Hierarchical task network planning: formalization, analysis, and implementation, ph.D. thesis, (1995), University of Maryland College Park, MD
[22] Etzioni, O., Acquiring search-control knowledge via static analysis, Artificial intelligence, 62, 2, 255-302, (1993) · Zbl 0778.68071
[23] Garson, J.W., Quantification in modal logic, (), 249-307 · Zbl 0875.03050
[24] Gerevini, A.; Schubert, L., Accelerating partial-order planners: some techniques for effective search control and pruning, J. artificial intelligence res., 5, 95-137, (1996)
[25] Green, C., Application of theorem proving to problem solving, (), 219-239
[26] Gupta, N.; Nau, D.S., On the complexity of blocks-world planning, Artificial intelligence, 56, 223-254, (1992) · Zbl 0785.68046
[27] Halpern, J.Y.; Vardi, M.Y., Model checking vs. theorem proving: A manifesto, (), 325-334 · Zbl 0765.68189
[28] Hennessy, M., The semantics of programming languages: an elementary introduction using structural operational semantics, (1990), Wiley New York · Zbl 0723.68067
[29] Johnson, D.S., A catalog of complexity classes, (), 69-161 · Zbl 0900.68246
[30] Joslin, D.; Pollack, M., Least-cost flaw repair: A plan refinement strategy for partial-order planning, (), 1004-1009
[31] Kanellakis, P.C., Elements of relational database theory, (), 1071-1156 · Zbl 0900.68090
[32] Kautz, H.; Selman, B., Pushing the envelope: planning, propositional logic, and stochastic search, (), 1194-1201
[33] Kautz, H.; Selman, B., Blackbox: A new approach to the application of theorem proving to problem solving, (1998), System available at http://www.research.att.com/ kautz
[34] Kautz, H.; Selman, B., The role of domain-specific knowledge in the planning as satisfiability framework, (), 181-189
[35] Kibler, D.; Morris, P., Don’t be stupid, (), 345-347
[36] Knoblock, C., Automatically generating abstractions for planning, Artificial intelligence, 68, 2, 243-302, (1994) · Zbl 0942.68712
[37] Koehler, J.; Nebel, B.; Hoffmann, J.; Dimopoulos, Y., Extending planning graphs to an ADL subset, (), 273-285, System available at http://www.informatik.uni-freiburg.de/ koehler/ipp.html
[38] Laird, J.; Newell, A.; Rosenbloom, P., SOAR: an architecture for general intelligence, Artificial intelligence, 33, 1, 1-67, (1987)
[39] Manna, Z.; Pnueli, A., The temporal logic of reactive and concurrent systems: specication, (1992), Springer New York
[40] McDermott, D., A heuristic estimator for means-end analysis in planning, ()
[41] Minton, S.; Bresina, J.; Drummond, M., Total-order and partial-order planning: A comparative analysis, J. artificial intelligence res., 2, 227-262, (1994)
[42] Minton, S., Learning search control knowledge, (1988), Kluwer Academic Dordrecht
[43] Parekh, S., A study of procedural search control in Simon, (1996), http://www.cs.washington.edu/homes/sparekh/quals.ps
[44] Pednault, E., ADL: exploring the middle ground between STRIPS and the situation calculus, (), 324-332
[45] Poet, M.; Smith, D.E., Threat-removal strategies for partial-order planning, (), 492-499
[46] Rosenschein, S.J., Plan synthesis: A logical perspective, (), 115-119
[47] Russell, S.; Norvig, P., Artificial intelligence A modern approach, (1995), Prentice Hall Englewood Cliffs, NJ · Zbl 0835.68093
[48] Sacerdoti, E., Planning in a hierarchy of abstraction spaces, Artificial intelligence, 5, 115-135, (1974) · Zbl 0288.68052
[49] Selman, B., Near-optimal plans, tractability and reactivity, (), 521-529
[50] Sistla, A.P., Safety, liveness, and fairness in temporal logic, Formal aspects of computing, 6, 495-511, (1994) · Zbl 0820.68077
[51] Sistla, A.P.; Clarke, E.M., The complexity of propositional linear temporal logic, J. ACM, 32, 733-749, (1985) · Zbl 0632.68034
[52] Srivastava, B.; Kambhampati, S., Synthesizing customized planners from specifications, J. artificial intelligence res., 8, 93-128, (1998)
[53] Stephan, W.; Biundo, S., Deduction-based refinement planning, (), 213-220
[54] Tash, J.; Russell, S., Control strategies for a stochastic planner, (), 1079-1085
[55] Tate, A., Generating project networks, (), 888-893
[56] Thompson, C., Carpoolworld, (1998), University of Waterloo Ont, Undergraduate project in CS486
[57] Vardi, M.Y., The complexity of relational query langauges, (), 176-185
[58] Vardi, M.Y., Computational model theory: an overview, Logic J. IGPL, 6, 4, 601-623, (1998) · Zbl 0909.03031
[59] Veloso, M.; Carbonell, J.; Pérez, A.; Borrajo, D.; Fink, E.; Blythe, J., Integrating planning and learning: the PRODIGY architecture, J. experimental and theoretical artificial intelligence, 7, 1, (1995) · Zbl 0939.68830
[60] Weld, D.; Etzioni, O., The first law of robotics (a call to arms), (), 1042-1047
[61] Weld, D.S., An introduction to least commitment planning, AI magazine, 15, 4, 27-61, (1994)
[62] Wilkins, D., Practical planning: extending the classical AI planning paradigm, (1988), Morgan Kaufmann San Mateo, CA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.