Algorithm - Help please.

[imcram]

I think (for the lack of any better idea) that the attractor scenario needs a really
accurate quantification, i,e, the actual numbers you assign for the actual forces
with which objects 'attract' because you don't want your robot standing still with
a dead battery near the destination location and being 'ah, to bad, it was nearly optimal'.

I don't have any better ideas (yet?) though ... Here's another question: do you
*know* that there are so many yellow objects available no matter the space
ship layout? Or could it be that the entire space ship happens to be empty?

kind regards,

Jos

U seem to be interested in the thing. Well, u can get an idea of it coz there is a method which returns the actual package counts. It says how many yellow, pink, brown, black and battery packs in the spaceship. The numbers vary from map to map.

[imcram]

I think (for the lack of any better idea) that the attractor scenario needs a really
accurate quantification, i,e, the actual numbers you assign for the actual forces
with which objects 'attract' because you don't want your robot standing still with
a dead battery near the destination location and being 'ah, to bad, it was nearly optimal'.

I don't have any better ideas (yet?) though ... Here's another question: do you
*know* that there are so many yellow objects available no matter the space
ship layout? Or could it be that the entire space ship happens to be empty?

kind regards,

Jos

U seem to be interested in the thing. Well, u can get an idea of it coz there is a method which returns the actual package counts. It says how many yellow, pink, brown, black and battery packs in the spaceship. The numbers vary from map to map. But, the package counts and heights are different, and there is no way to find out the total height of yellow packs at the start.

[JosAH]

U seem to be interested in the thing.

It is an interesting little problem. I gave it some more thoughts and IMHO the
attractors thingy is no good at all because your robot has to explore (part of)
the space ship first.

Here are some more questions//thoughts:

1) will it always be possible to explore the entire space ship first given the
number of spare batteries (known up front)?

2) It is possible to calculate the minimum amount of energy to reach that
safe spot, no matter the profit of the payload. I guess a complete failure
(dead batteries) is worse than a return to that safe spot empty handed?

3) (thinking while writing) there are two extreme strategies: explore the entire
space ship first and then try to be smart or, start running like a madman and
(given that you can get back to the safe spot) then return.

4) IMHO both extremes are far out. The first is a constructive method that plays
it safe all the time while the second method is no better than any random
strategy.

5) if it is possible to investigate the entire ship plus take all the loot using the
battery plus the spare batteries, the full investigation method would be feasible.

6) Local search heuristics come to mind. An LSM uses its partial knowledge
the best it can, e.g. there's enough power left to safely return and there's
a profitable payload detected. Calculate whether or not a safe return will be
possible *with* the payload; if so, grab it and see how much power is left for
further investigation. Otherwise don't grab it and how much further
investigation is possible.

7) If a spare battery is spotted; calculate whether or not it needs to be grabbed now
(if your robot has (nearly) full batteries on board, just remember the spot of
the spare battery and consider it a safe path home to the final safe spot.

Those LSMs are analogous to you skiing in the mountains while suddenly
it gets foggy: you want to go down but can't see anything. You can apply a
'steepest descent' but you stand the risk then of ending up in some local
minimum. You could also register the little information you have and start your
descent in little steps. The recorded information allows you to get back from
where you started (or any non-fatal pit) and try again.

I think those shortest path things are far out because of the incomplete
information at the start of the game.

kind regards,

Jos

[imcram]

It is an interesting little problem. I gave it some more thoughts and IMHO the
attractors thingy is no good at all because your robot has to explore (part of)
the space ship first.

Here are some more questions//thoughts:

1) will it always be possible to explore the entire space ship first given the
number of spare batteries (known up front)?

2) It is possible to calculate the minimum amount of energy to reach that
safe spot, no matter the profit of the payload. I guess a complete failure
(dead batteries) is worse than a return to that safe spot empty handed?

3) (thinking while writing) there are two extreme strategies: explore the entire
space ship first and then try to be smart or, start running like a madman and
(given that you can get back to the safe spot) then return.

4) IMHO both extremes are far out. The first is a constructive method that plays
it safe all the time while the second method is no better than any random
strategy.

5) if it is possible to investigate the entire ship plus take all the loot using the
battery plus the spare batteries, the full investigation method would be feasible.

6) Local search heuristics come to mind. An LSM uses its partial knowledge
the best it can, e.g. there's enough power left to safely return and there's
a profitable payload detected. Calculate whether or not a safe return will be
possible *with* the payload; if so, grab it and see how much power is left for
further investigation. Otherwise don't grab it and how much further
investigation is possible.

7) If a spare battery is spotted; calculate whether or not it needs to be grabbed now
(if your robot has (nearly) full batteries on board, just remember the spot of
the spare battery and consider it a safe path home to the final safe spot.

Those LSMs are analogous to you skiing in the mountains while suddenly
it gets foggy: you want to go down but can't see anything. You can apply a
'steepest descent' but you stand the risk then of ending up in some local
minimum. You could also register the little information you have and start your
descent in little steps. The recorded information allows you to get back from
where you started (or any non-fatal pit) and try again.

I think those shortest path things are far out because of the incomplete
information at the start of the game.

kind regards,

Jos

Your ideas are interesting.

1. The size of the spaceship is not known at the start. Though you can get some idea about it by the package counts, it is by no means accurate. So, it is impossible to say whether it'd be possible to explore the whole spaceship and still have enough battery to get the best loot home. Sometimes you do not want to search the whole ship. If the total height of yellow packs you found exceed 120, there is no need to search fr more as 120 is the capacity of the robot. That's just one of the situations where u do not want to search everything. The number of spare batteries is known upfront, but this does not have much impact as the battery packs can only provide a maximum of 500 battery life boost. And as the starting battery life is in hundreds of thousands, battery packs do not have any impact on the game.

2. Yep.

3. The first idea is way better. But you won't get to or have to explore the whole ship most of the time.

7. As I said, spare batteries don't play a part.

Shortest paths are not far out. You can keep the information you have gained in your own map. And that map will help to calculate the paths to safety or into the fray. ex : The squares lying between two explored and unexplored areas can be marked as the boundaries of the known world. And, if the batteries permit further exploration, a boundary will be the first spot the bot should consider going to. To tis extent, boundaries are like attractors.

The most crucial thing though is knowing when to stop. Keeping all the packages you find onboard is not an option as this prohibits the bot greately. So, periodically the bot has to drop its belongings one way or another. And my problem still stands. How do you find the lowest cost path which visits all these dropoff points and reaches the starting point in the end?