Modification strategies for SAT-based plan adaptation

• Autorzy: Van der Krogt R.
• Języki publikacji: EN

Abstrakty

EN

Planning, the generation of a course of action to achieve a set of goals, is an important technique in the development of intelligent agents. Heretofore, planning has been largely considered as a one-shot problem. However, in practice, we are often dealing with situations in which an existing plan has to be adapted. Not only might we be facing a dynamic environment that requires a plan to be repaired, but it may also be that we recognize the new planning problem as being similar to one that we have solved before (i.e. case-based planning). This paper investigates a plan adaptation framework based on SAT-encodings of the planning problem. Compilation techniques have been very successfully applied to planning, as evidenced by their success in recent planning competitions. So far, however, such techniques have not been used for plan adaptation purposes. This paper explores whether it is feasible to modify the generated SAT instances such as to encode information that was extracted from the solution to the original planning problem.

Słowa kluczowe

EN

plan repair; planning as satisfiability

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2008
• Tom: Vol. 18, no. 2
• Strony: 203--230
• Opis fizyczny: Bibliogr. 36 poz., rys., tab.

Twórcy

autor

Van der Krogt R.

• Cork Constraint Computation Centre, University College Cork, Ireland,

Bibliografia

• [1] M. AI-CHANG, J. BRESINA, K. FARRELL, J. HSU, A. JONSSON, B. KANEFSKY, M. MCCURDY, P. MORRIS, K. RAJAN, A. VERA, J. YGLESIAS, L. CHAREST and P. MALDAGUE: MAPGEN: Mixed-initiative activity planning for the mars exploration rover mission. Proc. of Demonstration Systems Track, (2003).
• [2] P. VAN BEEK and X. CHEN: CPlan: A constraint programming approach to planning. Proc. Sixteenth National Conference on Artificial Intelligence, Menlo Park, CA, (1999), AAAI Press, 585-590.
• [3] A. L. BLUM and M. L. FURST: Fast planning through planning graph analysis. Artificial Intelligence, 90 (1997), 281-300.
• [4] T. BYLANDER: The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1-2), (1994), 165-204.
• [5] Y. CHEN, Z. XING and W. ZHANG: Long-distance mutual exclusion for propositional planning. Proc. Twentieth Int. Joint Conf on Artificial Intelligence, Hyderabad, India, (2007), 1840-1845.
• [6] P. R. COHEN: Empirical methods for artificial intelligence. The MIT Press, Cambridge, MA, 1995.
• [7] N. EÉN and N. SÖRENSSON: An extensible SAT-solver. In G. Goos, J. Hartmanis, and J. van Leeuwen, (Ed), Theory and Applications of Satisfiability Testing, volume 2919 of Lecture Notes on Computer Science, Springer Verlag, Berlin, Germany, (2004), 502-518.
• [8] M. D. ERNST, T. D. MILLSTEIN and D. S. WELD.: Automatic SAT-compilation of planning problems. Proc. Fifteenth Int. Joint Conf on Artificial Intelligence, Nagoya, Japan, (1997), 1169-1177.
• [9] M. FOX, A. GEREVINI, D. LONG and I. SERINA: Plan stability: replanning versus plan repair. Proc. Int. Conf on Automated Planning and Scheduling, Menlo Park, CA, (2006), AAAI Press, 193-202.
• [10] M. R. GAREY and D. S. JOHNSON: Computers and intractability - a guide to the theory of NP-completeness. W.H. Freeman and Company, New York, NY, 1979.
• [11] A. GEREVINI and I. SERINA: Fast plan adaptation through planning graphs: Local and systematic search techniques. Proc. Fifth Int. Conf on Artificial Intelligence Planning Systems, Menlo Park, CA 94025, (2000), AAAI Press, 112-121.
• [12] E. GOLDBERG and Y. NOVIKOV: BerkMin: A fast and robust SAT-solver. Proc. Conf on Design, automation and test in Europe, Washington, DC, USA, (2002), IEEE Computer Society, 142-149.
• [13] C. P. GOMES, B. SELMAN and H. KAUTZ: Boosting combinatorial search through randomization. Proc. Fifteenth National Conf. Artificial Intelligence, Menlo Park, CA, AAAI Press, (1998), 431-437.
• [14] J. HOFFMANN and S. EDELKAMP: The deterministic part of IPC-4: An overview. J. Artificial Intelligence Research, 24 (2005), 519-579.
• [15] S. KAMBHAMPATI; Refinement planning as a unifying framework for plan synthesis. Al Magazine, 18(2), (1997), 67-97.
• [16] S. KAMBHAMPATI, C. A. KNOBLOCK and Q. YANG: Planning as refinement search: A unified framework for evaluating design tradeoffs in partial-order planning. Artificial Intelligence, 76(1-2), (1995), 167-238.
• [17] H. KAUTZ and B. SELMAN: Pushing the envelope: Planning, propositional logic, and stochastic search. Proc. Thirteenth National Conf. Artificial Intelligence, Menlo Park, CA, AAAI Press, (1996), 1194-1201.
• [18] H. KAUTZ and B. SELMAN: BLACKBOX: A new approach to the application of theorem proving to problem solving. Working notes of the Workshop on Planning as Combinatorial Search, held in conjunction with AIPS'98, (1998).
• [19] H. KAUTZ, B. SELMAN and J. HOFFMANN: SatPlan: Planning as satisfiability. Abstracts of the 5th Int. Planning Competition, (2006).
• [20] H. A. KAUTZ, D. MCALLESTER and B. SELMAN: Encoding plans in propositional logic. Proc. Fifth Int. Conf on the Principle of Knowledge Representation and Reasoning, Menlo Park, CA, AAAI Press, (1996), 374-384.
• [21] D. LEAKE: Case-based reasoning : Experiences, lessons and future directions. AAAI Press, Menlo Park, CA, 1996.
• [22] D. LONG and M. Fox: The 3rd International Planning Competition: Results and analysis. J. Artificial Intelligence Research, 20 (2003), 1-59.
• [23] A. LOPEZ and F. BACCHUS: Generalizing graphplan by formulating planning as a CSP. Proc. Eighteenth Int. Joint Conf on Artificial Intelligence, (2003), 954-960.
• [24] A. NADEL: The Jerusat SAT solver. Master's thesis, Hebrew University of Jerusalem, Jerusalem, Israel, 2002.
• [25] D. NAU, M. GHALLAB and P. TRAVERSO: Automated planning: Theory & practice. Morgan Kaufmann Publishers, San Mateo, CA, 2004.
• [26] B. NEBEL and J. KOEHLER: Plan modifications versus plan generation: A complexity-theoretic perspective. Technical Report RR-92-48, Deutsches Forschungszentrum fur Kanstliche Intelligenz GmbH, 1992.
• [27] J. RINTANEN, K. HELJANKO and I. NIEMELA: Planning as satisfiability: parallel plans and algorithms for plan search. Artificial Intelligence, 170(12), (2006), 1031-1080.
• [28] L. RYAN: Efficient algorithms for clause-learning SAT solvers. Master's thesis, Simon Fraser University, Vancouver, B.C., Canada, 2004.
• [29] L. SPALAllI: A survey on case-based planning. Artificial Intelligence Review, 16 (2001), 3-36.
• [30] S. STEEL: The bread and butter of planning. Artificial Intelligence Review, 1 (1987), 159-181.
• [31] M. VAN DEN BRIEL and S. KAMBHAMPATI: Optiplan: Unifying ip-based and graph-based planning. J. Artificial Intelligence Research, 24 (2005), 919-931.
• [32] M. VAN DEN BRIEL and S. KAMBHAMPATI: IPPlan: Planning as integer programming. In Abstracts of the 5th Int. Planning Competition, 2006.
• [33] R. VAN DER KROGT: Plan Repair in Single-Agent and Multi-Agent Systems. PhD thesis, Delft University of Technology, Delft, The Netherlands, 2005.
• [34] R. VAN DER KROGT and M. DE WEERDT: Plan repair as an extension of planning. Proc. Int. Conf. Automated Planning and Scheduling, Menlo Park, CA,AAAI Press, (2005), 161-170.
• [35] V. VIDAL and S. TABARY: The new version of CPT, an optimal temporal POCL planner based on constraint programming. Abstracts of the 5th Int. Planning Competition, 2006.
• [36] Z. X ING, Y. CHEN and W. ZHANG: Optimal STRIPS planning by maximum satisfiability and accumulative learning. Proc. Int. Conf Automated Planning and Scheduling, Menlo Park, CA, AAAI Press, (2006), 442-446.