×

zbMATH — the first resource for mathematics

Goal distance estimation for automated planning using neural networks and support vector machines. (English) Zbl 1334.68204
Summary: Many of today’s most successful planners perform a forward heuristic search. The accuracy of the heuristic estimates and the cost of their computation determine the performance of the planner. Thanks to the efforts of researchers in the area of heuristic search planning, modern algorithms are able to generate high-quality estimates. In this paper we propose to learn heuristic functions using artificial neural networks and support vector machines. This approach can be used to learn standalone heuristic functions but also to improve standard planning heuristics. One of the most famous and successful variants for heuristic search planning is used by the FastForward (FF) planner. We analyze the performance of standalone learned heuristics based on nature-inspired machine learning techniques and employ a comparison to the standard FF heuristic and other heuristic learning approaches. In the conducted experiments artificial neural networks and support vector machines were able to produce standalone heuristics of superior accuracy. Also, the resulting heuristics are computationally much more performant than related ones.
MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T05 Learning and adaptive systems in artificial intelligence
Software:
Graphplan; PDDL; WEKA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Blum A, Furst M (1995) Fast planning through planning graph analysis. In: IJCAI’95: proceedings of the 14th international joint conference on artificial intelligence, pp 1636–1642
[2] Bonet B, Geffner H (2000) HSP: heuristic search planner. Entry at AIPS-98 planning competition. AI Mag 21(2)
[3] Bonet B, Geffner H (2001) Planning as heuristic search. Artif Intell 129(1–2):5–33 · Zbl 0971.68146 · doi:10.1016/S0004-3702(01)00108-4
[4] Botea A, Enzenberger M, Müller M, Schaeffer J (2005) Macro-FF: improving AI planning with automatically learned macro-operators. J Artif Intell Res 24(1):581–621 · Zbl 1080.68657
[5] Bylander T (1994) The computational complexity of propositional STRIPS planning. Artif Intell 69:165–204 · Zbl 0821.68065 · doi:10.1016/0004-3702(94)90081-7
[6] Coles A, Smith KA (2007) Marvin: a heuristic search planner with online macro-action learning. J Artif Intell Res 28:119–156 · Zbl 1182.68231
[7] Cortes C, Vapnik V (1995) Support-vector networks. Mach Learn 20(3):273–297 · Zbl 0831.68098
[8] Drucker H, Burges CJC, Kaufman L, Smola AJ, Vapnik V (1996) Support vector regression machines. In: Mozer M, Jordan MI, Petsche T (eds) NIPS. MIT Press, Cambridge, pp 155–161
[9] Ebendt R, Drechsler R (2009) Weighted A* search–unifying view and application. Artif Intell 173:1310–1342 · Zbl 1194.68207 · doi:10.1016/j.artint.2009.06.004
[10] Fern A, Khardon R, Tadepalli P (2011) The first learning track of the international planning competition. Mach Learn 84:81–107 · Zbl 06031594 · doi:10.1007/s10994-011-5234-y
[11] Fikes R, Nilsson NJ (1971) STRIPS: a new approach to the application of theorem proving to problem solving. Artif Intell 2(4):189–208 · Zbl 0234.68036 · doi:10.1016/0004-3702(71)90010-5
[12] Frank J (2007) Using data mining to enhance automated planning and scheduling. In: Proceedings of the IEEE symposium on computational intelligence and data mining. IEEE, pp 251–260
[13] Ghallab M, Howe A, Knoblock C, McDermott D, Ram A, Veloso M, Weld D, Wilkins D (1998) PDDL–the planning domain definition language. Technical report. Yale Center for Computational Vision and Control
[14] Hall M, Frank E, Holmes G, Pfahringer B, Reutemann P, Witten IH (2009) The WEKA data mining software: an update. SIGKDD Explor 11(1):10–18
[15] Helmert M (2006) The fast downward planning system. J Artif Intell Res 26:191–246 · Zbl 1182.68245 · doi:10.1007/s10462-007-9049-y
[16] Helmert M, Domshlak C (2009) Landmarks, critical paths and abstractions: what’s the difference anyway? In: ICAPS’09: proceedings of the 19th international conference on automated planning and scheduling. AAAI
[17] Hoffmann J (2001) FF: the fast-forward planning system. AI Mag 22:57–62
[18] Nilsson NJ (1982) Principles of artificial intelligence. Springer, Berlin · Zbl 0474.68094
[19] Rumelhart DE, Hinton GE, Williams RJ (1988) Learning representations by back-propagating errors. In: Neurocomputing: foundations of research, pp 696–699. http://www.nature.com/nature/journal/v323/n6088/abs/323533a0.html
[20] Satzger B, Kramer O (2010) Learning heuristic functions for state-space planning. In: CI’10: proceedings of the 5th international conference on computational intelligence, pp 36–43
[21] Satzger B, Kramer O, Lässig J (2010) Adaptive heuristic estimates for automated planning using regression. In: International conference on artificial intelligence, pp 576–581
[22] Satzger B, Pietzowski A, Trumler W, Ungerer T (2008) Using automated planning for trusted self-organising organic computing systems. In: ATC’08: proceedings of the 5th international conference on autonomic and trusted computing. Springer, pp 60–72
[23] Shevade S, Keerthi S, Bhattacharyya C, Murthy K (1999) Improvements to the SMO algorithm for SVM regression. IEEE Trans Neural Networks. doi: 10.1109/72.870050 · Zbl 1085.68629
[24] Swiercz M, Kochanowicz J, Weigele J, Hurst R, Liebeskind D, Mariak Z, Melhem E, Krejza J (2008) Learning vector quantization neural networks improve accuracy of transcranial color-coded duplex sonography in detection of middle cerebral artery spasm–preliminary report. Neuroinformatics 6:279–290 · doi:10.1007/s12021-008-9023-0
[25] Vapnik V (1995) The nature of statistical learning theory. Springer, New York · Zbl 0833.62008
[26] Widrow B, Hoff ME (1960) Adaptive switching circuits. IRE WESCON Conv Record 4:96–104
[27] Xu Y, Fern A, Yoon S (2009) Learning weighted rule sets for forward search planning. In: Workshop on planning and learning, ICAPS-2009
[28] Yoon SW, Fern A, Givan R (2006) Learning heuristic functions from relaxed plans. In: ICAPS’06: proceedings of the 16th international conference on automated planning and scheduling. AAAI, pp 162–171
[29] Yoon S, Fern A, Givan R (2008) Learning control knowledge for forward search planning. J Mach Learn Res 9:683–718 · Zbl 1225.68246
[30] Zimmerman T, Kambhampati S (2003) Learning-assisted automated planning: looking back, taking stock, going forward. AI Mag 24(2):73–96
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.