quote:Original post by Samith
Timkin: If I'm following you correctly, you are telling me I need to check all neighboring nodes to see if their g costs are lower, otherwise it won't find the fastest path.

Err, no, I don't believe I was saying that... but then I'm not sure what you're saying here... so I can't be certain that I wasn't saying what I think you thought I was saying. Confused? I am!



Anyway...

What I was saying was that assume you are expanding child nodes from your current node and it happens that one of these new nodes already appears in your closed list. This is a common problem with searches on regular grids/lattices. You've computed the path cost of that child node through its parent and find that this is a lower cost for that node than the path cost listed for that node in the closed list. This can happen because these two instances of the same node have different parents, representing different paths to this node. You need to decide which path to keep. Obviously you go with the path with the lower of the two costs. IF that happens to be the new node you generated, you need to look at the subtree below the node that is in the closed list, because you're about to tell that entire subtree that to get to the subtree, you need to go through a different parent node (the parent of the newly generated node, not the old one in the closed list). Since getting to the current node costs less than getting to the node in the closed list, then all the costs in the subtree below the old node need to be updated... AND, you need to tell each of the children of the old node that their parent is now the new node. This operation is called splicing. Essentially you've disconnected the subtree from the old node, stuck it under the new node, updated the subtree costs and deleted the old node (because we don't need it any more).

I hope this makes sense.

Cheers,

Timkin

[edited by - Timkin on June 2, 2004 3:31:24 AM]

Timkin; I agree with you on the expense, but most implementations of A* I have seen don''t maintain the information you would need to do this.

Most implementations I have looked at have a pointer from a node to the parent. To propagate the costs as you are suggesting, wouldn''t the parent need to also have a pointer to all of its children?

Do you have any references to implementations that do this? I am very curious about the complexity difference. I believe most of the AI Gem implementations just reopen the node.

Timkin: That is what I was saying, pretty much. I think we''re mixing terminologies and implementations though. In my implementation, the nodes don''t exactly have children, the "children" I guess are just all the nodes adjacent to it. There is no real tree structure. Each node does, however, have a parent, which is a node adjacent to it with the lowest g cost.

So in my old implementation, when you were searching through all the neighbors of a node, one of them, obviously, has to be in the closed list, this would most likely be the node you searched previous to the current node, so it would be the parent. Now in the old implementation, I would skip nodes in the closed list and only update the g cost of a node in the open list. In the new implementation, after taking your advice, I made the program also update the g cost of nodes in the closed list.

It''s kind of hard for me to explain since I''m not really used to the terminology, but whatever I''m doing, it''s working and it''s working well, and I''m doing it the way I am because of what you said.

quote:Original post by BrianL
Timkin; I agree with you on the expense, but most implementations of A* I have seen don''t maintain the information you would need to do this.

Most implementations I have looked at have a pointer from a node to the parent. To propagate the costs as you are suggesting, wouldn''t the parent need to also have a pointer to all of its children?

Whether you explicitly realise it or not the tree structure is there... ask yourself how do you generate the successor nodes of any given node in the first place, when you want to work out which nodes to open? The search space, which is a tree structure, is defined by the set of actions that can be executed in each node (the transitions) which define the directed edges between nodes. So, no matter how you represent it, the tree is there, even if you don''t explicity store a set of pointers to child (successor/neighbour) nodes. You MUST have a function that identifies successor nodes from any given node. If you have a tree, you know whether the node is open or closed by whether it is a branch or leaf node. If you don''t represent the tree with pointers (but generate successors via a function applied to the node) then you store within the node whether it is open or closed or never seen before (which is actually more information). Clearly you could apply this successor-identifying function to all neighbouring nodes (successors of the current node) to find the subtree, adjusting the costs as you go.

As for implementations that use this... plenty... I have code of my own that does this... and indeed, most implementations of search I have looked at throughout my career have started with the premise of a search tree data structure, or a graph structure of some form (for example, when implementing Dijkstra''s algorithm). There is a tradeoff between the extra memory required to store the tree and the extra computation it takes to generate subtrees whenever you have to perform splicing... but the memory method wins out, since we''re only storing pointers and that''s trivial.

Samith, we are talking about the same thing... it''s just that internal representations are probably different between our methodologies... which can lead to confusion... sorry if I contributed to this in any way. I''m very glad to hear that your search is working properly!

Cheers,

Timkin

Thank you for pointing out my blindness there. You are right; getting the children of the node is trivial. I wasn't thinking about the search space when you mentioned the splice; I was thinking about the node structure storing the shortest path through back pointers.

Very good explaination, thank you!

[edited by - BrianL on June 2, 2004 11:43:51 PM]