search

aig-upf / fs-private

This is the private version of the FS planner repository
GNU General Public License v3.0
5 stars 1 forks source link

Specialize data structures and algorithms to conjunction-of-atoms formulas #25

Closed gfrances closed 7 years ago

gfrances commented 7 years ago

The current Formula data structures are too ineffective when using width-based algorithms that require that the same formula be evaluated over and over again a large number of times. We should see how we can specialize this for all those large amount of problems where all formulas are conjunctions of simple atoms. Most of the time now is spent evaluating recursively the formulas, whereas a simple specialization that efficiently stores the necessary information in a std::vector<Atom> or similar, would be much more efficient when dealing with the evaluation.

Additional note: the UnsatisfiedGoalAtomsHeuristic should also be specialized to handle this.

gfrances commented 7 years ago

To highlight the relevance of this, profiling Thoughtful/p11_6_53-typed from IPC14 shows that fs0::fstrips::Conjunction::interpret() takes about 44% of execution time

miquelramirez commented 7 years ago

I can see the impact - now that we're generating and evaluating so many nodes.

I will be taking a look at the code, let's see if I find the time to send some suggestions.

Miquel

On Fri, 3 Feb 2017, 02:34 Guillem Francès notifications@github.com wrote:

To highlight the relevance of this, profiling Thoughtful/p11_6_53-typed from IPC14 shows that fs0::fstrips::Conjunction::interpret() takes about 44% of execution time

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/aig-upf/fs-private/issues/25#issuecomment-276990552, or mute the thread https://github.com/notifications/unsubscribe-auth/AAbIKbp0Jo-wzuN8zOk-1kRnS-_Dk-VBks5rYfeZgaJpZM4L1OCK .

gfrances commented 7 years ago

I was basically thinking on subclassing Formula with a new class AtomConjunction which contains a std::vector<std::pair<VariableIdx, ObjectIdx>>, and overloads the interpret function in the expected manner. I'll test that tomorrow morning, but suggestions are more than welcome. This will likely help a bit, but still I think that iterating through all available ground actions upon the expansion of a state and checking for each action whether the precondition holds or not in that state... is way too naive...

miquelramirez commented 7 years ago

Hello again,

as I wrote on the chat: with the Match Tree you're not supposed to test the preconditions of the actions returned by the iterator, since they're guaranteed to be true at the current state s. Is that maybe being enforced actively? Now I don't remember exactly what I settled for. Let me check it out.

The optimisation you mention sounds to me quite direct, by adding to the method Conjunction::bind the "intelligence" to return instead of a general conjunction, the more efficient version.

miquelramirez commented 7 years ago

Okay I went and I implemented the specialisation, see Pull Request https://github.com/aig-upf/fs-private/pull/26

On other news, there seems to be something wonky with the Match Tree...

gfrances commented 7 years ago

Yes, replying to your previous comment... the action iterators implemented so far didn't have that guarantee, they simply prune some actions which were guaranteed NOT to be applicable in the current state, but then the precondition of the non-pruned actions needs to be assessed anyway. Your point is then very valid, I can create an additional mechanism for that. I understand however that there's something else wrong with the Match tree?

miquelramirez commented 7 years ago

Yes, I will take a look into it tonight :)

On Fri, 3 Feb 2017, 20:17 Guillem Francès notifications@github.com wrote:

Yes, replying to your previous comment... the action iterators implemented so far didn't have that guarantee, they simply prune some actions which were guaranteed NOT to be applicable in the current state, but then the precondition of the non-pruned actions needs to be assessed anyway. Your point is then very valid, I can create an additional mechanism for that. I understand however that there's something else wrong with the Match tree?

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/aig-upf/fs-private/issues/25#issuecomment-277200364, or mute the thread https://github.com/notifications/unsubscribe-auth/AAbIKcSBxFaHC-T4qwT9Hmu6aCDLTyvzks5rYvCmgaJpZM4L1OCK .

gfrances commented 7 years ago

Ok, let me take care of adapting the other side of this so that once the match-tree works, we no longer check twice for applicability of preconditions :-)

miquelramirez commented 7 years ago

https://goo.gl/images/mMB0oI

gfrances commented 7 years ago

ops, as I said in the PR:

wow, I've fixed a couple of things and tested this with a couple of Thoughtful instances only... one of them goes from 16 sec to 3 sec, the other from 51sec to 9sec. Much better than I expected... Thanks again Miquel!

I'll close this for now and open a new issue for the match-tree thing.