next up previous
Next: State Hashing Up: Implementation Enhancements in Macro-FF Previous: Implementation Enhancements in Macro-FF

Open Queue

FF tries to find a solution using an enhanced hill climbing method and, if no solution is found, switches to a best-first search algorithm. Profiling runs showed that in the Pipesworld domains of the planning competition up to 90% of the CPU time is spent inserting nodes into the open queue. The open queue was implemented as a single linked list. We changed the implementation to use a linked list of buckets, one bucket for each heuristic value. The buckets are implemented as linked lists and need constant time for insertion, since they no longer have to be sorted.

Adi Botea 2005-08-01