#include <BackwardChainer.h>

Collaboration diagram for opencog::BackwardChainer:

Public Member Functions
	BackwardChainer (AtomSpace &as, Handle rbs)

void	set_target (Handle init_target)

UREConfigReader &	get_config ()

const UREConfigReader &	get_config () const

void	do_chain ()

void	do_step ()

const VarMultimap &	get_chaining_result ()

Private Member Functions
void	process_target (Target &target)

std::vector< Rule >	filter_rules (const Target &target)

Rule	select_rule (Target &target, const std::vector< Rule > &rules)

HandleSeq	match_knowledge_base (const Handle &htarget, Handle htarget_vardecl, std::vector< VarMap > &vmap)

HandleSeq	ground_premises (const Handle &htarget, const VarMap &vmap, std::vector< VarMap > &vmap_list)

bool	unify (const Handle &hsource, const Handle &hmatch, Handle hsource_vardecl, Handle hmatch_vardecl, VarMap &result)

Handle	gen_sub_varlist (const Handle &parent, const Handle &parent_varlist, std::set< Handle > additional_free_varset)

Private Attributes
AtomSpace &	_as

UREConfigReader	_configReader

AtomSpace	_garbage_superspace

Handle	_init_target

TargetSet	_targets_set

unordered_set< Type >	_logical_link_types = { AND_LINK, OR_LINK, NOT_LINK }

Friends
class	::BackwardChainerUTest

Detailed Description

Backward chaining falls in to two cases

Truth value query - Given a target atom whose truth value is not known and a pool of atoms, find a way to estimate the truth value of the target Atom, via combining the atoms in the pool using the inference rule. Eg. The target is "Do people breath"

(InheritanceLink people breath)

the truth value of the target is estimated via doing the inference "People are animals, animals breathe, therefore people breathe."
Variable fulfillment query - Given a target Link (Atoms may be Nodes or Links) with one or more VariableAtoms among its targets, figure what atoms may be put in place of these VariableAtoms, so as to give the grounded targets a high

strength * confidence

Eg. What breathes (InheritanceLink $X breath) can be fulfilled by pattern matching, whenever there are are multiple values to fill $X we will use fitness value measure to choose the best other compound example is what breathes and adds ANDLink InheritanceLink $X Breath InheritanceLink $X adds

Anatomy of current implementation

First check if the target matches to something in the knowledge base already
If not, choose an inference Rule R (using some Rule selection criteria) whose output can unify to the target
Reverse ground R's input to restrict the permises search
Find all permises that matches the restricted R's input by Pattern Matching
For each set of permies, Forward Chain (a.k.a apply the rule, or Pattern Matching) on the R to see if it can solve the target.
If not, add the permises to the targets list (in addition to some permise selection criteria)
Do target selection and repeat.

Definition at line 91 of file BackwardChainer.h.

Constructor & Destructor Documentation

BackwardChainer::BackwardChainer	(	AtomSpace &	as,
		Handle	rbs
	)

Definition at line 40 of file BackwardChainer.cc.

Member Function Documentation

void BackwardChainer::do_chain ( )

The public entry point for full backward chaining.

Parameters

max_steps The maximum number of backward chain steps

XXX TODO add more stopping param like fitness criterion, etc

Definition at line 78 of file BackwardChainer.cc.

References _configReader, do_step(), and opencog::UREConfigReader::get_maximum_iterations().

Here is the caller graph for this function:

void BackwardChainer::do_step ( )

Do a single step of backward chaining.

Definition at line 95 of file BackwardChainer.cc.

References _targets_set, opencog::Target::get_handle(), opencog::Target::get_vardecl(), opencog::Target::get_varseq(), process_target(), opencog::TargetSet::select(), opencog::TargetSet::size(), and opencog::Atom::toShortString().

Here is the caller graph for this function:

std::vector< Rule > BackwardChainer::filter_rules ( const Target & target )

private

Find all rules in which the output could generate target.

This method will try sub-atom unification if no whole output unification is possible.

Parameters

htarget the target to be generated by the rule's output

Returns: a vector of rules

Definition at line 461 of file BackwardChainer.cc.

References _configReader, _garbage_superspace, opencog::AtomSpace::add_atom(), opencog::Rule::gen_standardize_apart(), gen_sub_varlist(), opencog::get_all_unique_atoms(), opencog::Target::get_handle(), opencog::Rule::get_implicand_seq(), opencog::UREConfigReader::get_rules(), opencog::Rule::get_vardecl(), opencog::Target::get_vardecl(), and unify().

Here is the caller graph for this function:

Handle BackwardChainer::gen_sub_varlist	(	const Handle &	parent,
		const Handle &	parent_varlist,
		std::set< Handle >	additional_free_varset
	)

private

Given a VariableList, generate a new VariableList of only the specific vars.

Mostly to keep the typed definition from the original VariableList. Also put any "free" variables not inside the original VariableList in the new list. The "free" variables are passed in as a parameter.

VariableNodes not in the original VariableList nor in the free_varset will be considered bound already.

Parameters

parent	the atom the VariableList was for
parent_varlist	the original VariableList
additional_free_varset	a set of free VariableNodes to be included

Returns: the new sublist

Definition at line 869 of file BackwardChainer.cc.

References createVariableList, opencog::LinkCast(), opencog::FindAtoms::search_set(), python.undocumented.blocksworld::t, and opencog::FindAtoms::varset.

Here is the caller graph for this function:

const VarMultimap & BackwardChainer::get_chaining_result ( )

Get the current result on the initial target, if any.

Returns: a VarMultimap mapping each variable to all possible solutions

Definition at line 128 of file BackwardChainer.cc.

References _init_target, _targets_set, opencog::TargetSet::get(), and opencog::Target::get_varmap().

Here is the caller graph for this function:

UREConfigReader & BackwardChainer::get_config ( )

Definition at line 61 of file BackwardChainer.cc.

References _configReader.

const UREConfigReader & BackwardChainer::get_config ( ) const

Definition at line 66 of file BackwardChainer.cc.

References _configReader.

HandleSeq BackwardChainer::ground_premises	(	const Handle &	hpremise,
		const VarMap &	premise_vmap,
		std::vector< VarMap > &	vmap_list
	)

private

Try to ground any free variables in the input target.

Parameters

hpremise	the input atom to be grounded
premise_vmap	the original mapping to the variables in hpremise
vmap_list	the final output mapping of the variables

Returns: the mapping of the hpremise

Definition at line 642 of file BackwardChainer.cc.

References _garbage_superspace, _logical_link_types, opencog::AtomSpace::add_link(), opencog::get_free_vars_in_tree(), opencog::Atom::getType(), opencog::LinkCast(), match_knowledge_base(), opencog::FindAtoms::search_set(), opencog::Atom::toShortString(), opencog::Handle::UNDEFINED, and opencog::FindAtoms::varset.

Here is the caller graph for this function:

HandleSeq BackwardChainer::match_knowledge_base	(	const Handle &	htarget,
		Handle	htarget_vardecl,
		std::vector< VarMap > &	vmap
	)

private

Find all atoms in the AtomSpace matching the pattern.

Parameters

hpattern	the atom to pattern match against
hpattern_vardecl	the typed VariableList of the variables in hpattern
vmap	an output list of mapping for variables in hpattern

Returns: a vector of matched atoms

Definition at line 539 of file BackwardChainer.cc.

References _as, _configReader, _garbage_superspace, _logical_link_types, opencog::AtomSpace::add_atom(), opencog::AtomSpace::add_link(), createPatternLink, createVariableList, opencog::AtomSpace::get_atom(), opencog::BackwardChainerPMCB::get_pred_list(), opencog::UREConfigReader::get_rules(), opencog::BackwardChainerPMCB::get_var_list(), opencog::Atom::getType(), opencog::is_atom_in_tree(), opencog::FindAtoms::search_set(), opencog::Atom::toShortString(), opencog::Handle::UNDEFINED, opencog::VariableListCast(), and opencog::FindAtoms::varset.

Here is the caller graph for this function:

void BackwardChainer::process_target ( Target & target )

private

The main recursive backward chaining method.

Parameters

target the Target object containing the target atom

Definition at line 138 of file BackwardChainer.cc.

References _as, _garbage_superspace, _logical_link_types, _targets_set, opencog::AtomSpace::add_atom(), opencog::classserver(), createLink, createVariableList, opencog::TargetSet::emplace(), filter_rules(), opencog::Rule::gen_standardize_apart(), gen_sub_varlist(), opencog::get_all_unique_atoms(), opencog::get_free_vars_in_tree(), opencog::Rule::get_handle(), opencog::Target::get_handle(), opencog::Rule::get_implicand(), opencog::Rule::get_implicand_seq(), opencog::Rule::get_implicant(), opencog::Rule::get_vardecl(), opencog::Target::get_vardecl(), opencog::Target::get_varseq(), opencog::Target::get_varset(), opencog::Atom::getType(), ground_premises(), opencog::Instantiator::instantiate(), opencog::LinkCast(), reorder_log::m, match_knowledge_base(), opencog::FindAtoms::search_set(), select_rule(), opencog::Target::store_step(), opencog::Target::store_varmap(), opencog::Substitutor::substitute(), opencog::Atom::toShortString(), unify(), and opencog::FindAtoms::varset.

Here is the caller graph for this function:

Rule BackwardChainer::select_rule	(	Target &	target,
		const std::vector< Rule > &	rules
	)

private

Select a candidate rule from the set of filtered rules.

XXX TODO use the rule weight XXX should these selection functions be in callbacks like the ForwardChainer?

Parameters

target	the original target the set of filtered rules are unifiable to
rules	a vector of filtered rules to select from

Returns: one of the rule

Definition at line 842 of file BackwardChainer.cc.

References opencog::Target::get_selection_count(), and opencog::Target::rule_count().

Here is the caller graph for this function:

void BackwardChainer::set_target ( Handle init_target )

Set the initial target for backward chaining.

Parameters

init_target Handle of the target

Definition at line 52 of file BackwardChainer.cc.

References _garbage_superspace, _init_target, _targets_set, opencog::AtomSpace::add_atom(), opencog::TargetSet::clear(), createVariableList, opencog::TargetSet::emplace(), and opencog::get_free_vars_in_tree().

Here is the caller graph for this function:

bool BackwardChainer::unify	(	const Handle &	hsource,
		const Handle &	hmatch,
		Handle	hsource_vardecl,
		Handle	hmatch_vardecl,
		VarMap &	result
	)

private

Unify two atoms, finding a mapping that makes them equal.

Use the Pattern Matcher to do the heavy lifting of unification from one specific atom to another, let it handles UnorderedLink, VariableNode in QuoteLink, etc.

This will in general unify htarget to hmatch in one direction. However, it allows a typed variable A in htarget to map to another variable B in hmatch, in which case the mapping will be returned reverse (as B->A).

Parameters

hsource	the atom from which to unify
hmatch	the atom to which hsource will be unified to
hsource_vardecl	the typed VariableList of the variables in hsource
hmatch_vardecl	the VariableList of the free variables in hmatch
result	an output VarMap mapping varibles from hsource to hmatch

Returns: true if the two atoms can be unified

Definition at line 757 of file BackwardChainer.cc.

References _garbage_superspace, opencog::AtomSpace::add_atom(), createPatternLink, createVariableList, opencog::AtomSpace::get_atom(), opencog::BackwardChainerPMCB::get_pred_list(), opencog::BackwardChainerPMCB::get_var_list(), opencog::is_atom_in_tree(), opencog::FindAtoms::search_set(), opencog::Handle::UNDEFINED, opencog::VariableListCast(), and opencog::FindAtoms::varset.

Here is the caller graph for this function:

Friends And Related Function Documentation

friend class ::BackwardChainerUTest

friend

Definition at line 93 of file BackwardChainer.h.

Member Data Documentation

AtomSpace& opencog::BackwardChainer::_as

private

Definition at line 125 of file BackwardChainer.h.

UREConfigReader opencog::BackwardChainer::_configReader

private

Definition at line 126 of file BackwardChainer.h.

AtomSpace opencog::BackwardChainer::_garbage_superspace

private

Definition at line 127 of file BackwardChainer.h.

Handle opencog::BackwardChainer::_init_target

private

Definition at line 128 of file BackwardChainer.h.

unordered_set<Type> opencog::BackwardChainer::_logical_link_types = { AND_LINK, OR_LINK, NOT_LINK }

private

Definition at line 133 of file BackwardChainer.h.

TargetSet opencog::BackwardChainer::_targets_set

private

Definition at line 130 of file BackwardChainer.h.

The documentation for this class was generated from the following files:

opencog/rule-engine/backwardchainer/BackwardChainer.h
opencog/rule-engine/backwardchainer/BackwardChainer.cc

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Anatomy of current implementation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation