5
$\begingroup$

I'm looking at Wikipedia's pseudocode implementation of A* and found myself wondering about what they call openSet. That is, the neighbours we've seen, but not yet analyzed.

The first part of the outer loop reads:

 current := the node in openSet having the lowest fScore[] value

And this makes sense to me, as I intuitively think of openSet as a heap. So we just pop() and get whatever's most interesting to look at next.

But when looping through the neighbours in the inner loop, this happens:

 if neighbor not in openSet // Discover a new node
                openSet.Add(neighbor)

And obviously, that's not going to go well with a heap. So what I'm wondering is this:

How is this contains() check meant to be carried out? Am I supposed to use something like an AVL tree to get logarithmic performance on both lookup and pop?

Would it make sense to keep a separate hashset to keep track?

Or can I altogether ignore this step?

What would be most effecient?

$\endgroup$
3
$\begingroup$

I think I never heard the term "Open Set" as we usually call it "OPEN list" (and by convention we use upper-case letters). I mention this to highlight the fact that this structure is closer to a list than a set indeed ---thought sets might be used as well, see below.

Anyway, your understanding of the purpose of the OPEN list is perfect. It should contain all nodes generated that are awaiting for expansion, in contraposition to the so-called CLOSED list that contains all nodes that have been already expanded.

There are many different implementations of the OPEN list. For a good review of different ways to implement it, see Chapter 3 of Stefan Edelkamp, Stefan Schroedl Heuristic Search: Theory and Applications, Morgan Kaufmann 2011. In the following I'm just describing three typical alternatives:

Plain open list

The first alternative consists simply of using a list which sorts nodes in ascending order of their $f$-value. Extracting nodes from the list is done in $O(1)$ as it just suffices to take the first item from the list. Inserting is a little bit more difficult. The best would consist of creating a small OPEN list with the descendants of a node that has just been expanded and to sort it in ascending order of their $f$-values. Next, merge this sort list with the global OPEN list. The operation has a cost which is logarithmic in the size of the global OPEN list, but be aware that its size grows exponentially.

Bucketed open list

If the $f$-values of all nodes are known to be discrete and also to be bounded by a constant $B$, then create an array with $(B+1)$ locations, each one pointing to one different list. This ensures that inserting nodes in the OPEN list takes only $O(1)$: given a node with an $f$-value equal to $x$, just add it to the tail of the list pointed to by location OPEN[x]. Extracting is a little bit more difficult, but still very easy. You have to keep track of the lower non-empty index $x$, min x. When popping a node return the first node in the list pointed to by OPEN[min x]. Clearly, this requires some maintanenance: first, when removing all nodes with an $f$-value equal to min x, it is necessary to update this lower bound; secondly, if a node with an $f$-value strictly less than the current min x is inserted, min x has to be updated as well.

Using sets

A$^*$ might additionally require to perform searches in the OPEN list. Strictly speaking, this is not required and the only purpose for doing it is to save some memory ---which anyway will grow exponentially. Note please that this will not avoid redundant expansions, as the CLOSED list already serves specifically to that purpose (in a nutshell: before the expansion of any node verify it is not in the CLOSED list; if so, skip the current expansion; otherwise, expand it and insert it into CLOSED) so I do not think it is really common practice to avoid the insertion of nodes in OPEN that are already in OPEN.

Anyway, if you are interested in saving some additional memory at the expense of investing some additional CPU running time, create a set with the current contents of the OPEN list (implemented in either way) and use it only for performing searches. Yeap, you might be thinking that you are then using twice the memory required by A$^*$ but be aware that the memory consumption of this algorithm is exponential in the depth of the paths generated, so that multiplying the memory usage by a low constant (such as two) will not prevent your algorithm from finding solutions that otherwise could have been found.

Hope this helps,

$\endgroup$
  • $\begingroup$ Thank you so much for this answer. As soon as you mentioned bucketing, I was pretty excited, as it seemed to fit my problem domain quite well. And I'm sure it did, but I would still have to be a bit faster. I'll keep trying, I guess. This has been very useful. $\endgroup$ – Christofer Ohlsson May 13 '17 at 16:54
  • $\begingroup$ So happy to hear that Christofer!! Thanks a lot also for closing this question. Please, if you have further questions post them in stackexchange.com We are a lot of people willing to give answers (provided we know them, of course! :) ) If you want, send me an e-mail (you can easily find my e-mail googling my name but be aware I'm not the mexican professor of geology that has also my name :) ) and I will send you back an implementation of the buckets that might help you in C++. $\endgroup$ – Carlos Linares López May 14 '17 at 21:22
  • $\begingroup$ "By convention, we use upper-case letters." That doesn't seem like a useful convention, to me. Wikipedia doesn't use it, I don't recall Russell and Norvig using it either. I say, ditch it! $\endgroup$ – David Richerby Jun 5 '17 at 10:13
  • $\begingroup$ Oh well ... All I can say is that in the heuristic search community (see papers in conferences such as AAAI, ICAPS or SoCS) we do use upper case letters for these lists (both OPEN and CLOSED). Another example are the books Heuristics by Judea Pearl and Heuristic Search: Theory and Practice by Edelkamp and Schrodl. I think it is just a matter of taste and, of course, you are very welcome to avoid those conventions if you dislike them. Besides, I dislike the book by Russell and Norvig which I do not use in my lectures. Cheers, $\endgroup$ – Carlos Linares López Jun 6 '17 at 19:35
1
$\begingroup$

First of all, it makes sense to implement the gScore in the Wikipedia's pseudocode as a hash table.

Next, considering an arbitrary node $v \in V$, it may have three "states":

  1. It is in the open list,
  2. It is in the closed list,
  3. It is in neither open nor closed lists.

Also, note that the key set of gScore is exactly all the nodes in open and closed lists.

Open + Closed = gScore

Now, you can implement

neighbor not in openSet

as

neighbor not mapped in gScore

Why this works?

Well, if we reached that very test, it means that it is not in the closed list, which implies that neighbor is in the open list or none of the lists. Since gScore contains all open nodes, neighbor is in the open list only if it is in the gScore.

Hope that helps.

$\endgroup$
  • $\begingroup$ That's interesting! I might have to revisit this. $\endgroup$ – Christofer Ohlsson Jun 5 '17 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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