Traversing a graph in finite time, maximizing utility I am working on a problem in robotics, where we have a problem of having finite time horizon T, and a set of actions. Each take some time to perform and each have a utility. We can transition from any action to another after completing that particular action, and each transition takes a unique, finite time. Our goal is maximize the sum of the utilities after the time horizon has ended. 

I am currently thinking of this as a graph problem, and have some trouble formalizing it. 

Let the nodes be the actions, and the edges be the transition between the actions. Each node have some value, and take some time T. How do I find the path in this graph which maximizes the utility, and takes time less than or equal to T?
I think this is the knapsack problem, with the following correspondences:


item: activity
item weight: activity performance time
item value: activity utility
knapsack maximum weight: finite time horizon T


One solves it using dynamic programming.

(I don't think a graph model would be useful here, as it does not seem easy to encode the problem into a standard graph problem.)