refine_plan.algorithms.gfactor

Implementation of the GFactor factorisation algorithm.

GFactor was introduced in: Wang, A.R.R., 1990. Algorithms for multilevel logic optimization.

The implementation here is based on the implementation in: https://github.com/SimonaGug/BT-from-planning-experts

Which is an implementation of the paper:

Gugliermo, S., Schaffernicht, E., Koniaris, C. and Pecora, F., 2023. Learning behavior trees from planning experts using decision tree and logic factorization. IEEE Robotics and Automation Letters.

It is not entirely clear if the version of GFactor in the paper is identical to that in the original PhD thesis it came from.

Note the implementation I am referencing here does not have an associated license.

My reimplementation improves readability, makes bug fixes from the original, and makes general quality of life improvements.

Author: Charlie Street Owner: Charlie Street

Module Contents

Functions

most_common_condition(formula)	Find the most condition in a formula.
gfactor(formula[, divisor_fn])	Runs the GFactor factorisation algorithm.
get_random_divisor(formula)	Get a random divisor for GFactor. The divisor is a single variable.
quick_divisor(formula)	Implements the quick divisor function from the thesis below.

Attributes

MAX_TRIES

refine_plan.algorithms.gfactor.MAX_TRIES = 10

refine_plan.algorithms.gfactor.most_common_condition(formula)

Find the most condition in a formula.

Finds the variable (which represents a logical condition) which appears in the most conjunctions.

The assumption here I think is that the expression is DNF. And that a variable only appears once in a conjunction. Given our sympy expressions are logical expressions, this should always be satisfied.

Parameters:

formula – The formula to search through

Returns:

The most common condition, or None if there isn’t one

refine_plan.algorithms.gfactor.gfactor(formula, divisor_fn=most_common_condition)

Runs the GFactor factorisation algorithm.

Implements GFactor as in the pseudocode in both papers listed at the top of the file.

Parameters:

• formula – A sympy formula

• divisor_fn – Optional. Sets the function to use for the initial divisor.

Returns:

A factorised formula in the format p*q + r

refine_plan.algorithms.gfactor.get_random_divisor(formula)

Get a random divisor for GFactor. The divisor is a single variable.

Parameters:

formula – The formula we’re trying to factorise

Returns:

A random variable to choose as divisor

refine_plan.algorithms.gfactor.quick_divisor(formula)

Implements the quick divisor function from the thesis below.

Wang, A.R.R., 1990. Algorithms for multilevel logic optimization.

Parameters:

formula – The formula we’re trying to factorise

Returns:

The initial divisor for gfactor