# Strategic planning and multi dimensional knapsack problem

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?

• It might help to divide the knowledge vector by the effort - this way you know how much knowledge per effort an article gives you. – user6916458 Oct 30 '17 at 10:53
• Very well structured and interesting question. Welcome to AI! – DukeZhou Oct 31 '17 at 17:47
• Is addition of the vectors so they sum to the knowledge vector the only criterion? If so, you're problem seem to be a multi-dimensional case of the coin problem en.wikipedia.org/wiki/Coin_problem msp.org/involve/2011/4-2/involve-v4-n2-p07-p.pdf – Daniel Feb 18 '18 at 0:20
• Could you clarify that you don't want critique of the "learning of new material" model (which IMO seems an unusual way to model acquiring knowledge, whilst the goal of attaining an arbitrary score within the model is more well-defined)? I don't think you do from what is written, but now this has been bumped up to the top, it is possible that someone will respond to that, and not to the knapsack problem presented – Neil Slater Apr 30 '19 at 11:42

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.