2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The time between actions is a global constant, or it depends on the actions? $\endgroup$ – Eugen Oct 31 '18 at 8:27
  • $\begingroup$ The time between actions depends on the actions, i.e different edges connecting actions take different time $\endgroup$ – Sridhar Thiagarajan Nov 1 '18 at 1:08
4
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ The problem is the sequentiality, transitioning between actions takes a finite amount time (different from each pair). I cannot find a way to encode this into the knapsack problem. Sorry I did not mention this, edited into the question now. $\endgroup$ – Sridhar Thiagarajan Oct 30 '18 at 22:33
2
$\begingroup$

This problem is an instance of the Orienteering problem, a combination of the knapsack and the travelling salesman.

A good survey is https://www.sciencedirect.com/science/article/pii/S0377221710002973

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.