Specialize for Classic STRIPS Operators

[gfrances]

If we assumed all problems we have to deal with are propositional; all operators are given in the classic "set-theoretic" STRIPS representation, and we further assume that checking for preconditions and generating the next state is the bottleneck, as it is with BFWS and width-based algorithms, what would be a more aggressive degree of optimization?

State Representation

There are three highly-engineered options that I would test, in increasing degree of sophistication=complexity:

1. Using std::vector<bool>s,
2. using std::vector<uint_64>s and managing the bitwise operations ourselves. For instance, a state with 112 state variables will require two u_int64s.
3. using static std::bitset<N>s and compiling per-instance executables specific to the number N of fluents. For instance, for a problem with 112 fluents, we will compile a binary where the declaration of the state contains a single member std::bitset<112>. For a modern architecture with 64-bits, this gets transformed under-the-hood into an array of two longs; the source code is pretty well-designed and self-explanatory.

Running preliminary tests on this without a "full-scale" implementation/refactoring should be easy.

Operator Representation

Whatever the option above chosen, what should be the representation of operators? This is discussed in some old email with miquel and hector which I cannot find right now... Operators get compiled into three "extended" bitmaps with the same implementation than the state (i.e. a direct set-theoretical implementation, with sets represented as bitmaps): the pre, the add and the del bitmap. All operations described below assume there is one single bitmap, i.e. #fluents <= 64, but can be extended trivially to larger states (in an easily parallelizable manner, btw). Assume we have an operator o and a state s

1. The pre bitmap is the bitmap-encoding of pre(o) seen as a set. a is applicable in s iff: a.pre & s == a.pre
2. The add bitmap is the bitmap-encoding of add(o) seen as a set, and the del bitmap is the complement of the bitmap-encoding of del(o) seen as a set. The successor state s' = f(a,s) is: ((s & a.del) | a.add)

This is of course the trivial, direct implementation of the STRIPS semantics, nothing revolutionary. One important thing to keep in mind is how this potentially interactuates with our match-tree implementation. For problems with small number of ground actions, we might want not to use the match tree at all but rather iterate through all actions, etc.

[miquelramirez]

Option 3 sounds to me like a winner, really.

[miquelramirez]

For a reference implementation, you should ask Blai for the old HSP (the original, one and only) code - he was generating successors exactly as you describe on the second part of your post.