3
$\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?

Improve this question
$\endgroup$
2
  • $\begingroup$ The time between actions is a global constant, or it depends on the actions? $\endgroup$
    – Eugen
    Oct 31, 2018 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, 2018 at 1:08

2 Answers 2

Reset to default
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.)

Improve this answer
$\endgroup$
1
  • $\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, 2018 at 22:33
3
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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