zbMATH — the first resource for mathematics

Using machine learning for decreasing state uncertainty in planning. (English) Zbl 07283365
Summary: We present a novel approach for decreasing state uncertainty in planning prior to solving the planning problem. This is done by making predictions about the state based on currently known information, using machine learning techniques. For domains where uncertainty is high, we define an active learning process for identifying which information, once sensed, will best improve the accuracy of predictions.
We demonstrate that an agent is able to solve problems with uncertainties in the state with less planning effort compared to standard planning techniques. Moreover, agents can solve problems for which they could not find valid plans without using predictions. Experimental results also demonstrate that using our active learning process for identifying information to be sensed leads to gathering information that improves the prediction process.
68T Artificial intelligence
Full Text: DOI
[1] Aineto, D., Jim´enez, S., & Onaindia, E. (2018). Learning STRIPS action models with classical planning. InProceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, ICAPS 2018, Delft, The Netherlands, June 2429, 2018., pp. 399-407.
[2] Albore, A.; Palacios, H., & Geffner, H. (2009). A translation-based approach to contingent planning. InProceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI’09). · Zbl 1211.68392
[3] Amir, E., & Chang, A. (2008). Learning partially observable deterministic action models. Journal of Artificial Intelligence Research,33(1), 349-402. · Zbl 1183.68565
[4] Barfoot, T. D. (2017).State Estimation for Robotics. Cambridge University Press.
[5] Bertsimas, D., Pawlowski, C., & Zhuo, Y. D. (2018). From predictive methods to missing data imputation: An optimization approach.Journal of Machine Learning Research, 18(196), 1-39. · Zbl 06982952
[6] Blythe, J. (1999).An Overview of Planning Under Uncertainty, chap. An Overview of Planning Under Uncertainty, pp. 85-110. Springer Berlin Heidelberg, Berlin, Heidelberg.
[7] Bonet, B., & Geffner, H. (2000). Planning with incomplete information as heuristic search in belief space. InProceedings of the 5th International Conference on Artificial Intelligence Planning Systems (AIPS’00), pp. 52-61.
[8] Botea, A., Enzenberger, M., M¨uller, M., & Schaeffer, J. (2005). Macro-ff: Improving AI planning with automatically learned macro-operators.Journal of Artificial Intelligence Research,24, 581-621. · Zbl 1080.68657
[9] Boutilier, C., Dean, T., & Hanks, S. (1996). Planning under uncertainty: Structural assumptions and computational leverage. InIn Proceedings of the Second European Workshop on Planning, pp. 157-171. IOS Press. · Zbl 0918.68110
[10] Brafman, R., & Hoffmann, J. (2004). Conformant planning via heuristic forward search: A new approach. InProceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS’04), pp. 355-364.
[11] Brafman, R. I., & Shani, G. (2012). Replanning in domains with partial information and sensing actions.Journal of Artificial Intelligence Research,45, 565-600. · Zbl 1253.68295
[12] Bryce, D., Kambhampati, S., & Smith, D. E. (2006). Planning graph heuristics for belief space search.Journal of Artificial Intelligence Research,26. · Zbl 1182.68225
[13] Camacho, A., Muise, C., & McIlraith, S. A. (2016). From fond to robust probabilistic planning: Computing compact policies that bypass avoidable deadends. InThe 26th International Conference on Automated Planning and Scheduling, pp. 65-69.
[14] Cashmore, M., Fox, M., Long, D., Magazzeni, D., Ridder, B., Carrera, A., Palomeras, N., Hurtos, N., & Carreras, M. (2015). Rosplan: Planning in the robot operating system. InProceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS’15).
[15] Cassandra, A. R., Kaelbling, L. P., & Kurien, J. A. (1996). Acting under uncertainty: Discrete Bayesian models for mobile robot navigation. InIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
[16] Celorrio, S. J., Fern´andez, F., & Borrajo, D. (2008). The PELA architecture: Integrating planning and learning to improve execution. InAAAI.
[17] Cesa-Bianchi, N., Gentile, C., Vitale, F., & Zappella, G. (2013). Random spanning trees and the prediction of weighted graphs.Journal of Machine Learning Research,14, 1251-1284. · Zbl 1317.68146
[18] Chen, Y., Lasko, T. A., Mei, Q., Denny, J. C., & Xu, H. (2015). A study of active learning methods for named entity recognition in clinical text.Journal of Biomedical Informatics,58, 11-18.
[19] Cohn, D. A., Ghahramani, Z., & Jordan, M. I. (1996). Active learning with statistical models.Journal Of Artificial Intelligence Research,4(1), 129-145. · Zbl 0900.68366
[20] Coles, A., & Smith, A. (2007). Marvin: a heuristic search planner with online macro-action learning.Journal of Artificial Intelligence Research,28, 119-156. · Zbl 1182.68231
[21] Coles, A., Coles, A., Fox, M., & Long, D. (2010). Forward-chaining partial-order planning. InProceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS’10), pp. 42-49.
[22] de la Rosa, T., Celorrio, S. J., Fuentetaja, R., & Borrajo, D. (2011). Scaling up heuristic planning with relational decision trees.Journal of Artificial Intelligence research, JAIR,Vol 40(2011). · Zbl 1216.68242
[23] Fox, M., & Long, D. (2003). PDDL2.1: An extension to pddl for expressing temporal planning domains.Journal of Artificial Intelligence Research,20, 61-124. · Zbl 1036.68093
[24] Francis, R., Estlin, T., Doran, G., Johnstone, S., Gaines, D., Verma, V., Burl, M., Frydenvang, J., Montao, S., Wiens, R. C., Schaffer, S., Gasnault, O., DeFlores, L., Blaney, D., & Bornstein, B. (2017). Aegis autonomous targeting for chemcam on mars science laboratory: Deployment and results of initial science team use.Science Robotics,2.
[25] Fuentetaja, R., & Borrajo, D. (2006). Improving control-knowledge acquisition for planning by active learning. In F¨urnkranz, J., Scheffer, T., & Spiliopoulou, M. (Eds.),Machine Learning: ECML 2006, pp. 138-149. Springer Berlin Heidelberg.
[26] Gentile, C., Herbster, M., & Pasteris, S. (2013). Online similarity prediction of networked data from known and unknown graphs.Journal of Machine Learning Research,30.
[27] Ghazanfar, M. A., Pr¨ugel-Bennett, A., & Szedmak, S. (2012). Kernel-mapping recommender system algorithms.Information Sciences,208, 81-104.
[28] Guerin, J. T., Hanna, J. P., Ferland, L., Mattei, N., & Goldsmith, J. (2012). The academic advising planning domain. InProceedings of the 3rd Workshop on the International Planning Competition at ICAPS, pp. 1-5.
[29] Hoffmann, J., & Brafman, R. I. (2005). Contingent planning via heuristic forward search witn implicit belief states. InProceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS’05), pp. 71-80.
[30] Howey, R., Long, D., & Fox, M. (2004). VAL: Automatic plan validation, continuous effects and mixed initiative planning using pddl. In16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’04).
[31] Jahrer, M., T¨oscher, A., & Legenstein, R. (2010). Combining predictions for accurate recommender systems. InProceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10, pp. 693-702. ACM.
[32] Jimnez, S., De La Rosa, T., Fernndez, S., Fernndez, F., & Borrajo, D. (2012). A review of machine learning for automated planning.The Knowledge Engineering Review,27(4), 433467.
[33] Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains.Artificial Intelligence,101(1-2), 99-134. · Zbl 0908.68165
[34] Krivic, S., Cashmore, M., Magazzeni, D., Ridder, B., Szedmak, S., & Piater, J. (2017). Decreasing Uncertainty in Planning with State Prediction. InInternational Joint Conference on Artificial Intelligence, pp. 2032-2038. IJCAI.
[35] Krivic, S., Cashmore, M., Magazzeni, D., Ridder, B., Szedmak, S., & Piater, J. (2018).State Predictions System together with Domains and Test Scripts. https://github.com/Senka2112/StatePredictions.
[36] Krivic, S., & Piater, J. (2018). Pushing corridors for delivering unknown objects with a mobile robot. InAutonomous Robots, Vol. 43. Springer.
[37] Krivic, S., Szedmak, S., Xiong, H., & Piater, J. (2015). Learning missing edges via kernels in partially-known graphs. InEuropean Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning.
[38] Latouche, P., & Rossi, F. (2015). Graphs in machine learning: an introduction. InProceedings of the 23rd European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN), pp. 207-218.
[39] Lewis, D. D., & Gale, W. A. (1994). A sequential algorithm for training text classifiers. InProceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’94, pp. 3-12. Springer-Verlag.
[40] Li, M., & Sethi, I. K. (2006). Confidence-based active learning.IEEE Transactions on Pattern Analysis and Machine Intelligence,28(8), 1251-1261.
[41] Lin, Z., R.Liu, , & Su, Z. (2011). Linearized alternating direction method with adaptive penalty for low-rank representation.Advances in Neural Information Processing Systems,24, 612-620.
[42] Mausam, & Weld, D. S. (2006). Probabilistic temporal planning with uncertain durations. InProceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 1620, 2006, Boston, Massachusetts, USA, pp. 880-887. AAAI Press.
[43] McDermott, D., Ghallab, M., Howe, A., Knoblock, C., Ram, A., Veloso, M., Weld, D., & Wilkins, D. (1998). PDDL - the planning domain definition language. Tech. rep., Yale Center for Computational Vision and Control.
[44] Micchelli, C. A., Xu, Y., & Zhang, H. (2006). Universal kernels.Journal of Machine Learning Research,7, 2651-2667. · Zbl 1222.68266
[45] Ong, S. C. W., Png, S. W., Hsu, D., & Lee, W. S. (2010). Planning under uncertainty for robotic tasks with mixed observability.The International Journal of Robotics Research,29(8), 1053-1068.
[46] Palacios, H., & Geffner, H. (2006). Compiling uncertainty away: Solving conformant planning problems using a classical planner (sometimes). InProceedings of the 21st Conference on Artificial Intelligence (AAAI’06).
[47] Palacios, H., & Geffner, H. (2007). From conformant into classical planning: Efficient translations that may be complete too. InProceedings of the Seventeenth International Conference on International Conference on Automated Planning and Scheduling, ICAPS’07, pp. 264-271. AAAI Press.
[48] Palacios, H., & Geffner, H. (2009). Compiling uncertainty away in conformant planning problems with bounded width.Journal of Artificial Intelligence Research,35. · Zbl 1183.68584
[49] Palomeras, N., Carrera, A., Hurts, N., Karras, G. C., Bechlioulis, C. P., Cashmore, M., Magazzeni, D., Long, D., Fox, M., Kyriakopoulos, K. J., Kormushev, P., Salvi, J., & Carreras, M. (2016). Toward persistent autonomous intervention in a subsea panel. Autonomous Robots,40.
[50] Pineda, L. E., & Zilberstein, S. (2014). Planning under uncertainty using reduced models: Revisiting determinization. InProceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling, (ICAPS).
[51] Pommerening, F., Torralba, A., & Balyo, T. (2018).The International Planning Competition. http://www.icaps-conference.org/index.php/Main/Competition.
[52] Quigley, M., Conley, K., Gerkey, B., Faust, J., Foote, T., Leibs, J., Wheeler, R., & Ng, A. Y. (2009). ROS: an open-source robot operating system. InICRA workshop on open source software, Vol. 3.
[53] Smith, D. E., & Weld, D. S. (1998). Conformant graphplan. InPaper presented at the meeting of the AAAI/IAAI (AAAI’98), pp. 889-896.
[54] Szedmak, S., Ugur, E., & Piater, J. (2014). Knowledge propagation and relation learning for predicting action effects. InIntelligent Robots and Systems (IROS’14), pp. 623-629.
[55] Tong, S., & Koller, D. (2002). Support vector machine active learning with applications to text classification.Journal of Artificial Intelligence Research,2, 45-66. · Zbl 1009.68131
[56] Weld, D. S., Anderson, C. R., & Smith, D. E. (1998). Extending graphplan to handle uncertainty and sensing actions. InProceedings of the Fifteenth National/Tenth Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence, AAAI ’98/IAAI ’98, pp. 897-904, Menlo Park, CA, USA. American Association for Artificial Intelligence.
[57] Yang, Q., Wu, K., & Jiang, Y. (2007). Learning action models from plan examples using weighted max-sat.Artificial Intelligence,171(2), 107 - 143. · Zbl 1168.68555
[58] Younes, H. S., & Littman, M. L. (2004). PPDDL 1.0: An extension to PDDL for expressing planning domains with probabilistic effects. Tech. rep., Carnegie Mellon University.
[59] Zimmerman, T.
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.