Document Type
Article
Publication Date
10-18-2024
Abstract
E-learning courses often suffer from high dropout rates and low student satisfaction. One way to address this issue is to use personalized learning paths (PLPs), which are sequences of learning materials that meet the individual needs of students. However, creating PLPs is difficult and often involves combining knowledge graphs (KGs), student profiles, and learning materials. Researchers typically assume that the problem of creating PLPs belong to the nondeterministic polynomial (NP)-hard class of computational problems. However, previous research in this field has neither defined the different variations of the PLP problem nor formally established their computational complexity. Without clear definitions of the PLP variations, researchers risk making invalid comparisons and conclusions when they use different metaheuristics for different PLP problems. To unify this conversation, this article formally proves the NP-completeness of two common PLP variations and their generalizations and uses them to categorize recent research in the PLP field. It then presents an instance of the PLP problem using real-world data and shows how this instance can be cast into two different NP-complete variations. This article then presents three artificial intelligence (AI) strategies, solving one of the PLP variations with back-tracking and branch and bound heuristics and also converting the PLP variation instance to XCSP${}^{3}$, an intermediate constraint satisfaction language to be resolved with a general constraint optimization solver. This article solves the other PLP variation instance using a greedy search heuristic. The article finishes by comparing the results of the two different PLP variations.
Source Publication
IEEE Transactions on Artificial Intelligence ( eISSN 2691-4581)
Recommended Citation
S. A. Mochocki, M. G. Reith, B. J. Borghetti, G. L. Peterson, J. D. Jasper and L. D. Merkle, "Personalized Learning Path Problem Variations: Computational Complexity and AI Approaches," in IEEE Transactions on Artificial Intelligence, vol. 6, no. 3, pp. 574-588, March 2025, doi: 10.1109/TAI.2024.3483190.
Comments
This article was fully published online in October 2024 ahead of inclusion in an issue. It subsequently appeared in the March 2025 issue of IEEE Transactions on Artificial Intelligence, as cited below.
The dataset associated with this research is available by clicking here.
© 2024 The Authors.
This article is published by IEEE, licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Sourced from the published version of record in accordance with CC BY.