1
$\begingroup$

I am faced with a problem, that I'm pretty sure is a statistical one, but me taking 1 course in probability followed by 1 course in statistics back in university did not prepare me to adequately face it. With that in mind, while a R-based sample code is always helpful and appreciated, what I'm really after is some directions to learn about the problem at large. At the moment I'm at a stage where I'm not really sure what keywords to plug into google :)

So here is the set up (fully computerized simulation, even though objects might suggest physical entities).

  • I have a bunch of robots
  • The robots share power supply (this is the point of optimization)
  • Robots are not identical (further complicates optimization)
  • These robots perform various tasks
  • The tasks have value assigned to them. Once the task is complete by a robot I can tell how much benefit that brought, but I can't know it ahead of time.
  • I have a series of heuristics (H1, H2, ..., Hn) that try to approximate the real performance of a task before it is completed. I use these to decide which task a given robot should perform, obviously these are inaccurate.

From simulations ignoring the shared power supply I have:

  • Series representing the true performance of each robot (by letting each robot just do a bunch of tasks, exhaustive enumeration is impossible, so a sampling of possible tasks is used instead)
  • Series representing the total system performance (all individual robot performances combined)
  • Series corresponding to each heuristic function (a perfect heuristic would be identical to the true performance series, but I don't have one like that)

So what I want to establish are the following 2 things:

  1. Decide which heuristic functions are better at predicting future performance based on how they did in the simulation window (could be individual functions or combination). The problem here is that it's not a simple combination, since H1 can have values in [0, 1] and H2 in thousands.
  2. Decide power allocations % for each robot. In real use I'd like to make sure that I use the guiding heuristics (from #1) that ensures that each robot brings the most benefit. I intend to achieve this by insuring that the robot with the most accurate heuristics and the highest predictions of future performance gets the most power. But how much more power? How should I split it? This is the ultimate problem I need to solve.
Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
+50
$\begingroup$

Very interesting question Alex!

Part 1
First, I would suggest normalizing all the heuristics and outcome to return a value in [0,1]. If you know the properties of these values, you could use log and divide by the max available value.

Next, you want to build a model that maps the heuristics to an expected outcome. I would use a series of vectors based on your simulation to derive $f(H_1, H_2, .. H_n) = y$. You could use either regression analysis or SVM light if you want to be fancy.

Quick tip: If you believe the relationship between the heuristics can be more complex, you can create combination variables in the form of $(H_i \times H_j)$ to feed to your SVM.

Part 2
Once you have established a good heuristic function, it sounds like your next goal is given a fixed amount of power, to maximize the derived value. So in a sense your problem of power allocation % is the same as before, with a $y$ defined as overall system value. For this one I would recommend using linear solver with some constraints (i.e. power allocation can not be negative, and total amount to 100%) for getting the best values for each robot.

I would love to hear more details about what exactly are you trying to do, and possibly refine my answer based on that.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What kind of details would you find helpful? The question is pretty much complete as I understand the problem. Due to shared and finite power, it is suboptimal to have too many robots run at once, but robots are not identical in terms of their aptitude at a task, so I don't want to just pick a few. I need to assign robots power, based on how much they can contribute. So they get the most work done, before power runs out. $\endgroup$
    – Alex K
    Commented Oct 31, 2011 at 22:07
  • $\begingroup$ also what do you mean by H2xH2? $\endgroup$
    – Alex K
    Commented Oct 31, 2011 at 22:24
  • $\begingroup$ H2 x H2 was a mistake. I meant the cross function of any $H_i \times H_j$. This will allow the regression or SVM to come up with a combination weight for two heuristics together. So just to clarify your other comment, does it mean a couple of robots can not work at the same time. Meaning only one robot gets 100% of the power at a given time? $\endgroup$
    – Erad
    Commented Oct 31, 2011 at 23:00
  • $\begingroup$ Several robots can work at the same time. The only thing I know for sure is that having them all work all the time is a universally bad idea. So I run simulations on each robot (of different aptitude) against a sampling of tasks (of different difficulty/reward) and I seek to pick out the robots that are most useful to run, and how much power to give to each one (which is time it's active). The objective is not to exercise every robot or to accomplish all tasks, but to be as productive as possible before the power runs out. $\endgroup$
    – Alex K
    Commented Nov 1, 2011 at 4:50

Your Answer

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

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