Rename "closed list" to "pruned list"

[geoffsutcliffe]

We should rename the closed list to pruned list, to match the algorithm text.

[rhys-vdw]

Actually upon reading I'm not sure that closed and pruned are the same thing. Consider that nodes may be returned to the open list from the pruned list, but never would they be returned from the closed list (as per my understanding). Logically merging these two lists would have no effect (when compared to having an open and closed list). As node in the closed list will necessarily have a high d cost, therefore, if it was in the pruned list, it could never be considered for return into the open list. However inserting these nodes into the sorted pruned list would have some cost.

[geoffsutcliffe]

correct they are not the same thing.. in principle..

the point is moot. we only need open and pruned in das. ive grown the enum rather than changing it, to allow algos that use a closed set to use the same enum

[rhys-vdw]

In summary of what I said on the phone: You're right, in theory we need only open and pruned. There is, however a set of nodes who are in neither of these sets. If we insert all the expanded nodes into the pruned list, then the logic of the program will not be altered. The performance, however, will be.

The open set is the set of unexpanded nodes. The pruned set is the set of unexpanded nodes that are unreachable (ie. have a higher d^ cheapest cost than d max). I propose the closed set as the set of expanded nodes.

This means that we do not waste time inserting and retrieving nodes from the priority queue.

From the PriorityQueue JDoc:

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

This is needless cost considering we "close" one node per expansion. We will be expanding the "pruned" priority queue, increasing the cost of each insertion. And also performing more O(log(n)) insertions.

Since no expanded node will ever need to be retrieved, the "closed set" will require no representing data structure, it is just an enum option on each NodeInfo object.

From the pseudocode:

07 s <- remove state from open with minimal f(s)
08 if s is a oal and is better than incumbent
09   incumbent <- s
10 else if d^(s) < d max
11    foreach child s' in s
12       add s' to open
13 else
14   add s to pruned

Note that there is a situation where s is removed from open and not inserted into pruned.

[rhys-vdw]

I was mistaken about when states are considered from pruning, however I think that there is a third cell state there that you're not considering.

In fact I'm not even 100% sure that putting expanded nodes into the pruned set wont affect the logic, but I suspect their d cheapest would all be too high to consider.

[geoffsutcliffe]

Great description about the three set types. "Closed" is a meta set that we invent for our implementation.