I'm working on the details, and I have a couple concerns.   
      
   > [E]ach boundary node would retain not just one   
   > shortest path, but the shortest path relative to each combination of   
   > keys.   
      
   I don't see how we can use a closed list, at least in the normal sense,   
   because we want to re-visit nodes after acquiring a new key. A node   
   could be closed conditionally if the currently-expanding node has a   
   subset of the same key-list, but this check could as easily go   
   alongside the bestDist comparison (i.e., this is the best path if it   
   has a lower bestDist and the same or a superset of my key-list). Am I   
   looking at an A* minus the closed list?   
      
   > And if later we find that path (B E) is shorter than both (B C D) and   
   > (B D) and acquires K2, it doesn't replace the path with K1, but   
   > replaces the path with no key[.]   
      
   When a path is updated or "replaced" in this way, all of its children   
   must also be replaced (or deleted, if this is faster).   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)