{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T15:51:42Z","timestamp":1780588302337,"version":"3.54.1"},"reference-count":63,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T00:00:00Z","timestamp":1700438400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation (SNSF)","doi-asserted-by":"publisher","award":["407740_187246"],"award-info":[{"award-number":["407740_187246"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["MAKE"],"abstract":"<jats:p>In an era characterised by rapid technological advancement, the application of algorithmic approaches to address complex problems has become crucial across various disciplines. Within the realm of education, there is growing recognition of the pivotal role played by computational thinking (CT). This skill set has emerged as indispensable in our ever-evolving digital landscape, accompanied by an equal need for effective methods to assess and measure these skills. This research places its focus on the Cross Array Task (CAT), an educational activity designed within the Swiss educational system to assess students\u2019 algorithmic skills. Its primary objective is to evaluate pupils\u2019 ability to deconstruct complex problems into manageable steps and systematically formulate sequential strategies. The CAT has proven its effectiveness as an educational tool in tracking and monitoring the development of CT skills throughout compulsory education. Additionally, this task presents an enthralling avenue for algorithmic research, owing to its inherent complexity and the necessity to scrutinise the intricate interplay between different strategies and the structural aspects of this activity. This task, deeply rooted in logical reasoning and intricate problem solving, often poses a substantial challenge for human solvers striving for optimal solutions. Consequently, the exploration of computational power to unearth optimal solutions or uncover less intuitive strategies presents a captivating and promising endeavour. This paper explores two distinct algorithmic approaches to the CAT problem. The first approach combines clustering, random search, and move selection to find optimal solutions. The second approach employs reinforcement learning techniques focusing on the Proximal Policy Optimization (PPO) model. The findings of this research hold the potential to deepen our understanding of how machines can effectively tackle complex challenges like the CAT problem but also have broad implications, particularly in educational contexts, where these approaches can be seamlessly integrated into existing tools as a tutoring mechanism, offering assistance to students encountering difficulties. This can ultimately enhance students\u2019 CT and problem-solving abilities, leading to an enriched educational experience.<\/jats:p>","DOI":"10.3390\/make5040082","type":"journal-article","created":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T11:31:36Z","timestamp":1700479896000},"page":"1660-1679","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Proximal Policy Optimization-Based Reinforcement Learning and Hybrid Approaches to Explore the Cross Array Task Optimal Solution"],"prefix":"10.3390","volume":"5","author":[{"given":"Samuel","family":"Corecco","sequence":"first","affiliation":[{"name":"Faculty of Informatics, Universit\u00e0 della Svizzera Italiana (USI), 6900 Lugano, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2613-4467","authenticated-orcid":false,"given":"Giorgia","family":"Adorni","sequence":"additional","affiliation":[{"name":"Dalle Molle Institute for Artificial Intelligence (IDSIA), USI-SUPSI, 6900 Lugano, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca Maria","family":"Gambardella","sequence":"additional","affiliation":[{"name":"Dalle Molle Institute for Artificial Intelligence (IDSIA), USI-SUPSI, 6900 Lugano, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2023,11,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"100166","DOI":"10.1016\/j.chbr.2021.100166","article-title":"The CT-cube: A framework for the design and the assessment of computational thinking activities","volume":"5","author":"Piatti","year":"2022","journal-title":"Comput. Hum. Behav. Rep."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/1118178.1118215","article-title":"Computational thinking","volume":"49","author":"Wing","year":"2006","journal-title":"Commun. ACM"},{"key":"ref_3","unstructured":"Seehorn, D., Carey, S., Fuschetto, B., Lee, I., Moix, D., O\u2019Grady-Cunniff, D., Owens, B.B., Stephenson, C., and Verno, A. (2011). CSTA K\u201312 Computer Science Standards: Revised 2011, Association for Computing Machinery."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1145\/1929887.1929905","article-title":"Bringing Computational Thinking to K-12: What is Involved and What is the Role of the Computer Science Education Community?","volume":"2","author":"Barr","year":"2011","journal-title":"ACM Inroads"},{"key":"ref_5","unstructured":"Poulakis, E., and Politis, P. (2021). Research on E-Learning and ICT in Education: Technological, Pedagogical and Instructional Perspectives, Springer International Publishing."},{"key":"ref_6","unstructured":"Futschek, G. (2006). Informatics Education\u2014The Bridge between Using and Understanding Computers, Springer."},{"key":"ref_7","unstructured":"Adorni, G., and Piatti, A. (2023). The virtual CAT: A tool for algorithmic thinking assessment in Swiss compulsory education. Int. J. Child-Comput. Interact., submitted."},{"key":"ref_8","unstructured":"Adorni, G., Piatti, S., and Karpenko, V. (2023). virtual CAT: An app for algorithmic thinking assessment within Swiss compulsory education. SoftwareX, submitted."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"38","DOI":"10.3102\/0013189X12463051","article-title":"Computational Thinking in K\u201312","volume":"42","author":"Grover","year":"2013","journal-title":"Educ. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1007\/s42979-021-00592-x","article-title":"Machine Learning: Algorithms, Real-World Applications and Research Directions","volume":"2","author":"Sarker","year":"2021","journal-title":"SN Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Mukhamediev, R.I., Popova, Y., Kuchin, Y., Zaitseva, E., Kalimoldayev, A., Symagulov, A., Levashenko, V., Abdoldina, F., Gopejenko, V., and Yakunin, K. (2022). Review of Artificial Intelligence and Machine Learning Technologies: Classification, Restrictions, Opportunities and Challenges. Mathematics, 10.","DOI":"10.3390\/math10152552"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1080\/00461520.2011.611369","article-title":"The Relative Effectiveness of Human Tutoring, Intelligent Tutoring Systems, and Other Tutoring Systems","volume":"46","author":"VanLehn","year":"2011","journal-title":"Educ. Psychol."},{"key":"ref_13","first-page":"3","article-title":"The State of Educational Data Mining in 2009: A Review and Future Visions","volume":"1","author":"Baker","year":"2009","journal-title":"J. Educ. Data Min."},{"key":"ref_14","unstructured":"Russell, S.J., and Norvig, P. (2010). Artificial Intelligence a Modern Approach, Pearson."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"118221","DOI":"10.1016\/j.eswa.2022.118221","article-title":"Tracing the evolution of AI in the past decade and forecasting the emerging trends","volume":"209","author":"Shao","year":"2022","journal-title":"Expert Syst. Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"102383","DOI":"10.1016\/j.ijinfomgt.2021.102383","article-title":"Artificial intelligence in information systems research: A systematic literature review and research agenda","volume":"60","author":"Collins","year":"2021","journal-title":"Int. J. Inf. Manag."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"52026","DOI":"10.1109\/ACCESS.2023.3277953","article-title":"PHH: Policy-Based Hyper-Heuristic with Reinforcement Learning","volume":"11","author":"Udomkasemsub","year":"2023","journal-title":"IEEE Access"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s10844-021-00666-5","article-title":"An overview of machine learning techniques in constraint solving","volume":"58","author":"Popescu","year":"2021","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","article-title":"Machine learning for combinatorial optimization: A methodological tour d\u2019horizon","volume":"290","author":"Bengio","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/j.ejor.2021.04.032","article-title":"Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art","volume":"296","author":"Mohammadi","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1515\/math-2017-0029","article-title":"Learnheuristics: Hybridizing metaheuristics with machine learning for optimization with dynamic inputs","volume":"15","author":"Calvet","year":"2017","journal-title":"Open Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4018\/JCIT.2021010101","article-title":"AI in Education","volume":"23","author":"Tahiru","year":"2021","journal-title":"J. Cases Inf. Technol."},{"key":"ref_23","unstructured":"Pedro, F., Subosa, M., Rivas, A., and Valverde, P. (2019). Artificial Intelligence in Education: Challenges and Opportunities for Sustainable Development, United Nations Educational, Scientific and Cultural Organization (UNESCO). Available online: https:\/\/repositorio.minedu.gob.pe\/handle\/20.500.12799\/6533."},{"key":"ref_24","first-page":"1","article-title":"An Improved Teaching-Learning-Based Optimization Algorithm with Reinforcement Learning Strategy for Solving Optimization Problems","volume":"2022","author":"Wu","year":"2022","journal-title":"Comput. Intell. Neurosci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/j.cad.2010.12.015","article-title":"Teaching\u2013learning-based optimization: A novel method for constrained mechanical design optimization problems","volume":"43","author":"Rao","year":"2011","journal-title":"Comput.-Aided Des."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Liu, E.Z. (2023). Meta-Reinforcement Learning: Algorithms and Applications. [Ph.D. Thesis, Stanford University]. Available online: https:\/\/searchworks.stanford.edu\/view\/14784081.","DOI":"10.1007\/978-3-031-28394-9"},{"key":"ref_27","unstructured":"Kirsch, L., van Steenkiste, S., and Schmidhuber, J. (2019). Improving Generalization in Meta Reinforcement Learning using Learned Objectives. arXiv."},{"key":"ref_28","unstructured":"Kirsch, L., Harrison, J., Sohl-Dickstein, J., and Metz, L. (2022). General-Purpose In-Context Learning by Meta-Learning Transformers. arXiv."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1007\/s10479-020-03871-7","article-title":"Designing a hybrid reinforcement learning based algorithm with application in prediction of the COVID-19 pandemic in Quebec","volume":"312","author":"Khalilpourazari","year":"2021","journal-title":"Ann. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"100002","DOI":"10.1016\/j.caeai.2020.100002","article-title":"Application and theory gaps during the rise of Artificial Intelligence in Education","volume":"1","author":"Chen","year":"2020","journal-title":"Comput. Educ. Artif. Intell."},{"key":"ref_31","unstructured":"Corecco, S., and Adorni, G. CAT Optimal Hybrid Solver (1.0.0) Zenodo Software."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","article-title":"Data clustering: 50 years beyond K-means","volume":"31","author":"Jain","year":"2010","journal-title":"Pattern Recognit. Lett."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1145\/331499.331504","article-title":"Data Clustering: A Review","volume":"31","author":"Jain","year":"1999","journal-title":"ACM Comput. Surv."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Ahmed, M., Seraj, R., and Islam, S.M.S. (2020). The k-means Algorithm: A Comprehensive Survey and Performance Evaluation. Electronics, 9.","DOI":"10.3390\/electronics9081295"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1477","DOI":"10.1007\/s00521-013-1439-2","article-title":"The latest research progress on spectral clustering","volume":"24","author":"Jia","year":"2014","journal-title":"Neural Comput. Appl."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","year":"2007","journal-title":"Stat. Comput."},{"key":"ref_37","unstructured":"Ng, A., Jordan, M., and Weiss, Y. (2001). Advances in Neural Information Processing Systems, MIT Press. Available online: https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2001\/file\/801272ee79cfde7fa5960571fee36b9b-Paper.pdf."},{"key":"ref_38","unstructured":"Verma, D., and Meila, M. (2023, November 17). A Comparison of Spectral Clustering Algorithms. University of Washington Tech Rep UWCSE030501. Available online: https:\/\/sites.stat.washington.edu\/spectral\/papers\/UW-CSE-03-05-01.pdf."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by Simulated Annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1109\/101.17235","article-title":"Simulated annealing algorithms: An overview","volume":"5","author":"Rutenbar","year":"1989","journal-title":"IEEE Circuits Devices Mag."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1214\/ss\/1177011077","article-title":"Simulated Annealing","volume":"8","author":"Bertsimas","year":"1993","journal-title":"Stat. Sci."},{"key":"ref_42","first-page":"281","article-title":"Random search for hyper-parameter optimization","volume":"13","author":"Bergstra","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"ref_43","unstructured":"Andrad\u00f3ttir, S. (2014). Handbook of Simulation Optimization, Springer."},{"key":"ref_44","unstructured":"Zabinsky, Z.B. (2023, November 17). Random Search Algorithms. Department of Industrial and Systems Engineering, University of Washington, USA. Available online: https:\/\/courses.washington.edu\/inde510\/516\/AdapRandomSearch4.05.2009.pdf."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1613\/jair.301","article-title":"Reinforcement Learning: A Survey","volume":"4","author":"Kaelbling","year":"1996","journal-title":"J. Artif. Intell. Res."},{"key":"ref_46","unstructured":"Sutton, R.S., and Barto, A.G. (2018). Reinforcement Learning: An Introduction, MIT Press."},{"key":"ref_47","unstructured":"Li, Y. (2017). Deep Reinforcement Learning: An Overview. arXiv."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1038\/nature14236","article-title":"Human-level control through deep reinforcement learning","volume":"518","author":"Mnih","year":"2015","journal-title":"Nature"},{"key":"ref_49","first-page":"1928","article-title":"Asynchronous Methods for Deep Reinforcement Learning","volume":"Volume 48","author":"Balcan","year":"2016","journal-title":"Machine Learning Research, Proceedings of the 33rd International Conference on Machine Learning, New York, NY, USA, 19\u201324 June 2016"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"1291","DOI":"10.1109\/TSMCC.2012.2218595","article-title":"A Survey of Actor-Critic Reinforcement Learning: Standard and Natural Policy Gradients","volume":"42","author":"Grondman","year":"2012","journal-title":"IEEE Trans. Syst. Man Cybern. Part C (Appl. Rev.)"},{"key":"ref_51","unstructured":"Babaeizadeh, M., Frosio, I., Tyree, S., Clemons, J., and Kautz, J. (2016). Reinforcement Learning through Asynchronous Advantage Actor-Critic on a GPU. arXiv."},{"key":"ref_52","first-page":"486","article-title":"A Theoretical Analysis of Deep Q-Learning","volume":"Volume 120","author":"Bayen","year":"2020","journal-title":"Machine Learning Research, Proceedings of the 2nd Conference on Learning for Dynamics and Control, Berkeley, CA, USA, 11\u201312 June 2020"},{"key":"ref_53","unstructured":"Roderick, M., MacGlashan, J., and Tellex, S. (2017). Implementing the Deep Q-Network. arXiv."},{"key":"ref_54","unstructured":"Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal Policy Optimization Algorithms. arXiv."},{"key":"ref_55","first-page":"113","article-title":"Truly Proximal Policy Optimization","volume":"Volume 115","author":"Adams","year":"2020","journal-title":"Machine Learning Research, Proceedings of the 35th Uncertainty in Artificial Intelligence Conference, Tel Aviv, Israel, 22\u201325 July 2019"},{"key":"ref_56","unstructured":"Arthur, D., and Vassilvitskii, S. (2007, January 7\u20139). K-Means++: The Advantages of Careful Seeding. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA. Available online: https:\/\/theory.stanford.edu\/~sergei\/papers\/kMeansPP-soda.pdf."},{"key":"ref_57","unstructured":"Kocsis, L., and Szepesv\u00e1ri, C. (2006). Lecture Notes in Computer Science, Springer."},{"key":"ref_58","unstructured":"Solla, S., Leen, T., and M\u00fcller, K. (December, January 29). Policy Gradient Methods for Reinforcement Learning with Function Approximation. Proceedings of the 12th International Conference on Advances in Neural Information Processing Systems, Denver, CO, USA. Available online: https:\/\/proceedings.neurips.cc\/paper_files\/paper\/1999\/file\/464d828b85b0bed98e80ade0a5c43b0f-Paper.pdf."},{"key":"ref_59","first-page":"12348","article-title":"Stable-baselines3: Reliable reinforcement learning implementations","volume":"22","author":"Raffin","year":"2021","journal-title":"J. Mach. Learn. Res."},{"key":"ref_60","unstructured":"Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016). OpenAI Gym. arXiv."},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/s11257-011-9106-8","article-title":"A review of recent advances in learner and skill modeling in intelligent learning environments","volume":"22","author":"Desmarais","year":"2011","journal-title":"User Model. User-Adapt. Interact."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1080\/10494820.2018.1558257","article-title":"Intelligent tutoring systems: A systematic review of characteristics, applications, and evaluation methods","volume":"29","author":"Mousavinasab","year":"2018","journal-title":"Interact. Learn. Environ."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1080\/14703297.2016.1189346","article-title":"SITS: A solution-based intelligent tutoring system for students\u2019 acquisition of problem-solving skills in computer programming","volume":"55","author":"Hooshyar","year":"2016","journal-title":"Innov. Educ. Teach. Int."}],"container-title":["Machine Learning and Knowledge Extraction"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2504-4990\/5\/4\/82\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:26:34Z","timestamp":1760131594000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2504-4990\/5\/4\/82"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,20]]},"references-count":63,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["make5040082"],"URL":"https:\/\/doi.org\/10.3390\/make5040082","relation":{},"ISSN":["2504-4990"],"issn-type":[{"value":"2504-4990","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,20]]}}}