Algorithm - Help please.

[imcram]

Hi,
I want an algorithm that will provide the best path given a set of nodes. However, I have been unable to come up with a solution though I have tried for some time now. I want to know whether this can even be done. Here are my needs.

1. I have a set of nodes, usually about, 20 nodes.
2. Every node is connected to each other and I know all the initial weights.
3. I have to visit every node exactly once in the path. However, there is a special node that can be visited any number of times in the path.
4. The cost of travelling between two nodes are dynamic. Say the weigths S->A is 10 and A->B is 25. Now, if I were to take the path S->A->B, it would cost me not 10 + 25 = 35, but, 10 + (10 + 25) = 45. That is, you carry the last weights with you. So, as soon as you travel S->A, the weights of the edges connected to A are incremented by 10 (the cost of S->A.)
This is the cause of the headache for me. if this wasn't the case, applying Dijkstra's algorithm would have solved the problem. But because of this reason, I can't eliminate any path just by looking at the cost so far.

5. As soon as the path reachs the special node, say G, all the weights are reset to their original weights.

So, can anyone tell me an algorithm for this? I would be very greatful. Thank you.

[JosAH]

4. The cost of travelling between two nodes are dynamic. Say the weigths S->A is 10 and A->B is 25. Now, if I were to take the path S->A->B, it would cost me not 10 + 25 = 35, but, 10 + (10 + 25) = 45. That is, you carry the last weights with you. So, as soon as you travel S->A, the weights of the edges connected to A are incremented by 10 (the cost of S->A.)

Can you elaborate on this 'rule' a bit more? What if the path has three vertexes,
say S --> A --> B with individual edge costs equal to 10, 25 and 15. What would
the cost of the path be?

Second: is the starting vertex fixed?

kind regards,

Jos

[imcram]

Can you elaborate on this 'rule' a bit more? What if the path has three vertexes,
say S --> A --> B with individual edge costs equal to 10, 25 and 15. What would
the cost of the path be?

Second: is the starting vertex fixed?

kind regards,

Jos

Yes, the starting node is fixed.

Ok, lets say that we have four edges. S, A, B, C

At the beginning, this is how the weights stand:

S->A 10
A->B 25
B->C 15

We are not concerned about the other edges at the moment, so we do not need their weights for this example.

Now, if we were to take the path S->A->B->C, the total cost will be,

S->A A->B B->C

10 + (10) + 25 + ((10) + 25) + 15

so, total cost = 10 + (10 + 25) + ((10) + 25) + 15 = 95.

Hope that cleared up. It's like the weights accumulate when we visit a node. So, we have to carry all those past "sins" with us as well.

[imcram]

Can you elaborate on this 'rule' a bit more? What if the path has three vertexes,
say S --> A --> B with individual edge costs equal to 10, 25 and 15. What would
the cost of the path be?

Second: is the starting vertex fixed?

kind regards,

Jos

Yes, the starting node is fixed.

Ok, lets say that we have four edges. S, A, B, C

At the beginning, this is how the weights stand:

S->A 10
A->B 25
B->C 15

We are not concerned about the other edges at the moment, so we do not need their weights for this example.

Now, if we were to take the path S->A->B->C, the total cost will be,

S->A A->B B->C

10 + (10) + 25 + ((10) + 25) + 15

so, total cost = 10 + (10 + 25) + ((10) + 25) + 15 = 95.

Hope that cleared up. It's like the weights accumulate when we visit a node. So, we have to carry all those past "sins" with us as well.

Ah, the end node is fixed as well. it is the special node G.

[JosAH]

Allow me to summarize; please correct me if I'm wrong:

1) the start and end nodes are fixed;
2) there's one special node (distinct from the start and end nodes?)
3) every node should be visited exactly once except for that special node;
4) the costs of all edges are reset when the special node is visited.

Is that right? May I ask you a question: where does that problem come from?

kind regards,

Jos

[imcram]

Allow me to summarize; please correct me if I'm wrong:

1) the start and end nodes are fixed;
2) there's one special node (distinct from the start and end nodes?)
3) every node should be visited exactly once except for that special node;
4) the costs of all edges are reset when the special node is visited.

Is that right? May I ask you a question: where does that problem come from?

kind regards,

Jos

If u really want to know, try this :

http:\\www.marc.lk

If u've read the overview, perhaps u may be able to deduce what i am trying to do. I'll tell u how it came to this.
I programmed my bot so it will drop everything it is carrying when the package count it carries hits a certain value. So, I have multiple dropoff points when the robot decides that time's up (The number of dropoff points rarely exceed 20). So, the drpoff points are the nodes. I can use Dijkstra's (A* is bad coz we have teleport beams.) algorithm to check for the distances between each and every pair of nodes. And I have to bring all the goodies home. Currently, my bot is not doing a bad job of it. But, it would perform way better if I could program it to find the best path. That's where the problem comes from. Unfortunately I have been unable to find adequate resources on the internet about pathfinding when there are time & space variant weights. (As u can see, the only things I have been able to find are these words for it.). Anyway, I appreciate it if u could help. Thanx.

And about your query:

The special node is the end node.

[r035198x]

Just subscribing to it.

Sounds interesting.

[r035198x]

If u really want to know, try this :

http:\\www.marc.lk

If u've read the overview, perhaps u may be able to deduce what i am trying to do. I'll tell u how it came to this.
I programmed my bot so it will drop everything it is carrying when the package count it carries hits a certain value. So, I have multiple dropoff points when the robot decides that time's up (The number of dropoff points rarely exceed 20). So, the drpoff points are the nodes. I can use Dijkstra's (A* is bad coz we have teleport beams.) algorithm to check for the distances between each and every pair of nodes. And I have to bring all the goodies home. Currently, my bot is not doing a bad job of it. But, it would perform way better if I could program it to find the best path. That's where the problem comes from. Unfortunately I have been unable to find adequate resources on the internet about pathfinding when there are time & space variant weights. (As u can see, the only things I have been able to find are these words for it.). Anyway, I appreciate it if u could help. Thanx.

And about your query:

The special node is the end node.

Hey can you check the link again it says domain name does not exist.

[JosAH]

This one works: http://www.marc.lk/index.php

kind regards,

Jos

[Banfa]

You have said you need to calculate the "best" path but you have not said how you are qualifying a path as "best".

Is there a limit to the number of steps you take or is it solely on final score.

You have not actually said if you are trying to minimise or maximise the score. However I assume minimise because the solution for maximise is trivial (go to nodes in order largest to smallest only visiting node G at the end).

It is not clear how node G effects the score, listing nodes as ID(score) what would this path score

S -> A(10) -> B(20) -> G -> C(30)

?

[JosAH]

You have said you need to calculate the "best" path but you have not said how you are qualifying a path as "best".

Is there a limit to the number of steps you take or is it solely on final score.

You have not actually said if you are trying to minimise or maximise the score. However I assume minimise because the solution for maximise is trivial (go to nodes in order largest to smallest only visiting node G at the end).

It is not clear how node G effects the score, listing nodes as ID(score) what would this path score

S -> A(10) -> B(20) -> G -> C(30)

?

I just read the link the OP suppplied: it's about maximizing profits; the trouble
is that the cost/profit model is not linear, i.e. the profit is defined on the vertexes
while the edges contain the costs. The profits become costs again if the profit
has been 'taken'. I don't have a cookbook solution for this problem, I have to
give it some more thoughts ...

Even worse, this problem involves two phases: investigation of the solution space
(which comes with its own costs) and the 'harvesting' phase, collecting the
profits. Both phases can be merged of course.

At this very moment I'm thinking of 'attractors' but I don't know (yet?) how to
make this idea operational.

kind regards,

Jos

[imcram]

I just read the link the OP suppplied: it's about maximizing profits; the trouble
is that the cost/profit model is not linear, i.e. the profit is defined on the vertexes
while the edges contain the costs. The profits become costs again if the profit
has been 'taken'. I don't have a cookbook solution for this problem, I have to
give it some more thoughts ...

Even worse, this problem involves two phases: investigation of the solution space
(which comes with its own costs) and the 'harvesting' phase, collecting the
profits. Both phases can be merged of course.

At this very moment I'm thinking of 'attractors' but I don't know (yet?) how to
make this idea operational.

kind regards,

Jos

I do apologise, but I am looking at ur post and I do not understand all the jargon. However, I thank u all for ur concern. As it stands, even if I do get the answe from one of u to my problem, I think I will not be able to implement it in a day(There is a deadline, and it is tommorrow midnight & me being the snail I am I'll never get it done in time.). However, I would still like to know the answer to this problem sooner or later coz it really interests me.

So, I should clear it up a bit more.

The bot can carry packages. And each of the nodes are drop off points having various packages. So, at one point in time, the bot decides that it's had its share of exploring for the day and decides to go home with all the packages. The goal is to get the best packages to the starting point(G). Once the bot arrives at the starting point, there is no point in carrying the packs anymore, so it drops everything. So, once the robot arrives at the starting point, it does not have storage anymore. This is good as there is a penalty in battery cost for moving with packages onboard. (I hope I am not obscuring things even more.) That is why all the weights reset once the "special node" is visited.
So we have the distance between two nodes, the distance has to be multiplied by the battery life needed to move per unit length to find out the weight of the edge. The battery life required for unit length depends upon the number of packages the bot is carrying. Thus, it depends on the history of the path as the bot picks up packages at every node except G. So, I can't find out the lowest cost path which will visit all the nodes once(except G), and end with G. I don't think brute force is feasible, right?

Anyway, thanx.

Ah, and what are "attractors"?

[JosAH]

Ah, and what are "attractors"?

Consider them little magnets, i.e. they attract the robot. The more profit can
be collected, the harder they "attract". The farther away from the robot the
less they attract. The lower the battery level the more a fresh battery attracts.

The trouble with those attractors is (in contrast to real magnets) that there
can be an equilibrium in which the robot just moves a bit back and forth
without really being able to make a decision. The behaviour all depends on
how you define the attracting forces.

kind regards,

Jos

ps. I don't know whether or not attractors are the/a solution; it was just an idea
that came up when I read the problem description in the link you supplied.

[imcram]

Consider them little magnets, i.e. they attract the robot. The more profit can
be collected, the harder they "attract". The farther away from the robot the
less they attract. The lower the battery level the more a fresh battery attracts.

The trouble with those attractors is (in contrast to real magnets) that there
can be an equilibrium in which the robot just moves a bit back and forth
without really being able to make a decision. The behaviour all depends on
how you define the attracting forces.

kind regards,

Jos

ps. I don't know whether or not attractors are the/a solution; it was just an idea
that came up when I read the problem description in the link you supplied.

Ah, so u r talking about the whole big thing. OK. I think attractors would work better if u knew the whole scenario. Right? The map is not known at the start, it will only reveal itself when/if the bot explores. So, I guess unexplored areas are attractors themselves. attractors saying "explore me!". But I am not sure as to how much help they'd be in the exploration period. Ah, wait, perhaps the idea is very useful.
Anyway, I am thinking whether attractors can be used for the finishing manouver, which in my case is collecting packages and bringing them home. Plz let me know if u have any ideas on this.

[JosAH]

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

[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?