Inefficient existential preconditions resolution #328
Comments
|
The general procedure should be to start from the state, i.e. known facts and build the set of all derived facts from that. This applies to the existential quantification and the derived predicates. I assume, that there is a set
Algorithm for derived predicates
Algorithm to decide preconditionsBased on the before mentioned, we can decide, if the precondition of an action is satisfied.
|
|
@tobiaswjohn Thanks! I am working on improving the algorithm with your input. I will come back with some questions soon :) |
|
@Rezenders I see you did quite some work and made good progress on this issue. You made quite some comments in the pull request #330 Also: does the evaluation really take more than 30s on the (rather simple) example? This still sounds like quite some time :/ |
Yes, it takes around 37s to solve all derived predicates in the domain_derived.pddl. However, I don't think this is a problem necessarily related to the new evaluation implementation, using only the SymK planner to find a plan using the previous domain and the problem_derived.pddl problem formulation, takes around 278 seconds (ps: you need to remove the fluents from the pddl formulation to make it work with symk). I don't think this is a particularly easy example due to the The two main bottlenecks in the current approach are:
@tobiaswjohn Fortunately, for our use case this is much faster, it takes around 1s. It is not ideal, but .... |
|
Thank you for your comments. I think you made good progress and the time seems to be somehow usable for our use case (at least if we assume that executing an action takes several seconds anyways). At least, it should be small enough, that we can argue that it is not the center of our work to optimize this. One thing I was wondering about, which could be an optimization: Should one maybe have a list of all predicates, for which no assignment exists? E.g. for our work, consider the example from the top: If we saved somewhere, that e.g. "inferred-FunctionDesign" is empty, i.e. no assertion with this predicate exists, then we don't need to evaluate any of the other predicates. I think, this could speed up the whole process quite a bit. Just a vague idea, that might be not too complicated to implement. :) But I think, we can also focus on other things than optimizing this algorithm, if we want. |
In addition to this, when applying the effect of actions, we could keep track of the predicates inserted/removed and only reevaluate the derived predicates that could be impacted instead of reevaluating all derived predicates. Constantly reevaluating all derived predicates is a current bottleneck to the approach |
|
I had an idea: instead of saving the derived predicates as a vector, we could save it as a direct acyclic graph representing the dependencies between the derived predicates. For example: The derived predicates in the following domain: (:derived (inferred-InstanceA ?a)
(and
(= (?a instanceA))
)
)
(:derived (inferred-A ?a)
(and
(predicateA ?a)
)
)
(:derived (inferred-B ?b)
(and
(predicateB ?b)
)
)
(:derived (inferred-AA ?a)
(and
(inferred-A ?a)
)
)
(:derived (inferred-BB ?b)
(and
(inferred-B ?b)
)
)
(:derived (inferred-AB ?a ?b)
(and
(inferred-A ?a)
(inferred-B ?b)
)
)Could be represented with the following graph:
Then, instead of the current algorithm for solving derived predicates: We could traverse the graph and solve the derived predicates in the correct order. This only requires one pass to solve all derived predicates, in contrast to the previous approach, which could take several iterations to finish. Furthermore, most critically, the last iteration from the previous approach doesn't solve any additional derived predicate. It only confirms that all predicates that could be solved were solved. The graph search could be either breadth-first or depth-first, I don't think it makes any difference. Apply effectsWith the graph representation, when applying the effects of an action in a given state, we can check the graph to find out which derived predicates the effect impacts and only solve these derived predicates again. In the example above, if instances of Prune derivedFurthermore, since the end goal of solving the derived predicates is to use them to evaluate whether the actions being executed have their preconditions satisfied at execution time and to generate a plan-graph from the action plan, we could prune the derived predicate graph to contain only the derived predicates required for the actions in the current plan. For example: Given the following actions and the pddl formulation above: (:action actionA
:parameters (?a)
:precondition (and
(inferred-A ?a)
)
:effect (and
(predicateB ?a)
)
)
(:action actionB
:parameters (?b)
:precondition (and
(inferred-b ?b)
)
:effect (and
(goal ?b)
)
)Suppose the current plan is: The derived predicates graph could be pruned to:
|
|
I like the idea with the graph! I think this an work well, as long as the set of grounded derived predicates is not too large. |
|
Graph way looks promising :) |
Hi @fmrico,
Unfortunately, the solution I proposed for existential predicates is inefficient. It is literally exploring the whole state space to check if the predicates are satisfied. This can easily explode. For example, if there are 75 instances and an existential precondition has 5 variables, this results in 75^5 possible combinations to check, which is unfeasible.
A concrete example (complete formulation can be found here):
We need to come up with a mechanism to prune the possible variable combinations. I don't have any good ideas so far.
The text was updated successfully, but these errors were encountered: