Strategic planning and multi dimensional knapsack problem

Question

I'm trying to find a planning approach to solve a problem that attempts to model learning of new material. We assume that we only have one resource such as Wikipedia, which contains a list of articles represented as a vector of knowledge it contains and an effort to read that article.

Knowledge vector and effort

Before we start, we set a size for the vector, depending on the number of different types of knowledge. For example, we can define the items in the vector to be (algebra, geometry, dark ages), and then 'measure' all the articles from this point of view. So, a math article will probably be (5,7,0), since it will talk a lot about algebra and geometry but not about the dark ages. It will also have an effort to read it, which is simply an integer.

Problem

Given all the articles (represented as knowledge vectors with an effort), we want to find the optimal set of articles that help us to reach a knowledge goal (also represented as a vector).

So, a knowledge goal can be (4,4,0), and it's enough to read an article (2,1,0) and (2,3,0), since, when added, it adds up to the knowledge goal. We want to do this with minimal effort.

Question

I've tried to some heuristics to find an approximation, but I was wondering if there is any state of the art strategic planning method that can be used instead?

Answer 1

Here is a speculative cast of the problem to a travelling salesman problem, which would lead to shortest-path algorithms.

Please note this idea suggests different constraints to explore.

• Given the knowledge vectors and efforts, build a acyclic directed graph (acyclic, as we are not supposed to unlearn). A vertex is an article, represented by its knowledge vector. An edge links two articles, weighted by the effort to "move" to the target article/vertex (i.e. acquire the knowledge of that article).
• Assign a zero vector to a new participant. That is the starting point on the graph is vertex V0 = (0, ..., 0).
• Define a learning objective as a vector V.
• Use a shortest-path algorithm to find a (V0, V) plan.

This procedure is insufficient, as there are many ways to build the graph (in other words, the above is completely pointless as is). Extra constraints are necessary to make it practical. For example, we can order the vertices by ordering them along each dimension. Such setting would lead learners to start with "easy" articles (V[i] is low), and move step by step toward more complex topics ((V[i] gets higher).

The graph construction depends on the data available. For example, are knowledge vectors "absolute", or can they be relative? Relative can help in creating a path, as moving from V to W requires an effort that depends on your learner's initial conditions (V0 may not be 0 everywhere, afterall).

---

Is it an AI question? Definitely.